1. [I]nfo
  2. [M]oduli
  3. [B]acheca
  4. [P]rogramma
  5. [O]rari
  6. [E]sami
  7. E[v]enti
  8. [F]iles

Generali:

  • Dipartimento: Scienze Matematiche, Fisiche E Naturali
  • Settore Ministeriale: INF/01
  • Codice di verbalizzazione: 8060884
  • Metodi di insegnamento: Frontale
  • Metodi di valutazione: Scritto E Orale
  • Prerequisiti: Algoritmi e strutture dati
  • Obiettivi: Obiettivi: Sviluppo di capacita' critiche nell'analisi di problemi e loro soluzioni, nonche' capacita' di sviluppare autonome metodologie di soluzione di problemi. PROGRAMMA. 1) Calcolabilita'. Concetti preliminari: Cardinalità di insiemi, Insiemi numerabili e non numerabili, Diagonalizzazione, Macchine di Turing: Definizioni ed esempi, Macchine ad un nastro e a k nastri, Macchine di Turing deterministiche e non deterministiche e loro equivalenza, Macchina di Turing universale, Macchine di Turing con oracolo. Linguaggi e funzioni: Linguaggi e linguaggi complemento, Accettabilità e decidibilità di linguaggi, Calcolabilità di funzioni, Tesi di Church-Turing, Linguaggi non decidibili, Riducibilità tra linguaggi. 2) Complessità. Problemi e codifiche: Problemi decisionali, Problemi complementari, Problemi di ottimizzazione. Misure di complessità: Misure statiche e dinamiche, Assiomi di Blum, DTIME, DSPACE, NTIME, NSPACE. Classi di linguaggi: Inclusione, Completezza, Funzioni time-constructible, Definizione delle classi di complessità spaziale e temporale, Teorema di accelerazione. Classi di complessità temporale: classi complemento, chiusura rispetto a variazioni finite. La classe P: Definizione, Riducibilità polinomiale e chiusura di P rispetto alla riducibilità polinomiale, Esempi di problemi in P (2-SAT, 2-COLORABILITA'), Funzioni in FP, Trasformazione di una funzione booleana in forma congiuntiva normale. La classe NP: Definizione, Linguaggi NP-completi e Teorema di Cook, Chiusura rispetto alla riduzione polinomiale, Esempi di dimostrazioni di NP-completezza (3-SAT, Vertex Cover, 3-COLORABILITA', COLORABILITA', Independent Set, Clique, Hamiltonian Circuit/Path, Longest Path, Commesso Viaggiatore). Algoritmi pseudo-polinomiali, problemi numerici e NP-completezza in senso forte: il problema Knapsack. Oltre NP: La classe coNP, Definizione della gerarchia polinomiale, Complessità esponenziale: classi LEXP e PEXP (definizione). Problemi di ottimizzazione: Le classi PO e NPO, Linguaggi soggiacenti, La questione "PO = NPO?", La classe APX, Appartenenza ad APX di min-Vertex Cover, non Appartenenza ad AXP di min-TSP (se P diverso da NP), Appartenenza ad AXP di min-TSP con disuguaglianza triangolare e algoritmo di Christofiedes.

Didattica:

  • A.A.: 2012/2013
  • Canale: UNICO
  • Crediti: 6
2021 © Università di TorVergata  |  FAQ  |  Contatta la Redazione  |