„Algoritmusok és gráfok” változatai közötti eltérés

← Régebbi szerkesztés Újabb szerkesztés →

VizuálisWikiszöveges

@@ 48. sor: / 48. sor: @@
 A félév során egy ZH van, melyen 60 pontot lehet elérni.
+=== NZH 2018. ===
+=====1. feladat=====
+Igaz-e, hogy ha egy algoritmus lépésszáma 100×n<sup>2</sup>+10<sup>10</sup>×n+17, akkor az algoritmus lépésszáma O(n<sup>2</sup>)? Ha úgy véli, hogy ez igaz, akkor megfelelő c konstans és n<sub>0</sub> küszöbérték megadásával lássa ezt be, ha pedig úgy véli, hogy hamis, akkor bizonyítsa be ezt.
+=====2. feladat=====
+Egy kezdetben üres, 11 méretű hash táblába nyílt címzéssel, lineáris próbával  szúrtunk be néhány egész számot, majd kettőt közülük kitöröltünk, így az alábbi állapotot kaptuk. (* jelöli a törölt cellákat, a kitöltetlen cellák mindvégig üresek voltak) A használt hash függvény a h(K) = K maradéka 11-gyel osztva függvény volt.
+{| class="wikitable"
+|-
+! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10
+|-
+| 11 || 1  || 26 || * || 15 ||    || 6  || * ||    ||    || 10
+|}
+<br />
+a, Mi lehetett az a 30-nál kisebb pozitív egész szám, amit a 7-es cellából töröltünk?<br />
+Az összes lehetőséget adja meg!<br />
+b, Mi lehetett az a 30-nál kisebb pozitív egész szám amit a 3-as cellából töröltünk?<br />
+Az összes lehetőséget adja meg!
+=====3. feladat=====
+Egy bináris keresőfában az 1, 3, 8, 9, 10, 11, 13, 14 számokat tároljuk valamilyen elrendezésben és tudjuk, hogy amikor a 10-et keressük akkor a keresés során először a 3-as számot látjuk, utána a 13-at, majd a 9-et, végül pedig a 10-et. Rajzolja fel azt a 8 csúcsú bináris keresőfát, ahol ez megtörténhetett, majd lássa be, hogy a fa csak így nézhet ki.
+=====4. feladat=====
+Egy n elemű rendezett tömbben pontosan három különböző érték szerepel. Adjon O(log n) lépésszámú algoritmust ennek a három értéknek a megkeresésére. Például ha az input 0, 0, 1, 1, 1, 8 akkor az elvárt kimenet 0, 1, 8.
+=====5. feladat=====
+Egy szomszédossági mátrixával adott n csúcsú, egyszerű, irányított G gráfban minden csúcs színes: piros vagy kék. A csúcsok színei egy, a csúcsokkal indexelt S tömbben adottak. Adott továbbá két kijelölt csúcs, s (ez a csúcs piros) és t (ez a csúcs kék) és szeretnénk eldönteni, hogy van-e olyan irányított út s-ből t-be melyen a csúcsok felváltva pirosak és kékek. (Azaz minden páratlanadik csúcs piros, minden párosadik csúcs kék.) Úgy akarjuk megoldani ezt a feladatot, hogy módosítjuk G szomszédossági mátrixát oly módon, hogy ezután egy tanult algoritmus egyszeri futtatásával megkaphassuk az eredményt. Adjon O(n<sup>2</sup>) lépésszámú algoritmust, ami megfelelően módosítja a szomszédossági mátrixot, majd alkalmazza a megfelelő tanult algoritmust.
+=====6. feladat=====
+Éllistájával adott egy n csúcsú, 2018n élű, egyszerű, irányítatlan gráf. Adjon   O(n log n) lépésszámú algoritmust annak eldöntésére, hogy van-e két olyan csúcs a gráfban, melyek fokszáma eggyel tér el.
 === Vizsga ===
 TODO