Pages: [1]   Go Down
Print
Author Topic: Dubbio  (Read 2091 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« on: 04-02-2010, 16:40:17 »

Raga ho visto che in alcuni esercizi si chiede di dimostrare la correttezza degli algoritmi di Bellman-Ford e Dijkstra... sul libro stanno dei teoremi ad-hoc mentre a lezione e' stata dimostrata la correttezza di OGSSSP e poi fatto notare che Bellman-Ford rilassa tutti gli archi e dopo al piu' |V|-1 iterazioni del ciclo esterno avremo che d = \delta(selezioniamo tutti i nodi) mentre per Dijkstra abbiamo dimostrato che la scelta del nodo che al momento ha peso minimo e' una scelta gready corretta...

secondo voi negli esercizi di cui parlo e' possibile dimostrare la correttezza proprio come fatto a lezione?
Logged
Domenico Cantone
Moderator
Apprendista Forumista
*****
Offline Offline

Gender: Male
Posts: 345



« Reply #1 on: 04-02-2010, 17:24:00 »

Raga ho visto che in alcuni esercizi si chiede di dimostrare la correttezza degli algoritmi di Bellman-Ford e Dijkstra... sul libro stanno dei teoremi ad-hoc mentre a lezione e' stata dimostrata la correttezza di OGSSSP e poi fatto notare che Bellman-Ford rilassa tutti gli archi e dopo al piu' |V|-1 iterazioni del ciclo esterno avremo che d = \delta(selezioniamo tutti i nodi) mentre per Dijkstra abbiamo dimostrato che la scelta del nodo che al momento ha peso minimo e' una scelta gready corretta...

secondo voi negli esercizi di cui parlo e' possibile dimostrare la correttezza proprio come fatto a lezione?

Sì, è possibile ...
Logged
Pandemia000
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.714


Γνῶθι Σεαυτόν


« Reply #2 on: 04-02-2010, 18:17:24 »

Dijkstra è stato praticamente dimostrato (dimostrazione di OGSSSP più dimostrazione della selta greedy)
Per Bellman-Ford il meccanismo è identico: dimostrazione di OGSSSP più la dimostrazione che i duei cicli for obbediscono alla scelta di OGSSSP)
Logged

La disumanità del computer sta nel fatto che, una volta programmato e messo in funzione, si comporta in maniera perfettamente onesta. (Isaac Asimov)
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #3 on: 05-02-2010, 15:09:02 »

Grazie per le risposte  pray
Logged
Pages: [1]   Go Up
Print
Jump to: