Concetti AI Artificial Intelligence

AI – ARTIFICIAL INTELLIGENCE

A.A. 18/19 ~ Piffari Michele

Pre requisiti

Teoria della complessità computazionale

▪ Vedi anche qui.

Si tratta di andare a studiare qual è il numero di risorse di calcolo minime (tempo di calcolo e

memoria) per andare a risolvere un certo problema.

In base a quella che è la complessità e/o l’efficienza dell’algoritmo migliore che riesce a

risolvere una certa classe di problemi, si tende a classificare tali algoritmi in differenti classi di

complessità.

Le classi più “note” sono:

P: nella teoria della complessità computazionale, P, anche conosciuto

o O(1)

come PTIME o DTIME(n ), è una delle più importanti classi di complessità. Contiene

tutti i problemi decisionali che possono essere risolti da una macchina di

Turing deterministica usando una quantità polinomiale di tempo di computazione, o tempo

polinomiale.

NP: la classe di problemi NP comprende tutti quei problemi decisionali che, per trovare

o una soluzione su una macchina di Turing non deterministica, impiegano un tempo

polinomiale. La classe NP prende il suo nome dall'abbreviazione di Nondeterministic

Polynomial Time.

Si tratta quindi di problemi per cui un algoritmo può ipotizzare una soluzione, e poi

può verificare questa ipotesi (verifica la correttezza della soluzione, non è che la

computa) in un tempo polinomiale.

Big-O notation: la notazione matematica O-grande è utilizzata per descrivere

o il comportamento asintotico delle funzioni. Il suo obiettivo è quello di caratterizzare il

comportamento di una funzione per argomenti elevati in modo semplice ma rigoroso, al

fine di poter confrontare il comportamento di più funzioni fra loro. Più precisamente, è

usata per descrivere un limite asintotico superiore per la magnitudine di una funzione

rispetto ad un'altra, che solitamente ha una forma più semplice. Ha due aree principali di

applicazione: in matematica, è solitamente usata per caratterizzare il resto del

troncamento di una serie infinita, in particolare di una serie asintotica, mentre

in informatica risulta utile nell'analisi della complessità degli algoritmi.

La complessità temporale di un algoritmo è espressa comunemente usando la notazione O-

grande, che esclude i coefficienti e i termini di ordine inferiore. Quando è espressa in

questo modo, si dice che la complessità temporale è descritta asintoticamente, ossia,

quando la dimensione degli input va a infinito. Ad esempio, se il tempo richiesto da un

3

algoritmo su tutti gli input di dimensione n è al massimo 5n + 3n, la complessità

3

temporale asintotica è O(n ). Piffari Michele – AI – 18/19 1

Tempo polinomiale

Si dice che un algoritmo è in tempo polinomiale se il suo tempo di esecuzione è limitato

superiormente da un'espressione polinomiale nella dimensione dell'input per l'algoritmo,

k

cioè, T(n) = O(n ) per una qualche costante k.

I problemi per i quali esiste un algoritmo deterministico in tempo polinomiale appartengono

alla classe di complessità P, che è centrale nel campo della teoria della complessità

computazionale. La tesi di Cobham afferma che il tempo polinomiale è un sinonimo per

"trattabile", "fattibile", "efficiente" o "veloce".

Alcuni esempi di algoritmi in tempo polinomiale:

• 2

L'algoritmo di ordinamento quicksort su n interi svolge al massimo operazioni per

2

qualche costante A. Perciò si esegue nel tempo polinomiale ed è un algoritmo in

( )

tempo polinomiale.

• Tutte le operazioni aritmetiche basilari (addizione, sottrazione, moltiplicazione, divisione e

confronto) possono essere fatte in tempo polinomiale.

• Gli accoppiamenti massimi nei grafi si possono trovare in tempo polinomiale.

La notazione O() ci permette di discutere l’efficienza di un particolare algoritmo; l’analisi di

complessità prende invece in considerazione i problemi anziché gli algoritmi.

Piffari Michele – AI – 18/19 2

Pre requisiti ................................................................................................................................. 1

Definizione di Intelligenza Artificiale ............................................................................................ 10

Agire umanamente: il test di Touring (Alan Touring 1956) ........................................................ 10

Pensare umanamente .............................................................................................................. 12

Pensare razionalmente ............................................................................................................ 12

Agire razionalmente (rational agent approach) .......................................................................... 12

Un po' di storia dell’AI (in pillole discorsive) ................................................................................. 12

Agenti intelligenti ....................................................................................................................... 15

Funzione agente ..................................................................................................................... 16

L’aspirapolvere ....................................................................................................................... 16

Agente razionale ..................................................................................................................... 17

Misura di prestazione (performance measure) ........................................................................ 17

Razionalità ......................................................................................................................... 17

Onniscenza ......................................................................................................................... 18

Apprendimento ................................................................................................................... 18

Modellizzazione degli ambienti .................................................................................................... 19

Proprietà degli ambienti .......................................................................................................... 19

Struttura di un agente ................................................................................................................ 20

Programma agente ................................................................................................................. 21

Primo approccio: tabella ...................................................................................................... 21

Agenti reattivi semplici (simple reflex agents) ........................................................................ 21

Agenti reattivi basati su modello (model-based reflex agents) ................................................. 22

Agenti basati su obbiettivi.................................................................................................... 23

Agenti basati sull’utilità ....................................................................................................... 24

Agenti capaci di apprendere ................................................................................................. 24

Ricerca non informata (blind = “cieco” search) ............................................................................. 26

Agenti risolutori di problemi .................................................................................................... 26

Componenti di un problema..................................................................................................... 27

Ricerca soluzioni ..................................................................................................................... 28

State space ........................................................................................................................ 28

State space problem ............................................................................................................ 28

Nodi ................................................................................................................................... 28

Cicli negli alberi di ricerca .................................................................................................... 29

Misurare le prestazioni nella risoluzione di problemi ................................................................ 30

Ricerca in ampiezza (breadth first) .......................................................................................... 31

................................................................................... 32

Ricerca a costo uniforme (A* con h(n) = 0) Piffari Michele – AI – 18/19 3

Ricerca in profondità .............................................................................................................. 34

Ricerca a profondità limitata ................................................................................................... 35

Ricerca ad approfondimento iterativo ....................................................................................... 36

Ricerca bidirezionale ............................................................................................................... 37

Ricerca informata e locale .......................................................................................................... 38

Best first (=”prima [quello che sembra essere] il migliore”) ......................................................... 38

Best first greedy ( =”golosa”, “avida”) ................................................................................... 38

Ricerca A* (A-stella) ........................................................................................................... 39

Considerazione per ottimalità ............................................................................................................. 41

Come scegliere la funzione euristica (tips) ............................................................................. 43

Algoritmi di ricerca locale ........................................................................................................ 46

Ricerca hill-climbing ............................................................................................................ 46

Ricerca Simulated Annealling ............................................................................................... 48

Ricerca local beam .............................................................................................................. 49

Casi particolari ..................................................................................................................................... 49

Algoritmi genetici ................................................................................................................ 50

Ricerca con avversari.................................................................................................................. 51

Formalizzazione di un gioco: ................................................................................................... 51

Max e min ............................................................................................................................. 52

Strategie ottime .................................................................................................................. 52

Algoritmo MINIMAX .............................................................................................................. 53

Potatura alfa-beta (alpha-beta pruning) ................................................................................... 53

Giochi con elementi casuali ..................................................................................................... 55

Esempi di algoritmi per alcuni giochi particolari ......................................................................... 56

Constraint Satisfaction Problem .................................................................................................. 57

Grafo dei vincoli ..................................................................................................................... 57

Varianti del CSP .................................................................................................................... 58

Inferenza nei CSP ................................................................................................................... 58

Consistenza di nodo (node consistency) ................................................................................ 59

Consistenza di arco (arc consistency) ................................................................................... 59

Consistenza di cammino (path consistency) .......................................................................... 60

k-consistenza ...................................................................................................................... 60

Oltre i vincoli ......................................................................................................................... 61

Backtracking search ................................................................................................................... 62

Scelta della variabile ............................................................................................................... 62

MRV .................................................................................................................................. 63

Piffari Michele – AI – 18/19 4

Euristica di grado (DH = Degree Heuristic) ........................................................................... 63

Scegliere il valore .................................................................................................................... 63

LCV (Least Constaint Value) ............................................................................................... 63

Combinazione di ricerca ed inferenza ........................................................................................ 63

Forward checking ................................................................................................................ 63

Backtracking e backjumping ................................................................................................ 64

Agenti logici .............................................................................................................................. 65

Agenti basati sulla conoscenza ................................................................................................. 65

Mondo Wumpus ..................................................................................................................... 67

Logica ................................................................................................................................... 68

Conseguenza logica ............................................................................................................. 68

Model checking ................................................................................................................... 69

Logica proposizionale .............................................................................................................. 70

Sintassi .............................................................................................................................. 70

Semantica (=significato) ...................................................................................................... 70

Inferenza ............................................................................................................................ 71

Equivalenza logica................................................................................................................................ 72

Validità logica ...................................................................................................................................... 72

Soddisfacibilità logica .......................................................................................................................... 72

Regole di inferenza .............................................................................................................. 72

Modus Ponens(=modo che afferma) ................................................................................................... 72

Eliminazione degli and ......................................................................................................................... 73

Esempio di dimostrazione .................................................................................................... 73

Monotonicità ....................................................................................................................................... 73

Risoluzione ......................................................................................................................... 74

Logica del primo ordine .............................................................................................................. 76

Elementi logica del primo ordine .............................................................................................. 76

Termini e atomi ..................................................................................................................... 76

Formule complesse ................................................................................................................. 77

Quantificatore universale ..................................................................................................... 77

Quantificatore esistenziale ................................................................................................... 77

Regole di inferenza ................................................................................................................. 77

Pianificazione ............................................................................................................................ 78

Machine learning ........................................................................................................................ 80

Introduzione ........................................................................................................................... 80

Categorie di problemi di ML ........................................................