„Algoritmuselmélet - Vizsga, 2013.05.30.” változatai közötti eltérés

← Régebbi szerkesztés

VizuálisWikiszöveges

@@ 3. sor: / 3. sor: @@
 ==2013.06.06. vizsga megoldásai==
 ===1. Feladat===
-TODO
+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
 |mutatott=<big>'''Megoldás'''</big>
 |szöveg=
-TODO
+'''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>''
 }}
@@ 23. sor: / 37. sor: @@
 *A fa levelei a gyökértől egyenlő távolságra vannak (vagyis a levelek 1 szinten vannak).
 *A belső csúcsokban mutatókat (M) és 1, vagy 2 kulcsot (S) tárolunk.
-**Ha a csúcsnak 2 fia van, akkor 2 mutatót, és egy kulcsot tárol. [[File:2_3_2.png|300px]]
+**Ha a csúcsnak 2 fia van, akkor 2 mutatót, és egy kulcsot tárol. [[File:Algel vizsga 2013tavasz V1 2 2fia.png|300px]]
 ***A bal részfában az elemek kisebbek, mint S1.
 ***A jobb részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1).
-**Ha a csúcsnak 3 fia van, akkor 3 mutatót, és 2 kulcsot tárol. [[File:2_3_3.png|400px]]
+**Ha a csúcsnak 3 fia van, akkor 3 mutatót, és 2 kulcsot tárol. [[File:Algel_vizsga_2013tavasz_V1_2_3fia.png|400px]]
 ***A bal részfában az elemek kisebbek, mint S1.
 ***A középső részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1), de kisebbek, mint S2.
 ***A jobb részfában az elemek nagyobb-egyenlőek, mint S2 (vagyis az 1. elem S2).
-:::::::::::::::::[[File:2_3_pelda.PNG|400px]]
 '''Adjon felső becslést a fa szintszámára n tárolt elem esetén, állítását bizonyítsa is!'''
 <math>log_2n+1\leq m \leq log_3n+1</math>, ahol <math>m</math> a fa szintszáma.
+$$$ Ez nem pont fordítva van a dián? $$$
 ''Bizonyítás:''