Algoritmi e Strutture Dati

Docente: Alberto Montresor alberto.montresor@unitn.it

Programma del corso

Introduzione

• Introduzione [CLRS Cap. 1]
  • Algoritmi e strutture dati
  • Potenzialità e limiti degli algoritmi
  • Algoritmi come tecnologia
• Per cominciare [CLRS Cap. 2]
  • Analisi algoritmi: primi cenni
  • Modelli computazionali
  • Insertion Sort
  • Merge Sort

Analisi degli algoritmi

• Notazione asintotica [CLRS Cap 3.1]
• Alcuni richiami di analisi [CLRS Cap 3.2]
• Ricorrenze [CLRS Cap. 4]
  • Metodo dell'iterazione
  • Metodo della sostituzione
  • Teorema fondamentale delle ricorrenze (Master Theorem)
• Analisi ammortizzata [CLRS Cap. 17]

Strutture dati base

• Strutture dati elementari [CLRS Cap. 10]
• Pile, code, liste
• Alberi
• Grafi [CLRS Cap. 22.1]

Ordinamento e selezione

• Heapsort [CLRS Cap. 6]
• Quicksort [CLRS Cap. 7]
• Limiti inferiori per l'ordinamento [CLRS Cap. 8.1]
• Ordinamento in tempo lineare [CLRS Cap. 8]
• Mediane e statistiche d'ordine [CLRS Cap. 9]

Tecniche di programmazione

• Divide et impera
  • Moltiplicazione di interi
  • Moltiplicazione tra matrici [CLRS Cap. 28.2]
• Programmazione dinamica [CLRS Cap. 15]
  • Distanza fra stringhe di caratteri
  • Associatività prodotto matrici
• Algoritmi greedy [CLRS Cap. 16]
  • Compressione di huffman
  • Problema dello zaino frazionario 
  • Problema dello zaino 0-1
  • Problema del resto
  • Problema dello scheduling
  • Selezione delle attività
    
• Backtrack
  • String matching
• Tecniche euristiche
  • Algoritmo A*

Strutture dati avanzate

• Alberi binari ricerca [CLRS Cap. 12]
• Alberi RB [CLRS Cap. 13]
• Tabelle hash [CLRS Cap. 11]
• B-alberi [CLRS Cap. 18]
• Strutture dati per insiemi disgiunti [CLRS Cap. 21]

Algoritmi su grafi

• Algoritmi su grafi elementari [CLRS Cap. 22]
  • Visite in ampiezza e profondità
  • Ordinamento topologico
  • Componenti fortemente connesse
• Alberi di copertura minima [CLRS Cap. 23]
  • Kruskal
  • Prim
• Cammini minimi con singola sorgente [CLRS Cap. 24]
• •  Bellman-Ford
  • Cammini minimi su DAG
  • Dijkstra
• Cammini minimi fra tutte le coppie [CLRS Cap. 25]
• • Floyd-Warshall
  • Johnson
• Problemi di flusso [CLRS Cap. 26]
• • Ford-Fulkerson
  • Edmonds-Karp