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.

Calendario accademico

Il calendario accademico riporta le scadenze, gli adempimenti e i periodi rilevanti per la componente studentesca, personale docente e personale dell'Università. Sono inoltre indicate le festività e le chiusure ufficiali dell'Ateneo.
L’anno accademico inizia il 1° ottobre e termina il 30 settembre dell'anno successivo.

Calendario accademico

Calendario didattico

Il calendario didattico indica i periodi di svolgimento delle attività formative, di sessioni d'esami, di laurea e di chiusura per le festività.

Definizione dei periodi di lezione
Periodo Dal Al
I semestre 4-ott-2010 31-gen-2011
II semestre 1-mar-2011 15-giu-2011
Sessioni degli esami
Sessione Dal Al
Sessione straordinaria 1-feb-2011 28-feb-2011
Sessione estiva 16-giu-2011 29-lug-2011
Sessione autunnale 1-set-2011 30-set-2011
Sessioni di lauree
Sessione Dal Al
Sessione autunnale 21-ott-2010 21-ott-2010
Sessione straordinaria 15-dic-2010 15-dic-2010
Sessione invernale 24-mar-2011 24-mar-2011
Sessione estiva 19-lug-2011 19-lug-2011
Vacanze
Periodo Dal Al
Festa di Ognissanti 1-nov-2010 1-nov-2010
Festa dell'Immacolata Concezione 8-dic-2010 8-dic-2010
Vacanze Natalizie 22-dic-2010 6-gen-2011
Vacanze Pasquali 22-apr-2011 26-apr-2011
Festa della Liberazione 25-apr-2011 25-apr-2011
Festa del Lavoro 1-mag-2011 1-mag-2011
Festa del Santo Patrono di Verona S.Zeno 21-mag-2011 21-mag-2011
Festa della Repubblica 2-giu-2011 2-giu-2011
Vacanze Estive 8-ago-2011 15-ago-2011

Calendario esami

Gli appelli d'esame sono gestiti dalla Unità Operativa Segreteria Corsi di Studio Scienze e Ingegneria.
Per consultazione e iscrizione agli appelli d'esame visita il sistema ESSE3.
Per problemi inerenti allo smarrimento della password di accesso ai servizi on-line si prega di rivolgersi al supporto informatico della Scuola o al servizio recupero credenziali

Calendario esami

Per dubbi o domande leggi le risposte alle domande più frequenti F.A.Q. Iscrizione Esami

Docenti

B C D F G M O P Q S V Z

Bombieri Nicola

symbol email nicola.bombieri@univr.it symbol phone-number +39 045 802 7094

Bonacina Maria Paola

symbol email mariapaola.bonacina@univr.it symbol phone-number +39 045 802 7046

Carra Damiano

symbol email damiano.carra@univr.it symbol phone-number +39 045 802 7059

Cristani Matteo

symbol email matteo.cristani@univr.it symbol phone-number 045 802 7983

Cristani Marco

symbol email marco.cristani@univr.it symbol phone-number +39 045 802 7841

Cubico Serena

symbol email serena.cubico@univr.it symbol phone-number 045 802 8132

Drioli Carlo

symbol email carlo.drioli@univr.it symbol phone-number +39 045 802 7968

Farinelli Alessandro

symbol email alessandro.farinelli@univr.it symbol phone-number +39 045 802 7842

Favretto Giuseppe

symbol email giuseppe.favretto@univr.it symbol phone-number +39 045 802 8749 - 8748

Fiorini Paolo

symbol email paolo.fiorini@univr.it symbol phone-number 045 802 7963

Fontana Federico

symbol email federico.fontana@univr.it symbol phone-number +39 045 802 7032

Fracastoro Gerolamo

symbol email gerolamo.fracastoro@univr.it symbol phone-number + 39 0458122786

Fummi Franco

symbol email franco.fummi@univr.it symbol phone-number 045 802 7994

Fusiello Andrea

symbol email nome.cognome[at]uniud.it

Giachetti Andrea

symbol email andrea.giachetti@univr.it symbol phone-number +39 045 8027998

Giacobazzi Roberto

symbol email roberto.giacobazzi@univr.it symbol phone-number +39 045 802 7995

Macedonio Damiano

symbol email damiano.macedonio@univr.it symbol phone-number 045-802.7079

Manca Vincenzo

symbol email vincenzo.manca@univr.it symbol phone-number 045 802 7981

Mastroeni Isabella

symbol email isabella.mastroeni@univr.it symbol phone-number +390458027089

Menegaz Gloria

symbol email gloria.menegaz@univr.it symbol phone-number +39 045 802 7024

Merro Massimo

symbol email massimo.merro@univr.it symbol phone-number 045 802 7992

Monti Francesca

symbol email francesca.monti@univr.it symbol phone-number 045 802 7910

Oliboni Barbara

symbol email barbara.oliboni@univr.it symbol phone-number +39 045 802 7077

Pravadelli Graziano

symbol email graziano.pravadelli@univr.it symbol phone-number +39 045 802 7081

Quaglia Davide

symbol email davide.quaglia@univr.it symbol phone-number +39 045 802 7811

Segala Roberto

symbol email roberto.segala@univr.it symbol phone-number 045 802 7997

Vigano' Luca

symbol email luca.vigano@univr.it

Villa Tiziano

symbol email tiziano.villa@univr.it symbol phone-number +39 045 802 7034

Zorzi Margherita

symbol email margherita.zorzi@univr.it symbol phone-number +39 045 802 7908

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.

CURRICULUM TIPO:

1° Anno 

InsegnamentiCreditiTAFSSD
12
B
ING-INF/05
12
B
INF/01
12
B
ING-INF/05
InsegnamentiCreditiTAFSSD
12
B
ING-INF/05
12
B
INF/01
12
B
ING-INF/05
Insegnamenti Crediti TAF SSD

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.




S Stage e tirocini presso imprese, enti pubblici o privati, ordini professionali

Codice insegnamento

4S02709

Crediti

12

Coordinatore

Margherita Zorzi

Lingua di erogazione

Italiano

L'insegnamento è organizzato come segue:

COMPLESSITÀ

Crediti

6

Periodo

I semestre

ALGORITMI

Crediti

6

Periodo

II semestre

Obiettivi formativi

Modulo: ALGORITMI
-------
Acquisire un'adeguata conoscenza dei principali paradigmi avanzati di algoritmi per problemi di ottimizzazione combinatorica con particolare attenzione per i paradigmi che permettono di determinare soluzione approssimante per problemi di ottimizzazione combinatoria difficili.


Modulo: COMPLESSITÀ
-------
In questo corso si introducono le nozioni principali della complessità strutturale dei problemi computazionali,con particolare attenzione alle relazioni tra le principali classi di complessità e alla teoria del NP-completezza. Lo scopo è quello di fornire agli studenti gli strumenti formali necessari per analizzare la difficoltà di risoluzione dei problemi da un punto di vista computazionale.

Programma

Modulo: ALGORITMI
-------
Richiamo dei principali concetti inerenti ai problemi computazionali: descrizione, istanze, codifica, modelli precisi e modelli approssimati. Problemi computazioni di ottimizzazione. Esempi di problemi computazionali.
Richiamo dei principali concetti inerenti agli algoritmi: risorse computazionali, codifica dell'input, dimensione dell'input, definizione di tempo computazionale. Analisi caso peggiore e caso medio. Tempo di calcolo e ordini di grandezza: possibili insidie.
Tempi di calcolo e miglioramenti hardware: relazioni principali. Algoritmi efficienti e problemi trattabili.

Paradigma divide et impera
--------------------------
Richiamo struttura. Analisi complessità. Esempi di applicazione: prodotto tra due numeri, Prodotto fra due matrici.
Introduzione al problema della mediana e, generalizzazione, al problema della selezione. Risoluzione del problema della selezione.

Paradigma greedy
----------------
Richiamo struttura. Esempio di applicazione per il problema dell'albero minimo di ricoprimento. Richiamo sulla struttura dati per insiemi disgiunti. Esempio di applicazione per il problema dei cammini minimi da sorgente singola (algoritmo di Dijkstra).
Introduzione ai matroidi: definizione, proprietà fondamentali. Problema del Massimo di un matroide pesato. Dimostrazione che la tecnica greedy determina sempre la soluzione ottima per il problema del Massimo di un matroide pesato.
Valutazione due soluzioni all'esercizio di ricerca elemento in una matrice ordinata.
Uso dei matroidi per la risoluzione del problema di programmazione di task unitari su singolo processore. Limiti della rappresentazione con i matroidi. Esempi di problemi risolvibili con tecnica greedy che non sono rappresentabili da matrodidi.
Approfondimento: Codifica di Huffman.

Tecnica backtracking
--------------------
Introduzione. Schema generale. Aspetti cruciali.
Applicazione della tecnica al problema dello zaino con ripetizione. Analisi correttezza e complessità.
Introduzione uso della tecnica al problema dell'inviluppo convesso: algoritmo di Graham. Uso della tecnica backtracking al problema del string matching: algoritmo di Knuth, Morris & Pratt.

Tecnica branch & bound
----------------------
Introduzione. Schema generale. Aspetti cruciali.
Scelta ordine di visita dei figli: strategia hill climbing. Tecnica come nuova tecnica ricerca in un albero: strategia best-first.
Applicazione della tecnica al problema dell'assegnamento e al problema dello zaino.
Applicazione della tecnica al problema del commesso viaggiatore come esempio di funzione lower bound non banale.

Paradigma programmazione dinamica
---------------------------------
Introduzione. Schema generale. Aspetti cruciali. Applicazione della tecnica al problema della massima sottosequenza crescente. Applicazione della tecnica al problema del string matching approssimato e al problema dello zaino.
Analisi di esempi di applicazione. Pattern ricorrenti per la determinazione di sottoproblemi.
Tecnica memoization (annotazione)
Introduzione e analisi vantaggi svantaggi.

Algoritmi probabilistici
------------------------
Definizione. Algoritmi probabilistici numerici, algoritmi di Monte Carlo e algoritmi di Las Vegas. Esempi di problemi risolti con tali algoritmi: Buffon's needle, Pattern Matching e Universal hashing.


Tecnica ricerca locale
----------------------
Introduzione e studio caso applicazione al problema dell'albero minimo di ricoprimento. Risoluzione del problema dell'ordinamento mediante tecnica di ricerca locale: ordinamento per inserimento e ShellSort.
Tecniche avanzate di ricerca locale: Simulated annealing e Tabù search.


Algoritmi di approssimazione
----------------------------
Classi NPO e PO. Errore relatio e indice di performance. Algorimo r-approssimante. Problema r-approssimabile.
Studio dell'approssimabilità del problema Min Vertex Cover: dall'algoritmo greedy all'algoritmo pseudo-casuale.


Modulo: COMPLESSITÀ
-------
Si riporta una versione sintetica del programma d'esame. Per il programma preciso (con indicazioni utili per gli studenti), vedere il file pdf "Diario delle Lezioni"

1)Introduzione

Concetti di modello di calcolo, risorsa computazionale, algoritmo efficiente e problema trattabile.



2) Modelli di calcolo e complessità in tempo

Macchina di Turing (MdT) deterministica ad un nastro e a k nastri

Complessità in tempo rispetto al modello Mdt.
Classe di complessità TIME(f(n)).
Teorema di relazione polinomiale tra le computazioni delle macchine k-MdT e 1-MdT
Definizione Macchina ad accesso casuale RAM 

Teoremi di simulazione MdT-RAM 

Tesi del calcolo sequenziale e conseguenze.

Teorema dell'accelerazione lineare (linear speed-up) e sue conseguenze.

La classe di complessità P.

Esempi di problemi della classe P.


MdT non deterministica (NMdT).

La risorsa tempo nelle NMdT a k-nastri.
Classe di complessità NTIME(f(n)).

Esempi di algoritmi non deterministico computabile da una NMdT in tempo polinomiale.
Relazione tra NMdT e MdT.

La classe di complessità NP.

Caratterizzazione alternativa della classe NP: verificatori polinomiali.

La classe di complessità EXP.



4)Complessità in spazio

Concetto di complessità spaziale.
Macchina di Turing con input e output.
Classi di complessità SPACE(f(n)) e NSPACE(f(n)).

Teorema di compressione
Classi di complessità L e NL.

Esempi di problemi in L ed NL.

Relazione tra spazio e tempo di computazione per una MdT con I/O.


5)Relazioni tra classi di complessità

Concetto di funzione propria ed esempi di funzioni.

Il metodo di raggiungibilità.
Teorema di inclusione tra classi in tempo e in spazio.
 Concetto di Macchina di Turing Universale.

Lemmi per il teorema di gerarchia temporale.

Teorema di gerarchia in tempo. Corollario P ⊂ EXP.

Teorema di gerarchia in spazio. Corollario L ⊂ PSPACE.
Il teorema del Gap.

Teorema di Savitch con Corollario. Corollario PSPACE=NPSPACE.



6)Riduzioni e completezza

Concetto di riduzione e di riduzione logaritmica in spazio.
 Esempi di riduzione: HAMILTON PATH ≤log SAT, PATH ≤log CIRCUIT VALUE, CIRCUIT SAT ≤log SAT.

Esempio di riduzione per generalizzazione.

Proprietà delle riduzioni: transitiva e riflessiva.
 Concetto di completezza di un linguaggio.

Concetto di chiusura rispetto alla riduzione.
Chiusura delle classi L, NL, P, NP, PSPACE e EXP.
 Concetto di tabella di computazione.

Dimostrazione che CIRCUIT VALUE è P-completo.

Teorema di Cook.

Esempi di problemi NP-completi e riduzioni.

7)Cenni sulle classi complemento: Complemento e non determinismo
Classi complemento
NP e coNP

Bibliografia

Testi di riferimento
Autore Titolo Casa editrice Anno ISBN Note
Christos H. Papadimitriou Computational complexity Addison Wesley 1994 0201530821

Modalità d'esame

Modulo: ALGORITMI
-------
Prova scritta, parte della prova complessiva del corso qualifying Algoritmi (altro modulo: Complessità).


Modulo: COMPLESSITÀ
-------
Esame scritto, domande a risposta aperta.

Le/gli studentesse/studenti con disabilità o disturbi specifici di apprendimento (DSA), che intendano richiedere l'adattamento della prova d'esame, devono seguire le indicazioni riportate QUI

Tipologia di Attività formativa D e F

Insegnamenti non ancora inseriti

Prospettive


Avvisi degli insegnamenti e del corso di studio

Per la comunità studentesca

Se sei già iscritta/o a un corso di studio, puoi consultare tutti gli avvisi relativi al tuo corso di studi nella tua area riservata MyUnivr.
In questo portale potrai visualizzare informazioni, risorse e servizi utili che riguardano la tua carriera universitaria (libretto online, gestione della carriera Esse3, corsi e-learning, email istituzionale, modulistica di segreteria, procedure amministrative, ecc.).
Entra in MyUnivr con le tue credenziali GIA: solo così potrai ricevere notifica di tutti gli avvisi dei tuoi docenti e della tua segreteria via mail e a breve anche tramite l'app Univr.

Prova Finale

Scadenziari e adempimenti amministrativi

Per gli scadenziari, gli adempimenti amministrativi e gli avvisi sulle sessioni di laurea, si rimanda al servizio Sessioni di laurea - Scienze e Ingegneria.

Necessità di attivare un tirocinio per tesi

Per stage finalizzati alla stesura della tesi di laurea, non è sempre necessaria l'attivazione di un tirocinio tramite l'Ufficio Stage. Per maggiori informazioni, consultare il documento dedicato, che si trova nella sezione "Documenti" del servizio dedicato agli stage e ai tirocini.

Regolamento della prova finale

Alla tesi di laurea sono dedicati 24 CFU, per un lavoro che non deve superare i 4-5 mesi a tempo pieno per la/o studentessa/studente.

Scopo della Tesi di Laurea

La Tesi di Laurea costituisce un importante ed imprescindibile passo nella formazione della/del futura/o laureata/o Magistrale in Ingegneria e Scienze Informatiche. Scopo della tesi è quello di sviluppare uno studio quanto più originale che può culminare con un progetto applicativo o un risultato teorico connesso a specifici problemi di natura progettuale o una rassegna critica sullo stato dell'arte in un determinato ambito di studio. Su proposta della/del relatrice/relatore, può essere compilato e discusso in lingua straniera. Nel corso dello svolgimento della Tesi il laureando dovrà, sotto la guida della relatrice/relatore ed eventuali correlatrici/correlatori, affrontare lo studio e l'approfondimento degli argomenti scelti, ma anche acquisire capacità di sintesi e applicazione creativa delle conoscenze acquisite. Il contenuto della Tesi deve essere inerente a tematiche dell'ingegneria e delle Scienze Informatiche o discipline strettamente correlate. La Tesi consiste nella presentazione in forma scritta di attività che possono essere articolate come:

  1. progettazione e sviluppo di applicazioni o sistemi;
  2. analisi critica di contributi tratti dalla letteratura scientifica;
  3. contributi originali di ricerca.

La Tesi può essere redatta sia in lingua inglese che in lingua italiana, e può essere discussa sia in inglese che in italiano, anche mediante l'ausilio di supporti multimediali quali slide, filmati, immagini e suoni. Nel caso di tesi redatta in lingua italiana alla medesima dovrà essere aggiunto un breve riassunto in lingua inglese.

Modalità di svolgimento e valutazione

Ogni Tesi di Laurea può essere interna o esterna a seconda che sia svolta presso l'Università di Verona o in collaborazione con altro ente, rispettivamente. Ogni Tesi prevede una/un relatrice/relatore eventualmente affiancata/o da una/uno o più correlatrici/correlatori e una/un controrelatrice/controrelatore. La/il controrelatrice/controrelatore è nominata/o dal Collegio Didattico di Informatica almeno 20 giorni prima della discussione della Tesi, verificata l'ammissibilità della/o studentessa/studente a sostenere l’esame di Laurea Magistrale. Per quanto riguarda gli aspetti giuridici (e.g., proprietà intellettuale dei risultati) legati alla Tesi e ai risultati ivi contenuti si rimanda alla legislazione vigente in materia ed ai Regolamenti di Ateneo.

Valutazione delle Tesi

I criteri su cui sono chiamati ad esprimersi relatore ed eventuali correlatori e controrelatore sono i seguenti:

  1. livello di approfondimento del lavoro svolto, in relazione allo stato dell'arte dei settori disciplinari di pertinenza informatica;
  2. avanzamento conoscitivo o tecnologico apportato dalla Tesi;
  3. impegno critico espresso dalla/dal laureanda/o;
  4. impegno sperimentale e/o di sviluppo formale espresso dal laureando;
  5. autonomia di lavoro espressa dalla/dal laureanda/o;
  6. significatività delle metodologie impiegate;
  7. accuratezza dello svolgimento e della scrittura;
  8. la/il controrelatrice/controrelatore non è chiamata/o ad esprimersi sul punto 5.

Voto di Laurea

Il voto di Laurea (espresso in 110mi) è un valore intero compreso tra 66/110 e 110/110 e viene formato dalla somma, arrotondata al numero intero più vicino (e.g., 93.50 diventa 94, 86.49 diventa 86), dei seguenti addendi:

  • 1. media pesata sui crediti e rapportata a 110 dei voti conseguiti negli esami di profitto;
  • 2. valutazione del colloquio di Laurea e della Tesi secondo le seguenti modalità:
    • a. attribuzione di un coefficiente compreso tra 0 e 1 (frazionario con una cifra decimale) per ciascuno dei punti 1-7 elencati sopra;
    • b. attribuzione di un coefficiente compreso tra 0 e 1 (frazionario con una cifra decimale) per la qualità della presentazione;
    • c. somma dei coefficienti attribuiti ai punti a e b.

La presenza di eventuali lodi ottenute negli esami sostenuti, la partecipazione a stage ufficialmente riconosciuti dal Collegio Didattico di Informatica, il superamento di esami in soprannumero ed il raggiungimento della Laurea in tempi contenuti rispetto alla durata legale del corso degli studi possono essere utilizzati dalla Commissione di Laurea per attribuire un ulteriore incremento di un punto.

Qualora la somma ottenuta raggiunga 110/110, la Commissione può decidere l'attribuzione della lode. La lode viene proposta e discussa dalla Commissione, senza l'adozione di particolari meccanismi di calcolo automatico. In base alle norme vigenti, la lode viene attribuita solo se il parere è unanime.

Tesi esterne

Una Tesi esterna viene svolta in collaborazione con un ente diverso dall'Università di Verona. In tal caso, la/il laureanda/o dovrà preventivamente concordare il tema della Tesi con una/un relatrice/relatore dell'Ateneo. Inoltre, è previsto almeno una/un correlatrice/correlatore appartenente all'ente esterno, quale riferimento immediato per la/o studentessa/studente nel corso dello svolgimento dell’attività di Tesi. Relatrice/relatore e correlatrici/correlatori devono essere indicate/i nella domanda di assegnazione Tesi. Le modalità assicurative della permanenza della/o studentessa/studente presso l'Ente esterno sono regolate dalle norme vigenti presso l'Università di Verona. Se la Tesi si configura come un periodo di formazione presso tale ente, allora è necessario stipulare una convenzione tra l'Università e detto ente. I risultati contenuti nella Tesi sono patrimonio in comunione di tutte le persone ed enti coinvolti. In particolare, i contenuti ed i risultati della Tesi sono da considerarsi pubblici. Per tutto quanto riguarda aspetti non strettamente scientifici (e.g. convenzioni, assicurazioni) ci si rifà alla delibera del SA. del 12 gennaio 1999

Relatrice/relatore,correlatrici/correlatori,controrelatrici/controrelatori

La Tesi di Laurea viene presentata da una/un relatrice/relatore docente di ruolo del Dipartimento di Informatica o inquadrato nei SSD ING-INF/05 e INF/01. Oltre a coloro che hanno i requisiti indicati rispetto al ruolo di relatrice/relatore (come indicato sopra), possono svolgere il ruolo di correlatrici/correlatori anche ricercatrici/ricercatori operanti in istituti di ricerca extrauniversitari assegnisti di ricerca, titolari di borsa di studio post-dottorato, dottorandi di ricerca, personale tecnico del Dipartimento, cultrici/cultori della materia nominate/i da un Ateneo italiano ed ancora in vigore, referenti aziendali esperte/i nel settore considerato nella Tesi. Può essere nominata/o controrelatrice/controrelatore qualunque docente professoressa/professore o ricercatrice/ricercatore del Dipartimento di Informatica dell'Università degli Studi di Verona, che risulti particolarmente competente nell'ambito specifico di studio della Tesi.

Elenco delle proposte di tesi e stage

Proposte di tesi Area di ricerca
Analisi ed identificazione automatica del tono/volume della voce AI, Robotics & Automatic Control - AI, Robotics & Automatic Control
Analisi e percezione dei segnali biometrici per l'interazione con robot AI, Robotics & Automatic Control - AI, Robotics & Automatic Control
Integrazione del simulatore del robot Nao con Oculus Rift AI, Robotics & Automatic Control - AI, Robotics & Automatic Control
Tesi in ragionamento automatico Computing Methodologies - ARTIFICIAL INTELLIGENCE
Sviluppo sistemi di scansione 3D Computing Methodologies - COMPUTER GRAPHICS
Sviluppo sistemi di scansione 3D Computing Methodologies - IMAGE PROCESSING AND COMPUTER VISION
Dati geografici Information Systems - INFORMATION SYSTEMS APPLICATIONS
Analisi ed identificazione automatica del tono/volume della voce Robotics - Robotics
Analisi e percezione dei segnali biometrici per l'interazione con robot Robotics - Robotics
Integrazione del simulatore del robot Nao con Oculus Rift Robotics - Robotics
Tesi in ragionamento automatico Theory of computation - Logic
Tesi in ragionamento automatico Theory of computation - Semantics and reasoning
Proposte di tesi/collaborazione/stage in Intelligenza Artificiale Applicata Argomenti vari
Proposte di Tesi/Stage/Progetto nell'ambito dell'analisi dei dati Argomenti vari

Modalità di frequenza

Come riportato nel Regolamento Didattico, la frequenza al corso di studio non è obbligatoria.
 


Gestione carriere


Area riservata studenti


Erasmus+ e altre esperienze all’estero