Programma del Corso A.A. 2005/06 (Provvisorio)
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.
- Appunti del corso in rete.
This topic: Algoritmi1
> WebHome > ProgrammaDelCorsoAA200405
Topic revision: r3 - 2005-12-20 - TizianaCalamoneri