DESIGN AND ANALYSIS OF ALGORITHMS

Internazionalizzazione della Didattica DESIGN AND ANALYSIS OF ALGORITHMS

0622700081
DIPARTIMENTO DI INGEGNERIA DELL'INFORMAZIONE ED ELETTRICA E MATEMATICA APPLICATA
CORSO DI LAUREA MAGISTRALE
INGEGNERIA INFORMATICA
2021/2022



OBBLIGATORIO
ANNO CORSO 1
ANNO ORDINAMENTO 2017
PRIMO SEMESTRE
CFUOREATTIVITÀ
540LEZIONE
18ESERCITAZIONE
324LABORATORIO


Obiettivi
L’INSEGNAMENTO FORNISCE LA CAPACITÀ DI ANALIZZARE UN PROBLEMA, DI PROGETTARE UNA SOLUZIONE EFFICIENTE, ANCHE ATTRAVERSO L’UTILIZZO DI TECNICHE DI PROGRAMMAZIONE EVOLUTE E STRUTTURE DATI AVANZATE, E DI REALIZZARNE UN'IMPLEMENTAZIONE IN UN LINGUAGGIO DI PROGRAMMAZIONE ORIENTATO AGLI
OGGETTI.

CONOSCENZE E CAPACITÀ DI COMPRENSIONE
TECNICHE DI PROGRAMMAZIONE EVOLUTE E STRUTTURE DATI AVANZATE. IMPLEMENTAZIONE DELLE STRUTTURE DATI COMUNEMENTE FORNITE NELLE LIBRERIE STANDARD DEI LINGUAGGI DI PROGRAMMAZIONE PIÙ DIFFUSI.
TERMINOLOGIA UTILIZZATA NEGLI AMBITI DI APPROFONDIMENTO DEL CORSO.

CONOSCENZA E CAPACITÀ DI COMPRENSIONE APPLICATE
APPLICARE LE TECNICHE DI PROGRAMMAZIONE E LE STRUTTURE DATI PROPOSTE NELLA RISOLUZIONE DI PROBLEMI COMPLESSI. IMPLEMENTARE GLI ALGORITMI E LE STRUTTURE DATI AVANZATE IN UN LINGUAGGIO DI PROGRAMMAZIONE AD OGGETTI.
Prerequisiti
CONOSCENZA DI UN LINGUAGGIO DI PROGRAMMAZIONE ORIENTATO AGLI OGGETTI. CONOSCENZA DELLE STRUTTURE DATI ELEMENTARI E DEI PRINCIPI DELLA PROGRAMMAZIONE. CONOSCENZA DELLE TECNICHE DI ANALISI DEGLI ALGORITMI.
Contenuti
LINGUAGGIO PYTHON (ORE LEZIONE/ESERCITAZIONE/LABORATORIO 6/0/0)
- TIPI DI DATI (2 ORE DI LEZIONE)
- FUNZIONI E CLASSI (3 ORE DI LEZIONE)
- MODULI E LIBRERIE (1 ORE DI LEZIONE)

ALGORITMI E STRUTTURE DATI (ORE LEZIONE/ESERCITAZIONE/LABORATORIO 28/21/0)
- ABSTRACT DATA TYPES E STRUTTURE DATI ELEMENTARI E ALBERI BINARI DI RICERCA (4 ORE DI LEZIONE E 3 ORE DI ESERCITAZIONE)
- ALBERI DI RICERCA BILANCIATI E B-TREES (5 ORE DI LEZIONE E 5 ORE DI ESERCITAZIONE)
- CODE A PRIORITÀ (2 ORE DI LEZIONE E 2 ORE DI ESERCITAZIONE)
- MAPPE E TABELLE HASH (2 ORE DI LEZIONE E 2 ORE DI ESERCITAZIONE)
- STRUTTURE DATI ED ALGORITMI SU STRINGHE (2 ORE DI LEZIONE E 2 ORE DI ESERCITAZIONE)
- GRAFI (10 ORE DI LEZIONE E 6 ORE DI ESERCITAZIONE)
- NETWORK FLOW (3 ORE DI LEZIONE E 1 ORA DI ESERCITAZIONE)

TECNICHE DI PROGRAMMAZIONE EVOLUTE (ORE LEZIONE/ESERCITAZIONE/LABORATORIO 9/8/0)
- PROGRAMMAZIONE GREEDY (2 ORE DI LEZIONE E 3 ORE DI ESERCITAZIONE)
- TECNICHE DI RICERCA ESAUSTIVA E PROGRAMMAZIONE DINAMICA (3 ORE DI LEZIONE E 3 ORE DI ESERCITAZIONE)
- ALGORITMI DI APPROSSIMAZIONE (2 ORE DI LEZIONE)
- ALGORITMI DI RICERCA LOCALE (2 ORE DI LEZIONE E 2 ORE DI ESERCITAZIONE)

TOTALE ORE LEZIONE/ESERCITAZIONE/LABORATORIO 43/29/0
Metodi Didattici
L’INSEGNAMENTO CONTEMPLA SIA LEZIONI TEORICHE CHE ESERCITAZIONI, IN AULA O IN LABORATORIO.
NELLE LEZIONI VENGONO PRESENTATI ALGORITMI E STRUTTURE DATI E VIENE DISCUSSA LA LORO UTILIZZABILITÀ PER LA SOLUZIONE DI PROBLEMI REALI. NELLE ESERCITAZIONI IN LABORATORIO GLI STUDENTI IMPLEMENTANO GLI ALGORITMI E LE STRUTTURE DATI PRESENTATI NEL CORSO. NELLE ESERCITAZIONI IN AULA VENGONO ASSEGNATI AGLI STUDENTI, DIVISI PER GRUPPI DI LAVORO, UNO O PIU' PROJECT-WORK DA SVILUPPARE DURANTE TUTTO LO SVOLGIMENTO DEL CORSO. IL PROGETTO COMPRENDE UNITARIAMENTE TUTTI I CONTENUTI DELL’INSEGNAMENTO ED È STRUMENTALE ALL’ACQUISIZIONE, OLTRE CHE DELLE CAPACITÀ DI RISOLVERE UN PROBLEMA DI PROGRAMMAZIONE, PROGETTANDO E REALIZZANDO UNA SOLUZIONE ALGORITMICA AVANZATA, ANCHE A SVILUPPARE E RAFFORZARE LE CAPACITÀ DI LAVORARE IN TEAM.
Verifica dell'apprendimento
LA PROVA DI ESAME È FINALIZZATA A VALUTARE NEL SUO COMPLESSO IL LIVELLO DI CONOSCENZA E COMPRENSIONE DEI CONCETTI PRESENTATI A LEZIONE, NONCHÉ LA CAPACITÀ DI APPLICARE TALI CONOSCENZE NELLA PROGETTAZIONE E REALIZZAZIONE DI UN PROGRAMMA PER RISOLVERE PROBLEMI COMBINATORIALI NON BANALI.

LA PROVA D’ESAME SI ARTICOLA NELLA DISCUSSIONE DEL PROGETTO SVOLTO DURANTE IL CORSO ED UNA PROVA SCRITTA. LA PROVA SCRITTA CONSISTE DI TRE ESERCIZI ED E' FINALIZZATA A VALUTARE LE CONOSCENZE ACQUISITE IN MERITO A STRUTTURE DATI AVANZATE E TECNICHE DI PROGRAMMAZIONE EVOLUTE E LA CAPACITA' DI APPLICARLE IN SEMPLICI SITUAZIONI. CON IL PROGETTO SARANNO VALUTATE LE CAPACITÀ DI APPLICARE A CASI CONCRETI LE STRUTTURE DATI E LE TECNICHE DI PROGRAMMAZIONE PROPOSTE A LEZIONE E DI FORNIRNE DELLE IMPLEMENTAZIONI EFFICIENTI.

NELLA VALUTAZIONE FINALE, ESPRESSA IN TRENTESIMI, LA VALUTAZIONE DEL PROGETTO PESERÀ PER IL 60% E LA PROVA SCRITTA PER IL RESTANTE 40%. LA LODE POTRÀ ESSERE ATTRIBUITA AGLI STUDENTI CHE DIMOSTRINO UNA PIENA CONOSCENZA E PADRONANZA DI TUTTE LE PRINCIPALI TEMATICHE AFFRONTATE AL CORSO E CAPACITÀ DI APPLICARLI ANCHE A CONTESTI DIFFERENTI DA QUELLI ANALIZZATI A LEZIONE.

Testi
M.T. GOODRICH, M. TAMASSIA, M.H. GOLDWASSER, “DATA STRUCTURES & ALGORITHMS IN PYTHON”,
WILEY 2013

KLEINBERG, TARDOS, "ALGORITHM DESIGN", PRENTICE HALL, 2005.

MATERIALE DIDATTICO INTEGRATIVO SARà DISPONIBILE NELLA SEZIONE DEDICATA DELL'INSEGNAMENTO ALL'INTERNO DELLA PIATTAFORMA E-LEARNING DI ATENEO (HTTP://ELEARNING.UNISA.IT) ACCESSIBILE AGLI STUDENTI DEL CORSO TRAMITE LE CREDENZIALI UNICHE DI ATENEO

LETTURE CONSIGLIATE:
T.H. CORMEN, C.E. LEISERSON, R.L. RIVEST, C. STEIN, “INTRODUZIONE AGLI ALGORITMI E STRUTTURE DATI”, SECONDA EDIZIONE, MCGRAW-HILL, 2005.
M. VENTO, P. FOGGIA, “ALGORITMI E STRUTTURE DATI”, MCGRAW-HILL.
P. MORIN, ”OPEN DATA STRUCTURES", (HTTP://WWW.OPENDATASTRCTURES.ORG).
C. DEMETRESCU, I. FINOCCHI, G. ITALIANO, “ALGORITMI E STRUTTURE DATI”, MCGRAW HILL, 2008.
Altre Informazioni
L'INSEGNAMENTO E' EROGATO IN INGLESE
  BETA VERSION Fonte dati ESSE3
  • Didattica