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, McGraw-Hill, 1990.
• Horowitz E. , Sahni S. e S.Anderson-Freed, Strutture Dati in C , McGraw-Hill, 1993.