Corso di Complessità

Laurea Magistrale in Logica computazionale

Anno accademico: 2011-2012

Stato: Il corso non e' attivo nell'A.A. corrente

Codice: I8066 - S8806

Settore Scientifico Disciplinare (SSD):

Numero di ore: 26 (in aula)
Numero di CFU (Crediti Formativi Universitari): 3

Moduli:

Compl (DE' LIGUORO Ugo)

Anno di Corso:	4/5
Periodo/i didattico/i in cui si svolge:	0 (dal -- al --)

Note: mutuato da modulo di AlgCompl

INDICE

1. Obiettivi del corso
2. Competenze attese e propedeuticità
3. Come si svolgono le lezioni (supporti alla didattica in uso alla docenza)
4. Programma/contenuti
5. Materiale didattico di supporto (a cura del docente)
6. Bibliografia (libri, articoli, documenti on-line, software,...)
7. Controllo dell'apprendimento (durante il corso)
8. Verifica (modalità d'esame)
9. Commissione d'esame

1. Obiettivi del corso

Il corso è finalizzato alla introduzione alla teoria della complessità computazionale, intesa come complessità strutturale ovvero teoria delle classi di complessità.

2. Competenze attese e propedeuticità

• Competenze attese in ingresso (richieste all'inizio del corso).

  Conoscenza degli algoritmi e della complessità concreta, calcolo proposizionale e dei predicati, modelli di calcolo, decidibilità.

• Eventuali corsi propedeutici (forniscono le "competenze attese in ingresso").

  Algoritmi, Logica, Calcolabilità.

• Competenze attese in uscita (acquisite durante il corso).

  Acquisizione delle nozioni rigorose di misura e classe di complessità; conoscenza delle principali classi e delle loro relazione di inclusione, nonché delle tecniche più importanti utilizzate per lo studio di tali inclusioni.

3. Come si svolgono le lezioni (supporti alla didattica in uso alla docenza) e modalità di frequenza

Le lezioni si svolgono in aula con mezzi tradizionali, ma si avvale di un corso sul sistema Moodle (istanza i-learn, titolo "Teoria della Complessità", sigla Compl) per distribuire il materiale didattico (lucidi, dispense appunti ed altro), nonché per le discussioni e gli avvisi.

4. Programma/contenuti

• In Italiano.
  1. Problemi e algoritmi
  2. Modelli di calcolo e misure di complessità
  3. Classi di complessità temporali e spaziali
  4. Riduzioni e completezza
  5. Problemi NP-completi
  6. P versus NP
  7. Comlpessità spaziale
  8. La gerarchia polinomiale
  9. Intrattabilita'
  
  
• In English.
  

5. Materiale didattico di supporto (a cura del docente)

Col procedere del corso, sul sistema Moodle saranno disponibili contenuti e riferimenti bibliografici per ciascuna lezione, nonché indicazione di esercizi rilevanti in relazione agli argomenti trattati.

6. Bibliografia (libri, articoli, documenti on-line, software,...)

1. C. Toffalori, F Corradini, S. Leonesi, S. Mancini, Teoria della computabilità e della complessità, McGrow-Hill, 2005.
2. M. Sipser, Introduction to the theory of computation, Snd Edition, Thomson, 2005.
3. C. H. Papadimitriou, Computational Complexity, Addison-Wesley 1994.

7. Controllo dell'apprendimento (durante il corso)

Il controllo dell'apprendimento è basato sulle domande che gli studenti fanno durante le ore di lezione e durante i ricevimenti, nonché sulla correzione di svolgimenti di esercizi attraverso il sistema Moodle.

8. Verifica (modalità d'esame)

L'esame consiste in una prova orale.

9. Commissione d'esame

BERARDI, Stefano
DAMIANI, Ferruccio
DE' LIGUORO, Ugo
ZACCHI, Maddalena

Appelli correntemente aperti: