ALGORITHMS AND DATA STRUCTURES-1

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.

Algoritmi, modelli di calcolo e metodologie di analisi: Introduzione informale agli algoritmi. Modelli di calcolo. Notazione asintotica. Ricorrenze. Master Theorem.
Tecniche fondamentali per il progetto di algoritmi: Tecnica divide et impera.
Strutture dati elementari: Array.
Algoritmo di Binary search.
Ordinamento: Selection sort, Insertion sort, BubbleSort, Merge sort, Quicksort.
Definizione di grafo, albero e visite degli alberi binari: pre-order, inorder, post-order, BFS.
Tabelle Hash.
Problemi NP-completi: Classi di complessita P e NP. Riducibilita polinomiale e NP-completezza. Esempi di problemi NP-completi.

[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

L’apprendimento viene verificato tramite un esame scritto, eventualmente seguito da una prova orale. Le domande, sia teoriche sia pratiche, mirano a valutare la comprensione degli argomenti trattati, la capacità di applicarli a casi concreti e l’abilità di analizzare criticamente le soluzioni algoritmiche proposte.
L’orale è obbligatorio alla fine del corso per chi ottiene un punteggio all'esame scritto compreso tra 15 e 17 (su 30), mentre è facoltativo per chi raggiunge la sufficienza (almeno 18).

L’esame scritto consiste in:
- un’unica prova scritta finale;
- due prove intermedie (se approvate dal collegio didattico): la prima a metà corso, la seconda al termine, accessibile solo dopo il superamento della prima.

scritto e orale

Il/la docente ha il dovere di vigilare affinché siano rispettate le regole di autenticità e originalità delle prove d'esame. Di conseguenza, nei casi in cui vi sia il sospetto di un comportamento irregolare, l'esame può prevedere un ulteriore approfondimento, contestuale alla prova d'esame, che potrà essere realizzato anche in modalità differente rispetto alle modalità sopra riportate.

La verifica dell'apprendimento avviene attraverso il superamento di un esame scritto. L'orale è obbligatorio per chi allo scritto prende un voto quasi sufficiente (tra il 15 e il 17), facoltativo per chi è sufficiente (almeno 18). 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 è strettamente 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.