---
# System prepended metadata

title: Appunti KEAI Live

---

kickoff beniamino

## Lezione 1 - 24/9/2024

Primo argomento Problem Solving mediante Ricerca in spazi degli stati. 

4 video introduttivi. 

L'AI nasce da turing!. 

Gran parte dei problemi di Intelligenza Artificiale hanno la ricerca come componente fondamentale.
I problemi si possono modellare come Problemi di  Ricerca in uno
spazio degli stati (Strategie di Ricerca).
* Lo spazio degli stati è l’insieme di tutti gli stati raggiungibili dallo stato iniziale con una qualunque sequenza di operatori.

Altri sistemi invece vedremo sono basati sulla logica. 
Si cerca un modo per formulare un problema con un insieme di simboli. 
A partire dalle formalizzazioni matematiche nascono i sistemi esperti. 

Finche McCulloch-Pitts non introdussero il percettrone e nacquero le reti neurali. 
Studieremo un linguaggio non imperativo ma logico che è prologo, e anche un linguaggio wsdl che realizza tali regole. 

## Space State Search

Partiamo con lo studio di una serie di problemi che possono essere formati come problemi di ricerca: 
- scrivere un programma di scacchi
- schedulazione dei voli di un aereoporto
- costruire un sistema per il riconoscimento facciale. 
La ricerca nello spazio degli stati si rappresenta come un albero di ricerca almeno concettualmente, fisicamente è un pò intrattabile computazionalmente perchè l'albero potrebbe esplodere. 

Il problema più noto è il problema dei ponti della città di konigsberg (eulero): si riesce a trovare un itinerario che tocchi le due isole che si trovano sul fiume e le rive del fiume, passando per i ponti una sola volta. Per risolvere questo problema, Eulero si inventò la teoria dei grafi, bisognava trovare un cammino attorno alla città e che attraversa i ponti una sola volta. 
Questo problema si modella attraverso un grafo, quindi un insieme di stati e un insieme di transizioni, che possiamo rappresentare visivamente con un grafo. 
![image](https://hackmd.io/_uploads/H1gAa-xC0.png)
le i1,i2 sono le isole, bi sono i ponti. 
Sicuramente è un problema di attraversamento del grafo. La soluzione del problema è un percorso nel grafo che parte da una radice. Un percorso di un grafo è una lista di nodi se gli archi non sono etichettati (coppie nodo1 e nodo2), se sono etichettati ci vuole anche l'etichetta dell'arco (tripla). 
Ci serve il percorso che nella lista ha tutti i nodi e una sola volta tutti gli archi. 
Dobbiamo quindi trovare un attraversamento del grafo per trovare il percorso, potremmo provare a forza bruta, ma non è ottimo, ci sarebbero troppi percorsi da verificiare. Ci serve una opportuna procedura di ricerca, che ci permetta di raggiungere agli stati obbiettivi, e dobbiamo trovare il percorso migliore per arrivarci. 

Queste strutture dati e attraversamenti li faremo in prolog!. 

Vedremo anche qualcosa per gli alberi, perchè dati tutti gli stati rappresentati da un grafo, e voglio studiare un attraverso di un grafo, ci serve uno spanning tree, che dato il grafo, lo spanning tree ne rappresenta un attraversamento, in cui posso trovare la soluzione. 

Definiamo ora un modello a spazio degli stati.
Tipicamente abbiamo un insieme di stati discreti, in cui devo avere uno stato di partenza e degli stati goal. I goal possono avere un valore, che si chiama funzione di utilità. Poi vedremo che i goal potranno avere utility diverse, per ora supponiamo siano tutte unitarie. 
Ci sono anche la transizioni, che saranno gli archi del grafo, oppure come trasformazioni di uno stato all'altro. 

Fare recap di alberi e grafi, e macchine a stati finiti. 

Una soluzione consiste in una sequenza di operazioni che trasformano uno stato iniziale in uno stato goal. 

Vediamo un altro esempio simile al commesso viaggiatore ma un pò più semplice. 
![image](https://hackmd.io/_uploads/ryX3MMlCR.png)
La soluzione sarà un insieme di operatori, ossia di archi, che mi permettono di arrivare a una città più bella di quella di partenza. Vediamo la rappresentazione con un grafo: 
![image](https://hackmd.io/_uploads/SkszmGg0A.png)

Per risolvere al meglio un problema di ricerca nello spazio degli stati, ci serve un astrazione del problema, che sia sufficientemente astratta da nascondere i dettagli, ma che sia completa, cioè deve definire tutti gli elementi che mi servono per risolvere il problema, quindi potrei dover migliorare la rappresentazione del problema. Ovviamente nel problema possono esserci dei vincoli di cui bisogna tenere conto e che vanno rappresentati. 

Esempio recipienti da 3 e 4 litri. 

Esempio 8-Puzzle. 


Abbiamo detto che possiamo utilizzare un albero di ricera per la ricerca nello spazio degli stati. 
![image](https://hackmd.io/_uploads/rk10dfxAC.png)
Per l'esempio di prima delle città, vediamo il grafo e il corrispettivo albero di ricerca. 
![image](https://hackmd.io/_uploads/Sk1SYMg0A.png)
Oppure per il commesso viaggiatore: 
![image](https://hackmd.io/_uploads/ryChtzx0R.png)
Rivedere djikstra. 
L'albero di ricerca non è detto che debba contenere tutti i possibili percorsi. 

### Lezione 2 - 24/9/2024

Una delle procedjure di ricerca tramite un albero è partire dal nodo radice, e determinare tutti i successori, che vengono aggiunti all'albero. Tutto funziona finchè non incontriamo dei cicli, che dobbiamo evitare per non entrare nei loop nell'attraversamento. 
![image](https://hackmd.io/_uploads/SkC0TQg0C.png)
I nodi espansi ma non ancora visitati sono aperti, i nodi espansi e visitati diventano chiusi. 
Parliamo di ricerca di non informata se gli operatori (gli archi) non hanno costi, se hanno costi parliamo di ricerca informata. 
Il branching factor è il numero di figli di un nodo (non è detto che l'albero sia binario), e altri parametri quali la profondità ecc. 
Ciò che rende un attraversamento difficile è che non conosciamo la dimensione dell'albero e la forma, nemmeno la profondità dei nodi goal, e ciò impatta sulla complessità computazionale, sia in tempo che spazio. 
Questi algoritmi di ricerca li possiamo confrontare per completezza (riusciamo a raggiungere gli stati goal), complessità di tempo e spazio, e ottimalità (nella ricerca informata non tutti i nodi goal sono uguali). 

Nella ricerca non informata non utilizziamo nessuna ifnormazione speicfica di dominio, mentre nella informata ho delle regole di dominio che ci aiutano nell'esplorazione. 
Un altra questione è: la ricerca è guidata dal goal o dalla situazione di partenza (initial data del problema)? 
Quando facciamo una ricerca in un grafo e non troviamo una soluzione, dobbiamo tornare indietro e applicare il backtracking. 

Depth First Search (DFS)


Breadth First Search (BFS)

Arriva luigi: 
abbiamo uno stato iniziale e uno o più stati finali, vogliamo trovare un percorso che colleghi stato iniziale e finale/i. 

[qiao.github](https://qiao.github.io/PathFinding.js/visual/)

https://deniz.co/8-puzzle-solver/
uno stato è una configurazione nello spazio degli stati. Cerchiamo una sequenza di azioni che ci porti allo stato finale, ossia un percorso nello spazio degli stati. 
Quando affrontiamo questi problemi utilizziamo gli algoritmi informati e non informati.
DFS e BFS non hanno informazioni sullo spazio degli stati, è un pò alla cieca. Negli informati ad esempio ho delle informazioni in più, ad esempio il numero di km che collegano due città. 
![image](https://hackmd.io/_uploads/SJfmQNgRR.png)
esempio se quì la ricerca fosse informata, magari avrei informazioni sui km su ogni arco, se i nodi sono le città. 
Sicuramente se conosciamo queste informazioni possiamo fare una ricerca che ci consenta di trovare un percorso ottimo, che per esempio ottimizza il numero di km percorsi. 
Come lo risolviamo? sicuramente con algoritmi. 
Nella ricerca non informata usiamo dfs e bfs. Entrambi sono algoritmi non informata. 
Con il bfs, dal nodo iniziale, andiamo ad espandere tutti i nodi successivi in ampiezza, col dfs espandiamo in profondità. 
![image](https://hackmd.io/_uploads/ry0ON4lA0.png)
Nel bfs andiamo sempre da sinistra a destra finchè non ci sono più nodi da espandere, torno indietro con un backtracking. 

![image](https://hackmd.io/_uploads/SkbLVEg0R.png)

Nella ricerca informata, abbiamo l'algoritmo di djikstra, che si pasano su informazioni o pesi associati agli archi.
Nella ricerca informata, abbiamo anche l'euristica, che è un suggerimento che ci aiuta (esempio nel 8 puzzle sarebbe contare il numero di tessera fuori posto). 

La soluzione migliore è la via di mezzo, ossia una combinazione tra una ricerca informata e quella sulla euristica. 

Torniamo alle slide. 

### DFS
![image](https://hackmd.io/_uploads/SkdVL4eRC.png)
Dobbiamo muoverci in profondità da sinistra verso destra. Guardiamo prima il grafo. Da S espando verso A, da A vado verso B, e da B verso C. Non posso mai tornare indietro o fare cicli. Quando arrivo in C devo fare il backtracking, torno in B e vedo che posso espandere verso E o tornare verso A (ma farei un loop, non posso farlo, quindi mi serve una struttura dati di appoggio per tenere conto dei nodi già visitati), e quindi da B posso andare solo in E, da E poi posso andare in D o F. 

![image](https://hackmd.io/_uploads/BynCU4eCC.png)
Il BFS invece partiamo da S (non sappiamo dove si trova il goal). In ampiezza ci espandiamo da sx verso dx, quindi espando da A e D. 

Dal punto di vista implementativo ci serve una lista di nodi aperti e nodi chiusi. 

Iniziamo con DFS, possiamo utilizzare uno stack, mentre nel BFS possiamo usare una coda. 
Con questa struttura teniamo traccia dei nodi rimanenti e in che nodi li visiteremo. 
Gli algoritmi terminano quando tutti i nodi sono stati visitati. Quando un nodo non ha più un successore, il backtracking si fa eliminando il nodo dallo stack (pop). Lo stato corrente è quello che si trova in cima allo stack. 
Vedi video con animazione stack. 
Quando tutti i nodi sono stati inseriti nello stack, l'algoritmo non conosce il grafo, quindi farà una verifica se ci sono altri nodi da visitare che non sono già stati visitiati, e quindi cominciano una serie di backtracking a catena,, facendo tutto il percorso a ritrovo, tornando al nodo iniziale eventualmente se tutti sono stati già visitiati. L'algoritmo termina quando lo stack diventa vuoto, oppure quando lo stato corrente è quello goal. 

Nel BFS invece abbiamo detto usiamo una cosa, supponiamo di non avere nodo obiettivo, nella coda inseriamo tutti i diretti successori, la ricerca riprende poi dal primo nodo entrato, che se non ha successori viene rimosso dalla coda. 

A* è il più forte che combina euristica e ricerca informata. 

DFS e BFS non sono efficienti, possiamo migliorare un pò avviando una ricerca bidirezionale, ossia da iniziale->finale e finale->iniziale, che converge quando entrambe si incontrano. 

https://pathfinding-visualizer-31d8e.web.app/

Complessità computazionale. 

domani vediamo qualche approccio misto. 

### Lezione 3 - 25/9/2024

Semantic web nasce con l'idea di standardizzare i linguaggi. Tramite il w3c si standardizzano le ontologie!. 

Riprendiamo la ricerca nello spazio degli stati, dalla comparazione tra dfs e bfs. 

Se siamo sicuri non ci siano loop, o comunque siamo sicuri di poter arrivare al goal, dfs potrebbe funzionare meglio, altrimenti possiamo usare bfs per analizzare tutti i possibli cammini (eventualmente anche tramite implementazioni parallele). 

Un approcio mistro è la iterative-limited search, ossia si applica dfs fino a una profondità fissa e poi ci sarà backtracking, se non ho trovo il goal aumento la profondità. sicuramente ci serve più memoria per tenere traccia della frontiera. 
Se invece mi fermo a profondità m senza andare avanti sarà depth-limited search. 

E' un algoritmo che mi conviene usare se ho una complessità computazionale nota e voglio usarla tutta. 
Combina la garanzia di trovare una soluzione se esiste e l'efficienza spaziale, dato che non manteniamo tutto l'albero. 

Un altro metodo è la ricerca bidirezionale, in cui procedo simultaneamente sia dallo stato di partenza ma anche dai goal. Gia conosciamo gli operatori ossia gli archi (pensa alle strade). Ovviamente dipende se del problema conosco già lo stato goal. Migliora un pò la complessità temporale. 

#### stati ripetuti
quando lo spazio di ricerca ha dei ciclo, avremo degli stati ripetuti nell'albero di ricerca, ossia lo stesso stato può essere raggiunto tramite più percorsi. Tecniche per evitare stati ripetuti. 

### Ricerca Euristica e Informa

Vediamo un esempio tictactoe: 

![image](https://hackmd.io/_uploads/Sk4K5HWRA.png)

Lo stato iniziale lo possiamo semplificare lo spazio di ricerca nel modello, perchè alcuni stati sono simmetrici. Inoltre, possiamo pesare gli stati dato che possono portare a diverse probabilità di vincere. 
![image](https://hackmd.io/_uploads/ry1rorZAA.png)
Nota come abbiamo assegnato un peso agli archi. 
Ovviamente vogliamo trovare un percorso ottimo in termini di pesi. 
Stiamo già accennando un po la teoria dei giochi in cui c'è un avversario o N avversari. 

In generale noi vogliamo trovare un cammino a costo minimo che ci conduca agli stati goal. Vediamo quali sono le tipologie di costi:
- costo dal nodo start a un altro nodo corrente, sarà la somma dei pesi delle transizioni che costuituiscono il cammino. 
- costo dal nodo corrente al goal, tipicamente può essere solo stimato. Esempio google maps aversa-napoli, aversa-giugliano so tutti i costi dei cammini, ma da giugliano a napoli non conosco i costi, posso fare una stima della distanza in linea d'aria. 

#### Completezza e Ottimalità
Se trovo uno stato goal, allora la ricerca è completa, ma se con la ricerca trovo un cammino col minimo costo fino al goal, allora la procedura è ottima, ovviamente se è ottima é completa. 
Ottima => Completa. 

algoritmo scemo: forza bruta, li provo tutti e vedo quale è a costo minimo, ma esplode la complessità computazionale. 
Vediamo come trovare l'algoritmo migliore possibile. 

![image](https://hackmd.io/_uploads/HyRpRHZCR.png)
Supponiamo che i pesi degli archi siano tutti dello stesso segno, per esempio positivi. 
Supponiamo di voler trovare il percorso a costo minimo fino al goal G, e suppponiamo il costo del percorso ottimo ha costo c. 
Possiamo ignorare tutti i nodi aperti nell'albero di ricerca che hanno costo maggiore di c, perchè noi abbiamo già supposto di avere una solzuione a costo c, ed espandere questi nodi farebbe solo aumentare il costo. Sicuramente però dobbiamo esplorare tuttti i nodi aperti con costo minore dic, perchè essi potrebbero produrre un percorso al goal con costo minore di c. 
Vediamo il primo algoritmo

#### Uniform Cost Search
Noi abbiamo la lista di nodi aperti, quello che facciamo è ordinarli, ossia espandiamo prima quelli che avranno costo più basso. Quindi non sto applicando dfs o bfs, ma scelgo dalla frontiera il nodo (forse) più promettente. 
![image](https://hackmd.io/_uploads/BJQuxU-CA.png)
Da mantenere in memoria la frontiera. 

E' completo? si.
E' ottimo? 
- assumendo costi positivi
- si, perchè abbiamo sempre preferito il percorso a costo minimo. 

Bisogna mantenere sia l'albero di ricerca e la frontiera. 

### Lezione 4 - 1/9/2024
Riprende da shortest path principle

La uniform cost search è completa e ottima. 
Il costo in termini di complessità è O(b^d), dove b è il numero di branch e d la profondità del goal.

Adesso introduciamo delle euristiche

### Heuristic Search 
un euristica si occupa di introdurre una scorciatoria che si basa sulla conoscenza del dominio applicativo del problema, e dobbiamo dimostrare che l'algoritmo sia ottimo applicando le euristiche. 
Dobbiamo considerare non più la storia passata, ma una stima del futuro, arrivati sulla frontiera, noi vorremmo trovare un percorso a costo minore dalla frontiera al goal, questo sempre tramite l'euristica; non è detto che essa sia esatta. 

Definaimo una funzione euristica h(node) come il costo stimato del percorso di costo minore dal nodo al goal. Tipicamente la stima del costo del goal stesso, h(G) è uguale a zero. 
Vediamo un esempio:
![image](https://hackmd.io/_uploads/r1GCJHF0R.png)
Ho un euristica h che ci restituisce questi numeri che vediamo in figura. 
Vediamo un primo algoritmo con euristica

### Best First Search
espandiamo il nodo in accordo con ciò che ci dice l'euristica. Sicuramente posso fare backtracking con questo trucco dell'ordinamento della frontiera, è insito nell'algoritmo, l'ordinamento si effettua ad ogni passo.
![image](https://hackmd.io/_uploads/Sy2sxStC0.png)
Il best first è completo ma non è ottimo, ossia troviamo il goal ma non è detto che troviamo il percorso ottimo. 
La complessità è ancora O(b^d), anche se in realtà best-first esplora molti meno nodi. 

### Greedy Search o Hill-Climbing 
Se non posso fare backtracking, ossia non ho la frotinera ordinata, e se ogni volta che espando il nodo mi dimentico degli altri, come se la frontiera non esistesse più. 
E' un esempio di best-first senza backtracking. 
A che ci serve? è completo ma ancora non ottimo, costa poco!. 

Vediamo la soluzione più generale, ossia combinare i due approcci. Consderiamo come funzione di utilità la somma del path_cost e dell'euristica, somma perchè tutti i costi sono positivi e otteniamo un epsressione lienare.

f(n) = g(n) + h(n), dove g(n) è il path_cost

Che ci serve affinche l'algoritmo sia ottimo??
Un eurisitca è ammissibile se e solo se non sovrastima il path_cost dal nodo n fino al goal, quindi l'euristca deve essere più bassa di quel goal. 
Se abbiamo un euristica ammissibile, l'algoritmo che usiamo è A*. In realtà uniform cost search è un caso particolare di A*  con euristica sempre pari a 0, che è sempre un eurisitca ammissibile. 

Un algoritmo di ricerca è ammissile se per ogni grafo termina nella soluzione ottimale ogni volta che esiste un path dallo start al goal.

Monotonicità dell'euristica:
![image](https://hackmd.io/_uploads/H1dxQBtAR.png)
Un'euristica h è monotona se: 
- per tutti gli stati n_i e n_j, con n_j discendente di n_i, allora se:
h(n_i) - h(n_j) < cost(n_i,n_j)
where cost(n_i,n_j) è il costo attuale per andare da n_i ad n_j-
- l'eurisitca del goal è zero. 

L'eurisitca deve essere decrescente perchè deve arrivare a zero. 

Abbiamo anchee il concetto di informedness, ossia quanto siamo informati rispetto al dominio. Esempio h(n) = 0 non è informata, la posso usare in tutti i domini. 
Una eurisitca informata è quella che più si avvicina al costo. 
Un'euristica è più informata se per ogni nodo h1<h2, allora h2 è la più informata, devono essere entrambe monotone. Più l'euristica è informata, più veloce trovo la soluzione e percorro meno nodi. 

vediamo esempio A*
![image](https://hackmd.io/_uploads/SyoJSrtRC.png)
Notiamo che rispetto a birst first, l'albero di ricerca è più ampio. 
Quando arrivo a C lo metto nei nodi chiusi e non più nella frontiera. 

Vediamo esempio 8-puzzle: 
che eurisitca usiamo? una sempre minore del costo reale. 
Potremmo pensare di usare:
- somma delle distante dei tile dalla loro posizione goal. distanza di manhattan
- rompo il quadrato e le metto nella posizione corretta una alla volta, il costo è  il numero di tile che si trovano nella posizione sbagliata. 
Sono entrambe ammissibili, ossia hanno un costo minore di quello reale, quella della somma delle distanze è più informata e ci impiegherà meno tempo. 
C'è anche una terza:
- 2 volte il numero in scambio due tile tra di loro.

![image](https://hackmd.io/_uploads/SJ0NKrFAA.png)
confronto con bfs, entrambi sono completi e ottimi, ma A* è più veloce. 

Perchè A* è ottimo?
si considera un nodo sulla frontiera e un nodo la cui espansione mi farebbe trovare il goal, in questa situazione, il costo reale del goal è minore del costo del nodo N. 
fcost(G) = realcost(G) e h(G) = 0
fcost(N) è minore o uguale del realcost(N) per definzione di eurisitca ammissibile
allora realcost(G)<realcost(N), quindi se passo per N il percorso non è ottimo.
Quindi, se ho G nella frontiera, tutti gli altri nodi potrebbero ancora arrivare a G, ma i loro costi sono maggiori rispetto a quello che ci ha portato in G. 
nagg cpt
A* è matematicamente ottimo. utile per problemi intrattabili. 

Vediamo l'efficacia: 
confronto iterative deepening search e A* con le due euristiche, il numero di nodi esplode con l'aumentare della profondità. 

### Teoria dei giochi
La consideriamo come un particolare algoritmo o insieme di metodologie che rientrano nella ricerca dello spazio degli stati, quindi la affrontiamo come un problema di ricerca; ma stavolta consideriamo giochi a 2, quindi un opponente che userà la stessa strategia, ma con obiettivi opposti. 
Abbiamo una rappresentazione del mondo binario, ed euristiche definite, abbiamo dei goal chiari. 
E' un teoria molto complessa, si usa in economia, medicina ecc. 
La differenza tra i giochi sono i branch, e la profondità. 
Sono delle metodologie che riguardano anche l'AI, i due opponenti hanno la stessa informazione; il comportamento di un giocatore è non triviale. C'è un limite temporale di risposta. 
Possiamo fare machine learning, es. i pesi delle euristiche li possiamo aggiustare col machine learning. 

Facciamo un esempio di un gioco con scacchiera: 
abbiamo la configurazione della scacchiera che è lo stato corrente; lo spazio degli stati sono tutte le possibili configurazioni lecite della scacchiera. Gli operatori o archi sono le mosse lecite. Lo stato iniziale è la configurazione corrente, quindi facciamo una ricerca nello spazio degli stati ad ogni mossa, quindi dopo quella dell'opponente dobbiamo ripetere la ricerca; lo stato goal è la configurazione che dà vittoria a me e sconfitta all'avversario. 

L'albero di ricerca nello spazio degli stati è:
![image](https://hackmd.io/_uploads/rJgDeUtR0.png)
Gli stati adiacenti alle mie mosse sono le mosse dell'avversario. 

Vediamo la complessità
worst case O(b^d). negli scacchi abbiamo in media b=35 e d=100, quindi dopo 100 mosse si può arrivare al goal. 35^100, oppure 10^40 per le mosse legali, il problema è intrattabile!. Non possiamo mai implementare un algoritmo esaustivo che mantenga un albero di ricerca del genere. 
Per un tris è più trattabile ma comunque troppi nodi da esplorare. 

Vediamo ora che intendiamo con funzione di utilità: si assegna un valore numerico ad ogni stato terminale, che rappresentano quanto buono quello stato è per il computer. Ci serve anche un utilità per capire di quanto si vince rispetto all'avversario (es. dama, quante pedine ho in più). 

### Greedy Search with utilities
generiamo tutte le possibili mosse, e poi scegliamo la migliore per me. 

oggi pome minimax. 

### Minimax
l'opponente prende la mossa migliore per lui e peggiore per noi. La ricerca nell'albero è, a seconda dei livelli, ottima o peggiore per me.
Noi assumiamo che l'avversario sceglierà la mossa migliore per minimizzare il costo, cosi noi scegliamo la nostra miglior mossa.

![image](https://hackmd.io/_uploads/rk7hUvYAA.png)
quando stiamo al secondo livello, la mossa migliora per l'avversario è quella con -6, oppure nel secondo branch e terzo, lui sceglierà -2 e -4. Quindi, quello che facciamo è riportare su i valori della migliore mossa dell'avversario
![image](https://hackmd.io/_uploads/B1HlPDKCA.png)
Scegliermemo quindi la C, perchè se l'avversario gioca bene mi porta a -2. 
Noi vorremmo scegliere i percorsi che ci portano a una vittoria per noi. 
![image](https://hackmd.io/_uploads/BkDx_PKCR.png)

slide luigi carry. 

Esempio UCS: 
inseriamo nella lista  dei nodi chiusi il nodo e il peso dell'arco, dal grafo si costruisce l'albero. 
![image](https://hackmd.io/_uploads/r1fs1OFR0.png)
Nella fase 3 arrivo a un pinto in cui v5 e v6 costano di più, ritorno a v2 col backtracking. 

Gli algoritmi con l'euristica tendono a fare meno backtracking.


bfs siamo veloci non ottimali

mettiamo insieme costi e euristica e otteniamo o patatern A*


### Lezione 6 - 2/10/2024

Altri esempi luigi. A* robot navigation e map navigation

palla a beniamino. 

Vediamo esempio nim. ci sono 7 oggetti o un numero dispari di oggetti in fila, e bisogna dividerli ogni volta; quello che non si può fare non si può dividere in due pile uguali. 
![image](https://hackmd.io/_uploads/BkwP6_cAA.png)
Perde chi non riesce a dividere ulteriormente, i nodi foglia quindi saranno nodi di vittoria per chi fa quella mossa, e di sconfitta per l'altro. 
Nel minimax i nodi foglia hanno una funzione di utilità che misura il grado di vittoria, e facciamo propagare verso l'altro i valori migliori per chi deve giocare. 
![image](https://hackmd.io/_uploads/rydMkKcRA.png)
quelle sono le 3 foglie di vittoria/perdita, es sull ultimo livello max perde, perche min ha fatto la mossa vincente verso la foglia. 
diamo 0 al valore della configurazione che è una vittoria per min. 
le linee piene vanno verso la vittoria, le tratteggiate no. 

Vediamo un altro esempio, la funzione di utilità misura il grado di vittoria
![image](https://hackmd.io/_uploads/SygzWtqRR.png)
non ci interessa rappresentare tutto l'albero di ricerca o comunque mantenere tutti i possibili stati, ci serve mantenere solo gli stati che dobbiamo poter valutare o quelli che servono per creare successori verso la vittoria. 

complessità spaziale: devo mantenere le configurazioni di un nodo e basta devo solo scendere, la complessità spaziale è come DFS quindi O(bd), mentre dal punto di vista temporale sicuramente l'albero lo dobbiamo attraversare, quindi O(b^d). 

#### Alpha Beta Principle
Nel momento in cui procediamo depth-first, ma adesso vogliamo provare a togliere dei rami inutili, in cui ci sono nodi con valori minori di quello corrente. valore alpha è il massimo corrente, valore beta è il minimo corrente, quindi alpha beta pruning mi fa prunare l'albero se trovo un valore minore di alpha. 

Complessità
nel caso peggiore attraverso tutto, nel migliore solo un ramo, quindi nel caso medio ne attraverso mezzo, quindi nella pratica ho O(b^(d/2)) invece di O(b^d), quindi il fattore di branch si riduce alla sua radice quadrata (es. scaccchi b=35 -> b=6). 
Posso arrivare a una vittoria? probabilmente no se ci sono troppi nodi, ma mi permette di approfondire. 

Euristica orizzonte degli eventi. ci conviene propagare in maniera uniforme o vado deep in un branch? se devo cercare la mossa migliore per me, mi conviene non esplorare uniformemente, sperando di arrivare a una vittoria per me.

video scacchi vs deep blue. 

esempi luigi
[alpha,beta], mini registra beta, max registra alpha, il pruning avviene se beta<=alpha
quando si fa il backtracking, il giocatore max aggiorna alpha col valore corrente di beta. 

https://pascscha.ch/info2/abTreePractice/

### Lezione 7 - 8/10/2024

Oggi cominciamo al rappresentazione della conoscenza, prima dobbiamo vedere i modelli di rappresentazione. 

Mo vediamo una scarrellata sui formati di dati. 

Dobbiamo capire come la rappresentazione della conoscenza non è solo strutturare i dati in un formato, essa ci serve ad inferire nuova conoscenza tramite sistemi a regole. 

Nel mondo della rappresentazione dei dati abbiamo: 
-strutturati: sono quelli accompagnati da uno schema forte, esempio un database tramite un modello relazione stabilisce come i dati sono rappresentati tramite uno schema. Non c'è possibilità di errore, o appartengono a un tipo o no. 
![image](https://hackmd.io/_uploads/BJ-JhdMk1x.png)
- non strutturati: sono i raw data (grezzi), sono dati che non hanno un tipo associato, per esempio le immagini, che nonostante abbiano dei formati (che rappresentano un modo per aggiungere metadati sull'immagine quale data, proprietario ecc), e poi abbiamo rappresentazioni per esempio vettoriali o raw (densità, colori pixel), ma quello che l'immagine rappresenta non è rappresentato. Anche il testo si può vedere come informazione non strutturata. Quindi sia testi che immagini rappresentano comunque molte informazioni semantiche. 
- semistrutturati: ad esempio il formato html. Html fa parte di una famiglia di linguaggi di markup chiamato SGML (standard generalize markup language), che sono linguaggi basati su xml che permettono di taggare/aggiungere informazioni in una rappresentazione che tipicamente non è strutturata; quindi attraverso i markup language posso dare una struttura a un informazione che normalmente non lo è. 
Discorso simile riguarda http, è una rappresentazione a grafo di testi. Http fornisce implicitamente un informazione che rappresenta delle relazioni tra elementi non strutturati o semistrutturati. C'è semantica? ossia se ho beniamino di martino e gli metto un link a un file html a un paper del miur, quel link non ha un formato di rappresentazione forte, non mi dice sicuramente che beniamino di martino è un professore, a differenza di come potrei avere in un database. 
Per esempio il web è difficilmente usato per una rappresentazione forte di dati, per fare questo definiremo il semantic web. 
![image](https://hackmd.io/_uploads/rJwpTOGykl.png)
Per quanto riguarda i modelli relazionali, conosciamo sql, dbms.
Un DBMS è un sistema software che è in grado di gestire
collezioni di dati grandi, condivise e persistenti, in maniera
efficiente e sicura.
I dbms seguono uno standard comune che è sql, quindi la struttura dei dati può essere compresa perchè standard. 
![image](https://hackmd.io/_uploads/rJor0_Gyye.png)

![image](https://hackmd.io/_uploads/ryV_ROzJJe.png)
Vedremo qualcosa simile nel semantic web con owl. 

Nel mondo web/cloud, tutti i modelli che non sono basati sul modello relazionale vengono chiamati nosql. Idea di base nosql: superare la rigidità del modello relazionale nella definizione dello schema, consentendo una più facile espansione del DB in termini di dati, e di computazione distribuita. Machine readibile. Dovrebbe essere standardizzata ma ancora non lo è. Altre cose come la coerenza, acid ecc, in particolare two-way commit (o il dato viene scritto o viene annullato), tutto questo non viene garantito nei db nosql. Vediamo le tipologie di modelli non relazionali: 
- key-value store
- document: c'è una struttura gerarchica con dei link. 
- object: simile a document ma più strutturata. ci rifacciamo alla programmazione ad oggetti; ho degli oggetti e dei tipi, e gli oggetti possono avere relazioni tra loro. In un modello a oggetti incorporo tutti in oggetti (es file, una tabella di un database ecc). 
- graph store: 
- tuple: oggetto,attributo,valore. vedremo qualcosa simile in owl.
- grafo
- multimodello: li mescolo. 
![image](https://hackmd.io/_uploads/H1cNkKGJke.png)
MongoDB e firebase sono document store. 

Vediamo alcune rappresentazioni. 

La rappresentazione più semplice di dati è il CSV e anche la più utilizzabile da un sistema. formato opendata.
Formato csv può essere riparserizzato da tutti i parser, a patto di avere lo schema, ossia il significato delle colonne. 

#### Formato JSON - Javascript Object notation
E' un linguaggio di rappresentazione che permette di rappresentare i dati come oggetti, quindi diamo una struttura ai dati, e permette di definire anche la semantica cioè il tipo dei dati. I file json sono completamente strutturati, quindi non possiamo usare json come markup language, a differenza della famiglia di linguaggi xml. 

XML è un linguaggio di markup. E' un metalinguaggio, ossia potrei avere un documento e arrichirlo con xml aggiungendo informazione, è la base per altri linguaggi di rappresentazioni, es. owl è basato su xml o json. 
Per quanto riguarda i formati per dati non strutturati, abbiamo odt per la rappresentazione di documenti, esempio word o office di microsoft, si può esportare in odt; è standard. 
PDF è il rè dei linguaggi di rappresentazione documentale, adobe l'ha fatto standardizzare. 

Formati per dati geografici: dati georefernziati (opengis). GML è uno standard iso, in cui possiamo sovrapporre una geomteria, poligoni ecc. Posso rappresentare dei markup su un immagine. 

Modelli a grafo: rappresentnao in modo esplicito le relazioni, che assumono una valenza equivalente ai nodi che rappresentano gli oggetti. I modelli a grafo seguono bene la struttura del web, in particolare di http, possono essere anche dei modeli di markup per linguaggi semistrutturati. 
Neo4j e graphDB sono i più famosi. 

Gli open data se rappresentano relazioni si chiamano linked open data. 

Introduciamo i modelli semantici. 
I modelli semantici si possono vedere come un evoluzione di modelli a grafo. I modelli semantici ad oggi si basano su xml+http, hanno la stessa struttura del world wide web. Ci sono un insieme di strati
![image](https://hackmd.io/_uploads/ByMtoFG1Jl.png)

rdf e owl. 

Vediamo le principali fasi di un processo di gestione di dati non strutturati: opendata pipeline: 
![image](https://hackmd.io/_uploads/SkdGnYGy1g.png)
parto da una sorgente di dati di qualsiasi tipo, strutturati o non strutturati e li dobbiamo gestire. Facciaom ingestion dei dati e li conserviamo in un datalake (cosi come sono, nei formati in cui sono stati prodotti) nel rawlayer, li puliamo e standardizziamo. (work layer). Poi li arricchiamo aggiungendo conoscenza e li integriamo (se li posso rappresentare uno schema ma provengono da sorgenti differenti, li posso integrare) nell'enhanced layer. Infine, ci facciamo un analisi sopra (es. ricerca nello spazio degli stati ecc) nell'access layer. 
Data lakes è come il petrolio. vediamo na definizione seria non data da lui: 
Cos’è un Data Lake? Si tratta di un repository centralizzato che consente di archiviare grandi quantità di dati nel loro formato nativo, provenienti da molte fonti diversificate e disomogenee. 

w3c standardizza tutto ciò che riguarda il worldwide web

pubblico gli open data tramite file o api

Modelli di Rappresentazione dei Dati. Dati Strutturati, Non strutturati, Semi-Strutturati. Modello Relazionale e Modelli Non-Relazionali (cenni): Key-Value, Document, Object, Tabular, Tuple, Triple, Graph. Formati per i modelli non-relazionali: Csv, Tsv, jSON, SGML e XML-based. Modelli a Grafo. Graph Databases. Modello a Triple: Linked Open Data.



### Lezione 8 - 8/10/2024

### Knowledge Representation and Inference

Definizione di epistemologia: lo studio della conoscenza, incluso la sua natura, la struttura e le sue origini. 

Conoscenza a priori: derivano dalla percenzione del mondo al di fuori dai 5 sensi. 

Con conoscenza ci riferiamo a diversi tipi: 
- conoscenza procedurale: prevede una serie di fasi da realizzare/rappresentare nel tempo; esempio i business process che contengono azioni e dipendenze temporali e sui dati e seguono un workflow. 
- conoscenza dichiarativa: definisco dei fatti che esprimono dei concetti che possono essere veri o falsi, a seconda del caso a cui li applico (es. fatto = oggi piove, se è vero o falso dipende dalla giornata o dal luogo). noi studieremo questa nel dettaglio, che è rappresentata da modelli che storicamente hanno a che fare con l'IA, e anche i linguaggi e la logica (sistemi formali) sono un insieme di rappresentazione di fatti. 
- conoscenza tacita: che non si può esprimere, ad esempio imparare ad andare in bicicletta.
- meta conoscenza: Knowledge about knowledge. Example: “for the course material I know, these parts will be on the final”

tipi di knowledge representation: 
![image](https://hackmd.io/_uploads/B19GYjM1Jg.png)
reti semantiche sono i predecessori del paradigma oop. 
![image](https://hackmd.io/_uploads/SknotjzJJl.png)

triple: object-attribute-value

frames: altri precursori della oop. 

regole di produzione: ho delle regole da applicare a basi di conoscenza. per esempio un parser. 
![image](https://hackmd.io/_uploads/H1v9csGJJe.png)
vediamo in prolog dei parser. 

inferenza: ci riferiamo a sistemi a produzione di regole o sistemi esperti. L'inferenza è tante cose che caratterizzano la capacità di un essere inteliggente di ragionare. può essere:
- inferenza deduttiva: dalle premesse arrivo a una conclusione
- inferenza induttiva: parto dalle conclusione, trovo dei pattern, e infine ricavo la regola generale.
- abduzione: contrario di deduzione.

forward e backward chaining: dalle ipotesi dalla tesi e viceversa. 
forward dal fatto arrivo alle ipotesi, backward dalle ipotesi arrivo al fatto. se abbiamo un solo fatto sono equivalenti. 

nuove slide 

![image](https://hackmd.io/_uploads/H1tvAiGk1g.png)
dal linguaggio naturale passiamo a un linguaggio formale con cui rappresentiamo la conoscenza, e possiamo rappresentare i modelli concettuali che sono gli equivalenti dei modelli mentali che noi abbiamo del mondo. 
Programmare in una rappresentazione di conoscenza significa avere una base di conoscenza che sono le regole, avere i dati, e avere un algoritmo che esegue le regole. 
![image](https://hackmd.io/_uploads/r1UIy2fkyx.png)


### Rete semantiche
E' in buona sostanza un grafo. E' una struttura gerarchica. 

Vediamo un esempio di programmazione dichiarativa: 

![image](https://hackmd.io/_uploads/rJ4A-nzJye.png)

Una limitazione è la capacità di definire relazioni multiple.

fa schifo perche vuole esprimere in maniera statica le relazioni

sta a fa schif oggi
70 slide in mezz ora

### Grafi concettuali

### Lezione 9 - 9/10/2024

spawnato branco mo fa vedere una versione pazza di A* che hanno usato in un progetto.

A* è efficiente e trova il path più corto in maniera efficace. Può gestire a ostacoli e performa bene su problemi path planning. 


## formisano A* lo sa che esiste??

richiede molta memoria, è difficilmente utilizzabile in real time, e dipende molto dalla qualità dell'euristica. 

Il problema è che A* richiede un target, nel coverage path planning la cella goal può cambiare in base a come mi muovo. 

Ci serve un modo per risolvere questo problema aiutandoci con la potenza di A*. 

Tra i requisiti devo percorrere tutte le celle ma farlo con lo shortest path. 

forza branco
no fa ciata 

https://github.com/rodriguesrenato/coverage-path-planning

o fess chiede la complessità degli algoritmi all'esame. 

farlo parla p favore. 

non so sta cacann pop per il paper.

branco sta volando. 

### Grafi semantici di corsa

nessuno fa progettino!. chissa perche!!

Servono a rappresentare la conoscenza basata sul linguaggio naturale. Hanno lo scopo di rappresentare le relazioni. 

E' costituito da due tipi di nodi: 
- concept nodes: rappresentano entità, attributi, stati ed eventi
- relation nodes: relazioni

Rappresentazione flessibile, posso inventare tutti i relation nodes che voglio. 

Queste rappresentazioni non hanno mai dato luogo a un linguaggio o notazione standard. 

![image](https://hackmd.io/_uploads/r1GyM6Xkkg.png)

i grafi sono connessi, finiti e bipartiti. 

Concetti concreti e astratti, posso rappresentare un entità e un'istanza di un entità, es un gatto che si chiama beniamino è un istanza dell'entità gatto, ovviamente devo definire un relation nodes.

Lo stesso concetto lo posso rappresentare con diversi livelli di astrazione. 
![image](https://hackmd.io/_uploads/S15LMpXJyg.png)

![image](https://hackmd.io/_uploads/S1JRfTmy1e.png)

![image](https://hackmd.io/_uploads/r17LXT7J1l.png)

possiamo associare un identificatore. 


### Lezione 10 - 15/10/2024

I frame sono un modello di rappresentazione della conoscenza molto famosi. 
Le persone selezionano dalla memoria un frame/template quando si incontra una nuova situazione o un cambiamento nel contesto del problema, che si adatta alla realtà. Rappresenta una situazione stereotipata: esempio di una stanza, se sto in un salotto mi aspetto di trovare delle cose, se vado in una stanza di albergo mi aspetto di trovarne altre, oppure al ristorante, in un tradizionale prima mangio poi pago, oppure un fast food pago prima e poi mangio ecc. 

A frame is a data-structure for representing a stereotyped situation.
La oop nasce nel 1982. 

Ogni frame ha un nome, degli slot che sarebbero le proprietà del frame (dei valori du un attributo ad esempio). I valori possono essere di default, o ereditati da un altro frame oppure da una procedura che si chiama daemon. 

Posso esserci delle relazioni con altri frame. Le informazioni possono essere procedurali (come il daemon). 
![image](https://hackmd.io/_uploads/SJnZUhjy1l.png)
le frecce indicano relazioni di specializzazione, esempio la stanza contiene chair, bed, che a loro volta sono dei frame. 

La relazione più importante è quella di istanzazione (instance of), un frame può quindi rappresentare un istanza di una classe. 

I frame consentono l'ereditarietà multipla (java non la consente, servono le interfacce). In owl vedremo potremo ereditare da piu classi. Bisogna gestire conflitti se eredito attributi con gli stessi nomi. 

Vediamo le procedure. Abbiamo due tipi legati agli slot(attributi):
- when changed, la procedura viene eseguita quando il nuovo valore è valorizzato per lo slot, ossia quando il valore cambia.
- when needed, quando il valore per lo slot non è specificato ma viene richiesto. 

Ci sono anche i facets che forniscono un estensione alla struttura di un valore di uno slot. 

Per le relazioni, abbiamo
- generalizzazione: 'a-kind-of'
- aggregazione: 'a-part-of'
- associazione: descrivono le relazioni semantiche tra le classi. 
![image](https://hackmd.io/_uploads/HkZAP3j1Je.png)

![image](https://hackmd.io/_uploads/rkJMOhsJ1x.png)
La valorizzazione degli attributi si fa direttamente nell'istanza, ma potrebbe anche avvenire nei frame che non sono frame di istanza. 

Esempio terremoto: 
![image](https://hackmd.io/_uploads/SJHAOhjyye.png)
uragani nomi di donne. 

Dopodiche dobbiamo popolare la conoscenza!. Prendiamo una descrizione in nlp di un terremoto e dobbiamo popolare il nostro schema a frames. 
coi frames si può popolare anche in maniera errata la conoscenza. 

Subito dopo i frame vennero inventati gli script, che li completano nella rappresentazione di sequenze di eventi. Ad esempio le classi sono statiche, oppure diagramma delle classi in uml. 

Lo script è una sequenza stereotipata che rappresenta una situazioni.
Abbiamo gli attori e ruoli degli attori (use case diagram o bpmn con le pool e lane). 

![image](https://hackmd.io/_uploads/ryz9sho1Jl.png)
Abbiamo ruoli con attori e le props/attributi. 
Dopodiche ci sono delle scende (entra, ordina, mangia,..). 
Ci sono delle condizioni di ingresso di uno script (ad esempio Customer è affamato), o di uscita (customer non ha più fame e meno soldi). 
Ci possono essere eccezzioni che ci fanno uscire fuori dalla situazione stereotipata. 
La sintassi non è standard e non esistono parser.  Questo è un esempio di sistema formale. 

Anche gli script usano ereditarietà e lo stesso concetto di situazione stereotipata, ma si concentrano sulle sequenze di eventi. 

Vediamo delle situazioni in cui possiamo usare o meno lo script ristorante. 
Usando lo script visto, ci sono delle situazioni non stereotipate. 


mo luigi esempi reti semantiche e grafi concettuali. dopodiche semantic web. 

Frame: si rappresenta come un rettangolo denominato col nomo dello stereotipo da modellare. 
Frame veicolo ad esempio, gli slot sono degli attributi per memorizzare dei valori. Gli slot possono essere valorizzati o meno, esempio la velocità di un veicolo di solito non si valorizza, perchè ogni veicolo potrebbero averne di diverse. 
Gli slot potrebbero includere informazioni come: nome del frame, relazioni di un frame con altri frames. 

Per le relazioni, abbiamo generalizzazione: es. automobile è un tipo di veicolo, aggregrazioni(ruote) e associazioni(persona possiede automobile). 

![image](https://hackmd.io/_uploads/Skrpvpi1Je.png)
slide sbagliate. 

campo resticritions si usa per mettere delle opzioni. 

esempi

### Lezione 11 - 15/10/2024

nello scritto, data una frase nlp ci verrà chiesa di rappresentarla con rete sem, grafo concettuale, frame o script.

i frame rappresentano una parte statica di uno stereotipo, gli script la parte dinamica.


Nome script
track dello script (es. ristorante -> pizzeria)
props (oggetti di scena, es. tavoli, menu, soldi)
ruoli (es. cliente, cameriere)

ci sono delle relazioni standardizzare da schrank ma te mpar tu. 

inserisci qualcosa sui SISTEMI FORMALI. 

Con reti semantiche e grafi concettuali insegniamo alla macchina qualcosa su un determinato dominio. 
Con gli stereotipi (frame e script) insegniamo alla macchina il senso comune, sensazioni, legate all'esperienza. 

Gli script devono avere anche condizioni di ingresso e uscita. 

Voliamo a reti semantiche. 

La prima cosa da fare dalla conoscenza è ricoonoscere le entità, che diventano nodi della rete semantiche. 
I nodi possono essere oggetti o istanze di concetti. 
Esempio conoscenza internet, reti. 
es. amazon è un istanza di ecommerce. 
libri,cd,dvd classi. 


### Web Semantic
usiamo semantic web primer. 

Nel web e social network, i contenuti sono orientati agli essere umani che comprendono, quindi i contenuti o sono fortemente strutturati (tipo database ecc) che poi vnegono convertiti ad esempio in html; oppure ci sono dei web services, che tramite delle api, tramite protocollo http, possono comunicare direttamente con le macchine. 
Ci sono i linguaggio semi strutturati che consentono di aggiungere i metadati alle risorse. 
Esempio ecommerce, un umano cercherebbe qualcosa su diverse pagine di un sito, ma questo impiega molto tempo, vogliamo che una macchina possa accedere a tutti i contenuti in meno tempo possibile. 

Ci vuole una rappresentazione comune dell'informazione. 

Il semantic web vuole rappresentare un informazione in maniera formale, dove formale vuol dire machine readable, ma comunque sufficiente complessa da farci inferenza (tramite agenti software), e poi utilizzare la distribuzione di rappresentazione del web e la facilità con cui i formati di rappresentazione possono essere scambiati, quindi uri, http, xml. 

es. pagina web
![image](https://hackmd.io/_uploads/rJYeVe3J1l.png)
ho aggiunto dei collegamenti semantici. 

E' un estensione del web corrente, lo scopo è la collaborazione tra computer e persone in modo che le macchine possono essere utili agli umani. 

Il semantic web è una metadatazione dei contenuti del web. 

prime 20 slide. 

rappresenta in maniera univoca i metadati associati ai dati. i dati sono esposti tramite web classico, anche file excel e api di servizi. 

### Lezione 12 - 16/10/2024

esercizio5 rete sem stile esame (può essere anche partizionata!!)

C'è un per ogni, bisogna devifinire un general statement e una sua istanza, l'istanza la collego con un collegamento form a uno space.

I concetti fuori dallo space, le istanze dentro. 

Quando ci sono delle quantificazioni bisogna sempre inserire un partizionamento. 

Grafi concettuali ora
possiamo modellare relazioni di causa effetto. 
Le relazioni delle reti semantiche diventano nodi relazionali. 

Nodi coi quadrati sono i concetti 

Esempio1 grafi concettuali: 
Peter attraversa la strada sulle strisce pedonali. 
La relazione principale è attraversare, i concetti sono persona, strada, location dove si attraversa. 
Nei nodi abbiamo due tipi di informazioni
tipo del concetto: referente dell'istanza (es. Persona: peter). 
Se omettiamo referente, mettiamo : *. 
agent indica il soggetto, object l'oggetto (cosa attraversa? la strada). 
Conviene partire dalla relazione e poi definire agente, oggetto, location ecc. 

Può essere utile anche qui definire un partizionamento. Si usano le proposizioni (affermazioni o negazioni).

La direzione delle frecce parte sempre dalle relazioni. 

Situation ?? 

esempio2 
di venerdi bob guida la sua old chevy a st.louis
non ci sono situation e proposizioni, facciamo un grafo concettuale classico. 

Nodo drive relazionale
bob nodo concettuale Person:bob 
nodo concettuale Car: Chevy, attributo old
nodo concettuale Place: st.louis
relazione possesso tra bob e auto. 
i nomi sulle relazioni tra due nodi non sono standadizzati, mettiamo quello che vogliamo.

esercizio3 complesso. 
ci sono delle situation
in teoria uno cosi complesso non ce lo dà

esempio frame con gerarchia dominio medico. 

finito luigi

mo beniamino distrugge il semantic web.

XML assumiamo che lo sapete. 

Il semantic web è uno standard definito da w3c. 

E' costituito da un insieme di linguaggi standard e tool di supporto, il più importnate è protege che permette di definire ontologie in maniera grafica e di visualizzarle. 
Ci sono anche dei motori inferenziali. 
![image](https://hackmd.io/_uploads/Skxftepkye.png)
Il linguaggio su cui si basano tutti gli altri è xml, poi c'è il protocollo uri. Poi c'è RDF, rdf-schema da cui nasce owl. Poi ci sono linugaggi di querying come sparql che faremo e swdl, poi c'è la logica e altri linguaggi logici che accompagnano owl come prolog. 

Vediamo un po i layer

uri è il protocollo per identificatore univocamente le risorse. 

xml è un metalinguaggio di marcatura, tutti i linguaggi su xml sono dialetti di gsml. La cosa importante è lo xml schema, che definisce gli schemi e i tipi di dati rappresentati in xml, in maniera molto ligth, i tipi possono essere definiti dall'utente nello schema. L'xml schema rappresenta una semantica. 
namespace sono delle abbreviazioni, raggruppano i nomi per categorie. 

rdf layer. 
rdf è un linguaggio xml based, linguaggio di rappresentazione di oggetti e relazioni, come triple (oggetto-attributo-valore) in cui il valore può essere ancora un oggetto, nota che gli oggetti hanno gli uri, quindi se faccio concatenazioni possiamo costuire dei grafi; 
Attraverso gli rdf schema possiamo costruire schemi per oggetti e relazioni, e possiamo quindi definire una rappresentazione omogena di quali sono gli oggetti e quali sono gli attributi. 
Se ho una semantica per un oggetto, possiamo usare due uri differenti, e quindi creo qualcosa che non è consistente; questa è una limitazione

Dopodichè c'è OWL, che è un linguaggio ONTOLOGICO. E' un modello di rappresentazione della conoscenza, perchè ci permette di definire delle ontologie. 
OWL non rappresenta bene le sequenze temporali. 
abbiamo classi, relazioni, ma tutto web based, con standard aperti, machine readbable, e distribuiti.  Le relazioni prevedono delle proprietà. 

Le ontologie permettono massima portabilità.

logica e inferenza

sparql

unifying logic, bisogna seguire la logica scelta. 

trust

agenti software, sono dei software che usano owl. 


### Lezione 13 - 22/10/2024
seminario del cazzo.



### Lezione 14 - 22/10/2024
il web semantico non sostiuisce il web classico ma aggiunge delle cose. Il web semantico aggiunge tecnologie tutte xml based, come rdf, una tecnologie che consente di realizzare metadati. I dati devono essere descritti semanticamente. Per descriviere i dati ci serve un modello per definire le relazioni e le risorse da usare, e lo possiamo usare con rdf model o con owl più complesso. 

Recap XML. Se rubato e slide da uni bologna
http://lia.deis.unibo.it/Courses/TecnologieWeb0910/lezioni/1.06.XML.pdf

xml è uno standard di interscambio di dati, ma consente anche di definire altri linguaggi. 
Html ad esempio o svg (x immagini web), sono tutti xml based. 
Consente di rappresentare documenti e dati strutturati, e scambiarli tra applicazioni. Anche dati strutturati. 

Xml è un linguaggio di markup, non ci sono istruzioni procedurali ma tutte le istruzioni sono definite da dei tag o marcatori che descrivono la forma di un documento. Gli elementi possono racchiuderne altri, possiamo rappresentare un documento xml con una struttura ad albero. 
![image](https://hackmd.io/_uploads/ByWxnMHekg.png)
tag di apertura, chiusura e valori in mezzo. Possono essere presenti degli attributi, ad esempio in prezzo c'è un attributo valuta. ![image](https://hackmd.io/_uploads/HyyX2fSgke.png)
gli attributi sono coppie chiave valore. 

XML è indipendente dal tipo di piattaforma hardware indipendente dal tipo di piattaforma hardware e software su cui viene utilizzato. Xml si può usare per modificare gli open data. non è proprietario, quindi possiamo usarlo gratis e tramite qualsiasi editor. 

Xml è anche un metalinguaggio, può essere utilizzato per creare altri linguaggi tramite metaregole, questo perchè i tag non hanno significato, li scegliamo noi i significati dei tag. 
Se definisco delle metaregole o uso un linguaggio tipo html, non posso inventare i tag ma devo usare quelli predefiniti. 
![image](https://hackmd.io/_uploads/BJv8pfSlyl.png)

Per definire le regole, bisogna definirle in documenti esterni tramite specifici approcci; si stabilisce che tag si possono usare, la struttura logica ecc. Per definire le regolle si usano delle grammatiche, che è un insieme di regole che indica quali elementi possono essere utilizzati e con che struttura è possibile comporre frasi. Ci possono essere regole semantiche. 

regole di buona formazione
es. html funziona lo stesso pure se non chiuso un tag oppure tag incrociati, quindi html non è ben formato, quindi ammette che qualche regola xml possa essere non rispettata. 

DTD document type definition. difficili da creare. non posso specificare il numero minimo di tag in un documento. 
XML schema. risolve alcuni problemi di dtd. è più performante pure.

namespace in xml
definiamo l'insieme di tutti i prefissi che vogliamo utilizzare. es. possiamo usare dei prefissi per usare elementi da altri file.

voliamo a rdf

il web ad oggi è diventato più forte per via della semantica. prendo le risorse del web e le descriviamo tramite metadati. I metadati non sono inseriti nello stesso file della risorsa ma su file esterni. metadati sono dati che descrivono altri dati. es 'alberto cavallo', possono inserire come metadati nome, cognome, ecc. 

Tutti i metadati del web sono collegati tramite rdf, tutti rappresentati come un grande grafo, e le query diventano ricerche sul grafo. 
con rdf modelliamo triple per delle risorse sul web. 
![image](https://hackmd.io/_uploads/r1QMmQBlJl.png)
le query si fanno con dei linguaggi appositi che estranno sottografi, cioè sottoinsiemi di triple. tipicamente le relazioni sono standardizzati, si fa tramite ontologie. 

vediamo slide beniamino rdf. 

rdf è standardizzato da w3c. è un linguaggio per descrivere risorse, cioè per aggiungere dati (metadati) alle risorse stesse. è anche lo strumento base per la codifica, scambio e riutilizzo di metadati strutturati. 

con rdf definiamo dati per scambiare informazioni sul web. 

### Lezione 15 - 23/10/2024
beniamino kbs. 





