Università degli Studi di Parma Facoltà di Scienze MM. FF. NN. Corso di Laurea in Informatica
Presentazione Il corso di laurea Scegliere Informatica Obiettivi formativi Sbocchi professionali Per saperne di più ... Insegnamenti Piano degli studi Corsi attivati Docenti Orario dei corsi Iscrizione esami Tesi di laurea Mailing list Documenti ufficiali Organi del CdL Regolamenti Archivio	Algoritmi e Strutture Dati 1 ( + Laboratorio) Docente Prof. Grazia Lotti Docente per la parte di laboratorio Dott. Enea Zaffanella Aula Aula B (Dipartimento di Matematica, piano terra). Le lezioni di laboratorio del lunedì mattina si tengono presso il Laboratorio Informatico dell'edificio polifunzionale di Facoltà (presso il Campus). Programma del corso Analisi di algoritmi e complessità. Dimensione dei dati di un problema. Ordini di grandezza delle funzioni. Caso pessimo e medio. Limiti superiori ed inferiori alla complessità di un problema. Tecniche per la dimostrazione di limiti inferiori. Complessità polinomiale e superpolinomiale. Relazioni di ricorrenza: metodi di soluzione e teorema fondamentale. Modelli di calcolo sequenziale. Macchina ad accesso casuale (RAM). Risorse in spazio e tempo. Criteri di costo uniforme e logaritmico. Altri modelli di calcolo. Strutture dati elementari. Strutture elementari: liste, pile, code, heap e relative operazioni fondamentali. Esecuzione iterativa delle chiamate ricorsive: record di attivazione delle chiamate, loro gestione mediante una pila e analisi dello spazio di memoria utilizzato. Algoritmi e strutture dati per la gestione e manipolazione di insiemi: tabelle hash, alberi binari di ricerca, bilanciamento, skip-lists e B-alberi. Algoritmi e strutture dati per il problema Union-Find. Code con priorità, heap. Progetto di algoritmi. Tecniche di progettazione di algoritmi ed esempi di applicazione: tecnica divide et impera, backtrack, greedy, programmazione dinamica. Algoritmo di Karatzuba-Hoffman per il prodotto di interi. Prodotto di una sequenza di matrici. Codici di Huffman. Algoritmi di ricerca e ordinamento. Generalità sul problema dell'ordinamento. Ordinamento interno per confronti: numero minimo di confronti necessari per ordinare n elementi. Algoritmi primitivi di ordinamento: selection-sort, insertion-sort, bubble-sort. L'algoritmo heapsort. Algoritmi ricorsivi: mergesort, quicksort. Analisi del quicksort nel caso medio. Implementazione iterativa di quicksort e ottimizzazione dello spazio di memoria. Algoritmi lineari non basati sul confronto: counting-sort, radix-sort, bucket-sort. Determinazione dell'elemento medio. Algoritmi elementari sui grafi. Tecniche di rappresentazione di grafi orientati e non orientati. Algoritmi di visita in ampiezza e profondità, alberi di copertura. Algoritmi di visita su alberi. Calcolo delle componenti fortemente connesse. Cammini minimi su grafi. Testi consigliati T. H. Cormen, C. E. Leiserson, R. L. Rivest. Introduzione agli algoritmi, Vol. 1, 2, 3, Jackson, 1994. F. Romani. Appunti di teoria degli algoritmi, ECIG, 1991. A. Bertossi. Strutture algoritmi complessità, EGIC, 1993. G. Fiorentino, M. Laganà, F. Romani, F. Turini. C e Java: laboratorio di programmazione, McGraw-Hill, 1997. R. Sedgewick. Algoritmi in C, Addison-Wesley, 1993. R. Sedgewick. Algorithms in C.4ex++, Addison-Wesley, 1992. Materiale Didattico On-Line Dispense, lucidi, reference cards, ecc. Mailing list Algoritmi-Strutture-Dati
Pagina a cura di Enea Zaffanella	[Pagina aggiornata il 21/03/2004, 07:30:11.]