Stefano Guerrini
Pietro Cenciarelli
Le lezioni si tengono nell'Aula V del Dipartimento di Matematica nei giorni:
lunedì 17.00-19.00 (esercitazioni)
martedì 16.00-19.00 (di cui 2 di laboratorio di programmazione)
venerdì 16.00-18.00
Settimana 1 - 5 marzo
Non ci sono lezioni a causa dello stato di agitazione per protestare
contro il DDL Delega Moratti.
Lunedì 8 marzo
Introduzione al corso.
Ricerca di un elemento in un vettore: ricerca lineare.
Martedì 9 marzo
Ricerca binaria.
Richiami sull'uso della ricorsione nella progettazione di algoritmi.
Il metodo divide-et-impera.
Applicazione del metodo divide-et-impera al problema dell'ordinamento: il merge sort.
Codice:
ricerca binaria;
merge sort
Venerdì 12 marzo
Un altro approccio di tipo divide-et-impera al problema dell'ordinamento: il quick-sort.
Progettazione top-down di un algortimo di quick sort.
Codice:
quick sort
Martedì 16 marzo
Invariante di ciclo come strumento di progetto di un ciclo e di verifica della sua
correttezza.
Versione iterativa del merge-sort: invariante del ciclo principale e correttezza
dell'algoritmo.
Analisi e scrittura dell'algoritmo di bubble-sort basata sugli invarianti.
Richiami sulle funzioni che operano su stringhe (string.h).
Venerdì 19 marzo
Tavole dei simboli implementate con vettori e con liste. Introduzione alle tavole hash.
Martedì 23 marzo
Richiami sulle funzioni e sulle tecniche di hashing.
Introduzione ai tipi di dato astratti (ADT): interfaccia e implementazione.
Lo stack. Implementazione di stack con vettori. Esempi di utilizzo di uno stack.
Lo stack delle chiamate delle funzioni. Confronto tra programmazione ricorsiva ed iterativa.
Rovesciamento di una stringa utilizzando uno stack (algoritmo iterativo) e sfruttando lo
stack di sistema per le chiamate di funzione (algoritmo ricorsivo).
Codice:
stack (usando un vettore).
Venerdì 26 marzo
Sciopero generale.
Martedì 30 marzo
Liste come tipo di dato astratto. Implementazione di liste semplici con puntatori.
Implementazione di stack mediante liste.
Codice:
conversione di una stringa in una lista
Codice:
iterativo,
ricorsivo;
stack (usando le liste)
Venerdì 2 aprile
Notazione polacca. Uso di stack per la valutazione di espressioni
scritte in notazione polacca.
Codice:
valutazione di espressioni in notazione polacca
Martedì 6 aprile
Le code. Implementazione di code mediante liste. Implementazione mediante vettori.
Liste con sentinella, liste circolari e liste bidirezionali.
Codice:
code: usando liste,
usando vettori
Venerdì 16 aprile
Definizione di alberi e foreste. Alberi binari. Visite di alberi.
Codice:
alberi binari
Martedì 20 aprile
Assegnazione del primo modulo del progetto di laboratorio.
Esercizi sulla ricorsione su liste.
Esercizi:
ricorsione su liste
Venerdì 23 aprile
Sciopero.
Lunedì 26 aprile
Prossima lezione.
Martedì 27 aprile
Esercitazione.
Stefano Guerrini