Frame del contenuto
Salta la navigazione con i breadcrumb
Home  freccia Capitolo 8. NP-completezza e approssimazione  freccia Panoramica, animazioni ed esercizi svolti

Panoramica, animazioni ed esercizi svolti

Panoramica del capitolo

In questo capitolo introduciamo il concetto di riduzione polinomiale e quello di problema NP-completo, dimostrando la NP-completezza di alcuni problemi computazionali e fornendo alcuni suggerimenti su come dimostrare un nuovo risultato di NP-completezza. Infine, mostriamo come affrontare la difficoltà computazionale intrinseca di un problema facendo uso di algoritmi polinomiali di approssimazione.

Animazioni

L'animazione che state per guardare è in inglese e lo pseudo-codice in essa incluso è la naturale traduzione in inglese di quello presente nel libro. Pensiamo che ciò possa fornirvi uno spunto per contestualizzare gli argomenti studiati durante il corso nella lingua più frequentemente usata nel mondo del lavoro e della ricerca nell'ambito dell'informatica.

  1. Potete guardare l'animazione Algoritmo per decidere se un grafo connesso è colorabile con due colori relativa al codice 8.1 di pagina 274.
  2. Potete guardare l'animazione Algoritmo per il calcolo di un ricoprimento tramite vertici relativa al codice 8.4 di pagina 297.
  3. Potete guardare l'animazione Algoritmo per il calcolo di un tour approssimato del commesso viaggiatore relativa al codice 8.5 di pagina 301.

Esercizi svolti

  1. Fate clic qui per il download del file PDF con lo svolgimento degli esercizi 8.4, 8.5, 8.7.





Pearson Italia S.p.A. © 2013, tutti i diritti riservati, P.I. 07415430011.
Privacy policy

Torna in cima alla pagina