84745 - INTRODUZIONE AGLI ALGORITMI

Conoscenze e abilità da conseguire

Al termine del corso, lo studente: - conosce gli algoritmi per risolvere problemi computazionali di base su strutture di dati elementari; - conosce le tecniche di base per calcolare il costo computazionale degli algoritmi; - è in grado di progettare algoritmi efficienti per risolvere semplici problemi computazionali; - è in grado di stimare in ordine di grandezza il costo computazionale degli algoritmi; - è in grado di dare una valutazione circa l'efficienza e la correttezza di un algoritmo.

Contenuti

Progettazione e analisi di algoritmi. Complessita' computazionale. Ordini di grandezza. Equazioni di ricorrenza lineari di ordine costante e con partizione bilanciata. Limitazioni inferiori. Strutture di dati. Vettori, record e matrici. Liste, pile e code. Alberi. Visite di alberi (anticipata, simmetrica, differita, per livelli.) Insiemi. Dizionari. Ricerca binaria e per interpolazione. Tabelle hash. Code con priorita'. Heap. Alberi bilanciati di ricerca. Alberi red-black. MFSET. Grafi. Visite DFS e BFS. Tecniche di progettazione: divide-et-impera, backtrack, greedy, ricerca locale, programmazione dinamica, randomizzazione. Algoritmi di ordinamento: Mergesort, Countingsort, Heapsort, Quicksort, Shellsort. Complessita'. Le classi P ed NP. NP-completezza. Algoritmi pseudo-polinomiali, di approssimazione, branch-&-bound, ed euristici.

Testi/Bibliografia

A.A. Bertossi & A. Montresor, Algoritmi e Strutture di Dati, Citta' Studi Edizioni, Torino, 2014.

Metodi didattici

Il corso si svolge nel secondo semestre ed è strutturato in lezioni frontali in aula, comprendenti lezioni ed esrcitazioni. Vengono presentati innanzitutto gli aspetti teorici degli argomenti trattati. In particolare, dopo aver introdotto le nozioni di base, vengono presentate le principali strutture di dati e i piu' comuni problemi computazionali. Per tali problemi, sono progettati algoritmi risolutivi, evidenziando le varie tecniche di progettazione impiegate. Per gli algoritmi proposti, sono enunciati e talvolta dimostrati teoremi che provano la loro correttezza e la loro complessita' temporale. Successivamente ampio spazio viene dedicato alla risoluzione di esercizi.

Modalità di verifica e valutazione dell'apprendimento

La verifica dell'apprendimento avviene attraverso una prova scritta finale di 3 ore, durante la quale non è ammesso l'uso di libri, appunti, calcolatrici, supporti elettronici. La prova scritta consiste di 6 quesiti, alcuni dei quali sono esercizi che mirano ad accertare le abilità acquisite nel risolvere problemi computazionali tramite la progettazione di algoritmi efficienti, mentre altri sono domande aperte che mirano a verificare l'acquisizione delle conoscenze previste dal programma del corso.

Strumenti a supporto della didattica

Videoproiettore.

Orario di ricevimento

Consulta il sito web di Alan Albert Bertossi