Programma del Corso A.A. 2003/04

Attenzione: questo programma si riferisce allo scorso anno accademico

Gli argomenti in blu riguardano solo gli studenti di Informatica

Gli argomenti in rosso riguardano solo gli studenti di Tecnologie Informatiche

Gli argomenti in verde e quelli nel colore opposto a quello del canale di appartenenza sono facoltativi

a) Richiami di concetti fondamentali

• Specifica di algoritmi; astrazione dei dati.
• Progettazione, validazione, analisi e verifica di algoritmi.
• Esempi di progetto di algoritmi.

b) Analisi di algoritmi

• Analisi di algoritmi: analisi del caso peggiore, medio, migliore.
• Ordine di grandezza delle funzioni, notazione asintotica.
• Algebra della notazione asintotica; analisi delle costanti additive e moltiplicative.
• Richiamo degli algoritmi di ordinamento Bubble, Selection e Insertion Sort.
• Calcolo della complessità degli algoritmi di ordinamento in forma iterativa.
• Alberi di decisioni, limiti inferiori per l'ordinamento.
• Il concetto di stabilità nell'ordinamento.
• Ordinamento in tempo O(n ): ordinamento per conteggio, radix sort, bucket sort.
• Algoritmi ricorsivi.
• Confronto fra implementazione ricorsiva e iterativa di uno stesso algoritmo.
• Risoluzione di ricorrenze per iterazione, sostituzione e tramite albero.
• Calcolo della complessità nel caso peggiore dell'algoritmo di mergesort in forma ricorsiva.
• Calcolo della complessità nel caso peggiore, medio e migliore dell'algoritmo quicksort in forma ricorsiva.
• Selezione in tempo medio lineare.

c) Strutture dati:

• Pila e coda come tipi di dati astratti.
• Trasformazione da notazione infissa a notazione postfissa, calcolo di un'espressione postfissa.
• Gli alberi come tipi di dati astratti.
• Teorema di caratterizzazione degli alberi.
• Rappresentazione in memoria di alberi: rappresentazione tramite vettore o tramite struttura linkata; vettore dei padri.
• Generazione del codice di Prufer in tempo lineare. Ricostruzione di un albero a partire dal codice di Prufer in tempo lineare.
• Visita di un albero per livelli.
• Heap e code di priorità: costruzione di un heap, operazioni di inserimento e cancellazione.
• Heapsort.
• Calcolo della complessità nel caso peggiore dell'algoritmo heapsort in forma iterativa e ricorsiva.
• I grafi come tipi di dati astratti.
• Rappresentazione in memoria di un grafo: matrici e liste di adiacenza; matrici di incidenza; lista di archi. Ordinamento in tempo lineare di una lista di adiacenza.
• Visita di un grafo: visita in ampiezza e in profondità.
• Alberi ricoprenti.
• Caratterizzazione di alberi ricoprenti ottenuti per visite in ampiezza e profondità.
• Numerazione dei nodi degli alberi di copertura rispetto alla visita eseguita.
• Partizione degli spigoli degli alberi di copertura rispetto alla visita eseguita.

d) Algoritmi su alberi e su grafi:

• Generazione del grafo complemento e del grafo trasposto.
• Ricerca delle componenti connesse di un grafo.
• Ricerca dei cammini minimi da sorgente singola.
• Come verificare se un grafo è bipartito o aciclico.
• Caratterizzazione dei grafi bipartiti.
• Ricerca di un accoppiamento massimale in un grafo.
• Ricerca delle componenti biconnesse in un grafo.
• Ricerca delle componenti fortemente connesse in un grafo orientato.
• 2 algoritmi per la generazione di un ordinamento topologico.
• Ricerca di alberi ricoprenti di costo minimo: Algoritmo di Prim, Algoritmo di Kruskal.
• Algoritmi di Union & Find.

e) Gestione di dizionari:

• Alberi binari di ricerca : operazioni di ricerca, inserimento e cancellazione.
• Ricerca del max, del min, del predecessore e del successore in un albero binario di ricerca.
• Confronto della complessità delle operazioni di base sulle diverse strutture dati analizzate.
• Alberi binari di ricerca con informazioni aggiuntive: alberi di selezione, alberi di intervallo.
• Alberi di ricerca bilanciati: alberi AVL.
• Computo del fattore di bilanciamento.
• Calcolo delle limitazioni inferiori e superiori per l'altezza di un albero AVL.
• Operazioni di rotazione per ribilanciare un albero AVL dopo l'inserimento e la cancellazione.

Riferimenti bibliografici:

• Cormen T.H., Leiserson C.E. e Rivest R.L.,Introduction to Algorithms, Mc Graw Hill, 1990.
• Horowitz E. , Sahni S. e S.Anderson-Freed, Strutture Dati in C , Mc Graw Hill, 1993.