1. Venerdì 7 ottobre
Problemi, algoritmi, esecutori. Discussione sul concetto di azione
elementare.
Discussione sulla correttezza e terminazione dei programmi.
Esercitazione. Considerando un esecutore che sappia solo testare
l'uguaglianza e sommare uno,
scrivere un metodo per la somma di due numeri e il predecessore di un
numero naturale.
Divisione intera per differenze successive.
2. Venerdì 21 ottobre
Esercitazione. Sviluppo di semplici programmi C: predecessore,
somma di due numeri, divisione intera.
Gioco dell'alto-basso.
3. Venerdì 28 ottobre
Ricorsione e iterazione. Riformulazione ricorsiva di problemi
già risolti iterativamente.
Esempi: fibonacci iterativo ericorsivo.
Fibonacci ricorsivo efficiente e simulazione dell'iterazione
con la ricorsione.
Induzione e correttezza dei programmi ricorsivi.
4. Venerdì 4 novembre
Sviluppo di programmi su array: ordinamenti naturali: bubblesort e
selectsort.
bubblesort
selectsort
5. Venerdì 11 novembre
Sviluppo di programmi su array: ordinamenti efficienti: mergesort e
quicksort.
Il problema del passaggio di parametri: passaggio di array e la funzione
scambia senza variabile ausiliaria.
quicksort
mergesort
funzione scambia
6. Venerdì 18 novembre
Matrici e metodologia di programmazione top-down: il gioco del Tris (o
tic-tac-toe).
tris
7. Venerdì 25 novembre
Esercizi: matrice a spirale. Massimo di una matrice ricorsivo.
8. Giovedì 1 dicembre
Soluzione di problemi tramite backtrack. Il problema del giro di
cavallo e delle otto regine.
Giro di Cavallo
Problema delle n Regine
9. Venerdì 2 dicembre
Introduzione alle strutture dati dinamiche: liste concatenate.
Definizione induttiva di lista e rappresentazione in linguaggio C tramite
puntatori.
Programmi sulle liste: inserimento in testa, in coda, concatenazione di
due liste, rovesciamento di una lista.
Versioni iterative e ricorsive.
10. Venerdì 16 dicembre
Discussione su side effect su memoria allocata dinamicamente.
Il tipo di dato intero di dimensione arbitraria, implementato con liste di
cifre.
Aggiornata il 18/11/2005 da Ivano Salvo