Corso di laurea in Informatica

Gli obiettivi di questo insegnamento fanno parte degli Obiettivi formativi specifici del CdS in Informatica (L31), in particolare in riferimento all'area dell'informatica di base. Nel dettaglio, gli obiettivi sono:

1. Acquisire la padronanza di linguaggi di programmazione e pattern di coding adatti al rapido sviluppo di algoritmi efficienti, nonché nella capacità di selezionare velocemente l’algoritmo giusto per una data situazione.
2. Introdurre tecniche algoritmiche avanzate.
3. Sviluppare la capacità di lavorare in squadra per risolvere problemi algoritmici, e a comunicare in modo efficace. Il corso segue un format tipicamente utilizzato in gare di programmazione o durante le fasi di recruiting in aziende ICT di alto profilo.

CONOSCENZA E CAPACITÀ DI COMPRENSIONE

Conoscere algoritmi e strutture dati utili per la programmazione ad alte performance. Saper comprendere e interpretare un problema algoritmico per avviare una rapida progettazione e realizzazione della soluzione.

CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE

Capacità di utilizzare in maniera adeguata gli algoritmi e le strutture dati necessarie per risolvere problemi di programmazione non banali e con alte performance. Saper applicare tecniche avanzate di programmazione per ridurre la complessità in tempo e memoria, e realizzare soluzioni efficienti.

AUTONOMIA DI GIUDIZIO

Capacità di autovalutazione e stima della complessità algoritmica di una soluzione, sfruttando anche il supporto di strumenti come piattaforme online di valutazione su use-case difficili e/o su grandi moli di dati.

ABILITÀ COMUNICATIVE

Capacità di comunicare idee e soluzioni per problemi algoritmici, applicate in particolare al lavoro di squadra, utilizzando un linguaggio scientifico adeguato ed efficace.

CAPACITÀ DI APPRENDIMENTO

Acquisizione di capacità autonome di apprendimento, tramite identificazione di risorse e materiali rilevanti, incluse piattaforme di valutazione del codice, e definizione di obiettivi chiari nella progettazione e analisi di algoritmi avanzati.

1. Introduzione alla programmazione ad alte performance e competitiva: come affrontare problemi algoritmici con limiti di tempo e di memoria.
2. Problemi che si possono risolvere tramite libreria standard di C++.
3. Problemi con soluzione greedy, ottimizzazione e finestre scorrevoli.
   Capire quando una soluzione greedy è sufficiente per risolvere il problema.
4. Ricorsione esaustiva, backtracking e strategie per ridurre lo spazio da esplorare.
5. Catalogo di strategie risolutive e programmazione dinamica.
6. Algoritmi base su grafi, visite e cammini.
7. Alberi minimi ricoprenti e struttura dati Union-Find.
8. Ordinamento topologico e algoritmi su DAG.
9. Strutture dati per operazioni su intervalli: somme prefisse, range tree.

Il corso si articola in 12 moduli da 2 ore ciascuno. È richiesta la frequenza di almeno il 75% dei moduli al fine di poter accedere all'esame. Il completamento degli esercizi proposti per modulo (anche effettuati in maniera asincrona, senza la presenza alla lezione) è considerato come equivalente alla frequenza.

Ogni modulo affronta un argomento alternando parti teoriche e di esercitazione:

• Le parti teoriche sono effettuate come lezioni frontali con il supporto di lucidi e altro materiale di approfondimento. Le nozioni teoriche vengono declinate in particolare riferimento a dei problemi presentati, e a come possono essere applicate ad essi.
• Le esercitazioni tematiche si svolgeranno preferibilmente a squadre, esponendo un insieme di problemi che gli studenti devono analizzare, trovando soluzioni efficienti e determinandone la complessità e potenziali problematiche, ed infine sviluppando codice efficiente.

L’esame si terrà sotto forma di prova di programmazione al computer. La prova prevederà la risoluzione di 4 problemi algoritmici in un tempo massimo di 4 ore. Ogni problema prevede un punteggio parziale a seconda della complessità della soluzione prodotta. I problemi saranno proposti in lingua inglese, come nelle competizioni internazionali esistenti.

Nei mesi da settembre a marzo saranno proposti 5 appelli di esame o esonero, basati su una selezione di problemi delle competizioni nazionali delle olimpiadi di informatica individuali e a squadre. Uno specifico appello (in generale il primo nel mese di Settembre) sarà anche valevole come selezione della squadra che rappresenterà l’Università di Torino alla competizione internazionale SWERC dell’International Collegiate Programming Contest.

A metà del corso verrà inoltre proposta una prova intermedia di esonero, sostitutiva della prima metà della prova di esame.

Tutto il materiale di studio necessario verrà caricato nella pagina moodle del corso durante le lezioni, con riferimenti anche ad alcune attività accessibili online. Tutto il materiale sarà fornito in digitale e sarà possibile consultarlo online e, se si desidera, scaricarlo e stamparlo. I testi di riferimento sono suggerimenti di supporto, non strettamente necessari per seguire il corso.