Ez az előadás a villamosmérnök alapképzés
(BSc program) VISZAA05 neptun-kód alatt szereplő, 5 kredites
tárgyához tartozik. A
szakot ebben a félévben kezdő hallgatók ezt az elméleti
kurzust és egy hozzá tartozó gyakorlatot vegyenek fel, csakúgy mint mindenki más, akinek nincs
érvényes SzA aláírása, de a félév végén vizsgázni szeretne.
Két vizsgakurzus is indul. A az egyik a most tanított VISZAA05
tárgyból, míg a másik a korábban tanított, 4 kredites VISZAA02
tárgyhoz tartozik. Ez utóbbit azok a hallgatók vehetik fel,
akiknek érvényes VISZAA02 aláírásuk van, és ennek birtokában 4
kreditért szeretnének vizsgázni. A vizsgakurzusokhoz nem tartozik gyakorlat,
ezeken a kurzusokon aláírás nem szerezhető, a vizsgára hozott
pontszám nem javítható. Természetesen érvényes aláírás
birtokában is fel lehet venni a VISZAA05 kurzust (egy hozzá
tartozó gyakorlattal). Ekkor ismét szerezhető aláírás és
kijavítható az aláíráshoz járó hozott pontszám, és a sikeres
vizsga pedig 5 kreditet ér.
A két kurzushoz természetesen külön tételsorok
tartoznak: egy a VISZAA05-höz
és egy a régi VISZAA02-höz.
Előadások:
Kurzuskód |
Időpont |
Előadó |
Terem |
1 |
kedd 8:15-10:00 | Fleiner Tamás (fleiner@cs.bme.hu) |
IB028 |
Gyakorlatok:
Kurzuskód |
Időpont |
Gyakorlatvezető |
Terem |
11 |
szerda
8:30-10:00 |
Horváth Bálint |
IB139 |
12 | szerda 8:30-10:00 | Nguyen Hai | IB138 |
13 |
szerda 8:30-10:00 | Vékássy Áron |
IB140 |
14 |
szerda 8:30-10:00 | Dorogi Imre | IB145 |
17 |
szerda 10:15-11:45 | Horváth Bálint | IB139 |
18 | szerda 10:15-11:45 | Nguyen Hai | IB138 |
19 |
szerda 10:15-11:45 | Tóth
Sára |
IB146 |
20 | szerda 10:15-11:45 | Vékássy
Áron |
IB140 |
I1 (IMSC) |
szerda 8:30-10:00 | Fleiner Tamás | IE218 |
I2 (IMSC) |
szerda 10:15-11:45 | Fleiner Tamás | IE218 |
I3 (IMSC) | szerda 8:30-10:00 | Schwarcz Tamás | IB147 |
1.hét |
2021. szeptember 7. |
Leszámlálási alapfogalmak,
permutációk, variációk és kombinációk (ismétlés nélkül és
ismétléssel), példákkal, kiszámításuk, binomiális
együtthatók közti egyszerű összefüggések, a binomiális
tétel. Előadás videó Gyakorló feladatsor |
|||||
2.hét | 2021. szeptember 14. |
Gráfelméleti alapfogalmak. Gráfok fokszámösszege,
komponensek, utak, séták, élsorozatok, izomorfia. Fák és
erdők, azok egyszerűbb tulajdonságai. Előadás videó 1. rész Előadás videó 2. rész Gyakorló feladatsor |
|||||
2021. szeptember 15. | Egyetemi sportnap: a
gyakorlatok elmaradnak. |
||||||
3.hét | 2021. szeptember 21. |
Feszítőfa, alapkörrendszer (fundamentális körrendszer),
fundamentális vágásrendszer. Minimális költségű feszítőfa,
Kruskal algoritmusa. (Normál fa.) Előadás videó 1. rész Előadás videó 2. rész Gyakorló feladatsor |
|||||
4.hét | 2021. szeptember 28. | Gráfbejárás fogalma,
élek osztályozása, BFS. Legrövidebb utak és a BFS
tulajdonságai, legrövidebb utak fája. Élmenti javítás,
Dijkstra algoritmusa. Előadás videó 1. rész Előadás videó 2. rész Gyakorló feladatsor |
|||||
5.hét | 2021. október 5. |
A Dijkstra-algoritmus helyessége és lépésszáma. Ford és
Floyd algoritmusai. Mélységi keresés, irányított körök
keresése, aciklikus gráfok jellemzése. PERT feladat,
megoldásnak algoritmusa. Idén sem szerepel: Legszélesebb út keresése irányítatlan gráfban. Előadás videó 1. rész Előadás videó 2. rész Gyakorló feladatsor |
|||||
6.hét | 2021. október 12. |
Euler-séta és körséta, létezésük szükséges és elégséges
feltétele. Hamilton-kör és út fogalma.
Szükséges, illetve elégséges feltételek Hamilton-kör
létezésére: Dirac és Ore tételei ill. komponensszám
pontelhagyások esetén. Előadás videó Gyakorló feladatsor Az I. ZH anyaga eddig tart. |
|||||
7.hét | 2021. október 19. |
Gráfok színezése,
klikkméret, maxfokszám és kromatikus szám viszonya. Páros
gráf fogalma, jellemzése. Független/lefogó pont-/élhalmazok,
triviális egyenlőtlenségek, Gallai tételei. Gyakorló feladatsor Előadás videó (az előadás első része rejtélyes okból nem lett felvéve) |
|||||
8.hét | 2021. október 26. | Hálózati folyamok,
Ford-Fulkerson tétel, algoritmus maximális folyam keresése,
Edmonds-Karp tétel. Egészértékűségi lemma, többtermelős,
többfogyasztós hálózatok, csúcskapacitások és irányítatlan
élek visszavezetése szokásos hálózatra. Előadás videó 1. rész Előadás videó 2. rész Gyakorló feladatsor |
|||||
9.hét | 2021. november 2. |
Kőnig, Hall és Frobenius tételei páros gráfok
párosításairól. Algoritmus páros gráf maximális méretű
párosításának megkeresésére. Előadás videó 1. rész Előadás videó 2. rész Gyakorló feladatsor |
|||||
2021. november 5. | 8-10 óra I. ZH feladatok,
mintamegoldás Terembeosztás (vezetéknév kezdőbetűje szerint):
|
||||||
10.hét | 2021. november 9. |
Gráf síkba, illetve gömbre rajzolhatósága. Az Euler-féle
poliédertétel és következményei egyszerű, síkbarajzolható
gráfokra. Kuratowski gráfok, topologikus izomorfia,
Kuratowski tétele. Fáry-Wagner-tétel, 5-szín tétel. Előadás videó 1. rész Előadás videó 2. rész Gyakorló feladatsor |
|||||
11.hét | 2021. november 16. |
TDK konferencia: az előadás elmarad |
|||||
12.hét | 2021. november 23. | Oszthatóság, maradékos osztás. Euklideszi
algoritmus, prímek, számelmélet alaptétele,
osztók száma. Tételek a prímek eloszlásáról. Kongruenciák, lineáris kongruenciák megoldása. Maradékrendszerek, Euler-Fermat-tétel. Előadás videó 1. rész Előadás videó 2. rész Gyakorló feladatsor A II. ZH anyaga eddig tart. |
|||||
13.hét | 2021. november 30. | Algoritmusok bonyolultsága (input mérete,
algoritmus lépésszáma az inputméret függvényében,
polinomidejű algoritmus). Számelméleti algoritmusok:
alapműveletek, (modulo m) hatványozás és az euklideszi
algoritmus lépésszáma. Döntési problémák. P, NP, co-NP
bonyolultsági osztályok fogalma, feltételezett viszonyuk,
példa ilyen problémákra. Polinomiális visszavezethetőség
(Karp-redukció), NP-teljesség, Cook-Levin tétel, nevezetes
NP-teljes problémák: SAT, HAM, 3-SZÍN. k-SZÍN, MAXFTN,
MAXKLIKK. Idén nem szerepel: prímtesztelés, Fermat-teszt. Nyilvános kulcsú titkosírás, digitális aláírás. Az RSA titkosítási módszer. Előadás pdf Előadás videó Gyakorló feladatsor |
|||||
2021. december 3. | 8-10 óra II. ZH feladatok,
mintamegoldás Terembeosztás (vezetéknév kezdőbetűje szerint):
|
||||||
14.hét | 2021. december 7. |
A villamosságtan szempontjából fontos alkalmazási
területek. Síkbarajzolt gráf duálisa. Elvágó él, soros élek, vágás. A duális gráf tulajdonságai (élszám, csúcsszám, összefüggőség, kör-vágás dualitás, annak speciális esetei). Előadás pdf Előadás videó Gyakorló feladatsor |
|||||
Pótlási hét | 2021. december 15. |
10-12 pótZH, IB
028 feladatok,
mintamegoldás |
|||||
1.
vizsgahét |
2021. december 20. | 14-16 konzultáció, IE 217.1 | |||||
2021. december 21. |
10-12 aláíráspótlás, IB 026 | ||||||
3. vizsgahét |
2022. január 3. | 9-11 konzultáció, IB 134 | |||||
4.
vizsgahét |
2022. január 10. | 14-16 konzultáció, IB 134 | |||||
2022. január 13. | 12-14 konzultáció, IB 134 | ||||||
5. vizsgahét |
2022. január 17. | 9-11 konzultáció, IB 134 |
További
segédanyagok, érdeklődő hallgatóknak
Gyakorló
feladatok
Friedl-Recski-Simonyi:
Gráfelméleti
feladatok (Typotex 2006)
Van egy letölthető
példatár,
sőt, egy animációgyűjtemény is.
2014
őszi ZH feladatok, megoldások
2015
őszi ZH feladatok, megoldások
2016
őszi ZH feladatok, megoldások
2017 őszi ZH
feladatok, megoldások
2018
őszi ZH feladatok,
megoldások
2019
őszi ZH feladatok,
megoldások
2020
őszi ZH
feladatok,
megoldások
Értékelés, tárgykövetelmények, vizsga
A kari
vezetés rendelkezésének megfelelően a gyakorlatokon
kötelező a részvétel mindazok
számára, akik azt felvették. Akinek a tárgy
adatlapján meghatározottnál (ebben a félévben 3-nál) több
hiányzása bizonyítható, az nem
szerezhet sem aláírást,
sem kreditet
a VISZAA05 tárgyból. Ez tehát azt jelenti, hogy hiába van
érvényes aláírása valakinek: ha felveszi a gyakorlatot, de nem
látogatja a foglalkozásokat, akkor nem vizsgázhat.
A félév során két zárthelyi lesz. Mindkét
zárthelyi 90 perces és hat darab, egyenként 10 pontot érő
feladatból áll. A zárthelyin 50 pont megszerzése jelent 100%-os teljesítményt. Aki ennél
is többet ér el, annak az 50 pont feletti részt IMSC pontokban
írjuk jóvá. A zárthelyikre osztályzatot nem adunk, hanem az
azokon szerzett összpontszámot konvertáljuk
aláírásra ill. számítjuk be a vizsgajegybe. A zárthelyi
megírásakor az alábbi szabályok betartását követeljük meg.
Kérjük, hogy mindazon hallgatók,
akikre a dolgozatíráskor speciális szabályokat kell alkalmazni,
ezt legkésőbb egy héttel a dolgozatírás előtt jelezzék ezt a
tárgy előadójának.
A félév végi aláírást az szerzi meg (vagyis a szóbeli vizsgára az
jelentkezhet), aki az alábbi három feltétel mindegyikét teljesíti:
A két zárthelyi mellett lesz még két pótlási alkalom: elsőként a pótlási héten egy pótzárthelyi, majd a vizsgaidőszak első hétében egy aláíráspótló vizsga fedőnevű újabb lehetőség. Ezek mindegyikén újból meg lehet írni akár az első, akár a második zárthelyi dolgozatot, de egyszerre csak az egyiket. A dolgozat újbóli megírása természetesen nem azt jelenti, hogy a feladatsorok azonosak volnának. Mindhárom alkalommal ugyanazt az anyagrészt kérjük számon és - a szándékunk szerint - a kitűzött feladatsorok egyforma nehézségűek. E két pótlási alkalmat lehet tehát felhasználni az elmulasztott zárthelyik teljesítésére vagy egy korábban már megírt dolgozat eredményének a javítására. Ha valaki egy korábban már megírt dolgozatot teljesít újra valamelyik pótzárthelyin, akkor az újonnan szerzett pontszáma lesz érvényes (akkor is, ha az rosszabb, mint a korábbi), azzal a kivétellel, hogy egy már megszerzett aláírást nem lehet elveszíteni. Konkrétan: ha valaki már teljesítette az aláíráshoz szükséges feltételeket, majd egy javítónak szánt pótzárthelyin olyan eredményt ér el, hogy ezáltal az aláírása elveszne (akár azért, mert nem ért el 18 pontot, akár azért, mert az összpontszáma 48 alá csökken), akkor ettől az aláírása még megmarad és a vizsga eredményébe 48-as ZH összpontszám számít.
A pótzárthelyiken mindenki szabadon eldöntheti, hogy az első és a második zárthelyik közül melyiket kívánja pótolni vagy javítani, így annak sincs akadálya, hogy valaki mindkét pótlási alkalommal ugyanannak a dolgozatnak a pótlását (vagy javítását) kísérelje meg. A pótzárthelyire nem szükséges a neptunban jelentkezni: azon mindenki a saját döntése szerint részt vehet. Ha valaki mindkét zárthelyit már az első alkalommal (tehát pótlás nélkül) sikeresen teljesítette és (a TVSz biztosította jogával élve) mindkét zárthelyi eredményét még a szorgalmi időszakban javítani kívánja (és így erre az első pótzárthelyi alkalom nem elegendő), az keresse meg (e-mailben vagy személyesen) a tárgy előadóját legalább egy héttel az első pótzárthelyi időpontja előtt.A fent említett, pótlási héten biztosított
második pótlási alkalom a neptunban aláíráspótló vizsga
néven jelenik meg. (Ez a név tehát némileg félrevezető,
itt nem egy valódi vizsgáról van szó.) Erre a második
pótzárthelyi alkalomra vonatkozó szabályok az alábbiakban
különböznek az elsőre vonatkozóktól:
Az aláíráspótló vizsgán írt dolgozatokat még aznap kijavítjuk és biztosítjuk abba a betekintést. (Ennek a pontos helyszínét és időpontját a dolgozatírás közben hirdetjük ki.) A dolgozatok eredményei (legkésőbb a következő napon) a tárgy honlapjára is felkerülnek. Aki a megtekintésen nem tud megjelenni, az a dolgozatát kérésre később is megnézheti, de ekkor már a dolgozat pontozásán nem tudunk változtatni.
Korábban szerzett aláírásokA vizsga ebből a tárgyból szóbeli. A vizsga megkezdésekor a
vizsgázónak kisorsolunk egy tételt a tárgyhoz tartozó, a vizsgatételsorból.
Ennek a kidolgozására (vagyis a szóbeli felelethez egy vázlat
vagy bő jegyzet elkészítésére) legalább 45 percet biztosítunk.
Negyvenöt perc felkészülési idő letelte után a vizsgáztató abban
az esetben is elkezdheti a vizsgáztatást, ha a hallgató még nem
jelezte, hogy elkészült. A felelet abból áll, hogy a vizsgázó
egyrészt a jegyzeteire támaszkodva részletesen beszámol a húzott
tételben található tananyagról, másrészt a vizsgáztató néhány
szúrópróbaszerű, a tananyag további részével kapcsolatos
kérdésére válaszol. (A vizsga sikerességéhez tehát nem elég a
kihúzott tétel ismertetése, az fent említett további kérdésekre
is kell tudni válaszolni.) Az elégséges megszerzésének
elengedhetetlen feltétele, hogy a vizsgázó az anyagban szereplő
minden lényeges (a tételsorban félkövéren szedett) definíciót és
tételt pontosan ki tudjon mondani, illetve tudjon
értelmezni. Ugyancsak szükséges, hogy a nem vastagon
szedett részek esetében is legfeljebb egy-két hiányossága legyen
a vizsgázónak. Ennél több viszont nem is kell a ketteshez, azaz
a tételsorban szereplő tételek bizonyításainak ismerete csak a
közepes vagy jobb jegy megszerzéséhez szükséges. Ha valaki
az egyszerűbb bizonyításokat is tudja, akkor jók az esélyei a
hármas szóbeli feleletre. A négyes vagy ötös
felelethez (esetleg kisebb-nagyobb segítséggel) már a nehéz
bizonyításokat is el kell tudni mondani (és persze érteni is
kell azokat). A vizsgán számítani kell arra is, hogy a
zárthelyik által le nem fedett anyagrészből is kaphat kérdést a
vizsgázó.
A vizsgajegy a két zárthelyi eredményének ill. a vizsgán
nyújtott szóbeli teljesítménynek a súlyozott átlaga, amiben a
zárthelyik összeredményének súlya 2, a szóbeli vizsgáé pedig 3.
Ha a szóbeli vizsga elégtelen, akkor a vizsgajegy is elégtelen
(függetlenül a zárthelyik eredményétől). Ez a gyakorlatban azt
jelenti, hogy a zárthelyik eredményei alapján egy 19 és 40
közötti "hozott pontszámot" számítunk ki, ami a két ZH
(IMSC pontok nélküli) összpontszámának 40%-a, és ehhez adódik a
szóbeli vizsgán szerezhető, legfeljebb 60 pont. Ha a szóbeli
részen szerzett pontszám 24-nél kevesebb, akkor a vizsgajegy
elégtelen, egyébként pedig a hozott pontszám és a vizsgán
szerzett pontok összegéből az alábbiak szerint számítjuk a
vizsgajegyet: 40 és 54 pont között elégséges, 55 és 69 pont
között közepes, 70 és 84 pont között jó, végül 85 és 100 pont
között jeles.
Aki elégtelenre vizsgázik, az egy ízben ismétlő vizsgát tehet
amennyiben a vizsgaidőszak hátralévő részében még van
meghirdetett vizsgaalkalom és arra tud jelentkezni. Sikeres
vizsga esetén is tehető javító vizsga. Ismétlő ill. javító
vizsga esetén a zárthelyikből származó eredmények változatlan
módon érvényesek. A férőhelyek függvényében további
ismétlő/javító vizsgára is van lehetőség, azonban ugyanabban
félévben csupán két vizsga díjmentes: a harmadik alkalomtól ez
díjköteles, amit a neptun kiszámláz. Érdemes bölcsen élni ezzel
a lehetőséggel, tudva, hogy aki ugyanazon tárgyból hat vizsgán
is elégtelen eredményt ér el, azt az egyetem tanulmányi okból
elbocsátja.
A vizsgákat megelőző konzultáción a vizsgára való készülés
közben felmerült kérdéseket lehet feltenni. A konzultációk
időpontja és helyszíne a fenti ütemtervben található. A konzultáción bárki részt vehet, nem csak az, aki az éppen soron
következő vizsgára jelentkezett.
A vizsgán (ebből a tárgyból) nem szükséges alkalmi viseletben
megjelenni. A hallgató (egyébként civilizált) öltözködése
a vizsga eredményét semmilyen tekintetben sem
befolyásolja.
Összegyűjtöttünk néhány hasznos tanácsot
a sikeres vizsgázást megkönnyítendő.
IMSC
pontszámok