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

1. sor:

=== NZH 2018. ===

===NZH 2018.===

=====1. feladat=====

====1. feladat====

Igaz-e, hogy ha egy algoritmus lépésszáma ~~100×n~~<~~sup>2</sup~~>+10~~~~10</~~sup~~>~~×n+17~~, akkor az algoritmus lépésszáma O(n~~~~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.

Igaz-e, hogy ha egy algoritmus lépésszáma <math>100\cdot n^22+10^{10}\cdot n+17</math>, akkor az algoritmus lépésszáma <math>O(n^2)</math>? Ha úgy véli, hogy ez igaz, akkor megfelelő <math>c</math> konstans és <math>n_0</math> 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=====

====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.

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 2-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 <math>h(K)=K</math> maradéka <math>11</math>-gyel osztva függvény volt.

{| class="wikitable"

|-

11. sor:

|}

~~ ~~

* a, Mi lehetett az a <math>30</math>-nál kisebb pozitív egész szám, amit a 7-es cellából töröltünk? Az összes lehetőséget adja meg.

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?~~ ~~

* b, Mi lehetett az a <math>30</math>-nál kisebb pozitív egész szám amit a 3-as cellából töröltünk? Az összes lehetőséget adja meg.

Az összes lehetőséget adja meg~~! ~~

====3. feladat====

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?~~ ~~

Egy bináris keresőfában az <math>1, 3, 8, 9, 10, 11, 13, 14</math> számokat tároljuk valamilyen elrendezésben és tudjuk, hogy amikor a <math>10</math>-et keressük akkor a keresés során először a <math>3</math>-as számot látjuk, utána a <math>13</math>-at, majd a <math>9</math>-et, végül pedig a <math>10</math>-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.

Az összes lehetőséget adja meg!

====4. feladat====

=====3. feladat=====

Egy <math>n</math> elemű rendezett tömbben pontosan 3 különböző érték szerepel. Adjon <math>O(log n)</math> lépésszámú algoritmust ennek a 3 értéknek a megkeresésére. Például ha az input <math>0, 0, 1, 1, 1, 8</math> akkor az elvárt kimenet <math>0, 1, 8</math>.

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.

====5. feladat====

=====4. feladat=====

Egy szomszédossági mátrixával adott <math>n</math> csúcsú, egyszerű, irányított <math>G</math> gráfban minden csúcs színes: piros vagy kék. A csúcsok színei egy, a csúcsokkal indexelt <math>S</math> tömbben adottak. Adott továbbá 2 kijelölt csúcs, <math>s</math> (ez a csúcs piros) és <math>t</math> (ez a csúcs kék) és szeretnénk eldönteni, hogy van-e olyan irányított út <math>s</math>-ből <math>t</math>-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 <math>G</math> szomszédossági mátrixát oly módon, hogy ezután egy tanult algoritmus egyszeri futtatásával megkaphassuk az eredményt. Adjon <math>O(n^2)</math> lépésszámú algoritmust, ami megfelelően módosítja a szomszédossági mátrixot, majd alkalmazza a megfelelő tanult algoritmust.

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.

====6. feladat====

=====5. feladat=====

Éllistájával adott egy <math>n</math> csúcsú, <math>2018n</math> élű, egyszerű, irányítatlan gráf. Adjon <math>O(n log n)</math> lépésszámú algoritmust annak eldöntésére, hogy van-e 2 olyan csúcs a gráfban, melyek fokszáma eggyel tér el.

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~~~~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.

===NPZH 2018.===

=====6. feladat=====

====1. 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.

Az alábbi futási idők közül pontosan egyikre igaz, hogy <math>O(n^2)</math>.

* a, <math>2^{17}n^2+2018^2-100n log n</math>

* b, <math>\frac{10n^3}{log n}-10n^2</math>

Válassza ki, hogy melyik az és erre bizonyítsa is ezt be megfelelő <math>c</math> konstans és <math>n_0</math> küszöb megadásával.

====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 2-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 <math>h(K)=K</math> maradéka <math>11</math>-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

|}

* a, Mely cellákas és milyen sorrendbe járjuk be ebben a táblában a <math>4</math>-es szám keresése során?

* b, Mely cellákas és milyen sorrendbe járjuk be ebben a táblában a <math>4</math>-es szám beszúrása során?

====3. feladat====

Egy bináris keresőfa preorder bejárása során a fa csúcsait <math>3, 10, 4, 8, 7, 9</math> sorrendben látogatjuk meg. Rajzolja fel ezt a 6 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====

Adott 2 tömb, mindegyik <math>n</math> különböző egész számot tartalmaz. Adjon <math>O(n log n)</math> lépésszámú algoritmust az összes olyan szám megkeresésére, amik mindkét tömbben benne vannak.

====5. feladat====

Egy szomszédossági mátrixával adott <math>n</math> csúcsú, egyszerű, irányított <math>G</math> gráfban 2 csúcs kivételével minden csúcs színes: piros vagy kék vagy zöld. A csúcsok színei egy, a csúcsokkal indexelt <math>S</math> tömbben adottak. A 2 színtelen csúcs <math>s</math> és <math>t</math> és az a célunk, hogy megkeressük az <math>s</math>-ből <math>t</math>-be vezető legrövidebb egyszínű út hosszát. Adjon <math>O(n^2)</math> lépésszámú algoritmust, ami a szomszédossági mátrix (esetleg többszöri) módosításával és egy tanult algoritmus (esetleg többszöri) változtatás nélküli futtatásával megoldja ezt a feladatot.

====6. feladat====

Éllistájával adott egy <math>n</math> csúcsú, <math>2018n</math> élű egyszerű, irányított gráf. Adjon <math>O(n)</math> lépésszámú algoritmust, ami megkeresi a gráfban előforduló legnagyobb be-fokot és az összes olyan csúcsot, amibe ennyi él fut be.

@@ 1. sor: / 1. sor: @@
-=== NZH 2018. ===
+===NZH 2018.===
-=====1. feladat=====
+====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.
+Igaz-e, hogy ha egy algoritmus lépésszáma <math>100\cdot n^22+10^{10}\cdot n+17</math>, akkor az algoritmus lépésszáma <math>O(n^2)</math>? Ha úgy véli, hogy ez igaz, akkor megfelelő <math>c</math> konstans és <math>n_0</math> 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=====
+====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.
+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 2-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 <math>h(K)=K</math> maradéka <math>11</math>-gyel osztva függvény volt.
 {| class="wikitable"
 |-
@@ 11. sor: / 11. sor: @@
 |}
-<br />
+* a, Mi lehetett az a <math>30</math>-nál kisebb pozitív egész szám, amit a 7-es cellából töröltünk? Az összes lehetőséget adja meg.
-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 />
+* b, Mi lehetett az a <math>30</math>-nál kisebb pozitív egész szám amit a 3-as cellából töröltünk? Az összes lehetőséget adja meg.
-Az összes lehetőséget adja meg!<br />
+====3. feladat====
-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 />
+Egy bináris keresőfában az <math>1, 3, 8, 9, 10, 11, 13, 14</math> számokat tároljuk valamilyen elrendezésben és tudjuk, hogy amikor a <math>10</math>-et keressük akkor a keresés során először a <math>3</math>-as számot látjuk, utána a <math>13</math>-at, majd a <math>9</math>-et, végül pedig a <math>10</math>-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.
-Az összes lehetőséget adja meg!
+====4. feladat====
-=====3. feladat=====
+Egy <math>n</math> elemű rendezett tömbben pontosan 3 különböző érték szerepel. Adjon <math>O(log n)</math> lépésszámú algoritmust ennek a 3 értéknek a megkeresésére. Például ha az input <math>0, 0, 1, 1, 1, 8</math> akkor az elvárt kimenet <math>0, 1, 8</math>.
-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.
+====5. feladat====
-=====4. feladat=====
+Egy szomszédossági mátrixával adott <math>n</math> csúcsú, egyszerű, irányított <math>G</math> gráfban minden csúcs színes: piros vagy kék. A csúcsok színei egy, a csúcsokkal indexelt <math>S</math> tömbben adottak. Adott továbbá 2 kijelölt csúcs, <math>s</math> (ez a csúcs piros) és <math>t</math> (ez a csúcs kék) és szeretnénk eldönteni, hogy van-e olyan irányított út <math>s</math>-ből <math>t</math>-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 <math>G</math> szomszédossági mátrixát oly módon, hogy ezután egy tanult algoritmus egyszeri futtatásával megkaphassuk az eredményt. Adjon <math>O(n^2)</math> lépésszámú algoritmust, ami megfelelően módosítja a szomszédossági mátrixot, majd alkalmazza a megfelelő tanult algoritmust.
-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.
+====6. feladat====
-=====5. feladat=====
+Éllistájával adott egy <math>n</math> csúcsú, <math>2018n</math> élű, egyszerű, irányítatlan gráf. Adjon <math>O(n log n)</math> lépésszámú algoritmust annak eldöntésére, hogy van-e 2 olyan csúcs a gráfban, melyek fokszáma eggyel tér el.
-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.
+===NPZH 2018.===
-=====6. feladat=====
+====1. 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.
+Az alábbi futási idők közül pontosan egyikre igaz, hogy <math>O(n^2)</math>.
+* a, <math>2^{17}n^2+2018^2-100n log n</math>
+* b, <math>\frac{10n^3}{log n}-10n^2</math>
+Válassza ki, hogy melyik az és erre bizonyítsa is ezt be megfelelő <math>c</math> konstans és <math>n_0</math> küszöb megadásával.
+====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 2-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 <math>h(K)=K</math> maradéka <math>11</math>-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
+|}
+* a, Mely cellákas és milyen sorrendbe járjuk be ebben a táblában a <math>4</math>-es szám keresése során?
+* b, Mely cellákas és milyen sorrendbe járjuk be ebben a táblában a <math>4</math>-es szám beszúrása során?
+====3. feladat====
+Egy bináris keresőfa preorder bejárása során a fa csúcsait <math>3, 10, 4, 8, 7, 9</math> sorrendben látogatjuk meg. Rajzolja fel ezt a 6 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====
+Adott 2 tömb, mindegyik <math>n</math> különböző egész számot tartalmaz. Adjon <math>O(n log n)</math> lépésszámú algoritmust az összes olyan szám megkeresésére, amik mindkét tömbben benne vannak.
+====5. feladat====
+Egy szomszédossági mátrixával adott <math>n</math> csúcsú, egyszerű, irányított <math>G</math> gráfban 2 csúcs kivételével minden csúcs színes: piros vagy kék vagy zöld. A csúcsok színei egy, a csúcsokkal indexelt <math>S</math> tömbben adottak. A 2 színtelen csúcs <math>s</math> és <math>t</math> és az a célunk, hogy megkeressük az <math>s</math>-ből <math>t</math>-be vezető legrövidebb egyszínű út hosszát. Adjon <math>O(n^2)</math> lépésszámú algoritmust, ami a szomszédossági mátrix (esetleg többszöri) módosításával és egy tanult algoritmus (esetleg többszöri) változtatás nélküli futtatásával megoldja ezt a feladatot.
+====6. feladat====
+Éllistájával adott egy <math>n</math> csúcsú, <math>2018n</math> élű egyszerű, irányított gráf. Adjon <math>O(n)</math> lépésszámú algoritmust, ami megkeresi a gráfban előforduló legnagyobb be-fokot és az összes olyan csúcsot, amibe ennyi él fut be.