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à dei principi della buona programmazione.
Descrizione e progettazione di algoritmi efficienti
Introduzione
Concetti di algoritmo, di struttura dati, di efficienza; di costo 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;
costo computazionale nel caso migliore, peggiore e medio
Ricerca dicotomica o binaria in un vettore ordinato (vers. iterativa)
costo computazionale 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 del costo computazionale delle funzioni ricorsive tramite equazioni di ricorrenza
metodo di sostituzione
metodo iterativo
metodo dell'albero
teorema principale ( dimostrazione facoltativa )
Il problema dell'ordinamento
algoritmi naif: filosofia, pseudocodice e costo computazionale
insertion, selection e bubble sort
limitazione inferiore sul costo computazionale degli algoritmi di ordinamento per confronti; dimostrazione
funzione di fusione e merge sort; cenno alla tecnica del divide et impera
ordinamento in tempo lineare: counting sort e bucket sort
quick sort e suo costo computazionale nel caso peggiore, migliore e medio
heap e heap sort
Strutture dati fondamentali
insiemi dinamici ed operazioni su di essi
vettore non ordinato e ordinato
pila e coda, funzioni di inserimento ed estrazione, coda circolare
lista semplice e doppiamente puntata
coda con priorità
albero
definizione come grafo connesso aciclico
teorema di caratterizzazione degli alberi e dimostrazione
relazioni tra numero di nodi interni, numero di foglie ed altezza in un albero binario completo
rappresentazione in memoria di un albero binario
rappresentazione posizionale
rappresentazione con puntatori
vettore dei padri
visita in pre-, post- ed in-ordine e calcolo del costo computazionale tramite equazione di ricorrenza
Dizionari
indirizzamento diretto
tabelle hash
collisioni
soluzione delle collisioni per concatenazione (liste di trabocco e fattore di carico)
costo computazionale nel caso medio
soluzioni delle collisioni con indirizzamento aperto
vari tipi di scansione (lineare, quadratica ed hashing doppio)
costo computazionale nel caso medio
alberi binari di ricerca
definizione
algoritmo di ricerca e suo costo computazionale
algoritmi di ricerca del massimo, minimo, successore e predecessore e loro costo computazionale
algoritmo di inserimento e suo costo computazionale
algoritmo di cancellazione e suo costo computazionale
la problematica del bilanciamento per la limitazione del costo computazionale
alberi red black e teorema per la limitazione dell'altezza ( rotazioni ed altri dettagli facoltativi )
Grafi
rappresentazione in memoria
liste di adiacenza
matrice di adiacenza
matrice di incidenza
lista di archi
confronto del costo computazionale in termini di spazio e tempo in alcune operazioni elementari
visita in ampiezza (BFS)
definizione di albero ricoprente
proprietà degli archi non dell'albero
proprieta' della distanza dalla radice
visita in profondità (DFS)
proprietà degli archi non dell'albero
proprietà del numero di archi in funzione della lunghezza del cammino più lungo
similitudini e differenze tra le due visite
loro costo computazionale al variare della struttura dati usata
esempi di utilizzo delle visite
grafi euleriani e loro caratterizzazione
argomenti facoltativi:
grafi bipartiti e loro caratterizzazione (con dimostrazione)
accoppiamenti massimi e accoppiamenti massimali
accoppiamenti completi per grafi bipartiti e teoram di P. Hall (con dimostrazione)
colorazione di grafi ed enunciato del teroema di Brooks
grafi planari e formula di Eulero (con dimostrazione)
enunciato del teorema dei 4 colori
Programmazione
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.