Algoritmusok és gráfok ZH 2018

NZH 2018.

1. feladat

Igaz-e, hogy ha egy algoritmus lépésszáma Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 100\cdot n^22+10^{10}\cdot n+17} , akkor az algoritmus lépésszáma $O(n^{2})$? Ha úgy véli, hogy ez igaz, akkor megfelelő $c$ konstans és $n_{0}$ 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 $h(K)=K$ maradéka $11$-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 $30$-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 $30$-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 $1,3,8,9,10,11,13,14$ számokat tároljuk valamilyen elrendezésben és tudjuk, hogy amikor a Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 10} -et keressük akkor a keresés során először a Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 3} -as számot látjuk, utána a Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 13} -at, majd a Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 9} -et, végül pedig a Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n} elemű rendezett tömbben pontosan 3 különböző érték szerepel. Adjon Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(log n)} lépésszámú algoritmust ennek a 3 értéknek a megkeresésére. Például ha az input Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 0, 0, 1, 1, 1, 8} akkor az elvárt kimenet Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 0, 1, 8} .

5. feladat

Egy szomszédossági mátrixával adott Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n} csúcsú, egyszerű, irányított Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle G} gráfban minden csúcs színes: piros vagy kék. A csúcsok színei egy, a csúcsokkal indexelt Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle S} tömbben adottak. Adott továbbá 2 kijelölt csúcs, Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle s} (ez a csúcs piros) és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle t} (ez a csúcs kék) és szeretnénk eldönteni, hogy van-e olyan irányított út Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle s} -ből Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(n^2)} 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n} csúcsú, Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 2018n} élű, egyszerű, irányítatlan gráf. Adjon Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(n log n)} 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(n^2)} .

• a, Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 2^{17}n^2+2018^2-100n log n}
• b, Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \frac{10n^3}{log n}-10n^2}

Válassza ki, hogy melyik az és erre bizonyítsa is ezt be megfelelő Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle c} konstans és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n_0} 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle h(K)=K} maradéka Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 11} -gyel osztva függvény volt.

0	1	2	3	4	5	6	7	8	9	10
11	1	26	*	15	16	6	*			10

• a, Mely cellákas és milyen sorrendbe járjuk be ebben a táblában a Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 4} -es szám keresése során?
• b, Mely cellákas és milyen sorrendbe járjuk be ebben a táblában a Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 4} -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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 3, 10, 4, 8, 7, 9} 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n} különböző egész számot tartalmaz. Adjon Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(n log n)} 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n} csúcsú, egyszerű, irányított Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle G} 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle S} tömbben adottak. A 2 színtelen csúcs Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle s} és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle t} és az a célunk, hogy megkeressük az Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle s} -ből Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle t} -be vezető legrövidebb egyszínű út hosszát. Adjon Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(n^2)} 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 $n$ csúcsú, $2018n$ élű egyszerű, irányított gráf. Adjon $O(n)$ 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.