A számítástudomány alapjai

2018/19 első félév


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. A korábban tanított, 4 kredites VISZAA02 tárgyhoz vizsgakurzus tartozik. Ezt azok a hallgatók vehetik fel, akiknek érvényes VISZAA02 aláírásuk van, és csupán vizsgázni szeretnének. Akik tehát a vizsgakurzust veszik fel, azok nem vesznek fel gyakorlatot, és a félév végén 4 kreditért vizsgáznak. Természetesen érvényes aláírás birtokában is fel lehet venni a VISZAA05 kurzust (egy hozzá tartozó gyakorlattal), ám ekkor csakis az aláírás újbóli megszerzése után lehet vizsgázni, értelemszerűen 5 kreditért.

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
hétfő 8:15-10:00 Fleiner Tamás
(fleiner@cs.bme.hu)

Q-I

Gyakorlatok:

Kurzuskód
Időpont
Gyakorlatvezető
Terem
11
kedd 10:15-11:45
Tóth Ádám
IB147
12 kedd 10:15-11:45 Varga Kitti IB139
13
kedd 10:15-11:45 Wiener Gábor IB140
14
kedd 10:15-11:45 Balassa Ádám IB145
15
kedd 10:15-11:45 Schwarcz Tamás
IB146
16
kedd 10:15-11:45 Nguyen Hai R504
18
csütörtök 10:15-11:45 Varga Kitti
IB139
19
csütörtök 10:15-11:45 Wiener Gábor IB140
20
csütörtök 10:15-11:45 Katona Dániel
IB145
22 csütörtök 10:15-11:45 Mihálka Zsuzsanna
IB138
I1 (IMSC)
kedd 10:15-11:45 Fleiner Tamás
IB134
I2 (IMSC)
csütörtök 8:15-9:45 Fleiner Tamás
IE217.1

Ütemterv:

1.hét
2018. szeptember 3.
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.
Gyakorló feladatsor
2.hét 2018. szeptember 10. Gráfelméleti alapfogalmak. Gráfok fokszámösszege, fák egyszerűbb tulajdonságai.
Gyakorló feladatsor
3.hét 2018. szeptember 17. Minimális költségű feszítőfa, Kruskal algoritmus. Legrövidebb utak és gráfbejárás  fogalma, BFS.
Gyakorló feladatsor
3. hét
2018. szeptember 20. Egyetemi Sportnap: a csütörtöki gyakorlatok elmaradnak.
4.hét 2018. szeptember 24. A BFS tulajdonságai, legrövidebb utak fája. Dijkstra, Ford és Floyd algoritmusai.
Gyakorló feladatsor
5.hét 2018. október 1. Legszélesebb út keresése irányítatlan gráfban. Mélységi keresés, irányított körök keresése, aciklikus gráfok jellemzése. Alapkörrendszer (fundamentális körrendszer), fundamentális vágásrendszer, PERT feladat, megoldásnak algoritmusa.
Gyakorló feladatsor
6.hét 2018. október 8. Euler-séta és körséta, létezésének 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.
Gyakorló feladatsor
Az I. ZH anyaga eddig tart.
6.hét 2018. október 13. Csütörtöki munkarend
7.hét
2018. október 15.
Gráfok színezése, klikkméret és kromatikus szám viszonya. Páros gráf fogalma, jellemzése. Hálózati folyamok, Ford-Fulkerson tétel, algoritmus maximális folyam keresése.
Gyakorló feladatsor 
7.hét 2018. október 19. 8-10 óra I. ZH feladatok, mintamegoldás 
Terembeosztás (vezetéknév kezdőbetűje szerint):
A-F
G-H
I-Pá
Pe-Zs
Q-I
Q-II
K234
ChFMax

8.hét 2018. október 22. Nemzeti ünnep miatti munkanapátyelyezés: az előadás elmarad
8.hét 2018. október 23. Nemzeti ünnep: a keddi gyakorlatok elmaradnak
9.hét 2018. október 29. Egészértékűségi lemma, Edmonds-Karp tétel, többtermelős, többfogyasztós hálózatok, csúcskapacitások és irányítatlan élek visszavezetése szokásos hálózatra. 
Páros gráfok, párosítások, Hall-tétel. Független/lefogó pont-/élhalmazok, Kőnig és Gallai tételei.
Gyakorló feladatsor 
9.hét 2018. november 1. Mindenszentek: a csütörtöki gyakorlatok elmaradnak.
10.hét 2018. november 5. Kőnig és Hall tételek bizonyítása, algoritmus maximális párosítás keresésére páros gráfban. Síkbarajzolhatóság, gömbre rajzolhatóság. Az Euler-féle poliédertétel és következményei egyszerű, síkbarajzolható gráfokra. Kuratowski gráfok, topologikus izomorfia, Kuratowski tétele.
Nem szerepel idén: 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).
Gyakorló feladatsor
11.hét 2018. november 12. Síkgráfok kromatikus száma, négyszíntétel.
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.
Gyakorló feladatsor
A II. ZH anyaga eddig tart. 
12.hét 2018. november 19. Maradékrendszerek, Euler-Fermat-tétel. Algoritmusok bonyolultsága (input mérete, algoritmus lépésszáma az inputméret függvényében, polinomidejű algoritmus).
Gyakorló feladatsor
12.hét 2018. november 23.  8-10 óra  II. ZH   feladatok, mintamegoldás
Terembeosztás (vezetéknév kezdőbetűje szerint):
A-F
G-H
I-Pá
Pe-Zs
Q-I
Q-II
K234
ChFMax

13.hét 2018. november 26. 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.
Gyakorló feladatsor
14.hét 2018. december 1. Rektori szünet: az előadás elmarad
14.hét 2018. december 3. k-SZÍN, MAXFTN, MAXKLIKK NP-teljessége. Prímtesztelés, Fermat-teszt. Nyilvános kulcsú titkosírás, digitális aláírás. Az RSA titkosítási módszer.
Gyakorló feladatsor
Pótlási hét 2018. december 12.
8-10 óra pótZH feladatok, mintamegoldás
Terembeosztás (vezetéknév kezdőbetűje szerint):
A-L
M-Zs
IB028
IB027

Pótlási hét
2018. december 17.
10-12 IE216.1
Konzultáció
Pótlási hét 2018. december 17.
10-12 IB028
aláíráspótlás
Pótlási hét 2018. december 20. 10-12 IB134
Konzultáció
Pótlási hét 2019. január 3.
10-12 IB134
Konzultáció
Pótlási hét 2019. január 7.
10-12 IB134
Konzultáció
Pótlási hét 2019. január 14. 10-12 IB134
Konzultáció


Jegyzetek:   Katona-Recski-Szabó: A számítástudomány alapjai   (Typotex 2002, 2003)

                       NESZ

További segédanyagok:

Gyakorló feladatok 
Friedl-Recski-Simonyi:
Gráfelméleti feladatok   (Typotex 2006)
Van egy letölthető
példatár is, sőt, egy animációgyűjtermé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
A régi tematikához hasznos lehet:
2010 őszi ZH feladatok, megoldások
2011 őszi ZH feladatok, megoldások
2012 ő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 4-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.

Zárthelyik, pótzárthelyik, aláírás:

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 pontszámokat
konvertáljuk aláírásra ill. a szerzett összpontszámot 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, 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 az adott zárthelyin és - a szándékunk szerint - ezek 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 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, az "aláíráspótló vizsgán" viszont csak az vehet részt, aki arra a neptunban jelentkezik.

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 valamelyik előadóját legalább egy héttel az első pótzárthelyi időpontja előtt.

A kijavított zárthelyi és pótzárthelyi dolgozatokba a dolgozatok kijavítását követő gyakorlaton betekintést biztosítunk, és jogos reklamáció esetén az elért pontszámot  módosítjuk. Később is lehetőség van a betekintésre, ám ekkor a pontszámon már nem módosítunk.

Aláíráspótló vizsga:

A fentebb említett, a 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ó vizsga időpontja (körülbelül a szorgalmi időszak közepétől) a neptunból deríthető ki. Az aláíráspótló vizsgán írt dolgozatokat még aznap kijavítjuk és biztosítjuk abba a betekintést. (Ennek a pontos 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.

Változások a tárgykövetelményekben:

A tárgykövetelményekkel kapcsolatban eddig leírtak a 2016. őszi félévtől érvényesek. A tanulmányaikat korábban megkezdett hallgatók kedvéért alább összefoglaljuk, hogy a fentiek pontosan milyen változásokat jelentenek a korábban érvényes szabályokhoz képest.
Vizsga:

Vizsgázni csak az jöhet, aki a neptunban jelentkezett az adott vizsgaalkalomra, továbbá a vizsgára jelentkezéshez érvényes aláírással rendelkezik. Felhívjuk a figyelmet arra, hogy a neptun csak a vizsgára jelentkezett hallgatók eredményeinek a felvitelét engedélyezi, így nincs lehetőségünk olyan hallgatót vizsgáztatni, aki bármilyen okból nincs a neptun által generált vizsgalapon. A jelentkezések és lemondások a vizsgát megelőző napon 12 órakor lezárulnak. Elővizsgát nem tartunk.

A 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 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 bizonyosan kap 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 neptunban szintén megtalálható, de a konzultációra nem kell (és nem is lehet) jelentkezni. 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:

10-10 IMSC pontot lehet szerezni a két ZH mindegyikén a fent leírtak szerint, pótlás esetén a legutolsónak megírt dolgozatok alapján. További 10 IMSC pont szerezhető a szóbeli vizsgán mégpedig úgy, hogy a szóbelin nyújtott teljesítményt (az esetlegesen feltett, mélyebb megértést ellenőrző kérdéseket is beleértve) legfeljebb 72 ponttal értékeljük. Ez, illetve ebből legfeljebb 60 számít a vizsgajegybe. A 60-on felüli pontszám 5/6-odrésze pedig IMSC pontként kerül jóváírásra azzal, hogy a tárgyból összesen megszerezhető IMSC pontszám nem lehet 25-nél több.

Adatellenőrzés
A vizsgát követően mindenki győződjön meg arról, hogy a neptunba helyesen került be a vizsga eredménye és a félév során esetlegesen összegyűjtött IMSC pontszáma. Tömegével kell adminisztrálnunk ezeket az adatokat, és időnként sajnos hibázunk. Azonban minél hamarabb kapunk visszajelzést erről, annál hamarabb tudjuk korrigálni a hibát, és az esetleges negatív következményeknek elejét venni.

Extra stressz!!

A következő jelenségre hívjuk fel a figyelmet. Úgyszólván minden évben előfordul, hogy a vizsga előtt a jelentkezett hallgatók jó része nem érzi magát eléggé felkészültnek, ezért átjelentkezik egy későbbi alkalomra. Sőt, ezt akár többször is megteszi. Sajnos az is megesik, hogy valaki elégtelenre vizsgázik, és ezért szeretne ismétlő vizsgát tenni. Mindennek az eredménye, hogy az utolsó 1-2 vizsgaalkalommal a létszámkorlátnál lényegesen többen szeretnének próbálkozni. Ilyenkor aztán rengeteg kérést szoktunk kapni a létszámkorlát felemelésére. Mivel a vizsgáztatók időbeosztását jó előre meg kell határoznunk és a tanszék kapacitása amúgy is véges (és nem túl nagy), ezért erre egészen biztosan nem leszünk képesek. Ennek megfelelően csak az jöhet vizsgázni, aki befér az eredeti létszámkorlátba. Aki tehát várólistán marad a vizsga kezdetére, az sajnos egyáltalán nem jöhet. (A vizsgához ugyanis időnként várólistát is készítünk, hogy a jelentkezők sorba tudjanak állni a visszalépők miatt felszabaduló helyekért. Ennek az az egyedüli célja, hogy ne kelljen azon versenyezni, ki csap le hamarabb egy hirtelen adódó lehetőségre.) Mindannyiunk érdekében kérjük azt is, hogy aki már biztosan nem fog eljönni egy alkalomra, az mihamarabb jelentkezzen le (akkor is, ha várólistán van), hogy a várólistán maradóknak minél több esélye legyen. Azért sem butaság ezt időben megtenni, mert aki feljelentkezve marad, és így igazolatlan távollétet nyer, arra a neptun pénzbüntetést szabhat ki. A jelentkezések és lemondások a vizsgát megelőző napon 12 órakor lezárulnak: az ezt követő állapot végleges. Tudjuk, hogy rém kellemetlen, ha valaki mindössze 20 órával a vizsga előtt tudja meg, hogy jöhet vagy sem az adott számonkérésre. Sajnos ez a rendszer sajátosságából adódik, így ezen nem tudunk segíteni.

Mindezek miatt tisztelettel azt javasoljuk, hogy mindenki igyekezzék már az elsőnek választott alkalomra megfelelően felkészülni. Ez talán a legfrappánsabb módszer a fentiek miatti bosszúság elkerülésére.