ProgrammaDelCorso < Algoritmi1/Inf

Tags: view all tags

---++ <font color=990000> <b>Programma del corso di Algoritmi I (Informatica, A.A. 2008-2009)</b></font>

Se non diversamente specificato, i riferimenti bibliografici sono relativi al libro di testo "Algoritmi e strutture dati", 2/ed. Demetrescu, Finocchi, Italiano, !McGraw-Hill, 2008.

*<font color= 990000 >a) Introduzione</font>*

   * Progettazione ed analisi di algoritmi
      * verifica di correttezza
      * analisi del tempo di esecuzione
      * analisi dell'occupazione di memoria
   * Un esempio "giocattolo": il calcolo dei numeri di Fibonacci
   * Un secondo esempio: ricerca di duplicati.

_Rif._ Capitolo 1: tutto. Paragrafi 1.1, 1.2 e 1.3 del libro [DFFI07].

*<font color= 990000 >b) Metodologie di analisi</font>*

   * Ordine di grandezza delle funzioni, la notazione asintotica O, Omega, Theta
   * Algebra della notazione asintotica; analisi delle costanti additive e moltiplicative
   * Delimitazioni inferiori e superiori alla complessità di un problema rispetto ad una data risorsa di calcolo
   * Analisi nel caso peggiore e migliore
   * Analisi di algoritmi ricorsivi:
      * equazioni di ricorrenza, albero della ricorsione
      * risoluzione di ricorrenze tramite analisi dell'albero della ricorsione
      * metodo dell'iterazione
      * metodo della sostituzione
      * il teorema fondamentale delle ricorrenze (teorema master): enunciato ed esempi.

_Rif._ Capitolo 2: paragrafi 2.2, 2.3, 2.4 (tranne caso medio), 2.5. Appendice: paragrafi 17.1, 17.2, 17.3, 17.4

*<font color= 990000 >c) Algoritmi di ricerca e di ordinamento</font>*

   * Ricerca sequenziale e binaria: analisi nel caso peggiore e migliore.
   * Delimitazione inferiore al tempo di esecuzione di algoritmi di ordinamento basati su confronti: alberi di decisione
   * Algoritmi di ordinamento quadratici (con analisi nel caso peggiore): insertionSort, selectionSort, bubbleSort
   * Un algoritmo di ordinamento ottimo basato sulla tecnica del divide et impera (con analisi nel caso peggiore): mergeSort
   * Un algoritmo di ordinamento ottimo basato sull'uso di strutture dati efficienti (con analisi nel caso peggiore): heapSort
      * la struttura dati heap
      * cancellazione del minimo e costruzione di un heap in tempo lineare
      * rappresentazione posizionale di alberi binari
      * ordinamento in loco
   * Un algoritmo efficiente nel caso medio: quickSort (analisi nel caso peggiore, intuizione caso medio)
   * Il concetto di stabilità nell'ordinamento.
   * Ordinamento in tempo lineare: algoritmi intergerSort e bucketSort

_Rif._ Capitolo 2: paragrafo 2.4 (tranne caso medio). Capitolo 4: tutto tranne paragrafo 4.7. Appendice: paragrafi 17.3 e 17.4. Paragrafi 7.1, 7.2 e 7.4.1 del libro [CLRS01].

*<font color= 990000 >d) Dizionari</font>*

   * Implementazioni banali: array ordinati e liste collegate
   * Alberi binari di ricerca:
      * operazioni search, insert, delete
      * ricerca del massimo, del minimo, del predecessore e del successore
   * Bilanciamento in altezza: alberi AVL
      * calcolo del fattore di bilanciamento
      * limitazione superiore all'altezza di un albero AVL
      * rotazioni semplici e doppie
      * mantenimento del bilanciamento durante inserimenti e cancellazioni
 
_Rif._ Capitolo 3: paragrafo 3.1. Capitolo 6: paragrafi 6.1 e 6.2.

*<font color= 990000 >e) Alberi e grafi</font>*

   * Alberi
      * rappresentazioni indicizzate
      * rappresentazioni collegate
      * visite
   * I grafi come tipi di dati astratti
   * Definizioni e proprietà fondamentali
   * Rappresentazioni in memoria
      * matrice di adiacenza
      * liste di adiacenza
      * matrice di incidenza
      * lista di archi
   * Algoritmo di visita generica di un grafo
      * albero di copertura generato da una visita
      * analisi del tempo di esecuzione in funzione della rappresentazione usata
   * Algoritmi di visita in ampiezza e in profondità (sia per grafi orientati che non)
      * implementazione ricorsiva della visita in profondità 
      * implementazioni iterative di entrambe le visite basate su code e pile
      * proprietà degli alberi di copertura ottenuti dalle visite
      * partizione degli archi indotta dalle visite
   * Calcolo delle componenti connesse in grafi non orientati

_Rif._ Capitolo 3: paragrafo 3.3. Capitolo 12: tutto tranne paragrafo 12.5. Appendice: paragrafo 17.5.1


<!--

PROGRAMMA VECCHIO (2005-2006)

*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.
   * 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 dei cicli in un grafo e
caratterizzazione dei cicli tramite spigoli non
dell'albero della visita in profondita'.
   * Ricerca delle componenti connesse di un grafo.
   * Ricerca dei cammini minimi da sorgente singola.
   * Come verificare se un grafo è bipartito o aciclico.
   * Ricerca di un accoppiamento massimale in un grafo.
   * Ricerca delle componenti debolmente e
fortemente connesse in un grafo orientato.
   * 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.

-->