Algoritmusok és gráfok

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
Tantárgyi adatlap
Tárgyhonlap

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

• 2018-as oktató által lektorált jegyzet - Pócz Gergő

További feladatok

• Extra szorgalmi feladatsor 2018
• Extra szorgalmi feladatsor 2019

ZH

• 2018. ősz
  • mintafeladatok
  • NZH és PZH egyben
    • PDF-ben:
      • ZH (módosított változat)
      • PZH
• 2019. ősz
  • mintafeladatok
  • ZH, megoldások
  • PZH, megoldások
• 2020. ősz
  • ZH (2. rész)
• 2021. ősz
  • ZH, megoldások
  • PZH, megoldások
• 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
  • mintafeladatok
  • 1. vizsga (2018. december 19.)
  • 2. vizsga (2019. január 4.)
  • 3. vizsga (2019. január 9.)
  • 4. vizsga (2019. január 16.)
• 2019. ősz
  • 1. vizsga (2020. január 8.), megoldások
  • 2. vizsga (2020. január 15.), megoldások
  • 3. vizsga (2020. január 22.), megoldások
  • 4. vizsga (2020. január 29.), megoldások
• 2020. ősz
  • 1. vizsga
  • 2. vizsga
  • 3. vizsga
  • 4. vizsga
• 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
  • tanácsok

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

Üzemmérnök-informatikus BProf
1. félév	Algoritmusok és gráfok  •  A programozás alapjai  •  Bevezető matematika B  •  Digitális kompetenciák  •  Hardver alapok  •  Kalkulus
2. félév	Hálózatok alapjai és üzemeltetése  •  Kísérleti fizika  •  Objektumorientált programozás  •  Operációs rendszerek B  •  Valószínűségszámítás B
3. félév	Adatkezelés  •  Alkalmazott mesterséges intelligencia  •  Eseményvezérelt és vizuális programozás  •  Kódolás és IT biztonság  •  Szoftvertechnológia és -technikák
4. félév	Elektronika alapjai  •  Jelek és jelfeldolgozás  •  Menedzsment és vállalkozásgazdaságtan
5. félév	Mikro- és makroökonómia B  •  Jogi alapismeretek
6. félév	Záróvizsga