Pages: [1]   Go Down
Print
Author Topic: Argomenti da studiare  (Read 2892 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
marco
Apprendista Forumista
**
Offline Offline

Posts: 212


« on: 26-01-2009, 16:50:22 »

Ragazzi ma ttt i lemmi con le seguenti dim della 2° parte deicammini minimi si devono studiare...?!?!?!  cry
Logged
Domenico Cantone
Moderator
Apprendista Forumista
*****
Offline Offline

Gender: Male
Posts: 345



« Reply #1 on: 26-01-2009, 17:22:14 »

Ragazzi ma ttt i lemmi con le seguenti dim della 2° parte deicammini minimi si devono studiare...?!?!?!  cry

Mi aspetto che conosciate TUTTI gli enunciati dei lemmi, ma solo le dimostrazioni viste a lezione.
Logged
marco
Apprendista Forumista
**
Offline Offline

Posts: 212


« Reply #2 on: 26-01-2009, 17:24:40 »

Grazie prof
Logged
chief dr.Cox
Forumista
***
Offline Offline

Posts: 552



« Reply #3 on: 27-01-2009, 10:49:18 »

le dimostrazioni sono quindi quelle presenti nelle slide del corso, giusto?
Logged

Microsoft Student Partner
KingDavid
Forumista
***
Offline Offline

Posts: 788


Alla fine [...] tutta la realtà è binaria.


« Reply #4 on: 27-01-2009, 16:42:30 »

Qualcuno potrebbe elencarmi i teoremi visti a lezione? Magari riferendo i numeri di pagina. Grazie
Logged

Basti pensare che un ipotetico quadrato di specchi, lungo 200 chilometri per ogni lato, potrebbe produrre tutta l'energia necessaria all'intero pianeta.
(Carlo Rubbia)
EL TIBURON
Matricola
*
Offline Offline

Gender: Male
Posts: 90



« Reply #5 on: 29-01-2009, 16:11:43 »

Quindi nessuno saprebbe indicarmi se il prof ha fatto a lezione tutte le dimostrazioni dei lemmi nel secondo blocco di slide?

Help.
Logged

Eres lo que quieres ser.
Dott.Andrea
Guest
« Reply #6 on: 29-01-2009, 16:53:10 »

Mi accodo alla richiesta... Sarebbe importante sapere con precisione...
Logged
KingDavid
Forumista
***
Offline Offline

Posts: 788


Alla fine [...] tutta la realtà è binaria.


« Reply #7 on: 30-01-2009, 15:11:15 »

Allora, qui di sotto indico con dei numeri e dei riferimenti alle slide i lemmi. Spero che qualcuno così risponda:
N.B. Non ho elencato tutti i lemmi.

A)  Shortest Paths 1
      1) Condizione necessaria e sufficiente perchè un grafo pesato (G,w) ammetta cammini minimi da una
                     sorgente s è che non vi sia alcun ciclo di peso negativo raggiungibile da s. (pag. 7/13)
       
       2) Proprieà. MIN_PATHS(G;s)!=0 ==> PATHS(G's;s)  = MIN_PATHS(G;s)  (pag. 11/13)

B)  Shortest Paths 2
      3)Durante l'esecuzione di GSSSP(G,s,w), si ha:
                    a) La funzione d decresce monotonicamente
                    b) Vale sempre d >= dGs
                    (anche in assenza di cammini minima da s) (pag. 4/22)
     
      4) Pd != 0 <==> (V (u,v)€ E) d[v] <= d[ u ]+w(u,v) (pag. 5/22)

      5) Condizione necessaria e suffi. xkè l'esecuzione di GSSSP(G,s,w) termini è che d=δGs
                    (pag. 6/22)

      6) Supponiamo che (G,w) ammetta cammini minimi da una sorgente s.
                     Siano d:V -> R U {+inf} e Pred: V -> V U {NIL} e sia
                     T=(VT,ET) il grafo indotto da Pred, con
                     VT={x€V : d[ x ] != +inf.} e ET={(Pred[ x ],x): x€VT \ {s} }
                     ecc. (pag. 6/22)
       7) Se π: s ----->u -> v è cammino minimo da s a v in (G,w) e ad un certo punto di un'esecuzione di
                     GSSSP(G,w,s) vale d[ u ]=δGs(u), allora dopo l'esecuzione di RELAX (u,v;w) varrà
                     d[v] = δGs(v)  (pag. 11/22)
« Last Edit: 30-01-2009, 15:19:27 by KingDavid » Logged

Basti pensare che un ipotetico quadrato di specchi, lungo 200 chilometri per ogni lato, potrebbe produrre tutta l'energia necessaria all'intero pianeta.
(Carlo Rubbia)
Domenico Cantone
Moderator
Apprendista Forumista
*****
Offline Offline

Gender: Male
Posts: 345



« Reply #8 on: 30-01-2009, 16:56:01 »

Allora, qui di sotto indico con dei numeri e dei riferimenti alle slide i lemmi. Spero che qualcuno così risponda:
N.B. Non ho elencato tutti i lemmi.

A)  Shortest Paths 1
      1) Condizione necessaria e sufficiente perchè un grafo pesato (G,w) ammetta cammini minimi da una
                     sorgente s è che non vi sia alcun ciclo di peso negativo raggiungibile da s. (pag. 7/13)
       
       2) Proprieà. MIN_PATHS(G;s)!=0 ==> PATHS(G's;s)  = MIN_PATHS(G;s)  (pag. 11/13)

B)  Shortest Paths 2
      3)Durante l'esecuzione di GSSSP(G,s,w), si ha:
                    a) La funzione d decresce monotonicamente
                    b) Vale sempre d >= dGs
                    (anche in assenza di cammini minima da s) (pag. 4/22)
     
      4) Pd != 0 <==> (V (u,v)€ E) d[v] <= d[ u ]+w(u,v) (pag. 5/22)

      5) Condizione necessaria e suffi. xkè l'esecuzione di GSSSP(G,s,w) termini è che d=δGs
                    (pag. 6/22)

      6) Supponiamo che (G,w) ammetta cammini minimi da una sorgente s.
                     Siano d:V -> R U {+inf} e Pred: V -> V U {NIL} e sia
                     T=(VT,ET) il grafo indotto da Pred, con
                     VT={x€V : d[ x ] != +inf.} e ET={(Pred[ x ],x): x€VT \ {s} }
                     ecc. (pag. 6/22)
       7) Se π: s ----->u -> v è cammino minimo da s a v in (G,w) e ad un certo punto di un'esecuzione di
                     GSSSP(G,w,s) vale d[ u ]=δGs(u), allora dopo l'esecuzione di RELAX (u,v;w) varrà
                     d[v] = δGs(v)  (pag. 11/22)


In classe sono stati dimostrati tutti i lemmi citati sopra AD ECCEZIONE del Lemma 6:

Quote
      6) Supponiamo che (G,w) ammetta cammini minimi da una sorgente s.
                     Siano d:V -> R U {+inf} e Pred: V -> V U {NIL} e sia
                     T=(VT,ET) il grafo indotto da Pred, con
                     VT={x€V : d[ x ] != +inf.} e ET={(Pred[ x ],x): x€VT \ {s} }
                     ecc. (pag. 6/22)
Logged
KingDavid
Forumista
***
Offline Offline

Posts: 788


Alla fine [...] tutta la realtà è binaria.


« Reply #9 on: 30-01-2009, 17:09:46 »

perfetto grazie 
Logged

Basti pensare che un ipotetico quadrato di specchi, lungo 200 chilometri per ogni lato, potrebbe produrre tutta l'energia necessaria all'intero pianeta.
(Carlo Rubbia)
Pages: [1]   Go Up
Print
Jump to: