ALGORITHMS AND DATA STRUCTURES-2

L'insegnamento è uno dei corsi fondamentali del corso di studio e fornisce un'introduzione agli algoritmi, ovvero alla formalizzazione dei problemi, all'individuazione di soluzioni computazionali, e all'analisi di tali soluzioni, dal punto di vista della correttezza e dell'efficienza nell'uso di risorse. Inoltre presenta varie strutture dati fondamentali e tecniche di base per la progettazione e l'analisi degli algoritmi.

Conoscenza e comprensione:
- conoscenza e comprensione dei principali algoritmi e strutture dati
- comprensione e valutazione della complessità dei problemi informatici e capacità di selezionare metodi adeguati per la modellazione e risoluzione del problema

Capacità di applicare conoscenza e comprensione:
- capacità logico-deduttive e di problem solving
- capacità di formalizzare e implementare soluzioni per problemi reali e identificazione di pattern di soluzione appropriati

Capacità di giudizio:
- Sapere formulare ed argomentare soluzioni, sviluppando anche un approccio critico alla valutazione di soluzioni alternative

Familiarità con i concetti di base della matematica discreta e dell'analisi matematica. Conoscenza dei rudimenti della programmazione.

Alberi, Alberi binari di ricerca.
Heapsort, Heap e code di priorità.
Ordinamento in tempo lineare: counting sort, radix sort.
Algoritmi greedy.
Programmazione dinamica.
Algoritmi su grafi: Rappresentazione di grafi, Visite in ampiezza e in profondità, Alberi di copertura minimi (Kruskal e Prim), Cammini minimi (Dijkstra, Bellman-Ford, Floyd-Warshall).

[CLRS] Introduction to Algorithms, third edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
[KT] Algorithm Design by Jon Kleinberg and Éva Tardos. Addison-Wesley, 2005

La verifica dell'apprendimento avviene attraverso il superamento di un esame scritto atto a verificare le conoscenze degli argomenti presentati nel corso. L'esame scritto e l'eventuale orale comprendono sia domande teoriche sugli argomenti del corso, sia esercizi. L'orale è obbligatorio per chi è quasi sufficiente (tra il 15 e il 17), facoltativo per chi è sufficiente. Lo scritto (e l'eventuale orale) servono a verificare le conoscenze previste dal programma del corso.
Verranno inoltre proposte due prove intermedie durante l'anno (previa approvazione del collegio didattico), una a metà del corso e una dopo la fine del corso alla quale si accede solo con il superamento della prima prova. Il superamento di entrambe le prove esonererà dall'esame scritto.

La verifica dell'apprendimento avviene attraverso il superamento di un esame scritto. L'orale è obbligatorio per chi è quasi sufficiente (tra il 15 e il 17), facoltativo per chi è sufficiente. La prova orale vale un massimo di 6 punti bonus. Se superata positivamente, il bonus si somma al voto della prova scritta, formando il voto finale (se il voto finale è inferiore a 18, l'esame non è superato). Se invece la prova orale viene valutata negativamente, il bonus viene sottratto dal voto di partenza e lo studente potrebbe anche non superare l'intero esame. La valutazione dell'esame terrà conto sia della capacità di rispondere alle domande teoriche sugli argomenti dell'esame, sia sulla capacità si svolgere gli esercizi secondo un punteggio indicato in ogni domanda.
Verranno inoltre proposte due prove intermedie durante l'anno (previa approvazione del collegio didattico), una a metà del corso e una dopo la fine del corso alla quale si accede solo con il superamento della prima prova. Il superamento di entrambe le prove esonererà dall'esame scritto. Il voto finale sarà dato dalla media dei voti delle due prove.

Insegnamento organizzato in lezioni frontali ed esercizi su carta.

È richiesto che gli studenti si registrino sulla pagina del corso presente nella piattaforma e-learning moodle.unive.it.
Il corso si terrà in lingua inglese.