DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
====== 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