„Algoritmusok és gráfok” változatai közötti eltérés

(34 közbenső módosítás, amit 8 másik szerkesztő végzett, nincs mutatva)

5. sor:

|kredit=5

|felev=1

|kereszt=~~N/A~~

|kereszt=

|tanszék=SZIT

|~~vizsga~~=~~írásbeli~~

|kiszh=nincs

|nagyzh=1 db

|hf=nincs

|vizsga=írásbeli, javító szóbeli

|tad=https://portal.vik.bme.hu/kepzes/targyak/VISZBA01/

|targyhonlap=http://www.cs.bme.hu/~csima~~/algraf18~~/

|targyhonlap=http://www.cs.bme.hu/~csima/

|levlista=~~N/A~~ }}

|levlista= }}

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 '''ZH'''-n legalább elégséges (40%) teljesítése. Zh-n elérhető maximális pont: 16.

*'''Pótlási lehetőségek:'''

**A '''ZH''' pótlására két lehetősége is van a hallgatónak. A pót - illetve a pótpótzárthelyin. A pótzárthelyin lehetőség van akár javításra is (csak akkor, ha legalább 40%-ot előtte már elért), azonban, ha 40%-nál kevesebbet ér el, akkor az előző pontszáma törlődik. Az aláírása megmarad, de az új zárthelyi eredménye 40% lesz, és azt kell tovább vinnie a vizsgára. Pótpótzárthelyi már csak különeljárási díj fejében teljesíthető, és már nincs lehetőség a javításra, automatikusan az elért pont lesz az új eredmény.

=== A vizsgaidőszakban ===

A vizsga írásbeli, a vizsga 40%-tól sikeres.

*A vizsga írásbeli, a vizsga 40%-tól sikeres.

*Előfeltétele: aláírás megléte.

*Írásbeli vizsga, időtartama 100 perc. A vizsgán elérhető maximális pontszám 80 pont, mely 8 db 10 pontos feladatból jön össze.

=== 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.

*A jegyet 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%, az írásbeli vizsga eredménye pedig 60%-ban számít bele, és ehhez adjuk hozzá a szorgalmi pontszámát.

*Ponthatárok:

:{| class="wikitable" style="text-align: center; width: 110px; height: 40px;"

!Eredmény %!!Jegy

|-

|0 - 39|| 1

|-

|40 - 54|| 2

|-

|55 - 69|| 3

|-

|70 - 84|| 4

|-

|85 - 100|| 5

|}

== Tematika ==

~~Előadások és gyakorlatok összefésült témája~~:

=== Elaődásanyagok ===

* ~~algoritmusok bevezetés~~, ~~motiváció~~, ordó

* 2018 ősz (Berczédi Balázs kézzel írott előadásjegyzetei)

* rendező algoritmusok (összefésüléses, ~~kiválasztásos~~, ~~ládarendezés~~...)

#[[Media:Algraf_2018_ea_1.pdf | előadás, 2018.09.06]]

* bináris keresőfa, fabejárások

#[[Media:Algraf_2018_ea_2.pdf | előadás, 2018.09.13]]

* hash táblák

#[[Media:Algraf_2018_ea_3.pdf | előadás, 2018.09.27]]

* gráfok

#[[Media:Algraf_2018_ea_4.pdf | előadás, 2018.10.04]]

* szélességi keresés ~~(BFS)~~

#[[Media:Algraf_2018_ea_5.pdf | előadás, 2018.10.11]]

* mélységi keresés ~~(DFS)~~

#[[Media:Algraf_2018_ea_6.pdf | előadás, 2018.10.13]]

* irányított körmentes gráf ~~(DAG)~~

#[[Media:Algraf_2018_ea_7.pdf | előadás, 2018.10.18]]

* Bellman-Ford algoritmus

#[[Media:Algraf_2018_ea_8.pdf | előadás, 2018.10.25]]

~~TODO folytatás~~

#[[Media:Algraf_2018_ea_9.pdf | előadás, 2018.11.08]]

#[[Media:Algraf_2018_ea_10.pdf | előadás, 2018.11.15]]

#[[Media:Algraf_2018_ea_11.pdf | előadás, 2018.11.22]]

#[[Media:Algraf_2018_ea_12.pdf | előadás, 2018.11.29]]

#[[Media:Algraf_2018_ea_13.pdf | előadás, 2018.12.06]]

* 2019 ősz (Hivatalos jegyzetek)

#[[Media:Algraf_2019_ea_1.pdf | Algoritmus fogalma, pszeudokód, helyesség, lépésszám]]

#[[Media:Algraf_2019_ea_2.pdf | Kiválasztásos rendezés, ordó jelölés]]

#[[Media:Algraf_2019_ea_3.pdf | Beszúrásos rendezés és bináris keresés]]

#[[Media:Algraf_2019_ea_4.pdf | Összefésüléses rendezés]]

#[[Media:Algraf_2019_ea_5.pdf | Ládarendezés, tömb, lista, bináris fa, bináris keresőfa]]

#[[Media:Algraf_2019_ea_6.pdf | Bináris keresőfa műveletei, AVL-fa, hash]]

#[[Media:Algraf_2019_ea_7.pdf | Gráfok alapfogalmai, szomszédossági mátrix]]

#[[Media:Algraf_2019_ea_8.pdf | Összefüggőség, feszítőfa, szélességi bejárás]]

#[[Media:Algraf_2019_ea_9.pdf | Mélységi bejárás]]

#[[Media:Algraf_2019_ea_10.pdf | Topologikus sorrend, DAG-ság eldöntése]]

#[[Media:Algraf_2019_ea_11.pdf | Legrövidebb és leghosszabb út keresése DAG-ban; A legrövidebb út keresése általános esetben]]

#[[Media:Algraf_2019_ea_12.pdf | Dijkstra algoritmusa]]

#[[Media:Algraf_2019_ea_13.pdf | Minimális feszítőfa keresés, Prim és Kruskal algoritmusa]]

=== Gyakorlatanyagok ===

* 2018 ősz

#[[Media:elso_algo_ordo.pdf | Motiváció, ordó]]

#[[Media:masodik_rendezes_eleje.pdf | Rendező algoritmusok]]

#[[Media:harmadik_ismetles.pdf | Ismétlés (ordó, rendező)]]

#[[Media:otodik_lada_binkerfa.pdf | Ládarendezés, bináris keresőfa, fabejárások]]

#[[Media:hatodik_hash.pdf | Hash tábla]]

#[[Media:hetedik_graf.pdf | Gráfok]]

#[[Media:nyolcadik_bfs.pdf | BFS - szélességi keresés]]

#[[Media:tizedik_dfs.pdf | DFS - mélységi keresés]]

#[[Media:tizenegyedik_dag.pdf | DAG - irányított körmentes gráf]]

#[[Media:tizenkettedik_bf.pdf | Bellman-Ford-algoritmus]]

#[[Media:tizennegyedik_dijkstra_mst.pdf | Dijkstra-algoritmus, Prim-algoritmus]]

* 2019 ősz

#Pszeudokód, lépésszám: [[Media:Algraf_2019_gy_1.pdf | feladatsor]], [[Media:Algraf_2019_gy_1_sol.pdf | megoldások]]

#Pszeudokód, nagy ordó: [[Media:Algraf_2019_gy_2.pdf | feladatsor]], [[Media:Algraf_2019_gy_2_sol.pdf | megoldások]]

#Rendező algoritmusok: [[Media:Algraf_2019_gy_3.pdf | feladatsor]], [[Media:Algraf_2019_gy_3_sol.pdf | megoldások]]

#Összefésüléses rendezés, rendezéses feladatok: [[Media:Algraf_2019_gy_4.pdf | feladatsor]], [[Media:Algraf_2019_gy_4_sol.pdf | megoldások]]

#Ládarendezés, bináris fák bejárásai, bináris keresőfa: [[Media:Algraf_2019_gy_5.pdf | feladatsor]], [[Media:Algraf_2019_gy_5_sol.pdf | megoldások]]

#Bináris keresőfa, AVL-fa: [[Media:Algraf_2019_gy_6.pdf | feladatsor]], [[Media:Algraf_2019_gy_6_sol.pdf | megoldások]]

#Hash: [[Media:Algraf_2019_gy_7.pdf | feladatsor]], [[Media:Algraf_2019_gy_7_sol.pdf | megoldások]]

#Gráf, szomszédossági mátrix, szélességi bejárás: [[Media:Algraf_2019_gy_8.pdf | feladatsor]], [[Media:Algraf_2019_gy_8_sol.pdf | megoldások]]

#Mélységi bejárás, szöveges feladatok a bejárásokról: [[Media:Algraf_2019_gy_9.pdf | feladatsor]], [[Media:Algraf_2019_gy_9_sol.pdf | megoldások]]

#DAG, toplogikus sorrend, további szöveges feladatok a bejárásokról: [[Media:Algraf_2019_gy_10.pdf | feladatsor]], [[Media:Algraf_2019_gy_10_sol.pdf | megoldások]]

#Topologikus sorrendet használó lerövidebb/leghosszabb utas algo, Dijkstra: [[Media:Algraf_2019_gy_11.pdf | feladatsor]], [[Media:Algraf_2019_gy_11_sol.pdf | megoldások]]

#Prim és Kruskal algo, szöveges példák Dijkstra, Prim témában: [[Media:Algraf_2019_gy_12.pdf | feladatsor]], [[Media:Algraf_2019_gy_12_sol.pdf | megoldások]]

== Segédanyagok ==

~~TODO~~

~~== Számonkérések ==~~

~~=== Házi feladat ===~~

~~A félév során nincsen kötelező házi feladat.~~

=== ZH ===

=== Jegyzetek ===

~~A félév során egy ZH van, melyen 60 pontot lehet elérni~~.

*[[Media:BME-VIK-Algoritmusok_es_grafok-2018-19.pdf | 2018-as oktató által lektorált jegyzet]] - Pócz Gergő

=== ~~NZH 2018.~~ ===

=== További feladatok ===

~~=====1. feladat=====~~

*[[Media:Algraf-2018-extra.pdf | Extra szorgalmi feladatsor 2018]]

~~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.

*[[Media:Algraf_2019_extra.pdf | Extra szorgalmi feladatsor 2019]]

~~=====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~~

|}

~~ ~~

== ZH ==

~~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? ~~

*2018. ősz

~~Az összes lehetőséget adja meg! ~~

**[[Media:mintazh.pdf | mintafeladatok]]

~~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? ~~

**[[Algoritmusok és gráfok ZH 2018 | NZH és PZH egyben]]

~~Az összes lehetőséget adja meg!~~

***PDF-ben:

~~=====3~~. ~~feladat=====~~

****[[Media:algráf_ZH_2018-11-16_módosított.pdf | ZH (módosított változat)]]

~~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~~.

****[[Media:Algraf-2018-PZH.pdf | PZH]]

~~=====4~~. ~~feladat=====~~

*2019. ősz

~~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~~.

**[[Media:algráf_ZH_2019-ősz_minta.pdf | mintafeladatok]]

~~=====5~~. ~~feladat=====~~

**[[Media:algráf_ZH_2019-11-21.pdf | ZH]], [[Media:algráf_ZH_2019-11-21_megoldások.pdf | megoldások]]

~~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.

**[[Media:algráf_PZH_2019-12-05.pdf | PZH]], [[Media:algráf_PZH_2019-12-05_megoldások.pdf | megoldások]]

~~=====6~~. feladat~~=====~~

*2020. ősz

~~É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~~.

**ZH ([[Media:algráf_PZH_2020-11-19_kifejtős-feladatok.pdf |2. rész]])

~~=== Vizsga ===~~

*2021. ősz

~~TODO~~

**[[Media:algráf_ZH_2021-11-19.pdf | ZH]], [[Media:algráf_ZH_2021-11-19_megoldások.pdf | megoldások]]

**[[Media:algráf_PZH_2021-12-01.pdf | PZH]], [[Media:algráf_PZH_2021-12-01.pdf_megoldások.pdf | megoldások]]

*2022. ősz

**[[Media:algráf_ZH_2022-ősz_tanácsok.pdf | tanácsok]]

**[[Media:algráf_ZH_2022-11-24.pdf | ZH]], [[Media:algráf_ZH_2022-11-24_megoldások.pdf | megoldások]]

***Az 5. feladat leírása javítva és egyértelműsítve: ''"[...] Adjon O(n log n) lépésszámú algoritmust, ami eldönti, igaz-e, hogy mindegyik tömbben szereplő számnak a fele vagy a kétszerese szintén benne van a tömbben."''

== ~~Tippek~~ ==

== Vizsga ==

~~TODO~~

* 2018. ősz

** [[Media:minta_vizsga.pdf | mintafeladatok]]

** [[Media:Algraf-2018-vizsga-1.pdf | 1. vizsga (2018. december 19.)]]

** [[Media:Algraf-2018-vizsga-2.pdf | 2. vizsga (2019. január 4.)]]

** [[Media:Algraf-2018-vizsga-3.pdf | 3. vizsga (2019. január 9.)]]

** [[Media:Algraf_2018_v4.pdf| 4. vizsga (2019. január 16.)]]

* 2019. ősz

** [[Media:Algraf_2019_v1.pdf | 1. vizsga (2020. január 8.)]], [[Media:Algraf_2019_v1_sol.pdf | megoldások]]

** [[Media:Algraf_2019_v2.pdf | 2. vizsga (2020. január 15.)]], [[Media:Algraf_2019_v2_sol.pdf | megoldások]]

** [[Media:Algraf_2019_v3.pdf | 3. vizsga (2020. január 22.)]], [[Media:Algraf_2019_v3_sol.pdf | megoldások]]

** [[Media:Algraf_2019_v4.pdf | 4. vizsga (2020. január 29.)]], [[Media:Algraf_2019_v4_sol.pdf | megoldások]]

* 2020. ősz

** [[Media:algráf_vizsga_2020-12-22.pdf | 1. vizsga]]

** [[Media:algráf_vizsga_2021-01-05.pdf | 2. vizsga]]

** [[Media:algráf_vizsga_2021-01-12.pdf | 3. vizsga]]

** [[Media:algráf_vizsga_2021-01-19.pdf | 4. vizsga]]

* 2021. ősz

** [[Media:algráf_vizsga_2021-12-21.pdf | 1. vizsga]], [[Media:algráf_vizsga_2021-12-21_megoldások.pdf | megoldások]]

** [[Media:algráf_vizsga_2022-01-04.pdf | 2. vizsga]], [[Media:algráf_vizsga_2022-01-04_megoldások.pdf | megoldások]]

*** oktatói megjegyzés: ''2021-ben SzuperCsodásnak hívtam a DAG-os algoritmust a legrövidebb utak keresésére.''

** [[Media:algráf_vizsga_2022-01-11.pdf | 3. vizsga]], [[Media:algráf_vizsga_2022-01-11_megoldások.pdf | megoldások]]

** [[Media:algráf_vizsga_2022-01-18.pdf | 4. vizsga]], [[Media:algráf_vizsga_2022-01-18_megoldások.pdf | megoldások]]

* 2022. ősz

** [[Media:algráf_vizsga-tanácsok_2022-ősz.pdf | tanácsok]]

== Kedvcsináló ==

~~TODO~~

*[[Media:Algraf_2019_motivacio.pdf | Motivációs előadás 2019 ősz]]

*Animációk

**Bináris keresés: http://www.cs.armstrong.edu/liang/animation/web/BinarySearch.html

**Rendező algoritmusok: https://visualgo.net/bn/sorting?slide=1

**Összefésüléses rendezés eltáncolva: https://www.youtube.com/watch?v=XaqR3G_NVoo

**AVL-fa animáció: https://visualgo.net/bn/bst?slide=1

@@ 5. sor: / 5. sor: @@
 |kredit=5
 |felev=1
-|kereszt=N/A
+|kereszt=
 |tanszék=SZIT
-|vizsga=írásbeli
+|kiszh=nincs
 |nagyzh=1 db
 |hf=nincs
+|vizsga=írásbeli, javító szóbeli
 |tad=https://portal.vik.bme.hu/kepzes/targyak/VISZBA01/
-|targyhonlap=http://www.cs.bme.hu/~csima/algraf18/
+|targyhonlap=http://www.cs.bme.hu/~csima/
-|levlista=N/A  }}
+|levlista=  }}
 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 '''ZH'''-n legalább elégséges (40%) teljesítése. Zh-n elérhető maximális pont: 16.
+*'''Pótlási lehetőségek:'''
+**A '''ZH''' pótlására két lehetősége is van a hallgatónak. A pót - illetve a pótpótzárthelyin. A pótzárthelyin lehetőség van akár javításra is (csak akkor, ha legalább 40%-ot előtte már elért), azonban, ha 40%-nál kevesebbet ér el, akkor az előző pontszáma törlődik. Az aláírása megmarad, de az új zárthelyi eredménye 40% lesz, és azt kell tovább vinnie a vizsgára. Pótpótzárthelyi már csak különeljárási díj fejében teljesíthető, és már nincs lehetőség a javításra, automatikusan az elért pont lesz az új eredmény.
 === A vizsgaidőszakban ===
-A vizsga írásbeli, a vizsga 40%-tól sikeres.
+*A vizsga írásbeli, a vizsga 40%-tól sikeres.
+*Előfeltétele: aláírás megléte.
+*Írásbeli vizsga, időtartama 100 perc. A vizsgán elérhető maximális pontszám 80 pont, mely 8 db 10 pontos feladatból jön össze.
 === 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.
+*A jegyet 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%, az írásbeli  vizsga eredménye pedig  60%-ban számít bele, és ehhez adjuk hozzá a szorgalmi pontszámát.
+*Ponthatárok:
+:{| class="wikitable" style="text-align: center; width: 110px; height: 40px;"
+!Eredmény %!!Jegy
+|-
+|0 - 39|| 1
+|-
+|40 - 54|| 2
+|-
+|55 - 69|| 3
+|-
+|70 - 84|| 4
+|-
+|85 - 100|| 5
+|}
 == Tematika ==
-Előadások és gyakorlatok összefésült témája:
+=== Elaődásanyagok ===
-* algoritmusok bevezetés, motiváció, ordó
+* 2018 ősz (Berczédi Balázs kézzel írott előadásjegyzetei)
-* rendező algoritmusok (összefésüléses, kiválasztásos, ládarendezés...)
+#[[Media:Algraf_2018_ea_1.pdf | előadás, 2018.09.06]]
-* bináris keresőfa, fabejárások
+#[[Media:Algraf_2018_ea_2.pdf | előadás, 2018.09.13]]
-* hash táblák
+#[[Media:Algraf_2018_ea_3.pdf | előadás, 2018.09.27]]
-* gráfok
+#[[Media:Algraf_2018_ea_4.pdf | előadás, 2018.10.04]]
-* szélességi keresés (BFS)
+#[[Media:Algraf_2018_ea_5.pdf | előadás, 2018.10.11]]
-* mélységi keresés (DFS)
+#[[Media:Algraf_2018_ea_6.pdf | előadás, 2018.10.13]]
-* irányított körmentes gráf (DAG)
+#[[Media:Algraf_2018_ea_7.pdf | előadás, 2018.10.18]]
-* Bellman-Ford algoritmus
+#[[Media:Algraf_2018_ea_8.pdf | előadás, 2018.10.25]]
-TODO folytatás
+#[[Media:Algraf_2018_ea_9.pdf | előadás, 2018.11.08]]
+#[[Media:Algraf_2018_ea_10.pdf | előadás, 2018.11.15]]
+#[[Media:Algraf_2018_ea_11.pdf | előadás, 2018.11.22]]
+#[[Media:Algraf_2018_ea_12.pdf | előadás, 2018.11.29]]
+#[[Media:Algraf_2018_ea_13.pdf | előadás, 2018.12.06]]
+* 2019 ősz (Hivatalos jegyzetek)
+#[[Media:Algraf_2019_ea_1.pdf | Algoritmus fogalma, pszeudokód, helyesség, lépésszám]]
+#[[Media:Algraf_2019_ea_2.pdf | Kiválasztásos rendezés, ordó jelölés]]
+#[[Media:Algraf_2019_ea_3.pdf | Beszúrásos rendezés és bináris keresés]]
+#[[Media:Algraf_2019_ea_4.pdf | Összefésüléses rendezés]]
+#[[Media:Algraf_2019_ea_5.pdf | Ládarendezés, tömb, lista, bináris fa, bináris keresőfa]]
+#[[Media:Algraf_2019_ea_6.pdf | Bináris keresőfa műveletei, AVL-fa, hash]]
+#[[Media:Algraf_2019_ea_7.pdf | Gráfok alapfogalmai, szomszédossági mátrix]]
+#[[Media:Algraf_2019_ea_8.pdf | Összefüggőség, feszítőfa, szélességi bejárás]]
+#[[Media:Algraf_2019_ea_9.pdf | Mélységi bejárás]]
+#[[Media:Algraf_2019_ea_10.pdf | Topologikus sorrend, DAG-ság eldöntése]]
+#[[Media:Algraf_2019_ea_11.pdf | Legrövidebb és leghosszabb út keresése DAG-ban; A legrövidebb út keresése általános esetben]]
+#[[Media:Algraf_2019_ea_12.pdf | Dijkstra algoritmusa]]
+#[[Media:Algraf_2019_ea_13.pdf | Minimális feszítőfa keresés, Prim és Kruskal algoritmusa]]
+=== Gyakorlatanyagok ===
+* 2018 ősz
+#[[Media:elso_algo_ordo.pdf | Motiváció, ordó]]
+#[[Media:masodik_rendezes_eleje.pdf | Rendező algoritmusok]]
+#[[Media:harmadik_ismetles.pdf | Ismétlés (ordó, rendező)]]
+#[[Media:otodik_lada_binkerfa.pdf | Ládarendezés, bináris keresőfa, fabejárások]]
+#[[Media:hatodik_hash.pdf | Hash tábla]]
+#[[Media:hetedik_graf.pdf | Gráfok]]
+#[[Media:nyolcadik_bfs.pdf | BFS - szélességi keresés]]
+#[[Media:tizedik_dfs.pdf | DFS - mélységi keresés]]
+#[[Media:tizenegyedik_dag.pdf | DAG - irányított körmentes gráf]]
+#[[Media:tizenkettedik_bf.pdf | Bellman-Ford-algoritmus]]
+#[[Media:tizennegyedik_dijkstra_mst.pdf | Dijkstra-algoritmus, Prim-algoritmus]]
+* 2019 ősz
+#Pszeudokód, lépésszám: [[Media:Algraf_2019_gy_1.pdf | feladatsor]], [[Media:Algraf_2019_gy_1_sol.pdf | megoldások]]
+#Pszeudokód, nagy ordó: [[Media:Algraf_2019_gy_2.pdf | feladatsor]], [[Media:Algraf_2019_gy_2_sol.pdf | megoldások]]
+#Rendező algoritmusok: [[Media:Algraf_2019_gy_3.pdf | feladatsor]], [[Media:Algraf_2019_gy_3_sol.pdf | megoldások]]
+#Összefésüléses rendezés, rendezéses feladatok: [[Media:Algraf_2019_gy_4.pdf | feladatsor]], [[Media:Algraf_2019_gy_4_sol.pdf | megoldások]]
+#Ládarendezés, bináris fák bejárásai, bináris keresőfa: [[Media:Algraf_2019_gy_5.pdf | feladatsor]], [[Media:Algraf_2019_gy_5_sol.pdf | megoldások]]
+#Bináris keresőfa, AVL-fa: [[Media:Algraf_2019_gy_6.pdf | feladatsor]], [[Media:Algraf_2019_gy_6_sol.pdf | megoldások]]
+#Hash: [[Media:Algraf_2019_gy_7.pdf | feladatsor]], [[Media:Algraf_2019_gy_7_sol.pdf | megoldások]]
+#Gráf, szomszédossági mátrix, szélességi bejárás: [[Media:Algraf_2019_gy_8.pdf | feladatsor]], [[Media:Algraf_2019_gy_8_sol.pdf | megoldások]]
+#Mélységi bejárás, szöveges feladatok a bejárásokról: [[Media:Algraf_2019_gy_9.pdf | feladatsor]], [[Media:Algraf_2019_gy_9_sol.pdf | megoldások]]
+#DAG, toplogikus sorrend, további szöveges feladatok a bejárásokról: [[Media:Algraf_2019_gy_10.pdf | feladatsor]], [[Media:Algraf_2019_gy_10_sol.pdf | megoldások]]
+#Topologikus sorrendet használó lerövidebb/leghosszabb utas algo, Dijkstra: [[Media:Algraf_2019_gy_11.pdf | feladatsor]], [[Media:Algraf_2019_gy_11_sol.pdf | megoldások]]
+#Prim és Kruskal algo, szöveges példák Dijkstra, Prim témában: [[Media:Algraf_2019_gy_12.pdf | feladatsor]], [[Media:Algraf_2019_gy_12_sol.pdf | megoldások]]
 == Segédanyagok ==
-TODO
-== Számonkérések ==
-=== Házi feladat ===
-A félév során nincsen kötelező házi feladat.
-=== ZH ===
+=== Jegyzetek ===
-A félév során egy ZH van, melyen 60 pontot lehet elérni.
+*[[Media:BME-VIK-Algoritmusok_es_grafok-2018-19.pdf | 2018-as oktató által lektorált jegyzet]] - Pócz Gergő
-=== NZH 2018. ===
+=== További feladatok ===
-=====1. feladat=====
+*[[Media:Algraf-2018-extra.pdf | Extra szorgalmi feladatsor 2018]]
-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.
+*[[Media:Algraf_2019_extra.pdf | Extra szorgalmi feladatsor 2019]]
-=====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 />
+== ZH ==
-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 />
+*2018. ősz
-Az összes lehetőséget adja meg!<br />
+**[[Media:mintazh.pdf | mintafeladatok]]
-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 />
+**[[Algoritmusok és gráfok ZH 2018 | NZH és PZH egyben]]
-Az összes lehetőséget adja meg!
+***PDF-ben:
-=====3. feladat=====
+****[[Media:algráf_ZH_2018-11-16_módosított.pdf | ZH (módosított változat)]]
-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.
+****[[Media:Algraf-2018-PZH.pdf | PZH]]
-=====4. feladat=====
+*2019. ősz
-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.
+**[[Media:algráf_ZH_2019-ősz_minta.pdf | mintafeladatok]]
-=====5. feladat=====
+**[[Media:algráf_ZH_2019-11-21.pdf | ZH]], [[Media:algráf_ZH_2019-11-21_megoldások.pdf | megoldások]]
-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.
+**[[Media:algráf_PZH_2019-12-05.pdf | PZH]], [[Media:algráf_PZH_2019-12-05_megoldások.pdf | megoldások]]
-=====6. feladat=====
+*2020. ősz
-É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.
+**ZH ([[Media:algráf_PZH_2020-11-19_kifejtős-feladatok.pdf |2. rész]])
-=== Vizsga ===
+*2021. ősz
-TODO
+**[[Media:algráf_ZH_2021-11-19.pdf | ZH]], [[Media:algráf_ZH_2021-11-19_megoldások.pdf | megoldások]]
+**[[Media:algráf_PZH_2021-12-01.pdf | PZH]], [[Media:algráf_PZH_2021-12-01.pdf_megoldások.pdf | megoldások]]
+*2022. ősz
+**[[Media:algráf_ZH_2022-ősz_tanácsok.pdf | tanácsok]]
+**[[Media:algráf_ZH_2022-11-24.pdf | ZH]], [[Media:algráf_ZH_2022-11-24_megoldások.pdf | megoldások]]
+***Az 5. feladat leírása javítva és egyértelműsítve: ''"[...] Adjon O(n log n) lépésszámú algoritmust, ami eldönti, igaz-e, hogy mindegyik tömbben szereplő számnak a fele vagy a kétszerese szintén benne van a tömbben."''
-== Tippek ==
+== Vizsga ==
-TODO
+* 2018. ősz
+** [[Media:minta_vizsga.pdf | mintafeladatok]]
+** [[Media:Algraf-2018-vizsga-1.pdf | 1. vizsga (2018. december 19.)]]
+** [[Media:Algraf-2018-vizsga-2.pdf | 2. vizsga (2019. január 4.)]]
+** [[Media:Algraf-2018-vizsga-3.pdf | 3. vizsga (2019. január 9.)]]
+** [[Media:Algraf_2018_v4.pdf| 4. vizsga (2019. január 16.)]]
+* 2019. ősz
+** [[Media:Algraf_2019_v1.pdf | 1. vizsga (2020. január 8.)]], [[Media:Algraf_2019_v1_sol.pdf | megoldások]]
+** [[Media:Algraf_2019_v2.pdf | 2. vizsga (2020. január 15.)]], [[Media:Algraf_2019_v2_sol.pdf | megoldások]]
+** [[Media:Algraf_2019_v3.pdf | 3. vizsga (2020. január 22.)]], [[Media:Algraf_2019_v3_sol.pdf | megoldások]]
+** [[Media:Algraf_2019_v4.pdf | 4. vizsga (2020. január 29.)]], [[Media:Algraf_2019_v4_sol.pdf | megoldások]]
+* 2020. ősz
+** [[Media:algráf_vizsga_2020-12-22.pdf | 1. vizsga]]
+** [[Media:algráf_vizsga_2021-01-05.pdf | 2. vizsga]]
+** [[Media:algráf_vizsga_2021-01-12.pdf | 3. vizsga]]
+** [[Media:algráf_vizsga_2021-01-19.pdf | 4. vizsga]]
+* 2021. ősz
+** [[Media:algráf_vizsga_2021-12-21.pdf | 1. vizsga]], [[Media:algráf_vizsga_2021-12-21_megoldások.pdf | megoldások]]
+** [[Media:algráf_vizsga_2022-01-04.pdf | 2. vizsga]], [[Media:algráf_vizsga_2022-01-04_megoldások.pdf | megoldások]]
+*** oktatói megjegyzés: ''2021-ben SzuperCsodásnak hívtam a DAG-os algoritmust a legrövidebb utak keresésére.''
+** [[Media:algráf_vizsga_2022-01-11.pdf | 3. vizsga]], [[Media:algráf_vizsga_2022-01-11_megoldások.pdf | megoldások]]
+** [[Media:algráf_vizsga_2022-01-18.pdf | 4. vizsga]], [[Media:algráf_vizsga_2022-01-18_megoldások.pdf | megoldások]]
+* 2022. ősz
+** [[Media:algráf_vizsga-tanácsok_2022-ősz.pdf | tanácsok]]
 == Kedvcsináló ==
-TODO
+*[[Media:Algraf_2019_motivacio.pdf | Motivációs előadás 2019 ősz]]
+*Animációk
+**Bináris keresés: http://www.cs.armstrong.edu/liang/animation/web/BinarySearch.html
+**Rendező algoritmusok: https://visualgo.net/bn/sorting?slide=1
+**Összefésüléses rendezés eltáncolva: https://www.youtube.com/watch?v=XaqR3G_NVoo
+**AVL-fa animáció: https://visualgo.net/bn/bst?slide=1
+{{Lábléc_-_Üzemmérnök-informatikus_alapszak}}