Forum Informatica Unict

Vecchi ordinamenti ad esaurimento => Algoritmi 2 => Topic started by: marco on 26-01-2009, 16:50:22



Title: Argomenti da studiare
Post by: marco on 26-01-2009, 16:50:22
Ragazzi ma ttt i lemmi con le seguenti dim della 2° parte deicammini minimi si devono studiare...?!?!?!  :"-(


Title: Re:Argomenti da studiare
Post by: Domenico Cantone on 26-01-2009, 17:22:14
Ragazzi ma ttt i lemmi con le seguenti dim della 2° parte deicammini minimi si devono studiare...?!?!?!  :"-(

Mi aspetto che conosciate TUTTI gli enunciati dei lemmi, ma solo le dimostrazioni viste a lezione.


Title: Re:Argomenti da studiare
Post by: marco on 26-01-2009, 17:24:40
Grazie prof


Title: Re:Argomenti da studiare
Post by: chief dr.Cox on 27-01-2009, 10:49:18
le dimostrazioni sono quindi quelle presenti nelle slide del corso, giusto?


Title: Re:Argomenti da studiare
Post by: KingDavid on 27-01-2009, 16:42:30
Qualcuno potrebbe elencarmi i teoremi visti a lezione? Magari riferendo i numeri di pagina. Grazie


Title: Re:Argomenti da studiare
Post by: EL TIBURON 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.


Title: Re:Argomenti da studiare
Post by: Dott.Andrea on 29-01-2009, 16:53:10
Mi accodo alla richiesta... Sarebbe importante sapere con precisione...


Title: Re:Argomenti da studiare
Post by: KingDavid 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)


Title: Re:Argomenti da studiare
Post by: Domenico Cantone 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)


Title: Re:Argomenti da studiare
Post by: KingDavid on 30-01-2009, 17:09:46
perfetto grazie  .smile