Topic outline

  • General

    Collapse all Expand all

  • Libri di testo

    • D. Mundici "Dalla macchina di Turing a P/NP" Mc Graw Hill (2013): è il libro di testo principale del corso.
    • M. Garey, D. Johnson "Computers and intractability" (1979): contiene moltissimi esempi di problemi NP-completi.
    • Consigliate anche le dispense P. Crescenzi: le trovate  suo sito. E' un libro per informatici, per cui presenta molto più materiale di quanto vediamo al corso.
    • Per chi volesse approfondire le Zero-Knowledge Proofs: Goldreich, O. "Foundations of Cryptography". 

  • Possibili seminari

    Gli studenti hanno la possibilità di presentare degli argomenti in classe.

    Tra i possibili argomenti, ci sono altri modelli di computazione (oltre a quelli già visti in classe).

    In particolare, al cap. 4 delle dispense di P. Crescenzi vengono presentati tre modelli di computazione (ma altre proposte sono le benvenute):

    • Algoritmi di Markov 
    • Macchine di Post 
    • Macchine RAM


    Più avanti, quando saranno presentati la classe NP ed i problemi NP-completi, ci saranno possibili proposte di seminari su esempi di problemi NP-completi (ma altre proposte, ad es. dal libro di Garey & Johnson, sono le benvenute).

  • Possibili seminari su problemi NP completi

    Ecco una lista molto incompleta di possibili problemi NP-completi da presentare come seminario (di durata tra 30 minuti ed 1 ora):

    I seguenti sono sul libro di Mundici:

    • KNAPSACK
    • COLORABILITY
    • DSTP  (commesso viaggiatore)
    • CLIQUE e INDEPENDENT SET

    I seguenti sono sul libro di Garey & Johnson:

    • 3 DIMENSIONAL MATCHING
    • VERTEX COVER
    • HAMILTON CIRCUIT e HAMILTON PATH
    • PARTITION

    Altri problemi interessanti (accennati sul libro di Garey-Johnson: do il riferimento su come trovarli nell'appendice):

    • DOMINATING SET (A1.1-GT2 p.190)
    • ACHROMATIC NUMBER (A1.1-GT5 p.190)
    • MINIMUM MAXIMAL MATCHING (A1.1-GT10 p.192)
    • PARTITIONS OF GRAPHS: (A1.1-GT11, GT12, GT13, GT14, GT15, GT16)
    • INDUCED SUBGRAPH WITH PROPERTY PI (A1.1-GT21)
    • SPANNING TREES (A2.1 p. 206: varie varianti)
    • ROUTING PROBLEMS (A2.3: varie varianti, incluso TRAVELING SALESMAN): in particolare, LONGEST CIRCUIT/PATH (ND28, ND29) 
    • etc. etc. etc.

    I seguenti sono su articolo

    • QUADRATIC CONGRUENCE (descritti in A7.2.AN1 e A7.2.AN8 su Garey & Johnson)

    Inoltre,
    • PRIME è in P, 
    • GRAPH ISOMORPHISM (accennato in A1.4-GT48) ancora non si sa.

  • Programma in breve

    1. Parte A e Parte B del libro di Mundici (niente crittografia)
    2. Approfondimenti sulla calcolabilità/ricorsione: funzioni e insiemi ricorsivi, equivalenza tra funzioni ricorsive e funzioni Turing-calcolabili (Tesi di Church-Turing), Teorema di Post
    3. Esempi di problemi NP-completi: HAMILTONIAN CIRCUIT, 3 DIMENSIONAL MATCHING, VERTEX COVER

    Argomenti extra (cenni): le classi BPP, RP, EXP-Time, P-Space. Zero Knowledge Proofs (esempio: GRAPHS ISOMORPHISM)