Docente
|
DEMETRESCU CAMIL
(programma)
1-Introduzione agli algoritmi.2-Modelli di calcolo e metodologie di analisi: notazioni asintotiche; delimitazioni inferiori e superiori; caso migliore, peggiore, medio; equazioni di ricorrenza e Master theorem; algoritmi randomizzati; analisi ammortizzata.3-Strutture dati elementari: liste, pile, code, alberi, array dinamici.4-Ordinamento: delimitazione inferiore della complessità; algoritmi ottimali: heap e heapsort; mergesort; quicksort e quicksort randomizzato; algoritmi in tempo lineare: integersort, bucketsort, radixsort.5-Selezione e statistiche d'ordine: heapselect, quickselect randomizzato e deterministico.6-Alberi di ricerca: ABR; bilanciamento; AVL, B-tree; strutture autoadattive: splay tree.7-Tavole hash: funzioni hash e loro proprietà; collisioni: liste di collisione e indirizzamento aperto.8-Code con priorità: d-heap, heap binomiali e di Fibonacci.9-Union-find: quickFind, quickUnion, euristiche di bilanciamento e di compressione.10-Tecniche algoritmiche: divide-et-impera, programmazione dinamica, strategia greedy.11-Stringhe: distanza di editing; massima sottosequenza comune (LCS).12-Grafi e visite di grafi: grafi orientati e no; rappresentazione; BFS, DFS e loro proprietà; componenti connesse.13-Minimo albero ricoprente: proprietà dei MST; algoritmi greedy di colorazione degli archi: Kruskal, Prim, Boruvka. 14-Cammini minimi: distanze in un grafo, rilassamento, algoritmi di Bellman-Ford, Dijkstra e Floyd-Warshall.
|