Metodi per la risoluzione dei problemi nella intelligenza artificiale

Nils J. Nilsson

Metodi per la risoluzione dei problemi nella intelligenza artificiale

Printed Edition

41.50

Pages: 292

ISBN: 9788820424596

Edition: 5a edizione 1988

Publisher code: 700.5

Availability: Discreta

L'intelligenza artificiale può essere riguardata come quella branca della scienza' che studia come programmare i calcolatori per risolvere i tipi di problemi che comunemente si pensa richiedano della «intelligenza,,. Tra questi problemi si possono ricordare la dimostrazione di teoremi matematici, lo svolgimento di partite in vari giochi (dama, scacchi, bridge, ecc,), l'analisi delle immagini e l'interpretazione del linguaggio.

In questo volume sono descritte alcune importanti strategie generali, basate sull'idea della «ricerca» e utilizzabili nella soluzione di problemi del tipo sopra indicato. Un problema viene risolto ricercandone la soluzione in un ampio spazio dì possibili soluzioni.

E metodi che usano questa strategia darebbero raramente buoni risultati se la ricerca procedesse semplicemente per tentativi. Essi invece guidano euristicamente la ricerca verso quel. le parti dello spazio delle soluzioni in cui è più probabile trovarne. Questo volume illustra più precisamente i metodi di soluzione dei problemi (per mezzo della «ricerca») che sono stati sviluppati nel settore dell'intelligenza artificiale. Tali metodi sono illustrati attraverso l'applicazione a diversi semplici problemi e la loro significatività viene evidenziata dall'indicazione del problemi molto più complessi risolti per mezzo di essi. Nell'opera sono presenti inoltre tre capitoli che trattano della dimostrazione di teoremi nel calcolo dei predicati e della sua utilizzazione nella soluzione di problemi. li presente volume costituisce un testo introduttivo per allievi del secondo biennio del corso di laurea in matematica o in fisica e per allievi del 4 - 5 anno del corso di laurea in ingegneria. Esso può essere usato anche per lo studio autonomo, grazie ai numerosi riferimenti bibliografici e al ben articolati esercizi alla fine di ogni capitolo. Il livello della presentazione non richiede particolari prerequisiti; la lettura del testo sarà comunque particolarmente facile per un lettore avente familiarità con il vocabolario della matematica combinatoria e della logica.

N.J. Nilsson ha compiuto gli studi di ingegneria presso la Stanford University (Usa), dove ha conseguito il dottorato nel 1958. A partire da tale data ha svolto attività di ricerca sulla ricezione di segnali radar, sul riconoscimento di configurazioni e sull'intelligenza artificiale. Parallelamente ha tenuto corsi presso la University of California, Berkeley, e presso la Stanford University. Attualmente fa parte dell'Artificial Intelligence Group presso lo Stanford Research lnstitute. E' autore di diversi articoli e di un volume sulle «macchine che apprendono».

Presentazione all'edizione italiana, di Marco Somalvico
Prefazione, di Nils J. Nilsson
1. Introduzione
1.1. Risoluzione di problemi e intelligenza artificiale
1.2. Rompicapo e giochi come esempi di problemi
1.3. Stati e operatori del problema
1.4. Riduzione di problemi a sottoproblemi
1.5. L'uso della logica nella risoluzione di problemi
1.6. Due elementi della risoluzione di problemi: la rappresentazione e la ricerca
1.7. Note bibliografiche e storiche
1.7.1. L"'intelligenza" dei calcolatori
1.7.2. Panoramiche dell'intelligenza artificiale
1.7.3. Modi di affrontare l'intelligenza artificiale
1.7.4. Metodi per la risoluzione di problemi
1.7.5. Applicazioni dei programmi per la risoluzione di problemi
1.7.6. Fonti importanti per l'intelligenza artificiale
1.8. Problemi
Bibliografia
2. Rappresentazione nello spazio degli stati
2.1. Descrizioni degli stati
2.2. Operatori
2.3. Stati finali
2.4. Terminologia per i grafi
2.5. Rappresentazione dello spazio degli stati mediante programmi non deterministici
2.6. Alcuni esempi di rappresentazioni di problemi
2.6.1. Il problema del commesso viaggiatore
2.6.2. Problemi di analisi sintattica
2.6.3. Problemi di distribuzione
2.6.4. Problemi di controllo
2.7. La scelta di una "buona" rappresentazione
2.8. Note bibliografiche e storiche
2.8.1. Gli elementi di una rappresentazione nello spazio degli stati
2.8.2. I programmi non deterministici
2.8.3. Letteratura fondamentale sui problemi degli esempi
2.8.4. Il problema di trovare una buona rappresentazione
2.9. Problemi
Bibliografia
3. Metodi di ricerca nello spazio degli stati
3.1. Processi di ricerca nei grati
3.2. Metodi di ricerca in ampiezza
3.3. Un metodo di ricerca in profondità
3.4. Modifiche richieste dalla ricerca nei grafi
3.5. Discussione della conoscenza euristica
3.6. L'uso delle funzioni di valutazione
3.7. Un algoritmo ottimo di ricerca
3.8. L'ammissibilità di A
3.9. L'ottimalità di A *
3.10. Il potere euristico di
3.11. L'importanza di g
3.11.1. L'argomento intuitivo contro l'inclusione di
3.11.2. L'argomento intuitivo a favore dell'inclusione di
3.12. L'uso di differenti euristiche
3.12.1. La ricerca a stadi
3.12.2. Limitazione dei successori
3.12.3. Generazione di un successore alla volta
3.13. Misure di prestazione
3.14. Note bibliografiche e storiche
3.14. 1. Algoritmi perla ricerca del cammino più breve
3.14.2. Tecniche di ricerca euristica
3.14.3. Misure di prestazione
3.15. Problemi
Bibliografia
4. Rappresentazione per la riduzione a sottoproblemi
4.1. Un esempio
4.2. Descrizioni di problema
4.3. Operatori di riduzione a sottoproblemi
4.4. Descrizione dei problemi primitivi
4.5. I grafi AND/OR
4.6. Rappresentazione di grafi AND/OR mediante programmi non deterministici
4.7. Esempi di rappresentazioni per la riduzione a sottoproblemi
4.7.1. Il problema dell'integrazione simbolica
4.7.2. Dimostrazione di teoremi di geometria piana
4.8. Meccanismi di pianificazione nella riduzione a sottoproblemi
4.9. Gli operatori chiave
4.10. Le differenze
4.11. Spazi degli stati a livello superiore
4.12. Giochi
4.13. Note bibliografiche e storiche
4.13.1. Metodi di riduzione a sottoproblemi e grafi AND/OR
4.13.2. Esempi di programmi che usano il metodo di riduzione a sottoproblemi
4.13.3. giochi e il metodo di riduzione a sottoproblemi
4.14. Problemi
Bibliografia
5. Metodi di ricerca per la riduzione a sottoproblemi
5.1. Processi di ricerca sui grati AND/OR
5.2. Ricerca in ampiezza
5.3. Ricerca in profondità
5.4. Ricerca sui grafi AND/OR
5.5. Costi degli alberi risolutivi
5.6. L'uso di stime di costo per dirigere la ricerca
5.7. Un algoritmo di ricerca ordinata per gli alberi AND/OR
5.8. Ammissibilità dell'algoritmo di ricerca ordinata
5.9. La scelta del nodo da espandere in • Ø
5.10. Modifiche
5.11. La procedura del minimassimo per la ricerca sugli alberi di gioco
5.12. La procedura alfa-beta
5.13. L'efficienza di ricerca della procedura alfa-beta
5.14. Procedure alfa-beta e di ordinamento combinate
5.14.1. Ordinamento fisso
5.14.2. Ordinamento dinamico
5.15. Possibili miglioramenti dei metodi basati sul minimassimo
5.16. Note storiche e bibliografiche
5.16.1. Sviluppo delle tecniche di ricerca per i grafi AND/OR
5.16.2. Sviluppo delle tecniche di ricerca per gli alberi di gioco
5.16.3. Alcuni programmi di gioco di particolare interesse
5.17. Problemi
Bibliografia
6. Dimostrazione di teoremi nel calcolo dei predicati
6.1. Il calcolo dei predicati come linguaggio per la risoluzione di problemi
6.2. La sintassi
6.3. La semantica
6.4. Variabili e quantificatori
6.5. Validità e soddisfacibilità
6.6. La forma a clausole
6.7. L'universo di Herbrand
6.8. La base di Herbrand
6.9. La costruzione dell'albero semantico
6.10. I nodi di fallimento
6.11. I nodi d'inferenza
6.12. L'unificazione
6.13. I risolventi
6.14. Il principio di risoluzione
6.15. Correttezza e completezza della risoluzione
6.16. Note bibliografiche e storiche
6.16.1. Fondamenti di logica
6.16.2. La procedura di prova di Herbrand e la risoluzione
6.17. Problemi
Bibliografia
7. Applicazione del calcolo dei predicati alla risoluzione di problemi
7.1. Il calcolo dei predicati nella risoluzione di problemi
7.2. Un esempio
7.3. Il processo di estrazione della risposta
7.4. Congettura con variabili universalmente quantificare
7.5. Un esempio di programmazione automatica
7.6. L'uso del calcolo dei predicati per la risoluzione di problemi nello spazio degli stati
7.7. Una formalizzazione per la risoluzione di problemi nello spazio degli stati
7.8. Note bibliografiche e storiche
7.8.1. Sistemi a domanda e risposta (question-answering Systems)
7.8.2. Processi per l'estrazione della risposta
7.8.3. Applicazione del calcolo dei predicati alla risoluzione di problemi nello spazio degli stati
7.8.4. Dimostrazione di teoremi matematici
7.9. Problemi
Bibliografia
8. Metodi per la costruzione delle dimostrazioni nel calcolo dei predicati
8.1. Strategie di ricerca
8.2. Le strategie di semplificazione
8.2.1. Eliminazione delle tautologie
8.2.2. Eliminazione mediante valutazione di predicati
8.2.3. Eliminazione per sussunzione
8.3. Le strategie di raffinamento
8.4. Dimostrazioni con vincolo di discendenza
8.5. La strategia dell'insieme di supporto
8.6. Strategie più restrittive
8.7. Strategie basate su modelli
8.8. Le reputazioni P,
8.9. Strategie combinate
8.10. Le strategie di ordinamento
8.11. Note bibliografiche e storiche
8.11.1. Discussione delle strategie di ricerca
8.11.2. Strategie di semplificazione
8.11.3. Strategie di raffinamento
8.11.4. Strategie di ordinamento
8.11.5. Esempi di realizzazione
8.12. Problemi
Bibliografia
Bibliografia generale


Contributors: M. Colombetti, M. Somalvico

Serie: Informatica

Level: Textbooks - Books for Professionals