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

A VIK Wikiből
Ugrás a navigációhoz Ugrás a kereséshez
(start)
 
(32 közbenső módosítás, amit 9 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
−
|kiszh=TODO
+
|kiszh=nincs
−
|vizsga=TODO
+
|nagyzh=1 db
−
|nagyzh=TODO
+
|hf=nincs
−
|hf=TODO
+
|vizsga=írásbeli
 
|tad=https://portal.vik.bme.hu/kepzes/targyak/VISZBA01/
 
|tad=https://portal.vik.bme.hu/kepzes/targyak/VISZBA01/
−
|targyhonlap=Nincs
+
|targyhonlap=http://www.cs.bme.hu/~csima/
−
|levlista=N/A }}
+
|levlista=  }}
  
−
{{TODO BProf}}
+
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.
  
−
Ide szükség lenne pár mondat a tárgyról, csak úgy előszóként. Például, hogy miről szól, mire jó, mitől érdekes, ha valamire kiemelten figyelni kellene, stb...
 
  
 
== Követelmények ==
 
== Követelmények ==
 +
 
=== A szorgalmi időszakban ===
 
=== A szorgalmi időszakban ===
−
TODO
+
*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 ===
−
TODO
+
*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 ===
−
TODO
+
*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 ==
−
TODO
+
=== 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]]
 +
#[[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ő
−
TODO
 
  
−
=== ZH ===
+
=== További feladatok ===
−
TODO
+
*[[Media:Algraf-2018-extra.pdf | Extra szorgalmi feladatsor 2018]]
 +
*[[Media:Algraf_2019_extra.pdf | Extra szorgalmi feladatsor 2019]]
  
−
=== Vizsga ===
+
== ZH ==
−
TODO
+
*2018. ősz
 +
**[[Media:mintazh.pdf | NZH mintafeladatok]]
 +
**[[Algoritmusok és gráfok ZH 2018 | NZH & PZH feladatok]] PDF-ben: [[Media:Algraf-2018-ZH.pdf | ZH]] és [[Media:Algraf-2018-PZH.pdf | PZH]]
  
−
== Tippek ==
+
== Vizsga ==
−
TODO
+
*2018. ősz
 +
**[[Media:minta_vizsga.pdf | Vizsga 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]]
  
 
== 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 2022. február 6., 19:34-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
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://wiki.sch.bme.hu/index.php?title=Algoritmusok_és_gráfok&oldid=201649”