„Algoritmusok és gráfok” változatai közötti eltérés
Ugrás a navigációhoz
Ugrás a kereséshez
(Szóbeli vizsga lehetőségének hozzáadása) |
|||
(27 közbenső módosítás, amit 7 másik szerkesztő végzett, nincs mutatva) | |||
7. sor: | 7. sor: | ||
|kereszt= | |kereszt= | ||
|tanszék=SZIT | |tanszék=SZIT | ||
− | | | + | |kiszh=nincs |
|nagyzh=1 db | |nagyzh=1 db | ||
|hf=nincs | |hf=nincs | ||
+ | |vizsga=írásbeli, javító szóbeli | ||
|tad=https://portal.vik.bme.hu/kepzes/targyak/VISZBA01/ | |tad=https://portal.vik.bme.hu/kepzes/targyak/VISZBA01/ | ||
− | |targyhonlap=http://www.cs.bme.hu/~csima | + | |targyhonlap=http://www.cs.bme.hu/~csima/ |
|levlista= }} | |levlista= }} | ||
20. sor: | 21. sor: | ||
=== A szorgalmi időszakban === | === A szorgalmi időszakban === | ||
− | *A | + | *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 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 === | === Félévvégi jegy === | ||
− | *A | + | *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 == | == Tematika == | ||
− | + | === Elaődásanyagok === | |
− | * | + | * 2018 ősz (Berczédi Balázs kézzel írott előadásjegyzetei) |
− | + | #[[Media:Algraf_2018_ea_1.pdf | előadás, 2018.09.06]] | |
− | + | #[[Media:Algraf_2018_ea_2.pdf | előadás, 2018.09.13]] | |
− | + | #[[Media:Algraf_2018_ea_3.pdf | előadás, 2018.09.27]] | |
− | + | #[[Media:Algraf_2018_ea_4.pdf | előadás, 2018.10.04]] | |
− | + | #[[Media:Algraf_2018_ea_5.pdf | előadás, 2018.10.11]] | |
− | + | #[[Media:Algraf_2018_ea_6.pdf | előadás, 2018.10.13]] | |
− | + | #[[Media:Algraf_2018_ea_7.pdf | előadás, 2018.10.18]] | |
− | + | #[[Media:Algraf_2018_ea_8.pdf | előadás, 2018.10.25]] | |
− | + | #[[Media:Algraf_2018_ea_9.pdf | előadás, 2018.11.08]] | |
− | * Prim | + | #[[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 == | == Segédanyagok == | ||
− | + | ||
− | + | === Jegyzetek === | |
− | * | + | *[[Media:BME-VIK-Algoritmusok_es_grafok-2018-19.pdf | 2018-as oktató által lektorált jegyzet]] - Pócz Gergő |
− | + | ||
− | + | === További feladatok === | |
− | + | *[[Media:Algraf-2018-extra.pdf | Extra szorgalmi feladatsor 2018]] | |
− | * | + | *[[Media:Algraf_2019_extra.pdf | Extra szorgalmi feladatsor 2019]] |
− | |||
− | |||
− | |||
− | |||
− | |||
− | * | ||
== ZH == | == ZH == | ||
− | *2018 | + | *2018. ősz |
− | **[[Media:mintazh.pdf | | + | **[[Media:mintazh.pdf | mintafeladatok]] |
− | **[[Algoritmusok és gráfok ZH 2018 | NZH | + | **[[Algoritmusok és gráfok ZH 2018 | NZH és PZH egyben]] |
− | * | + | ***PDF-ben: |
+ | ****[[Media:algráf_ZH_2018-11-16_módosított.pdf | ZH (módosított változat)]] | ||
+ | ****[[Media:Algraf-2018-PZH.pdf | PZH]] | ||
+ | *2019. ősz | ||
+ | **[[Media:algráf_ZH_2019-ősz_minta.pdf | mintafeladatok]] | ||
+ | **[[Media:algráf_ZH_2019-11-21.pdf | ZH]], [[Media:algráf_ZH_2019-11-21_megoldások.pdf | megoldások]] | ||
+ | **[[Media:algráf_PZH_2019-12-05.pdf | PZH]], [[Media:algráf_PZH_2019-12-05_megoldások.pdf | megoldások]] | ||
+ | *2020. ősz | ||
+ | **ZH ([[Media:algráf_PZH_2020-11-19_kifejtős-feladatok.pdf |2. rész]]) | ||
+ | *2021. ősz | ||
+ | **[[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."'' | ||
== Vizsga == | == Vizsga == | ||
− | *2018 | + | * 2018. ősz |
− | **[[minta_vizsga.pdf | | + | ** [[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ó == | ||
+ | *[[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}} | |
− |
A lap jelenlegi, 2023. április 17., 11:19-kori változata
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.
Tartalomjegyzék
Követelmények
A szorgalmi időszakban
- 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.
- 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 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:
Eredmény % Jegy 0 - 39 1 40 - 54 2 55 - 69 3 70 - 84 4 85 - 100 5
Tematika
Elaődásanyagok
- 2018 ősz (Berczédi Balázs kézzel írott előadásjegyzetei)
- előadás, 2018.09.06
- előadás, 2018.09.13
- előadás, 2018.09.27
- előadás, 2018.10.04
- előadás, 2018.10.11
- előadás, 2018.10.13
- előadás, 2018.10.18
- előadás, 2018.10.25
- előadás, 2018.11.08
- előadás, 2018.11.15
- előadás, 2018.11.22
- előadás, 2018.11.29
- előadás, 2018.12.06
- 2019 ősz (Hivatalos jegyzetek)
- Algoritmus fogalma, pszeudokód, helyesség, lépésszám
- Kiválasztásos rendezés, ordó jelölés
- Beszúrásos rendezés és bináris keresés
- Összefésüléses rendezés
- Ládarendezés, tömb, lista, bináris fa, bináris keresőfa
- Bináris keresőfa műveletei, AVL-fa, hash
- Gráfok alapfogalmai, szomszédossági mátrix
- Összefüggőség, feszítőfa, szélességi bejárás
- Mélységi bejárás
- Topologikus sorrend, DAG-ság eldöntése
- Legrövidebb és leghosszabb út keresése DAG-ban; A legrövidebb út keresése általános esetben
- Dijkstra algoritmusa
- Minimális feszítőfa keresés, Prim és Kruskal algoritmusa
Gyakorlatanyagok
- 2018 ősz
- Motiváció, ordó
- Rendező algoritmusok
- Ismétlés (ordó, rendező)
- Ládarendezés, bináris keresőfa, fabejárások
- Hash tábla
- Gráfok
- BFS - szélességi keresés
- DFS - mélységi keresés
- DAG - irányított körmentes gráf
- Bellman-Ford-algoritmus
- Dijkstra-algoritmus, Prim-algoritmus
- 2019 ősz
- Pszeudokód, lépésszám: feladatsor, megoldások
- Pszeudokód, nagy ordó: feladatsor, megoldások
- Rendező algoritmusok: feladatsor, megoldások
- Összefésüléses rendezés, rendezéses feladatok: feladatsor, megoldások
- Ládarendezés, bináris fák bejárásai, bináris keresőfa: feladatsor, megoldások
- Bináris keresőfa, AVL-fa: feladatsor, megoldások
- Hash: feladatsor, megoldások
- Gráf, szomszédossági mátrix, szélességi bejárás: feladatsor, megoldások
- Mélységi bejárás, szöveges feladatok a bejárásokról: feladatsor, megoldások
- DAG, toplogikus sorrend, további szöveges feladatok a bejárásokról: feladatsor, megoldások
- Topologikus sorrendet használó lerövidebb/leghosszabb utas algo, Dijkstra: feladatsor, megoldások
- Prim és Kruskal algo, szöveges példák Dijkstra, Prim témában: feladatsor, megoldások
Segédanyagok
Jegyzetek
- 2018-as oktató által lektorált jegyzet - Pócz Gergő
További feladatok
ZH
- 2018. ősz
- 2019. ősz
- 2020. ősz
- ZH (2. rész)
- 2021. ősz
- 2022. ősz
- tanácsok
- ZH, 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."
Vizsga
- 2018. ősz
- 2019. ősz
- 2020. ősz
- 2021. ősz
- 1. vizsga, megoldások
- 2. vizsga, megoldások
- oktatói megjegyzés: 2021-ben SzuperCsodásnak hívtam a DAG-os algoritmust a legrövidebb utak keresésére.
- 3. vizsga, megoldások
- 4. vizsga, megoldások
- 2022. ősz
Kedvcsináló
- 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
1. félév | |
---|---|
2. félév | |
3. félév | |
4. félév | |
5. félév | |
6. félév |