Il programma di questo corso si compone di due parti che saranno portate avanti parallelamanete.
Una si occuperà della descrizione e progettazione di algoritmi efficienti, l'altra si occuperà di programmazione.
Descrizione e progettazione di algoritmi efficienti
Introduzione
Concetti di algoritmo, di struttura dati, di efficienza; di complessita' computazionale;
modello RAM; misura di costo uniforme e logaritmico.
Notazione asintotica
Definizione e significato degli insiemi O, Ω e Θ
Il problema della ricerca
Ricerca sequenziale in un vettore disordinato;
complessita' nel caso migliore, peggiore e medio
Ricerca dicotomica o binaria in un vettore ordinato (vers. iterativa)
complessita' nel caso migliore, peggiore e medio
Introduzione alla ricorsione
funzioni ricorsive
versione iterativa e ricorsiva di algoritmi: esempi
occupazione in memoria: l'esempio del calcolo dei numeri di Fibonacci
calcolo della complessita' delle funzioni ricorsive tramite equazioni di ricorrenza
metodo di sostituzione
metodo iterativo
metodo dell'albero
teorema principale (senza dimostrazione)
Il problema dell'ordinamento:
algoritmi naif: filosofia, codice e complessita'
limitazione inferiore sulla complessita' degli ordinamenti per confronti; dimostrazione
funzione di fusione e merge sort; cenno alla tecnica del divide et impera
quick sort e sua complessita' nel caso peggiore, migliore e medio
heap e heap sort
ordinamento in tempo lineare: counting sort
Strutture dati fondamentali
insiemi dinamici ed operazioni su di essi
vettore non ordinato e ordinato
lista semplice e doppiamente puntata
pila e coda, funzioni di inserimento ed estrazione, coda circolare
Si assume che gli studenti abbiano familiarità con i fondamenti del C e che siano in grado di usare variabili di tipo semplice (int, char, double, float),
e di tipo array (allocati staticamente),
il concetto di funzione ed il passaggio dei parametri (almeno per valore).
Esecutori e programmi. L'esecutore Tiny C.
Programmare per gerarchie di astrazioni: dal Tiny C alla risoluzione di problemi complessi.
Funzioni somma, differenza, esponenziale, e predecessore in Tiny C.
Moltiplicazione (ed esponenziale) egiziana.
Cenni alla completezza computazionale del Tiny C.
Conseguenze sulla complessità nell'usare un sistema unario di calcolo.
Correttezza dei programmi: introduzione all'uso di asserzioni logiche.
Pre-condizioni e post-condizioni di una funzione.
Correttezza dei programmi iterativi: invarianti di ciclo.
Progettazione di funzioni partendo dalla loro specifica logica: divisione intera.
Rivisitazione dei puntatori in C.
Operatori di referenziazione e dereferenziazione di un puntatore.
Uno strano tipo: void *.
Passaggio di parametri ed esecuzione delle funzioni.
Passaggi per indirizzo e passaggi per valore.
Regole di scoping: variabili locali e variabili globali.
Fenomeni pericolosi: alias e side-effects. Il caso della funzione scambia senza variabile di appoggio.
Lo stack di attivazione delle chiamate di funzione.
Ricorsione [2 lezioni].
Esempi di funzioni ricorsive.
Valutazione della correttezza di un programma ricorsivo per induzione.
Potenziali rischi di inefficienza della ricorsione. Il caso del calcolo dei numeri di Fibonacci.
Funzione ricorsiva efficiente per i numeri di Fibonacci.
Traduzione di un generico programma iterativo in ricorsivo.
Problemi a soluzione inerentemente ricorsiva. Il problema della Torre di Hanoi.
Cenni alla completezza computazionale della ricorsione.
Vettori:
Allocazione statica di un vettore.
Puntatori e vettori: scansione di vettori mediante l'aritmetica dei puntatori.
Passaggio di un vettore come parametro.
Sviluppo di funzioni su vettori con asserzioni logiche.
Introduzione all'allocazione dinamica di memoria: vettori allocati dinamicamente.
Cenni alle stringhe.
Vettori bidimensionali:
Dichiarazione, rappresentazione in memoria.
Allocazione dinamica di una matrice bidimensionale.
Passaggio di un vettore bidimensionale come parametro.
Metodologia di programmazione Top-Down. Esempio: il gioco del Forza4.
Liste in C [2 lezioni].
Specifica induttiva del tipo di dato sequenza.
Rappresentazione a puntatori di una sequenza in C. Creare nuovi tipi: typedef.
Ancora sull'allocazione dinamica della memoria.
Costruttori e distruttori di un tipo di dato e loro implementazione per il tipo sequenza.
Specifica mediante equazioni ricorsive di una funzione su sequenze.
Rivisitazione dei side-effects nel caso di liste.
Stile funzionale nella programmazione su liste: evitare i side-effects e garantire la trasparenza referenziale.
Tipici problemi sulle liste: concatenazione, rovesciamento, fusione ordinata di liste ordinate.
Trucchi del mestiere: uso dei parametri per memorizzare dati intermedi di un calcolo in una scansione ricorsiva di una lista.
Applicazioni delle liste: implementazione tipo di dato Coda e Pila.
Cenni alla traduzione di programmi ricorsivi in iterativi attraverso la simulazione della pila di attivazione delle chiamate ricorsive.
Alberi binari [2 lezioni]
Specifica induttiva del tipo albero binario.
Rappresentazione a puntatori di un albero in C.
Costruttori e distruttori del tipo albero binario e loro implementazione in C.
Specifica mediante equazioni ricorsive di una funzione su alberi.
Tipici problemi su alberi binari: uguaglianza, sottoalbero, bilanciamento.
Versioni ingenue e versioni che fanno un'unica scansione dell'albero.
In laboratorio:
Compilazione ed esecuzione di un programma C in Linux
Dal file C al file eseguibile: preprocessore, compilazione, linking
Assistenza allo sviluppo e testing di programmi.
Assistenza allo svolgimento degli homework.
Essendo un corso di algoritmi e programmazione, è stato ritenuto opportuno usare il linguaggio C,
evitando le complicazioni derivanti dall'uso di un linguaggio orientato agli oggetti come il C++.
La codifica in programma di un algoritmo infatti prevalentemente riguarda gli aspetti imperativi/funzionali
dei linguaggi di programmazione, tutti presenti nel C (che è il nucleo imperativo del C++).
La programmazione a oggetti, viceversa, mostra la sua utilità maggiore nella progettazione e sviluppo
di software di medie e grandi dimensioni e nell'integrazione di software scritto da diversi programmatori.