Matematica

IVANO SALVO
IVANO SALVO

Obiettivi generali

Acquisire conoscenze di base relativamente al progetto di algoritmi di base, iterativi e ricorsivi, ed alla valutazione della loro efficienza computazionale.

Obiettivi specifici

Conoscenza e comprensione:
Al termine del corso gli studenti conosceranno le metodologie di base per la progettazione e l'analisi di algoritmi iterativi e ricorsivi, le principali strutture dati, alcuni modi per scandire tali strutture, i principali algoritmi di ordinamento e le implementazioni più elementari dei dizionari. Avanno una buona conoscenza del linguaggio C, compresi aspetti avanzati come allocazione dinamica di memoria, aritmetica dei puntatori e compilazione separata dei programmi.

Applicare conoscenza e comprensione:
Al termine del corso gli studenti avranno acquisito familiarità con le principali strutture dati di base, in particolare quelle che implementano i dizionari. Sapranno spiegarne gli algoritmi e analizzarne la complessità, evidenziando come le prestazioni dipendano dalla struttura dati utilizzata. Saranno in grado di progettare nuove strutture dati e i relativi algoritmi, rielaborando quelli esistenti; sapranno spiegare i principali algoritmi di ordinamento, illustrando le strategie di progetto sottostanti e le relative analisi di complessità; saranno in grado di confrontare i comportamenti asintotici dei tempi di esecuzione degli algoritmi studiati; saranno in grado di progettare soluzioni ricorsive di problemi e di analizzare asintoticamente gli algoritmi risultanti. Sapranno infine implementare gli algoritmi e le strutture dati apprese in linguaggio C, con attenzione anche all’analisi di correttezza, alla chiarezza e all’efficienza concreta dei programmi.


Capacità critiche e di giudizio:
Lo studente avrà le basi per analizzare la qualità di un algoritmo e delle relative strutture dati, sia dal punto di vista della effettiva risoluzione del problema che da quello della efficienza computazionale con la quale il problema viene risolto.

Capacità comunicative:
Lo studente acquisirà la capacità di esporre in modo chiaro ed organizzato le proprie conoscenze, capacità che verrà verificata sia mediante i quesiti presentati nelle prove scritte che durante la prova orale.
Lo studente sarà in grado di esprimere un’idea algoritmica in modo rigoroso sia ad alto livello, tramite l’uso dello pseudocodice, che in linguaggio C.

Capacità di apprendimento:
Le conoscenze acquisite permetteranno allo studente, una volta concluso il ciclo di studi, di affrontare lo studio, individuale o previsto nell’ambito di un corso di laurea magistrale, di tecniche algoritmiche, di strutture dati più avanzate e di metodologie avanzate di programmazione.

Conoscenze e capacità di comprensione: algoritmi basi su vettori, algoritmi di ricerca & ordinamento, strutture dati (liste, pile, code, alberi, ABR, heap) e algoritmi su grafi.
Utilizzazione delle conoscenze e capacità di comprensione: applicare algoritmi a situazioni specifiche; analizzare inefficienze algoritmiche;
Capacità di trarre conclusioni: capire la difficoltà computazionale di un problema, formulare ipotesi su cui lavorare.
Abilità comunicative: descrivere in modo sintetico e astratto (ma senza ambiguità) una soluzione algoritmica a un problema.
Capacità di apprendere: studiare rapidamente risultati/soluzioni specifiche, grazie ai problemi generali studiati nel corso;

Nozioni base di programmazione.

Parte generale (60 ore):
Descrizione e progettazione di algoritmi efficienti: Introduzione ai concetti di algoritmo, di struttura dati, di efficienza, di complessità computazionale. Notazione asintotica. Introduzione alla ricorsione. Il problema dell'ordinamento. Strutture dati fondamentali (vettori, liste, pile, code, code con priorità, alberi). Dizionari. Grafi.

Parte sul linguaggio C (24 ore):
Linguaggio C: Principi di buona strutturazione dei programmi (programmazione strutturata, sviluppo di programmi corretti seguendo una metodologia top-down strutturando i programmi con utilizzo di funzioni). Richiamo di nozioni elementari del linguaggio C: costrutti iterativi e funzioni, vettori e strutture. Ricorsione in C. Puntatori e allocazione dinamica di memoria. Liste e alberi binari.

Testo di riferimento:
T. H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to algorithms, The MIT Press

Sarà cura dei docenti distribuire materiale didattico, relativo sia alle lezioni ed esercitazioni della parte generale (sotto forma di dispense) che alla parte sul linguaggio C (sotto forma di dispense e programmi di esempio scritti in linguaggio C).

Testi di consultazione e ispirazione:
J. Kleimberg, E. Tardos: "Algorithm Design", Pearson, 2006.
E. W. Dijkstra: "A Discipline of Programming", Prentice Hall, 1976.
J. Bentley: "Programming Pearls" (1986) and "More Programming Pearls" (1988), Addison Wesley.

La modalità di svolgimento è tradizionale in aula con slides.
Possibilità di didattica blended, a seconda della situazione pandemica.

Seguire le lezioni è fortemente raccomandato.

L’esame mira a valutare l’apprendimento tramite una prova scritta (consistente nella risoluzione di problemi dello stesso tipo di quelli svolti nelle esercitazioni), degli homework (consistente nella scrittura e nella esecuzione di programmi C di varia difficoltà) e una prova orale (consistente nella discussione dei temi più rilevanti illustrati nel corso). La prova scritta avrà una durata di circa due ore e può essere sostituita da prove intermedie, più brevi, che si svolgeranno durante il corso. Per superare l'esame occorre conseguire un voto non inferiore a 18/30. Lo studente deve dimostrare di aver acquisito una conoscenza sufficiente degli argomenti di entrambe le parti del programma. Per conseguire un punteggio pari a 30/30 e lode, lo studente deve invece dimostrare di aver acquisito una conoscenza eccellente di tutti gli argomenti trattati durante il corso ed essere in grado di raccordarli in modo logico e coerente.

Valutare la complessità asintotitca di un programma.
Scrivere lo pseudocodice di algoritmi su vettori, liste, alberi e grafi.
Applicare tipici schemi di progetto di algoritmi.

• I mattoni del Calcolare: Iterazione, Ricorsione, Tipi di Dato base


• Il problema dell'ordinamento: algoritmi base e avanzati


• Strutture dati: liste, pile, code, alberi, alberi binari di ricerca, alberi rosso-neri


• Introduzione ai grafi: algoritmi di ricerca, cammini minimi, componenti connesse