ProgrammaDelCorsoAA200405 < Algoritmi1

Tags: view all tags

---++ <font color=990000> <b>Programma del Corso A.A. 2005/06 (Provvisorio)</b></font>

<font color=red> Gli argomenti in rosso sono per il solo canale Informatica </font>

<font color=blue> Gli argomenti in blu sono per il solo canale Tecnologie Informatiche </font>

*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.
   * <font color=red> Generazione del codice di Prufer in tempo lineare. Ricostruzione di un albero a partire dal codice di Prufer in tempo lineare. </font>
   * 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.

---++ [[Programma del Corso A.A. 2003/04]]