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à.

Anno accademico:
Definizione dei periodi di lezione
Periodo Dal Al
1° Q - 2° anno e successivi 29-set-2003 28-nov-2003
2° Q 12-gen-2004 12-mar-2004
3° Q 5-apr-2004 11-giu-2004
Sessioni di lauree
Sessione Dal Al
Sessione straordinaria 17-dic-2003 17-dic-2003
Sessione invernale 17-mar-2004 17-mar-2004
Sessione estiva 22-lug-2004 22-lug-2004
Sessione autunnale 22-set-2004 22-set-2004
Vacanze
Periodo Dal Al
Festa di tutti i santi 1-nov-2003 1-nov-2003
Vacanze natalizie 22-dic-2003 6-gen-2004
Vacanze Pasquali 8-apr-2004 13-apr-2004
Festa del Patrono S. Zeno 12-apr-2004 12-apr-2004
Festa del lavoro 1-mag-2004 1-mag-2004
Festa della Repubblica 2-giu-2004 2-giu-2004
Vacanze estive 26-lug-2004 31-ago-2004

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

A B C F G M O P S V

Acquaviva Andrea

symbol email andrea.acquaviva@univr.it symbol phone-number +39 045 802 7059

Bonacina Maria Paola

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

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

Ferro Ruggero

symbol email ruggero.ferro@univr.it symbol phone-number 045 802 7909

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

Masini Andrea

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

Mastroeni Isabella

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

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

Orlandi Giandomenico

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

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

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

Villa Tiziano

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

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

InsegnamentiCreditiTAFSSD

2° Anno  Attivato nell'A.A. 2004/2005

InsegnamentiCreditiTAFSSD

3° Anno  Attivato nell'A.A. 2005/2006

InsegnamentiCreditiTAFSSD

4° Anno  Attivato nell'A.A. 2006/2007

InsegnamentiCreditiTAFSSD
3 insegnamenti affini (settori matematico e fisico) a scelta per un totale di 15 crediti (nell'anno accademico 2003/2004 l'insegnamento di Logica II è disattivato)

5° Anno  Attivato nell'A.A. 2007/2008

InsegnamentiCreditiTAFSSD
Laboratorio di informatica
10
E
-
Alte attività formative (tirocini, ecc...)
6
F
-
Prova finale
24
E
-
InsegnamentiCreditiTAFSSD
Attivato nell'A.A. 2004/2005
InsegnamentiCreditiTAFSSD
Attivato nell'A.A. 2005/2006
InsegnamentiCreditiTAFSSD
Attivato nell'A.A. 2006/2007
InsegnamentiCreditiTAFSSD
3 insegnamenti affini (settori matematico e fisico) a scelta per un totale di 15 crediti (nell'anno accademico 2003/2004 l'insegnamento di Logica II è disattivato)
Attivato nell'A.A. 2007/2008
InsegnamentiCreditiTAFSSD
Laboratorio di informatica
10
E
-
Alte attività formative (tirocini, ecc...)
6
F
-
Prova finale
24
E
-
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

4S00061

Crediti

5

Offerto anche nei corsi:

  • Complessità del corso Laurea specialistica in Sistemi intelligenti e multimediali

Lingua di erogazione

Italiano

Settore Scientifico Disciplinare (SSD)

INF/01 - INFORMATICA

Periodo

1° Q dal 2-ott-2006 al 1-dic-2006.

Sede

VERONA

Obiettivi formativi

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.

Programma

Concetto di modello di calcolo, risorsa computazionale, algoritmo efficiente e problema trattabile.
Richiamo del concetto di ordine di grandezza. 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, MAX FLOW, con analisi dei possibili algoritmi di risoluzione per MAX FLOW, 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 appartenente a L e PATH in 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 (solo enunciato).

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 relazione tra P ed EXP.
Teorema di gerarchia spaziale (solo enunciato). Corollario relazione tra L e 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 a SAT, PATH a CIRCUIT VALUE, CIRCUIT SAT a 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, MIN SET COVER, SET PACKING.

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

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: FPTAS, PTAS, APX, NPO. Esempi di problemi approssimabili e non approssimabili.

Modalità d'esame

L'esame consiste in una prova scritta e una orale (non obbligatoria).

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.

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. 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).

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

Documenti e avvisi

Anno accademico:

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.