„Algoritmusok és gráfok ZH 2018” változatai közötti eltérés
Új oldal, tartalma: „=== 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>…” |
NZH 2018 javítás, NPZH 2018 hozzáadása |
||
| 1. sor: | 1. sor: | ||
=== NZH 2018. === | ===NZH 2018.=== | ||
====1. feladat==== | |||
Igaz-e, hogy ha egy algoritmus lépésszáma | 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==== | |||
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 | 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" | {| class="wikitable" | ||
|- | |- | ||
| 11. sor: | 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==== | ||
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==== | ||
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 | ====6. 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á | ===NPZH 2018.=== | ||
====1. feladat==== | |||
Éllistájával adott egy n csúcsú, 2018n élű, egyszerű, irányítatlan gráf. Adjon | 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. | |||
A lap 2018. december 12., 18:44-kori változata
NZH 2018.
1. feladat
Igaz-e, hogy ha egy algoritmus lépésszáma , akkor az algoritmus lépésszáma ? Ha úgy véli, hogy ez igaz, akkor megfelelő konstans és 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 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 maradéka -gyel osztva függvény volt.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 11 | 1 | 26 | * | 15 | 6 | * | 10 |
- a, Mi lehetett az a -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.
- b, Mi lehetett az a -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.
3. feladat
Egy bináris keresőfában az számokat tároljuk valamilyen elrendezésben és tudjuk, hogy amikor a -et keressük akkor a keresés során először a -as számot látjuk, utána a -at, majd a -et, végül pedig a -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 elemű rendezett tömbben pontosan 3 különböző érték szerepel. Adjon lépésszámú algoritmust ennek a 3 értéknek a megkeresésére. Például ha az input akkor az elvárt kimenet .
5. feladat
Egy szomszédossági mátrixával adott csúcsú, egyszerű, irányított gráfban minden csúcs színes: piros vagy kék. A csúcsok színei egy, a csúcsokkal indexelt tömbben adottak. Adott továbbá 2 kijelölt csúcs, (ez a csúcs piros) és (ez a csúcs kék) és szeretnénk eldönteni, hogy van-e olyan irányított út -ből -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 szomszédossági mátrixát oly módon, hogy ezután egy tanult algoritmus egyszeri futtatásával megkaphassuk az eredményt. Adjon 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 csúcsú, élű, egyszerű, irányítatlan gráf. Adjon 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.
NPZH 2018.
1. feladat
Az alábbi futási idők közül pontosan egyikre igaz, hogy .
- a,
- b,
Válassza ki, hogy melyik az és erre bizonyítsa is ezt be megfelelő konstans és 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 maradéka -gyel osztva függvény volt.
| 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 -es szám keresése során?
- b, Mely cellákas és milyen sorrendbe járjuk be ebben a táblában a -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 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 különböző egész számot tartalmaz. Adjon 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 csúcsú, egyszerű, irányított 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 tömbben adottak. A 2 színtelen csúcs és és az a célunk, hogy megkeressük az -ből -be vezető legrövidebb egyszínű út hosszát. Adjon 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 csúcsú, élű egyszerű, irányított gráf. Adjon 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.
