Studying at the University of Verona

Here you can find information on the organisational aspects of the Programme, lecture timetables, learning activities and useful contact details for your time at the University, from enrolment to graduation.

Academic calendar

The academic calendar shows the deadlines and scheduled events that are relevant to students, teaching and technical-administrative staff of the University. Public holidays and University closures are also indicated. The academic year normally begins on 1 October each year and ends on 30 September of the following year.

Academic calendar

Course calendar

The Academic Calendar sets out the degree programme lecture and exam timetables, as well as the relevant university closure dates..

For the year 2001/2002 No calendar yet available

Exam calendar

Exam dates and rounds are managed by the relevant Science and Engineering Teaching and Student Services Unit.
To view all the exam sessions available, please use the Exam dashboard on ESSE3.
If you forgot your login details or have problems logging in, please contact the relevant IT HelpDesk, or check the login details recovery web page.

Exam calendar

Should you have any doubts or questions, please check the Enrollment FAQs

Academic staff

B C D F G M O P Q R S

Bellin Gianluigi

symbol email gianluigi.bellin@univr.it symbol phone-number +39 045 802 7969

Belussi Alberto

symbol email alberto.belussi@univr.it symbol phone-number +39 045 802 7980

Bonacina Maria Paola

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

Burattini Emilio

symbol email emilio.burattini@univr.it

Combi Carlo

symbol email carlo.combi@univr.it symbol phone-number +390458027985

Cristani Matteo

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

De Marchi Stefano

symbol email stefano.demarchi@univr.it symbol phone-number 045 8027978

Drago Nicola

symbol email nicola.drago@univr.it symbol phone-number 045 802 7081

Fontana Federico

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

Fummi Franco

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

Giacobazzi Roberto

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

Gregorio Enrico

symbol email Enrico.Gregorio@univr.it symbol phone-number 045 802 7937

Manca Vincenzo

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

Masini Andrea

symbol email andrea.masini@univr.it symbol phone-number 045 802 7922

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

Morato Laura Maria

symbol email laura.morato@univr.it symbol phone-number 045 802 7904

Murino Vittorio

symbol email vittorio.murino@univr.it symbol phone-number 045 802 7996

Oliboni Barbara

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

Orlandi Giandomenico

symbol email giandomenico.orlandi at univr.it symbol phone-number 045 802 7986

Pica Angelo

symbol email angelo.pica@univr.it
PiccininiNicola

Piccinini Nicola

symbol email piccinini@sci.univr.it symbol phone-number +39 349 7461319

Posenato Roberto

symbol email roberto.posenato@univr.it symbol phone-number +39 045 802 7967

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

Rossignoli Cecilia

symbol email cecilia.rossignoli@univr.it symbol phone-number 045 802 8173
Giuseppe Scollo in Waddenzee 1987,  February 18, 2005

Scollo Giuseppe

symbol email giuseppe . scollo at univr . it symbol phone-number 045 802 7940

Segala Roberto

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

Spoto Nicola Fausto

symbol email fausto.spoto@univr.it symbol phone-number +39 045 8027940

Study Plan

The Study Plan includes all modules, teaching and learning activities that each student will need to undertake during their time at the University.
Please select your Study Plan based on your enrollment year.

The Study plan 2001/2002 will be available by April 2nd. While waiting for it to be published, consult the Study plan for the current academic year at the following link.

Legend | Type of training activity (TTA)

TAF (Type of Educational Activity) All courses and activities are classified into different types of educational activities, indicated by a letter.




S Placements in companies, public or private institutions and professional associations

Teaching code

4S00061

Credits

5

Also offered in courses:

Language

Italian

Scientific Disciplinary Sector (SSD)

INF/01 - INFORMATICS

Period

First four-month term for the second year onwards dal Sep 27, 2004 al Nov 26, 2004.

Location

VERONA

Learning outcomes

Il corso è costituito da un'introduzione alla complessità strutturale, con particolare attenzione alla teoria del NP-completezza, e da un'introduzione alla analisi di complessità dei problemi rispetto alla loro approssimabilità computazionale.

Scopo di tale introduzione è fornire agli studenti gli strumenti necessari per comprendere e affrontare la difficoltà nel risolvere alcuni problemi comuni da un punto di vista computazionale.

Il corso viene svolto in 40 ore di lezione frontale.

Program

Introduzione al corso: programma, testi di riferimento e modalità d'esame.
Concetto intuitivo di modello di calcolo, risorsa computazionale, algoritmo efficiente e problema trattabile.
Richiamo del concetto di ordine di grandezza: O, Ω e Θ. Richiamo dei concetti principali inerenti all'espressioni booleane.

Problemi computazionali: descrizione, istanze, codifica, relazione con i linguaggi. Esempi di problemi: RAGGIUNGIBILITÀ (PATH), MASSIMO FLUSSO (MAX FLOW) e SODDISFACIBILITÀ (SAT).

Modelli di calcolo
Macchina di Turing (MdT): definizione, funzionamento, concetto di configurazione, produzione e di computazione. Esempio di MdT. MdT e linguaggi: differenza tra accettare e decidere un linguaggio. Estensione della MdT: MdT a più nastri (k-MdT).

Complessità in tempo
La risorsa computazionale tempo. Classe di complessità TIME(). Teorema di relazione polinomiale tra le computazioni delle macchine k-MdT e MdT (idea della dimostrazione).
Introduzione al modello di calcolo "Macchina ad accesso casuale" (RAM = Random Access Machine): concetti di configurazione, programma e computazione. Macchina ad accesso casuale (RAM): tempo di computazione secondo il criterio di costo uniforme e costo logaritmico. Ipotesi necessarie per poter utilizzare il criterio del costo uniforme.
Esempio di programma RAM per calcolare il prodotto di due interi.
Teorema sul costo di simulazione di una MdT mediante un programma RAM (idea della dimostrazione).
Teorema sul costo di simulazione di un programma RAM mediante una MdT (solo enunciato).
Tesi del calcolo sequenziale e sue conseguenze.
Teorema dell'accelerazione lineare (linear speed-up) e sue conseguenze.
La classe di complessità P.
Esempio di problemi della classe P: PATH. Esempio di problema della classe P: MAX FLOW. Insidie sui possibili algoritmi di risoluzione per MAX FLOW.
Esempio di problema della classe P: ACCOPPIAMENTO PERFETTO (PERFECT MATCHING).
Estensione della MdT: MdT non deterministica (NMdT).
La risorsa tempo nelle NMdT a k-nastri. Classe di complessità NTIME().
Esempio di algoritmo non deterministico computabile da una NMdT: algoritmo per SODDISFACIBILITÀ (SAT).
Relazione tra NMdT e MdT.
La classe di complessità NP.
Relazione tra NP e P. Esempio di problema in NP: problema del COMMESSO VIAGGIATORE (TSP).
Caratterizzazione alternativa della classe NP: verificatori polinomiali.
La classe di complessità EXP.

Complessità in spazio
Concetto di complessità spaziale. Macchina di Turing con input e output. Classi di complessità SPACE() e NSPACE().
Teorema di compressione (solo enunciato, dimostrazione per esercizio).
Classi di complessità L e NL.
Esempi di problemi: PALINDROME ∈ L e PATH ∈ NL.

Teoremi di relazione tra spazio e tempo di computazione per una MdT con I/O.
Relazioni tra classi di complessità
Concetto di funzione propria ed esempi di funzioni.
Il teorema del gap di Borodin.

Il metodo di raggiungibilità. Teorema di inclusione tra classi in tempo e in spazio: NTIME(f(n)) ⊆ SPACE(f(n)), NSPACE(f(n)) ⊆ TIME(k(log n+f(n))).
Concetto di Macchina di Turing Universale.
L'insieme Hf.
Lemma 1 per il teorema di gerarchia temporale. Lemma 2 per il teorema di gerarchia temporale.
Teorema di gerarchia in tempo: versione lasca e versione stretta. Corollario P ⊂ EXP.
Teorema di gerarchia spaziale (solo enunciato). Corollario L ⊂ PSPACE.
Teorema di Savitch. Corollario SPACE(f(n))=SPACE(f(n) al quadrato). Corollario PSPACE=NPSPACE.

Riduzioni e completezza
Concetto di riduzione e di riduzione logaritmica in spazio.
Esempio 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.
Dimostrazione alternativa del teorema di Cook: CIRCUIT SAT è NP-completo.
Esempi di problemi NP-completo e loro riduzioni: SAT e sue varianti (3SAT, 3SAT con vincoli). Il caso 2SAT.
Concetto di gadget e dimostrazione della completezza del problema dell'INSIEME DI INDIPENDENZA (INDEPENDENT SET).
Problemi collegati: CRICCA (CLIQUE) e RICOPRIMENTO DI VERTICI (VERTEX COVER). Cenni sulla completezza dei problemi: MASSIMO TAGLIO, K-COLORABILITÀ, CIRCUITO HAMILTONIANO, COMMESSO VIAGGIATORE, ACCOPPIAMENTO TRIDIMENSIONALE.

Cenni sulla completezza della PROGRAMMAZIONE LINEARE INTERA, ZAINO e RIEMPIMENTO DEI CESTINI (BIN PACKING). Concetto di algoritmo pseudo polinomiale. Problemi fortemente NP-completi. Altri problemi NP-completi secondo la classificazione di Garey e Johnson.

Algoritmi di approssimazione e classi di complessità approssimate
Concetto di soluzione approssimata e di algoritmo approssimante. Esempi. Concetto di classificazione dei problemi in base alla loro approssimabilità computazionale. Principali classi di approssimazione computazionale: PTAS, APX, NPO. Esempi di problemi approssimabili e non approssimabili.

Reference texts
Author Title Publishing house Year ISBN Notes
Christos H. Papadimitriou Computational complexity Addison Wesley 1994 0201530821 Teso di riferimento principale
A. Bernasconi B. Codenotti Introduzione alla complessità computazionale Springer 1998 8847000203 Teso di riferimento secondario, per ulteriore consultazione. In italiano.

Examination Methods

L'esame consiste in una prova scritta e una orale. Nella prova scritta il candidato dovrà risolvere degli esercizi in ordine crescente di difficoltà. Gli esercizi hanno lo scopo di verificare la preparazione dello studente sui concetti fondamentali e la loro applicazione. Non viene MAI richiesto di conoscere a memoria dettagli di dimostrazioni, ma di conoscere i teoremi, la loro dimostrazione nei punti fondamentali e di saperli applicare. Solitamente gli esercizi sono quattro a difficoltà crescente. I primi due esercizi valgono al massimo 7 punti ciascuno mentre gli ultimi due 8. La prova è superata se per ciascuno dei primi due esercizi si ottengono almeno 4 punti E si raggiunge il punteggio finale di 18. La prova ha una durata di un'ora e mezza. Chi supera la prova scritta può sostenere la prova orale o chiedere la 'conferma' del voto. In caso di conferma del voto scritto, il voto finale non potrà mai essere superiore a 24: votoFinale = (votoScritto > 24) ? 24 : votoScritto; La prova orale consiste in un colloquio dove viene richiesto di 'ragionare' su almeno due argomenti (a scelta del docente) del programma del corso. Il colloquio ha lo scopo di verificare la capacità dello studente di presentare gli argomenti e i principali risultati. Per quanto riguarda le dimostrazioni dei teoremi, lo studente è tenuto a conoscere le dimostrazioni principali fatte durante il corso (segnalate dal docente e sul programma). Una raccolta dei temi d'esame è disponibile all'indirizzo http://profs.sci.univr.it/~posenato/courses/complessita/temiEsame

Students with disabilities or specific learning disorders (SLD), who intend to request the adaptation of the exam, must follow the instructions given HERE

Teaching materials e documents

Type D and Type F activities

Training offer to be defined

Career prospects


Module/Programme news

News for students

There you will find information, resources and services useful during your time at the University (Student’s exam record, your study plan on ESSE3, Distance Learning courses, university email account, office forms, administrative procedures, etc.). You can log into MyUnivr with your GIA login details: only in this way will you be able to receive notification of all the notices from your teachers and your secretariat via email and soon also via the Univr app.