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

A VIK Wikiből
← Régebbi szerkesztés
VizuálisWikiszöveges
Nincs szerkesztési összefoglaló
Szóbeli vizsga lehetőségének hozzáadása
 
(33 közbenső módosítás, amit 7 másik szerkesztő végzett, nincs mutatva)
5. sor: 5. sor:
|kredit=5
|kredit=5
|felev=1
|felev=1
|kereszt=N/A
|kereszt=
|tanszék=SZIT
|tanszék=SZIT
|vizsga=írásbeli
|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/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.  
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 ==
== Követelmények ==
=== A szorgalmi időszakban ===
=== 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 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 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 ==
== 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 ==
== Segédanyagok ==
TODO


== Számonkérések ==
=== Jegyzetek ===
=== Házi feladat ===
*[[Media:BME-VIK-Algoritmusok_es_grafok-2018-19.pdf | 2018-as oktató által lektorált jegyzet]] - Pócz Gergő
A félév során nincsen kötelező házi feladat.
 
=== További feladatok ===
*[[Media:Algraf-2018-extra.pdf | Extra szorgalmi feladatsor 2018]]
*[[Media:Algraf_2019_extra.pdf | Extra szorgalmi feladatsor 2019]]


=== ZH ===
== ZH ==
A félév során egy ZH van, melyen 60 pontot lehet elérni.
*2018. ősz
====Korábbi ZH-k====
**[[Media:mintazh.pdf | mintafeladatok]]
*[[Algoritmusok és gráfok ZH 2018|NZH 2018]]
**[[Algoritmusok és gráfok ZH 2018 | NZH és PZH egyben]]
=== Vizsga ===
***PDF-ben:
TODO
****[[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."''


== 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ó ==
== 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}}

A lap jelenlegi, 2023. április 17., 12:19-kori változata

Algoritmusok és gráfok
Tárgykód
VISZBA01
Általános infók
Szak
üzemmérnök
Kredit
5
Ajánlott félév
1
Tanszék
SZIT
Követelmények
KisZH
nincs
NagyZH
1 db
Házi feladat
nincs
Vizsga
írásbeli, javító szóbeli
Elérhetőségek

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 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)
  1. előadás, 2018.09.06
  2. előadás, 2018.09.13
  3. előadás, 2018.09.27
  4. előadás, 2018.10.04
  5. előadás, 2018.10.11
  6. előadás, 2018.10.13
  7. előadás, 2018.10.18
  8. előadás, 2018.10.25
  9. előadás, 2018.11.08
  10. előadás, 2018.11.15
  11. előadás, 2018.11.22
  12. előadás, 2018.11.29
  13. előadás, 2018.12.06
  • 2019 ősz (Hivatalos jegyzetek)
  1. Algoritmus fogalma, pszeudokód, helyesség, lépésszám
  2. Kiválasztásos rendezés, ordó jelölés
  3. Beszúrásos rendezés és bináris keresés
  4. Összefésüléses rendezés
  5. Ládarendezés, tömb, lista, bináris fa, bináris keresőfa
  6. Bináris keresőfa műveletei, AVL-fa, hash
  7. Gráfok alapfogalmai, szomszédossági mátrix
  8. Összefüggőség, feszítőfa, szélességi bejárás
  9. Mélységi bejárás
  10. Topologikus sorrend, DAG-ság eldöntése
  11. Legrövidebb és leghosszabb út keresése DAG-ban; A legrövidebb út keresése általános esetben
  12. Dijkstra algoritmusa
  13. Minimális feszítőfa keresés, Prim és Kruskal algoritmusa


Gyakorlatanyagok

  • 2018 ősz
  1. Motiváció, ordó
  2. Rendező algoritmusok
  3. Ismétlés (ordó, rendező)
  4. Ládarendezés, bináris keresőfa, fabejárások
  5. Hash tábla
  6. Gráfok
  7. BFS - szélességi keresés
  8. DFS - mélységi keresés
  9. DAG - irányított körmentes gráf
  10. Bellman-Ford-algoritmus
  11. Dijkstra-algoritmus, Prim-algoritmus
  • 2019 ősz
  1. Pszeudokód, lépésszám: feladatsor, megoldások
  2. Pszeudokód, nagy ordó: feladatsor, megoldások
  3. Rendező algoritmusok: feladatsor, megoldások
  4. Összefésüléses rendezés, rendezéses feladatok: feladatsor, megoldások
  5. Ládarendezés, bináris fák bejárásai, bináris keresőfa: feladatsor, megoldások
  6. Bináris keresőfa, AVL-fa: feladatsor, megoldások
  7. Hash: feladatsor, megoldások
  8. Gráf, szomszédossági mátrix, szélességi bejárás: feladatsor, megoldások
  9. Mélységi bejárás, szöveges feladatok a bejárásokról: feladatsor, megoldások
  10. DAG, toplogikus sorrend, további szöveges feladatok a bejárásokról: feladatsor, megoldások
  11. Topologikus sorrendet használó lerövidebb/leghosszabb utas algo, Dijkstra: feladatsor, megoldások
  12. Prim és Kruskal algo, szöveges példák Dijkstra, Prim témában: feladatsor, megoldások

Segédanyagok

Jegyzetek

További feladatok

ZH

Vizsga

Kedvcsináló
1. félév
2. félév
3. félév
4. félév
5. félév
6. félév


A lap eredeti címe: „https://vik.wiki/index.php?title=Algoritmusok_és_gráfok&oldid=203884”