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
NagyZH	1 db
Házi feladat	nincs
Vizsga	írásbeli
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 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 (max 60 pont).

A vizsgaidőszakban

• A vizsga írásbeli, a vizsga 40%-tól sikeres.

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.

Tematika

Előadások és gyakorlatok összefésült témája:

• algoritmusok bevezetés, motiváció, ordó
• rendező algoritmusok (összefésüléses, kiválasztásos, ládarendezés...)
• bináris keresőfa, fabejárások
• hash táblák
• gráfok
• szélességi keresés (BFS)
• mélységi keresés (DFS)
• irányított körmentes gráf (DAG)
• Bellman-Ford algoritmus
• Dijsktra algoritmus
• Prim algoritmus

Segédanyagok

• Gyakorlati feladatosorok:
  • 2018 ősz
  1. Motiváció, ordó
  2. Rendező algoritmusok
  3. Ismétlés (ordó, rendező)
  4. Bináris keresőfa
  5. Hash
  6. Gráfok
  7. BFS
  8. DFS
  9. DAG
  10. Bellman-Ford
  11. Dijkstra

ZH

• 2018 ősz
  • NZH mintafeladatok
  • NZH & PZH feladatok

Vizsga

• 2018 ősz
  • Vizsga mintafeladatok

Kedvcsináló

• 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 AVL-fa animáció: https://www.youtube.com/watch?v=XaqR3G_NVoo