da alvinlee88 » 25/08/2008, 11:38
Non so se fanno al caso vostro, comunque questi sono quelli che il mio prog di programmazione chiama "esempi di applicazioni nella vita reale" dei problemi quali Indipendent Set e Set Cover.
Indipendent set: "Immaginate di gestire il racket dei lavavetri di una grande città. Il rapporto fra voi e i vostri lavoratori è basato sulla lealtà, e sul fatto che ogni lavoratore si deve sentire unico e indispensabile, poichè li pagate poco (NDRnotate il nonsense, voluto, di tutto questo). Li piazzate sugli incroci dlele città, ma dovete però fare in modo che nesusn lavavetri ne veda un altro, altirmenti si sente meno indispensabile e il rapporto di fiducia crolla. Ma ne volete comunque far lavorare il più possibile, perchè anche se siete uno sfruttatore di persone, avete il cuore tenero. Quindi la vostra città è il grafo, gli incroci i nodi, e compiere questo bel gesto equivale a torvare un indipendent set di dimensione massima nel vostro grafo"
Set Cover (notare i riferimenti politici, era il tempo delle elezioni di alemanno a sindaco di roma): "Supponete di essere il sindaco di una grande città, e di aver appena vinto le elezioni perchè avete puntato tutto sul tema della sicurezza. Ovviamente, i politici mantengono le promesse. Quindi dovete trovare un modo di sorvegliare la città e renderla sicura, usando telecamere. Ma siccome soldi ce ne sono pochi volete mettere il minimo numero di telecamere possibli (le telecamere, in questo esempio, dovrbebero "vedere" in tutte e 4 le direzioni...), e dislocarle negli incroci in modo che si possano vedere anche altri incroci. Il problema è quindi quello di Set Cover".
Il mio prof di Fisica I: "Hubble aveva cannato alla grande"