matematica:asd:asd_17:start
Differenze
Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.
| Entrambe le parti precedenti la revisioneRevisione precedenteProssima revisione | Revisione precedente | ||
| matematica:asd:asd_17:start [08/05/2018 alle 13:26 (7 anni fa)] – [Programma] Roberto Grossi | matematica:asd:asd_17:start [01/05/2019 alle 06:59 (6 anni fa)] (versione attuale) – [Algoritmi e Strutture dei Dati: A.A. 2017-2018] Roberto Grossi | ||
|---|---|---|---|
| Linea 2: | Linea 2: | ||
| Prof. Roberto Grossi\\ | Prof. Roberto Grossi\\ | ||
| - | Luca Versari | + | Dott. Luca Versari |
| {{: | {{: | ||
| Linea 8: | Linea 8: | ||
| ==== Avvisi ==== | ==== Avvisi ==== | ||
| - | * Lezioni | + | * Sono disponibili il [[progetto_17|[progetto]]] e il [[mini_progetto_17|[mini-progetto]]] |
| + | * Importante per consegnare il progetto | ||
| + | * Per chi intende sostenere l' | ||
| * Orario lezioni: mar 11-13, mer 14-16, ven 14-16. | * Orario lezioni: mar 11-13, mer 14-16, ven 14-16. | ||
| - | * Per il ricevimento, | ||
| - | * Per chi intende sostenere l' | ||
| - | * Mesi consigliati per consegnare il progetto e completare l' | ||
| * [[https:// | * [[https:// | ||
| * [[http:// | * [[http:// | ||
| Linea 45: | Linea 44: | ||
| * Parte prima, a scelta una delle seguenti possibilità: | * Parte prima, a scelta una delle seguenti possibilità: | ||
| * [[progetto_17|[progetto]]] con sviluppo di nuovi algoritmi e relativa implementazione, | * [[progetto_17|[progetto]]] con sviluppo di nuovi algoritmi e relativa implementazione, | ||
| - | * scritto con esercizi da svolgere, avente una votazione in trentesimi, più un [[mini_progetto16|[mini-progetto]]] con votazione booleana (prova superata o meno per valutare le capacità programmative); | + | * scritto con esercizi da svolgere, avente una votazione in trentesimi, più un [[mini_progetto_17|[mini-progetto]]] con votazione booleana (prova superata o meno per valutare le capacità programmative); |
| - | * seminario basato su un argomento di ricerca nel campo dell' | + | * seminario basato su un argomento di ricerca nel campo dell' |
| * Parte seconda, comune per tutti: verifica tramite l' | * Parte seconda, comune per tutti: verifica tramite l' | ||
| Linea 92: | Linea 91: | ||
| |04.05.2018| Classi di complessità P e NP: esempio dei cicli euleriani e hamiltoniani (HAM) nei grafi, colorazione di mappe (grafi) planari. Nozione di certificato polinomiale. Definizione della classe NP. Riduzione polinomiale. Esempio da HAM a commesso viaggiatore (TSP). | [CGGR, par. 8.1-8.3] [[http:// | |04.05.2018| Classi di complessità P e NP: esempio dei cicli euleriani e hamiltoniani (HAM) nei grafi, colorazione di mappe (grafi) planari. Nozione di certificato polinomiale. Definizione della classe NP. Riduzione polinomiale. Esempio da HAM a commesso viaggiatore (TSP). | [CGGR, par. 8.1-8.3] [[http:// | ||
| |08.05.2018| Relazione tra certificato polinomiale e non-determinismo polinomiale. Proprietà della riduzione polinomiale e definizione della classe NPC (problemi NP-completi). Problema della soddisfacibilità (SAT) e Teorema di Cook-Levin. Riduzione da 3-colorazione di mappe (3-COL) a SAT. | [CGGR, par. 8.4-8.6]| | |08.05.2018| Relazione tra certificato polinomiale e non-determinismo polinomiale. Proprietà della riduzione polinomiale e definizione della classe NPC (problemi NP-completi). Problema della soddisfacibilità (SAT) e Teorema di Cook-Levin. Riduzione da 3-colorazione di mappe (3-COL) a SAT. | [CGGR, par. 8.4-8.6]| | ||
| - | |11.05.2018| | + | |11.05.2018| Riduzioni a la Karp: da SAT a soddisfacibilità con clausole a 3 letterali (3-SAT), da vertex cover (VC) a 3-SAT, da independent set (IS) a VC, da hitting set (HS) a VC. Algoritmi di r-approssimazione.| [CGGR, par. 8.8-8.9] | |
| - | |15.05.2018| 2-approssimazione per min VC. Inapprossimabilità di TSP nel caso generale e sua 2-approssimazione per istanze metriche. | [CGGR, par. 8.10-8.11] | + | |15.05.2018| 2-approssimazione per min VC e max SAT. Inapprossimabilità di TSP nel caso generale e sua 2-approssimazione per istanze metriche. | [CGGR, par. 8.10-8.11] |
| - | |18.05.2018| | + | |18.05.2018| |
| - | + | |23.05.2018| Esercitazione: grafi e discussione progetto | [[http:// | |
matematica/asd/asd_17/start.1525785962.txt.gz · Ultima modifica: 08/05/2018 alle 13:26 (7 anni fa) da Roberto Grossi