Newsgroup: it.comp.ia
Titolo: Libro sulla NP-completezza

Voglio segnalare al gruppo il seguente libro sulla teoria della
NP-Completezza:
COMPUTERS AND INTRACTABILITY
A Guide to the Theory of NP-Completeness
Michael R. Garey / David S. Johnson
Bell Laboratories
W. H. FREEMAN AND COMPANY
41 Madison Avenue, New York, N.Y. 10010
ISBN 0-7167-1045-5
E' un libro piuttosto vecchio (1979) ma a mio avviso un "must" per chiunque
si occupi di Intelligenza Artificiale e di progettazione e sviluppo di
algoritmi in generale. Non so se esista la traduzione in italiano, ma se
conoscete un poco di inglese scientifico non dovreste avere grossi problemi
a comprendere questo testo.
Vi riporto un breve estratto del capitolo 1.1 tagliato e cucito per renderlo
breve che è veramente esilarante e illuminante al tempo stesso. La
traduzione è mia, quindi scusate se non è del tutto fedele.
Un giorno il vostro capo vi chiama nel suo ufficio e vi confida che la ditta
sta per entrare nel nuovo mercato molto competitivo delle cerniere a
strappo. Per questo motivo è necessario un buon metodo per determinare se
dato un insieme di specifiche per un nuovo componente possa essere
soddisfatto e, nel caso, costruire un profilo che le soddisfi. Poiché voi
siete il direttore aziendale per lo sviluppo degli algoritmi, il vostro
compito è trovare un algoritmo efficiente per fare ciò.
...dopo una marea di lavoro senza essere approdati a niente...
Finora non siete approdati a niente di meglio di un algoritmo che valuti
tutti i possibili profili. Questo non renderà felice il vostro boss, poiché
ci vorranno anni di tempo di calcolo per un solo insieme di specifiche.
Certamente non vorrete andare dal vostro capo e dirgli: "Non riesco a
trovare un algoritmo efficiente, credo di essere troppo scemo".
Per evitare un danno serio alla vostra posizione nella compagnia, sarebbe
meglio se poteste provare che il problema è intrinsecamente intrattabile,
che nessun algoritmo lo può risolvere velocemente. Potreste allora andare
dal vostro capo e dirgli: "Non riesco a trovare un algoritmo efficiente
perché un tale algoritmo non esiste!".
Sfortunatamente, provare l'intrinseca intrattabilità può risultare
altrettanto difficoltoso che trovare un algoritmo efficiente....
La teoria della NP-Completezza mette a disposizione molte tecniche per
provare che un dato problema è "altrettanto difficile" di un grande numero
di altri problemi che sono largamente riconosciuti essere difficili e che
hanno confuso gli esperti per anni. Armati con queste tecniche potete
dimostrare che il problema delle chiusure a strappo è NP-completo e che è
equivalente a tutti quegli altri problemi difficili.
Per lo meno il vostro boss capirà che non serve a nulla licenziarvi per
assumere un altro esperto di algoritmi.
Una delle parti che ho trovato più utile è l'appendice che elenca tutta una
serie di problemi NP-Completi forniti di una breve spiegazione e di
referenze per approfondire, molto utile se il vostro problema è riducibile
ad una di quelle forme e volete fare una ricerca bibliografica per sapere se
qualcuno ha risolto dei casi particolari.
Poiché ho visto che questo gruppo è frequentato da molti sviluppatori di
chatterbot e personalità virtuali, potrebbero essere interessati ai problemi
di Storage and Retrieval, Compression and representation, database problems,
Logic e soprattutto Automata and Language Theory.
Sperando di aver fatto cosa gradita, vi saluto.
Max Manfrin

 A Guide to the Theory of NP-Completeness
<domanda da provinciale>
Non e' che c'e' anche in italiano. No, eh?
</domanda>
-- 
Inviato il mer 19 set 2001 21:20:24 CEST da 
fw01-e31.inferentia.net
[217.29.160.1]
http://www.neuromante.net/

</domanda>
Il Garey-Johnson in italiano.. questa la vorrei vedere. :-)
-- 
Life's something u don't get out alive..
ObjectZone - 
http://space.tin.it/computer/csadun

 si occupi di Intelligenza Artificiale e di progettazione e sviluppo di
Cribbio.. se vuoi fare roba seria è da quasi da buttare! :)
Da allora ci sono stati sviluppi pazzenschi nel campo!
bye!

 Da allora ci sono stati sviluppi pazzenschi nel campo!
Fai un commento costruttivo e indica qualcosa di piů indicato, altrimenti
non serve a niente dire che č roba vecchia e c'č di meglio ;)
Ciao
Max Manfrin

> Da allora ci sono stati sviluppi pazzenschi nel campo!
Si', ma i problemi NP-Completi restano NP-Completi. Anche perche', essendo
tutti sostanzialmente equivalenti, un eventuale risolutore di uno sarebbe
utilizzabile (probabilmente) per tutti gli altri.
Stefano