|
|
| 47. sor: |
47. sor: |
| === ZH === | | === ZH === |
| A félév során egy ZH van, melyen 60 pontot lehet elérni. | | A félév során egy ZH van, melyen 60 pontot lehet elérni. |
| | | ====Korábbi ZH-k==== |
| === NZH 2018. ===
| | *[[Algoritmusok és gráfok ZH 2018|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 === | | === Vizsga === |
| TODO | | TODO |
Algoritmusok és gráfok
|
|
|
| Tárgykód
|
VISZBA01
|
|
|
|
Általános infók
|
| Szak
|
üzemmérnök
|
| Kredit
|
5
|
| Ajánlott félév
|
1
|
| Keresztfélév
|
N/A
|
| Tanszék
|
SZIT
|
Követelmények
|
|
|
|
|
|
|
|
|
|
|
|
|
| NagyZH
|
1 db
|
| Házi feladat
|
nincs
|
| Vizsga
|
írásbeli
|
Elérhetőségek
|
| Levlista
|
N/A
|
|
|
|
|
|
|
|
|
Diszkrét matematika alapelemeinek elsajátítása, a problémamegoldó, algoritmikus gondolkodás készségének fejlesztése, alapvető feladattípusok és algoritmusaik elméleti hátterének megismerése. Gráfelmélet alapjainak áttekintése.
Követelmények
A szorgalmi időszakban
A félév folyamán egy zárthelyit íratunk. A félévvégi aláírás megszerzésének (vagyis a vizsgára bocsátásnak) a feltétele a zárthelyin legalább 40%-os teljesítmény elérése.
A vizsgaidőszakban
A vizsga írásbeli, a vizsga 40%-tól sikeres.
Félévvégi jegy
A vizsgajegyet a zárthelyi eredményéből és a vizsgán nyújtott teljesítményből alakítjuk ki olyan módon, hogy abba a zárthelyi eredménye 40 százalék, az írásbeli vizsga eredménye pedig 60 százalék erejéig számít bele.
Tematika
Előadások és gyakorlatok összefésült témája:
- algoritmusok bevezetés, motiváció, ordó
- rendező algoritmusok (összefésüléses, kiválasztásos, ládarendezés...)
- bináris keresőfa, fabejárások
- hash táblák
- gráfok
- szélességi keresés (BFS)
- mélységi keresés (DFS)
- irányított körmentes gráf (DAG)
- Bellman-Ford algoritmus
TODO folytatás
Segédanyagok
TODO
Számonkérések
Házi feladat
A félév során nincsen kötelező házi feladat.
ZH
A félév során egy ZH van, melyen 60 pontot lehet elérni.
Korábbi ZH-k
Vizsga
TODO
Tippek
TODO
Kedvcsináló
TODO
