L'insegnamento, obbligatorio per tutti gli studenti, si propone un duplice obiettivo: da un lato, completare l'uso della programmazione quale strumento per la soluzione di problemi; dall'altro, studiare i concetti di base per la formulazione di soluzioni algoritmiche a problemi concreti. In particolare, verranno studiate soluzioni a problemi formulati in termini di strutture matematiche astratte (liste, code, grafi) e metodologie per identificare i problemi astratti che più si addicono allo studio di un problema concreto, mantenendo uno stretto legame con la loro implementazione in un programma.

Il corso ha tre obiettivi principali: rendere l'allievo in grado di risolvere problemi concreti usando un approccio algoritmico; valutare l'efficienza dell'algoritmo scelto in termini di tempo di esecuzione; capacità di implementare tale soluzione algoritmica come programma da eseguire su calcolatore. Queste capacità vengono applicate alla soluzione di problemi pratici, siano essi trattabili (quindi con soluzioni di costo polinomiale) o meno (quindi con soluzioni euristiche approssimate).

Sono richieste principalmente conoscenze del linguaggio di programmazione C (al livello del corso di Informatica del I anno), ed alcune nozioni basilari dell'Analisi Matematica.

1. Complementi di programmazione C
o Programmazione a moduli
o Ricorsione
§ Il concetto di ricorsione e relativa implementazione;
§ Funzioni matematiche ricorsive.
o Tipi di dato astratto (ADT) e strutture dati:
§ Astrazione e interfaccia
§ Pile e code, matrici e vettori dinamici;
§ Liste e alberi

2. Concetti di base sugli algoritmi
o Complessità degli algoritmi:
§ Notazione asintotica, e complessità di caso peggiore
§ Equazioni alle ricorrenze e metodi di risoluzione delle equazioni di ricorrenza

3. Ordinamento e selezione
o insertion sort, merge sort, heap sort, quick sort, quick sort probabilistico.
o Studio della complessità degli algoritmi di ordinamento, limite inferiore dell'ordinamento per confronti.
o Algoritmi lineari, counting sort, radix sort, bucket sort.
o Algoritmi di selezione, minimo, massimo

4. Strutture dati complesse:
o Code, pile, liste, heap
o Alberi: alberi binari di ricerca, alberi RB,
o Tabelle Hash

5. Paradigmi algoritmici:
o divide and conquer
o algoritmi greedy
o programmazione dinamica
o paradigmi basati su ricerca: backtracking

6. Grafi
o Definizione e rappresentazione di un grafo
o Visita in ampiezza e in profondità; ordinamento topologico, componenti connesse
o Alberi di copertura di costo minimo (Prim e Kruskal)
o Cammini minimi a sorgente singola (Dijkstra e Bellman-Ford) e multipla (Floyd-Warshall e Johnson)


7.Teoria della complessita'
o Non determinismo e algoritmi non deterministici
o Classi P e NP
o Approssimazione ed euristiche

Il corso prevede circa 10 ore di esercitazione in laboratorio, nelle quali alcuni degli algoritmi discussi in aula verranno tradotti in programmi.

- Dispense del corso a cura del docente
- T. Cormen, C. Leiserson, R. Rivest, C. Stein, 'Introduzione agli Algoritmi e Strutture Dati', McGraw-Hill Italia.
- H.M.Deitel e P.J.Deitel, 'C: Corso completo di programmazione', Apogeo.

L'esame consiste in una prova scritta a sua volta strutturata in due parti.
La prima parte è mirata ad accertare le conoscenze dello studente sugli aspetti teorici della materia (algoritmi e strutture dati);
la seconda parte valuta invece l'applicazione pratica dei concetti teorici, e prevede la realizzazione di un programma in linguaggio C che implementi la soluzione di un problema pratico che richiede l'uso di algoritmi o strutture dati complesse.