Algoritmusok és gráfok

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
Tantárgyi adatlap
Tárgyhonlap

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.

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²)? Ha úgy véli, hogy ez igaz, akkor megfelelő c konstans és n₀ 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.

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(n²) 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

TODO

Tippek

TODO

Kedvcsináló

TODO