Prima Provetta: dimostrazioni di NP-complessità

La provettà vi impegna a scrivere delle vostre dimostrazioni di NP-complessità. Nell'ottenere e nel descrivere tali riduzioni vi è richiesto di seguire le indicazioni del docente, senza risparmio in impegno. Il file deve essere in LaTex, ed in generale dovete fornire tutti i sorgenti (in formato non proprietario) del vostro lavoro.

Ma date un'occhiata alle prime provette pervenute per farvi un'idea ed assimilare uno standard comune. In particolare, il file .tar.gz fornito da Zanolli contiene un makefile, il che mi sembra conveniente.

Prima di partire con un argomento, dovete consultarvi ed accordarvi con me. Solo in questo modo potrete essere sicuri che un argomento vi sia stato affidato e sapere cosa sia effettivamente richiesto nel percorso di studio. (Cosa peraltro da decidere assieme, e con ampio margine di trattativa).

Quanto da voi fatto riceve due misurazioni:

  • la qualità è misurata in 30-esimi;
  • la mole è misurata in 100-esimi; La qualità esprime un voto che va a fare media per quello che sarà l'esame finale.
    La massa mi dice quanto io abbia già abusato di voi, e quindi il peso che io debba dare al voto espresso dalla qualità si dovesse arrivare al fare una media.

    Problema Descrizione Breve Studente (e-mail) browse/download qualità mole
    NC, CQ, IS, SUB-GRAPH ISO, 3SAT L'equivalenza polinomiale tra i seguenti problemi: node cover, independent set, clique, subgraph isomorphism, 3SAT, SAT. Paolo Larcheri
    plarcher(chiocciola)kirk(punto)science(punto)unitn(punto)it    		 Documento PDF Archivio_Sorgenti 30 90
    Steiner-tree NP-completezza del problema dello Steiner tree di cardinalità minima. Alessandro Santuari
    santuari(chiocciola)kirk(punto)science(punto)unitn(punto)it    		 Documento PDF Archivio_Sorgenti 30 45
    Dominating Set (DS) NP-completezza del problema del Dominating Set di cardinalità minima. Michele Zanolli
    3qn(chiocciola)kirk(punto)science(punto)unitn(punto)it    		 Documento PDF Archivio_Sorgenti 30 45
    Feedback Vertex Set (FVS) e Feedback Arc Set (FAS) NP-completezza del trovare Feedback Vertex Sets o Feedback Arc Sets di cardinalità minima. Edoardo Di Lorenzo
    edo.anna(chiocciola)tin(punto)it    		 Documento PDF Archivio_Sorgenti 30 60
    Dominating Set e Independent Set nel piano (DS + planarIS) NP-completezza del problema del Dominating Set di cardinalità minima e dell'Independent Set per grafi planari. Marco Stenico
    marcostenico(chiocciola)hotmail(punto)com    		 Documento PDF Archivio_Sorgenti 30 90
    3-Dimensional Matching (3DM) NP-completezza del problema del 3-Dimensional Matching. Lorenzo Vaccari
    vaccari(chiocciola)inwind(punto)it    		 Documento PDF Archivio_Sorgenti 30 70
    Partition into Triangles (PT) NP-completezza del problema di partizionare i nodi di un grafo in tiplette disgiunte, con ciascuna tripletta che induca un triangolo. Mirko Morandini
    mormir(chiocciola)dnet(punto)it    		 Documento PDF Archivio_Sorgenti 30 50

    created:   3 maggio 2003
    updated:   6 settembre 2004     		© Department of Computer Science
    University of Verona