CALCOLABILITA' E COMPLESSITA'

Salve a tutti ho un quesito da porvi, so che è tardi per questo genere di cose ma uno si accorge dei problemi il giorno prima dell'esame, classico!!

Bene ho una traccia del 22 marzo 2004, esercizio sulla riduzione tra problemi:
si parla di un problema sul CONTROLLO MILITARE
fondamentalmente abbiamo una mappa rappresentata da un grafo, un insieme di militari da piazzare sui nodi in modo tale da "proteggere" tutti gli obbiettivi (rappresentati dai nodi del grafo-mappa). quindi abbiamo un grafo G=(V,E) dove i nodi rappresentano obbiettivi di interesse militare, due interi K=numero di uomini a disposizione e C=numero di uomini impiegati... in più i vertici sono pesati in modo tale da dare più o meno importanza ad un obbiettivo e in più |P|C<=K dove per |P| intende i vertici di G che fanno parte di un cover dominante... infatti si deve utilizzare la riduzione dal problema del COVER DOMINANTE.

Svolgendo l'esercizio mii sono accorto del problema dei pesi sui nodi che sul cover dominante non saprei rappresentare!
Qualcuno mi sa dire qualcosa??
Vi ringrazio in anticipo!

GianMaria ha scritto:

Salve a tutti ho un quesito da porvi, so che è tardi per questo genere di cose ma uno si accorge dei problemi il giorno prima dell'esame, classico!!

Bene ho una traccia del 22 marzo 2004, esercizio sulla riduzione tra problemi:
si parla di un problema sul CONTROLLO MILITARE
fondamentalmente abbiamo una mappa rappresentata da un grafo, un insieme di militari da piazzare sui nodi in modo tale da "proteggere" tutti gli obbiettivi (rappresentati dai nodi del grafo-mappa). quindi abbiamo un grafo G=(V,E) dove i nodi rappresentano obbiettivi di interesse militare, due interi K=numero di uomini a disposizione e C=numero di uomini impiegati... in più i vertici sono pesati in modo tale da dare più o meno importanza ad un obbiettivo e in più |P|C<=K dove per |P| intende i vertici di G che fanno parte di un cover dominante... infatti si deve utilizzare la riduzione dal problema del COVER DOMINANTE.

Svolgendo l'esercizio mii sono accorto del problema dei pesi sui nodi che sul cover dominante non saprei rappresentare!
Qualcuno mi sa dire qualcosa??
Vi ringrazio in anticipo!

Io suppongo che può imporre che i pesi sugli archi siano 1. Se dimostri che è NP-hard il caso in cui il peso è 1, a maggior ragione dovrebbe esserlo il caso generale..

Carmine ha scritto:

Io suppongo che può imporre che i pesi sugli archi siano 1. Se dimostri che è NP-hard il caso in cui il peso è 1, a maggior ragione dovrebbe esserlo il caso generale..

thanks per la dritta... spero mi serva all'esame e non capiti SAT che è una piccola bestemmia!
Tu lo devi fare l'esame o l'hai già fatto?
ci vediamo in aula casomai

Ma no! Carmine è un signor dottore

Ma quando escono i risultati?? qualcuno lo sa?? io ho sentito solo che usciranno su UNIWEX!

Mi hanno detto il 23.. spero di non sbagliare!

Il prof all'esame ha detto che sarebbero usciti entro giovedì sera su Uniwex..
Anche se Malizia era molto poco convinto...

Incrociamo le dita..