„Algoritmuselmélet - Vizsga, 2013.05.30.” változatai közötti eltérés
| 3. sor: | 3. sor: | ||
==2013.06.06. vizsga megoldásai== | ==2013.06.06. vizsga megoldásai== | ||
===1. Feladat=== | ===1. Feladat=== | ||
Ebben a feladatban a Floyd algoritmussal kapcsolatos kérdésekre kell válaszolnia. (A Floyd-algoritmus egy grában minden pontpárra meghatározza a köztük levő legrövidebb út hosszát.) | |||
'''(a)''' Mit jelöl az <math> F_k </math> mátrix <math> F_k[i,j] </math> eleme? | |||
'''(b)''' Hogyan kell kiszámolni az <math> F_{k-1} </math> mátrixból az <math> F_k </math> mátrixot? | |||
'''(c)''' Igazolja, hogy ez a kiszámítási mód helyes! | |||
'''(d)''' Mennyi a lépésszáma a '''(b)''' lépés egyszeri végrehajtásának? (A lépésszámot nem kell igazolni.) | |||
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |szöveg= | ||
'''a)''' <math> F_k[i,j] </math> azon <math> i \rightarrow j </math> utak legrövidebbjeinek a hosszát tartalmazza, amelyek közbülső pontjai <math>k</math>-nál nem nagyobb sorszámúak. ''(Magyarul: Az <math> F_k[i,j] </math> azt mondja meg, hogy <math>i</math>-ből <math>j</math>-be mennyi a legrövidebb út összsúlya, ha csak az első <math>k</math> darab csúcsot használtuk.)'' | |||
'''b)''' <math> F_k[i,j]:=min\left \{ F_{k-1}[i,k]+F_{k-1}[k,j],F_{k-1}[i,j]\right \} </math> ''<math>(</math>Vagyis vagy az <math> i \rightarrow k \rightarrow j </math> lesz a legrövidebb út, vagy "marad a régi" <math> i \rightarrow j .)</math>'' | |||
'''c)''' Tulajdonképpen az előzőből következik. Hiszen vagy nem változik az új csúccsal a legrövidebb út a 2 pont között <math> (i \rightarrow j) </math>, vagy ha igen, akkor az a <math> (i \rightarrow k) + (k \rightarrow j) </math> lesz az. | |||
'''d)''' <math> O(n^2) </math>. ''<math>(</math>Maga az algoritmus <math>O(n^3)</math>, de csúcsonként <math> O(n^2) </math>, vagyis <math> n \cdot O(n^2) = O(n^3) ).</math>'' | |||
}} | }} | ||