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 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

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

Jegyzetek

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

Gyakorlati anyagok

1. Motiváció, ordó
2. Rendező algoritmusok
3. Ismétlés (ordó, rendező)
4. elmaradt
5. Ládarendezés, bináris keresőfa, fabejárások
6. Hash tábla
7. Gráfok
8. BFS - szélességi keresés
9. elmaradt
10. DFS - mélységi keresés
11. DAG - irányított körmentes gráf
12. Bellman-Ford-algoritmus
13. elmaradt
14. Dijkstra-algoritmus, Prim-algoritmus

További feladatok

• Extra szorgalmi feladatsor

ZH

• 2018 ősz
  • NZH mintafeladatok
  • NZH & PZH feladatok PDF-ben: ZH és PZH

Vizsga

• 2018 ősz
  • Vizsga mintafeladatok
  • 1. vizsga - 2018. december 19.
  • 2. vizsga - 2019. január 4.
  • 3. vizsga - 2019. január 9.

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: 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