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 didattico
Il calendario didattico indica i periodi di svolgimento delle attività formative, di sessioni d'esami, di laurea e di chiusura per le festività.
| Periodo | Dal | Al |
|---|---|---|
| I semestre | 1-ott-2012 | 31-gen-2013 |
| II semestre | 4-mar-2013 | 14-giu-2013 |
| Sessione | Dal | Al |
|---|---|---|
| Sessione straordinaria | 4-feb-2013 | 28-feb-2013 |
| Sessione estiva | 17-giu-2013 | 31-lug-2013 |
| Sessione autunnale | 2-set-2013 | 30-set-2013 |
| Sessione | Dal | Al |
|---|---|---|
| Sessione autunnale | 18-ott-2012 | 18-ott-2012 |
| Sessione straordinaria | 12-dic-2012 | 12-dic-2012 |
| Sessione invernale | 21-mar-2013 | 21-mar-2013 |
| Sessione estiva | 16-lug-2013 | 16-lug-2013 |
| Periodo | Dal | Al |
|---|---|---|
| Festa di Ognissanti | 1-nov-2012 | 1-nov-2012 |
| Festa dell'Immacolata Concezione | 8-dic-2012 | 8-dic-2012 |
| Vacanze di Natale | 21-dic-2012 | 6-gen-2013 |
| Vacanze di Pasqua | 29-mar-2013 | 2-apr-2013 |
| Festa della Liberazione | 25-apr-2013 | 25-apr-2013 |
| Festa del Lavoro | 1-mag-2013 | 1-mag-2013 |
| Festa del Santo Patrono di Verona - San Zeno | 21-mag-2013 | 21-mag-2013 |
| Festa della Repubblica | 2-giu-2013 | 2-giu-2013 |
| Vacanze estive | 9-ago-2013 | 16-ago-2013 |
Calendario esami
Gli appelli d'esame sono gestiti dalla Unità Operativa Didattica e Studenti 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
Per dubbi o domande leggi le risposte alle domande più frequenti F.A.Q. Iscrizione Esami
Docenti
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.
| Insegnamenti | Crediti | TAF | SSD |
|---|
| Insegnamenti | Crediti | TAF | SSD |
|---|
1° Anno
| Insegnamenti | Crediti | TAF | SSD |
|---|
2° Anno
| Insegnamenti | Crediti | TAF | SSD |
|---|
| 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.
Algoritmi - COMPLESSITÀ (2012/2013)
Codice insegnamento
4S02709
Docente
Crediti
6
Settore Scientifico Disciplinare (SSD)
ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
Lingua di erogazione
Italiano
Periodo
I semestre dal 1-ott-2012 al 31-gen-2013.
Per visualizzare la struttura dell'insegnamento a cui questo modulo appartiene, consultare: organizzazione dell'insegnamento
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.
Prerequisiti raccomandati
-------------------------
Per seguire con profitto l'insegnamento è raccomandato che lo studente abbia già acquisito competenze in:
1. Comuni strutture dati astratte come lista, stack, code, alberi, heap.
2. Rappresentazione di grafi e principali algoritmi sui grafi:
2.1 Visita di grafi: BFS, DFS.
2.2 Ordinamento topologico. Componenti connesse.
2.3 Alberi di copertura di costo minimo. Algoritmi di Kruskal e Prim.
2.4 Cammini minimi da singola sorgente: Algoritmi di Dijkstra e Bellman-Ford.
2.5 Cammini minimi per tutte le coppie: Algoritmi di Floyd-Warshall e Johnson.
2.6 Flusso massimo. Algoritmo di Ford-Fulkerson.
Un testo consigliato per rivedere tali concetti è "Introduction to Algorithms" di T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stein (3 ed.).
Programma
Introduzione
Concetto di modello di calcolo, risorsa computazionale, algoritmo efficiente e problema trattabile.
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 ∈ 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 (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 e 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)^2). 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, 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.
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.
Bibliografia
| Autore | Titolo | Casa editrice | Anno | ISBN | Note |
|---|---|---|---|---|---|
| Christos H. Papadimitriou | Computational complexity | Addison Wesley | 1994 | 0201530821 | |
| S. Arora, B. Barak | Computational Complexity. A modern approach (Edizione 1) | Cambridge University Press | 2009 | 9780521424264 |
Modalità d'esame
L'esame consiste in una prova scritta. Il voto di questo modulo vale 1/2 del voto finale.
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.
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:
i) progettazione e sviluppo di applicazioni o sistemi;
ii) analisi critica di contributi tratti dalla letteratura scientifica;
iii) 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
Gestione carriere
Modalità di frequenza
Come riportato al punto 25 del Regolamento Didattico per l'A.A. 2021/2022, la frequenza al corso di studio non è obbligatoria.Per le modalità di erogazione della didattica, si rimanda alle informazioni in costante aggiornamento dell'Unità di Crisi.
Ulteriori servizi
I servizi e le attività di orientamento sono pensati per fornire alle future matricole gli strumenti e le informazioni che consentano loro di compiere una scelta consapevole del corso di studi universitario.