Algoritmusok és gráfok ZH 2018 - Laptörténet

Gyöngyösi Máté: MintaZH linkjének eltávolítása, mivel az a tantárgyi oldalon már fel van tüntetve

2022-11-15T15:03:29Z

MintaZH linkjének eltávolítása, mivel az a tantárgyi oldalon már fel van tüntetve

← Régebbi változat		A lap 2022. november 15., 17:03-kori változata
47. sor:		47. sor:
	====6. feladat====		====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.		É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.
	~~===Minta NZH 2018.===~~
	* [[:Media:algraf-2018-mintaZH.pdf\|minta ZH 2018.]]

Pócz Gergely: /* Minta NZH 2018. */ hivatkozás javítása

2018-12-12T17:51:24Z

Minta NZH 2018.: hivatkozás javítása

← Régebbi változat		A lap 2018. december 12., 19:51-kori változata
48. sor:		48. sor:
	É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.		É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.
	===Minta NZH 2018.===		===Minta NZH 2018.===
	* [[:~~File~~:algraf-2018-mintaZH.pdf\|minta ZH 2018.]]		* [[:Media:algraf-2018-mintaZH.pdf\|minta ZH 2018.]]

Pócz Gergely: mintaZH2018 hozzáadása

2018-12-12T17:49:36Z

mintaZH2018 hozzáadása

← Régebbi változat		A lap 2018. december 12., 19:49-kori változata
47. sor:		47. sor:
	====6. feladat====		====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.		É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.
			===Minta NZH 2018.===
			* [[:File:algraf-2018-mintaZH.pdf\|minta ZH 2018.]]

Pócz Gergely: /* 2. feladat */ hash tábla javítása

2018-12-12T17:45:56Z

2. feladat: hash tábla javítása

← Régebbi változat		A lap 2018. december 12., 19:45-kori változata
33. sor:		33. sor:
	! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10		! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10
	\|-		\|-
	\| 11 \|\| 1 \|\| 26 \|\| * \|\| 15 \|\| \|\| 6 \|\| * \|\| \|\| \|\| 10		\| 11 \|\| 1 \|\| 26 \|\| * \|\| 15 \|\| 16 \|\| 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?		* 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?		* 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====		====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.		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.

Pócz Gergely: NZH 2018 javítás, NPZH 2018 hozzáadása

2018-12-12T17:44:44Z

NZH 2018 javítás, NPZH 2018 hozzáadása

← Régebbi változat		A lap 2018. december 12., 19:44-kori változata
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"		{\| 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.

Pompos Balázs: Új oldal, tartalma: „=== NZH 2018. === =====1. feladat===== Igaz-e, hogy ha egy algoritmus lépésszáma 100×n²+10¹⁰×n+17, akkor az algoritmus lépésszáma O(n^…”

2018-12-11T02:21:33Z

Új oldal, tartalma: „=== NZH 2018. === =====1. feladat===== Igaz-e, hogy ha egy algoritmus lépésszáma 100×n2+1010×n+17, akkor az algoritmus lépésszáma O(n…”

Új lap

=== NZH 2018. ===
=====1. feladat=====
Igaz-e, hogy ha egy algoritmus lépésszáma 100×n2+1010×n+17, akkor az algoritmus lépésszáma O(n2)? Ha úgy véli, hogy ez igaz, akkor megfelelő c konstans és n0 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
|}

 
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 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(n2) 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.