Gli argomenti in rosso sono per il solo canale Informatica
Gli argomenti in blu sono per il solo canale Tecnologie Informatiche
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.
Algoritmi ricorsivi.
Confronto fra implementazione ricorsiva e iterativa di uno stesso algoritmo.
Risoluzione di ricorrenze per iterazione e tramite albero.
Calcolo della complessitā nel caso peggiore dell'algoritmo di mergesort in forma ricorsiva.
Calcolo della complessitā nel caso peggiore e migliore dell'algoritmo quicksort in forma ricorsiva.
c) Strutture dati:
Gli alberi come tipi di dati astratti. Alberi binari, alberi m-ari.
Rappresentazione in memoria di alberi: rappresentazione tramite vettore o tramite struttura linkata; vettore dei padri. Rappresentazione degli alberi m-ari come alberi binari.
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.
Pile e code: notazione infissa e postfissa; passaggio da notazione infissa a postfissa; calcolo dell'espressione in notazione postfissa.
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 debolmente e fortemente connesse in un grafo orientato.
Ricerca delle componenti biconnesse.
2 algoritmi per la generazione di un ordinamento topologico.
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 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.
B-alberi: definizione, inserimento e cancellazione. Altezza di un B-albero.
Riferimenti bibliografici:
Alsuwaiyel, Algorithms - Design Techniques and Analysis, Word Scientific, 1999.
Cormen T.H., Leiserson C.E. e Rivest R.L., Introduction to Algorithms, Mc Graw Hill, 1990.
Demetrescu C., Finocchi I. e Italiano G.F., Algoritmi e Strutture Dati, Mc Graw Hill, 2004.
Horowitz E. , Sahni S. e S.Anderson-Freed, Strutture Dati in C , Mc Graw Hill, 1993.