Studiare
In questa sezione è possibile reperire le informazioni riguardanti l'organizzazione pratica del corso, lo svolgimento delle attività didattiche, le opportunità formative e i contatti utili durante tutto il percorso di studi, fino al conseguimento del titolo finale.
Piano Didattico
Il piano didattico è l'elenco degli insegnamenti e delle altre attività formative che devono essere sostenute nel corso della propria carriera universitaria.
Selezionare il piano didattico in base all'anno accademico di iscrizione.
1° Anno
2° Anno Attivato nell'A.A. 2022/2023
Insegnamenti | Crediti | TAF | SSD |
---|
Insegnamenti | Crediti | TAF | SSD |
---|
Insegnamenti | Crediti | TAF | SSD |
---|
4 insegnamenti a scelta
2 insegnamenti a scelta (A.A. 2022/23 Quantum computing non erogato)
3 insegnamenti a scelta (A.A. 2022/23 Quantum computing non erogato)
Legenda | Tipo Attività Formativa (TAF)
TAF (Tipologia Attività Formativa) Tutti gli insegnamenti e le attività sono classificate in diversi tipi di attività formativa, indicati da una lettera.
Fondamenti di algoritmi, complessita' e problem solving (2021/2022)
Codice insegnamento
4S008896
Crediti
12
Lingua di erogazione
Italiano
Settore Scientifico Disciplinare (SSD)
ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
L'insegnamento è organizzato come segue:
Teoria
Laboratorio
Obiettivi formativi
Uno degli obiettivi più elevati del corso stà nel riuscire a trasmettere alcuni aspetti del profondo ed importante interscambio dialettico tra la ricerca di algoritmi e lo studio della complessità dei problemi. Gli algoritmi costituiscono l'ossatura e la sostanza dell'informatica, ma allo stesso tempo il loro studio esula dall’ambito ristretto della scienza dei calcolatori e risulta trasversale e pervasivo a tutte le discipline che sono portatrici di problemi. Il progetto di un algoritmo prende avvio dallo studio della struttura del problema da risolvere ed il più delle volte ne rappresenta il coronamento. Lo studio degli algoritmi richiede ed offre metodologie e tecniche di problem solving, competenze logiche e matematiche.Il corso mira dunque a far acquisire agli studenti competenze e metodologie fondamentali nell'analisi dei problemi e nel progetto di algoritmi risolutori per gli stessi. Particolare enfasi viene data all'efficienza degli algoritmi stessi, e la teoria della Complessità Computazionale gioca un profondo ruolo metodologico nell'analisi dei problemi. Con riferimento agli obiettivi del percorso formativo del CdS il corso porta gli studenti ad approfondire e ampliare la formazione triennale in ambito di analisi e valutazione di problemi, algoritmi, e sistemi di calcolo, fornendo un bagaglio di strumenti avanzati per affrontare problemi non banali nei diversi ambiti dell’informatica. Gli studenti acquisiranno competenze logico-matematiche, tecniche, esperienza e metodologie utili nell'analisi di problemi algoritmici, dal rilevarne la struttura ed analizzarne la complessità computazionale al progettare algoritmi efficienti, al pianificare e condurre l’implementazione degli stessi. Inoltre il corso si propone di fornire: le basi teoriche della complessità computazionale con particolare attenzione alla teoria della NP-completezza; nozioni di algoritmi di approssimazione ed approcci di base per l'analisi di algoritmi di approssimazione per problemi “difficili”; approcci parametrizzati alla risoluzione di problemi “difficili”. Gli studenti applicheranno le principali tecniche algoritmiche: ricorsione, divide et impera, programmazione dinamica, alcune strutture dati, invarianti e monovarianti. Acquisiranno così sensibilità riguardo a quali problemi possano essere risolti efficientemente e con quali tecniche, acquisendo strumenti anche dialettici per collocare la complessità di un problema algoritmico ed individuare approcci promettenti per lo stesso, guardando al problema per coglierne la struttura. Imparerà a produrre, discutere, valutare, e validare congetture, ed affrontare anche in autonomia il percorso completo dall'analisi del problema, al progetto di un algoritmo risolutore, alla codifica e sperimentazione dello stesso, anche in contesti di ricerca in ambito aziendale come presso istituti di ricerca. I fondamenti della teoria della complessità acquisiti, consentiranno allo studente di avvalersi di riduzioni quali tecniche standard della teoria della Complessità per analizzare la natura dei problemi computazionali e valutare quali possano essere approcci alternativi alla sua risoluzione (approssimazione, parametrizzazione) in assenza di soluzioni in assoluto efficienti. Al termine del corso lo studente sarà in grado di: i) classificare problemi computazionalmente intrattabili; ii) comprendere e verificare la correttezza di una prova formale; ii) leggere e comprendere un articolo scientifico in cui venga proposto un nuovo algoritmo con associata analisi della complessità.
Programma
Rimandiamo alle schede dei singoli moduli.
Bibliografia
Modalità d'esame
Quando lo studente ha, nel proprio portafoglio voti, sia un voto positivo (almeno 18) per il modulo di Complessita` sia un voto positivo (almeno 18) per il modulo di Algoritmi, egli puo` richiedere al docente titolare del corso di procedere con la registrazione del voto per l'intero insegnamento, ottenuto come media dei voti per i due moduli.
La media e` arrotondata per eccesso ed un 30 e lode vale 33. Per generare un 30 e lode come voto finale serve almeno una lode e nessuna delle due valutazioni sotto il 30.
Quando ritieni giunto il momento di registrare il tuo voto, mandi una mail a romeo.rizzi@univr.it specificando:
1. voto per la parte di algoritmi e appello a cui lo hai conseguito (regola del max);
2. ultimo appello di complessita' al quale hai consegnato e voto conseguito;
3. voto che ti attendi ti venga verbalizzato e le tue generalita` (matricola VRxxxxxx).
Le modalita` con cui richiedere la registrazione e l'intero workflow sono riportati alla pagina:
http://profs.sci.univr.it/~rrizzi/classes/Algoritmi/index.html
Alla stessa pagina trovi inoltre il portafoglio dei tuoi voti, nonche` le informazioni su come venga prodotto e gestito il voto per il modulo di Algoritmi.
Per tali informazioni rimandiamo inoltre alle schede Dashboard della Didattica dei singoli moduli.