This page contains the abstracts of the talks held during the latest Venerdì Protetto on September 8, 2023.
Topics:
The overview of Venerdì Protetto is available here.
Dalle notifiche di Facebook ad un tweet stream, da Google Docs ai giochi multiplayer in HTML5, la necessità di uno scambio dati in due direzioni, efficiente e a bassa latenza, ha determinato l’ascesa negli ultimi anni di soluzioni basate su
WebSocket
.
Internet delle cose e web 2.0 trovano oramai sempre meno spazio all’interno del protocollo HTTP/1. Le tecniche di polling e long polling, in voga fino a pochi anni fa, non permettevano di trasmettere in
full duplex
(tra server e client) contemporaneamente, erano costrette ad un alto overhead HTTP e richiedevano diversi sforzi per simulare notifiche push server side.
Introduzione
A* è un algoritmo di ricerca e ottimizzazione basato su grafi. Viene frequentemente impiegato nell’intelligenza artificiale perché in grado di gestire grafi ampi e
indeterminati.
L’algoritmo A* può essere utilizzato per risolvere problemi come: gioco del 15, percorso minimo, Sudoku, cubo di Rubik, ecc.
In generale, A* può risolvere efficacemente i problemi che soddisfano i requisiti:
- La soluzione è determinata da cambamenti sequenziali di stato rappresentabili con grafi;
- Il nodo iniziale e il nodo finale devono essere noti. Talvolta è sufficiente conoscere solo le regole che compongono la soluzione (vedi Sudoku);
- Deve essere noto un algoritmo euristico che stima il costo del percorso tra un nodo qualsiasi e la soluzione.
- Deve essere sempre noto il costo che separa due nodi adiacenti. (Nella maggioranza dei problemi tale valore è sempre unitario).
L’euristica
L’algoritmo euristico ha il compito di stimare la distanza tra qualsiasi nodo e la soluzione.
L’euristica influenza fortemente i risultati conseguiti da A*. Esso, in particolare, ne determina il tempo complessivo di esecuzione.
Un algoritmo euristico molto efficace consente ad A* di trovare velocemente la soluzione.
Nel caso pessimo, una funzione euristica costante, A* diviene un algoritmo di ricerca molto simile a Dijkstra.
