[image]https://leganerd.com/wp-content/uploads/LEGANERD_038414.jpg[/image]
[quote]Soluzioni generali ti assicurano il 50% di mancia.[/quote]
Il [url=http://it.wikipedia.org/wiki/Problema_dello_zaino]Problema dello Zaino[/url] (Knapsack Problem) è un problema che riguarda l’ottimizzazione combinatoria (ricerca in un insieme di oggetti di quel sottoinsieme che sia ottimo -migliore- rispetto agli altri sottoinsiemi). La formulazione del PdZ chiede di trovare, dato un insieme di oggetti con dato peso e valore, il sottoinsieme di essi tale che sia massimo il valore complessivo e il peso totale non ecceda il peso sopportabile dallo zaino.
Nella vignetta quindi viene chiesto di trovare il sottoinsieme di antipasti che dia come totale esattamente 15.05 dollari e sia composto da quelli di massimo valore.
Il cameriere si lamenta dicendo che deve servire altri sei clienti ed ecco il nostro amico che conosce gli algoritmi che si offre di fargli conoscere il [url=http://it.wikipedia.org/wiki/Problema_del_commesso_viaggiatore]Problema del Commesso Viaggiatore[/url] (Traveling Salesman Problem).
Dall’ottimizzazione combinatoria passiamo alla teoria dei grafi: il problema, dato un insieme di nodi (i tavoli) e i possibili percorsi fra di essi (gli archi), chiede di determinare il percorso minimo (in questo caso in termini di tempo, che è il peso di ogni percorso) che tocchi tutti i nodi una e una sola volta.
Per giustificare il titolo, questi due problemi si dice siano NP-completi, ovvero -detto in soldoni- essi sono problemi con tutta probabilità non risolvibili in un tempo polinomiale (il tempo di risoluzione è funzione di un polinomio). Una risoluzione formale in tempo polinomiale garantirebbe a chi la svolgesse un incentivo di un milione di dollari, gentilmente offerti dal [url=http://www.claymath.org/millennium/P_vs_NP/]Clay Mathematics Institute[/url].
Per approfondimenti su questo tema consiglio il libro di Keith Devlin “I problemi del millennio”, che dedica un capitolo proprio a questo problema.
Vignetta originale su [url=http://xkcd.com/287/]XKCD[/url].
[more]
Come noterete questa vignetta è in italiano (grazie so leggere).
Sto traducendo alcune vignette di XKCD e cerchero’ di postare quante riuscirò a farne, per quelle per le quali vale approfondire cercherò di spiegare i concetti base usati, come per questa i due problemi di informatica teorica.
Questo è il mio primo post sulla Lega, ringrazio Itomi per la fiducia.
Ho rotolato parecchio vedendo i vari avvertimenti sullo “stile” di un post disseminati sia nella guida che nel blog (Nessuna categoria: ti ammazzo! :rofl: ).
[/more]
