Algoritmusok és gráfok

A VIK Wikiből
A lap korábbi változatát látod, amilyen Csia Klaudia Kitti (vitalap | szerkesztései) 2020. augusztus 7., 23:04-kor történt szerkesztése után volt.
(eltér) ← Régebbi változat | Aktuális változat (eltér) | Újabb változat→ (eltér)
Ugrás a navigációhoz Ugrás a kereséshez
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.
  • 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