-
Notifications
You must be signed in to change notification settings - Fork 0
/
voiceover.txt
27 lines (21 loc) · 1.87 KB
/
voiceover.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Salve a tutti! In questo video parleremo di grafi
Una struttura dati che viene utilizzata in moltissimi campi
Si pensi alle neural network oppure alle stazioni metro delle grandi metropoli
O ancora alle banche di una multinazionale che cercano di distribuire i propri soldi uniformemente
Insomma i grafi hanno un impatto enorme su di noi e riuscire a capirli è fondamentale
Un famoso problema dei grafi riguarda la copertura dei vertici.
Facciamo un esempio, l’azienda Google deve gestire migliaia di richieste al secondo il più rapidamente possibile mantenendo i costi dell’infrastruttura bassi.
Quando un utente cerca qualcosa su google la richiesta viene inoltrata ad un server tra i tanti che si occuperà internamente di comunicare con il server che ha le informazioni richieste.
Per comunicare i server necessitano dei router,
ogni server deve essere connesso ad almeno un router
Questo è un problema di ottimizzazione fondamentale per ridurre i costi e aumentare l'efficienza della rete.
La rete dei server si può rappresentare con questa struttura chiamata grafo.
Per semplificare possiamo trasformare i server in dei punti (o nodi).
Una coppia di nodi connessi tra loro formano a loro volta un arco, e quindi, un grafo è formato da tanti archi interconnessi tra loro.
Per andare a risolvere il problema di ottimizzazione di questi vari grafi, andremo a coprire la minor quantità di nodi possibili per coprire i vertici.
E considerando tutti gli archi in sequenza arbitraria, e se un arco non risulta coperto allora selezionando entrambi i suoi estremi, dovremmo riuscire a soddisfare questa richiesta.
[Mentre l'animazione colora i nodi]
I nodi coperti sono quelli che si colorano di rosso
[Momento animazione]
Ci sono ovviamente molti altri modi (forse anche più ottimali) per coprire i vertici, ovviamente, ma pensavamo che questo fosse il più interessante.
Grazie per l'attenzione!