====== Algoritmi e Strutture dei Dati ====== Docente: [[http://www.di.unipi.it/~prencipe|Giuseppe Prencipe]] ====== Materiale Didattico ====== **Testo consigliato:** P. Crescenzi, G. Gambosi e R. Grossi, Strutture di dati e algoritmi, Pearson -- Addison Wesley, 2006 ====== Contenuti del Corso ====== * Problemi Computazionali * Array e liste * Alberi e grafi * Dizionari * Pile e code * NP-completezza ====== Sommario delle lezioni ====== - [[Introduzione al Corso]http://sbrinz.di.unipi.it/~peppe/MaterialeCorsi/CorsoAlgStrDati/] (**__26/04/2007__**) - Problemi Computazionali (26/04/2007) * Problemi decidibili e indecidibili * Problemi trattabili e intrattabili * Problemi NP-completi * Modello RAM e complessità computazionale (**__03/05/2007__**) - Sequenze * Sequenze lineari: array e liste * Algoritmi di Ordinamento * Selection Sort * Insertion Sort * Complessità dei problemi conputazionali * Ricerca del Segmento di Somma Massima * Ricerca binaria (**__08/05/2007__**) * Limite inferiore della ricerca per confronti * Ricorsione e Paradigma del //Divide et Impera// * Equazioni di ricorrenza e teorema fondamentale * Mergesort * Quicksort, Quicksort randomizzato e analisi del caso medio * Moltiplicazione Veloce di due Matrici (**__10/05/2007__**) * Paradigma della Programmazione Dinamica * Fibonacci * Moltiplicazione di n matrici: ricerca della sequenza ottima * Partizione di un insieme di interi (**__15/05/2007__**) * Il problema dello Zaino - Didattica della ricorsione - Sequenze: Le Liste (**__17/05/2007__**) * Inserimento e Cancellazione * Problema dei Matrimoni Stabili * Skip List e Liste Randomizzate * Liste per Insiemi Disgiunti * Liste ad Auto-Organizzazione (Move-To-Front) * Cenni sull'Analisi Ammortizzata - Alberi (**__22/05/2007__**) * Alberi Binari * Visite (Anticipata, Posticipata, Simmetrica) * Minimo Antenato Comune e Range-Min Query * Memorizzazione Implicita e Succinta e Visita per Ampiezza * Alberi k-ari e Ordinali (**__24/05/2007__**) - Dizionari * Liste e Dizionari * Tabelle Hash * Gestione delle Collisioni * Alberi Binari di Ricerca * AVL: Alberi Binari di Ricerca Bilanciati (**__29/05/2007__**) * Liste Invertite * Trie e Trie Compatti - Grafi (**__31/05/2007__**) * Rappresentazione dei Grafi (Matrice e Lista) * Chiusura Transitiva * Colorazione dei Grafi * Modelli di Reti Complesse * Motori di Ricerca e Classificazione (**__14/06/2007__**) - Code e Pile * Realizzazione tramite array e liste * Notazione polacca inversa e pile * Visite su Grafo mediante Coda (ampiezza) * Visite su Grafo mediante Pila (profondita') ====== Indicazioni per la prova finale ====== La prova finale (relazione o relazione + presentazione) ha come obiettivo quello della preparazione di una lezione (o serie di lezioni) in cui viene presentato uno degli argomenti trattati durante il corso. Due sono le opzioni disponibili. **OPZIONE 1** L’esame consiste in una relazione scritta di 5/6 pagine ca. e in un frammento di lezione alla lavagna di 20 minuti ca. La relazione deve contenere: * Tipologia della classe a cui e' diretta la lezione * In quale corso di studi si colloca la lezione * Collocazione della lezione nell’ambito del modulo di Algoritmi e Strutture Dati: * Quali lezioni vengono fatte prima * Quali lezioni vengono fatte dopo * Prerequisiti * Obiettivi formativi della lezione: * Perché viene presentata * Cosa ci si aspetta che gli studenti imparino …. * Descrizione dettagliata degli argomenti presentati durante la lezione (con relativi tempi) * Descrizione di uno/due/tre esercizi di diversa difficoltà da presentare agli studenti per verificare l’apprendimento (un /due esercizio da fare in classe durante la lezione e un esercizio da assegnare a casa) * Spiegare di ogni esercizio le finalità * Identificazione dei punti di criticità della lezione La lezione di 20/25 minuti deve vertere su un argomento presentato nella relazione. Deve svolgersi in questo modo: * Breve descrizione dei prerequisiti, della collocazione e degli obiettivi (5 minuti) * Lezione teorica (15 minuti) * Spiegazione e/o soluzione dell’esercizio (5 minuti) Nei limiti del possibile la lezione deve essere autocontenuta. **OPZIONE 2** Preparazione di un sottomodulo composto di più lezioni. L’esame consiste in una relazione scritta di 15 pagine ca. La relazione deve contenere: * In quale corso di studi si colloca il sottomodulo * Collocazione del sottomodulo nell’ambito del modulo di Algoritmi e Strutture Dati: * Quali lezioni vengono fatte prima * Quali lezioni vengono fatte dopo * Motivazioni sulla durata del sottomodulo/proporzioni con l’intero modulo di sistemi * Prerequisiti * Obiettivi formativi del modulo * Perché viene presentata * Cosa ci si aspetta che gli studenti imparino …. * Descrizione delle lezioni. Per ogni lezione: * Argomenti presentati * Tempi da dedicare ai singoli argomenti * Descrizione di uno/due esercizi di diversa difficoltà da presentare agli studenti per verificare l’apprendimento (un esercizio da fare in classe e un esercizio da assegnare a casa) * Spiegare di ogni esercizio le finalità * Identificazione dei punti di criticità del sottomodulo La relazione deve essere consegnata per e-mail (prencipe@di.unipi.it) entro il 7 Settembre Il docente si riserva di richiedere revisioni/modifiche che vanno consegnate entro il 15 Settembre Per entrambe le opzioni, - se vengono presentati algoritmi, fornire cenni sulla loro complessita' utilizzando la metedologia ritenuta piu' opportuna - se vengono presentate strutture dati, fornire esempi significativi del loro utilizzo e cenni sulla complessita' delle principali operazioni fornite sulle stesse