FONDAMENTI DI INFORMATICA 2 - DIPLOMA II° MODULO
Riepilogo argomenti trattati nelle lezioni D.D.



 
 
 
 
20.1.99
  • Presentazione, informazioni varie, programma provvisorio. 
  • Algoritmi di ordinamento selection-sort / merge-sort. 
  • Analisi degli algoritmi (calcolo del costo di esecuzione nel caso migliore, medio, peggiore, notazione Q (theta))
    		•  Cap.1 CLR
    25.1.99 Strutture di dati e algoritmi per problemi di ordinamento. (Heapsort, Mergesort, Quicksort). 
    Alberi di decisione.    		 Cap. 7-8-9 CLR
    27.1.99 No lezione per malattia.
    1.2.99 Alberi binari di ricerca. 
    SEMINARIO - Alberi Rosso-Neri    		 Cap. 13-14 CLR 
    3.2.99 Alberi di decisione. 
    Notazioni O, W, Q.
    Strutture di dati e algoritmi per problemi di ordinamento. (Countingsort, Radixsort).    		 Cap. 10 CLR
    8.2.99 Problemi di selezione. (Ricerca del minimo, massimo, secondo elemento, cenni su algoritmo di selezione randomized-select per un elemento qualsiasi in tempo O(n) nel caso medio). 
    Tabelle Hash.    		 Cap. (?),  12 CLR
    10.2.99 Strutture dati per memoria secondaria. (B-alberi).  Cap. 4.3 CUD, (Cap. 19 CLR)
    15.2.99 Interruzione attività didattiche (vacanze carnevale).
    17.2.99 Strutture dati per memoria secondaria. (B-alberi). 
    Laboratorio.
    23.2.99  dalle 19.00 alle 21.00 seminario. Argomento: calcolabilita'
    lezioni successive fino al 3 Marzo Hashing dinamico. Grafi (definizioni). Algoritmi di Prim, Kruskal, Dijkstra.
    Laboratorio, visione delle pagine Web del corso.
    Esercitazioni su prove d'esonero passate e su alcune domande del libro (CLR).
    8.3.99 Algoritmo di Floyd/Warshall.
    Problema della bisaccia 0-1 (algoritmi di soluzione con tecnica greedy). Problema della bisaccia frazionario.
    Calcolabilita': problema della fermata.
    10.3.99 Calcolabilita'.
    15.3.99 dalle 18.00 alle 19.00 lezione normale (Trattabilita' computazionale, classi P, NP, EXP).
    ore 19.00 seminario. Argomento: algoritmi di programmazione dinamica per il problema della bisaccia.
    17.3.99 Argomenti previsti: Algoritmo di Bellman-Ford, Trattabilita', esercizi di preparazione all'esonero.
    22.3.99 NON C'E' LEZIONE DI FONDAMENTI (quattro ore di Teoria dei Circuiti)
    24.3.99 Esercizi di preparazione all'esonero.
    Giovedi 25.3.99 dalle 17.00 alle 20.00 esonero.
    Suggerimento: prendere visione anche dei capitoli 2 - 3 - 4 - 5 - 6 CLR (Parte prima - Fondamenti di Matematica), che trattano i metodi matematici utili per una migliore comprensione dell'analisi degli algoritmi. Cito dall'introduzione alla parte prima:
    "Si suggerisce al lettore di non provare a leggere tutti questi fondamenti matematici in una sola volta. Conviene, piuttosto, sfogliare prima i capitoli di questa parte per vedere gli argomenti contenuti e poi procedere direttamente ai capitoli che riguardano gli algoritmi. Questa parte puo' sempre essere utilizzata come riferimento per una migliore comprensione degli strumenti usati nel libro per l'analisi degli algoritmi."