A számítástudomány alapjai

2017/18 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.


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
szerda 10:15-11:45
Fleiner Tamás
IB139
12 szerda 10:15-11:45 Kaszanitzky Viktória E302
13
szerda 10:15-11:45 Drótos Márton IB147
14
szerda 10:15-11:45 Mihálka Zsuzsanna E404
16
péntek 12:15-13:45 Holczer András
IB139
18
péntek 12:15-13:45 Paulovics Zoltán IB145
19
péntek 8:15-9:45 Fleiner Tamás
IB139
20
péntek 8:15-9:45 Kaszanitzky Viktória IB140
21
péntek 8:15-9:45 Nguyen Hai
IB138
22 péntek 8:15-9:45 Tóth Nikolett
IB145
I1 (IMSC)
péntek 8:15-9:45 Recski András
IB134
I2 (IMSC)
csütörtök 15:15-16:45 Fleiner Tamás
IB134
Rendszeres konzultáció kedd 14:00-15:00
Csákány Rita IB217.1
A rendszeres konzultáción bárki (előzetes egyeztetés nélkül) részt vehet. Célja, hogy azon hallgatók, akiknek nehézséget okoz a reguláris gyakorlatok követése, még több lehetőséget kapjanak arra, hogy a kérdéseiket feltehessék és azokra választ kaphassanak. A rendszeres konzultáció látogatása nem érinti a gyakorlatokon való kötelező részvételt.
A tervezett előadások rövid kivonata:

1.hét
2017. szeptember 4.
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 2017. szeptember 11. Gráfelméleti alapfogalmak. Gráfok fokszámösszege, fák egyszerűbb tulajdonságai. Minimális költségű feszítőfa, Kruskal algoritmus.
Gyakorló feladatsor
3.hét 2017. szeptember 18. A Kruskal algoritmus helyességének bizonyítása, normál fák definíciója, megkeresésének módja. Legrövidebb utak és gráfbejárás  fogalma, BFS, legrövidebb utak fája.
Gyakorló feladatsor
3. hét
2017. szeptember 20. Egyetemi Sportnap, a szerdai gyakorlatok elmaradnak.
4.hét 2017. szeptember 25. Dijkstra, Ford és Floyd algoritmusai, legszélesebb út keresése irányított és irányítatlan gráfban.
Gyakorló feladatsor
4.hét 2017. szeptember 28-29. SCH QPA: a csütörtöki és pénteki gyakorlatok elmaradnak
5.hét 2017. október 2. 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 2017. október 9. 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.
7.hét
2017. október 16.
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 
8.hét 2017. október 23. Nemzeti ünnep: az előadás elmarad
8.hét 2017. október 26. 8-10 óra I. ZH feladatok, mintamegoldás  Eredmények
Terembeosztás (vezetéknév kezdőbetűje szerint):
A-D
E-J
K
L-M
N-R
S-Zs
IB028
IB025
IB026
IE007
E1C
E1B

9.hét 2017. október 30. 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, Algoritmus maximális párosítás keresésére páros gráfban. Független/lefogó pont-/élhalmazok, Kőnig és Gallai tételei.
Gyakorló feladatsor 
9.hét 2017. november 1. Mindenszentek: a szerdai gyakorlatok elmaradnak.
10.hét 2017. november 6. 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. 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 2017. november 13. 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,  maradékrendszerek, lineáris kongruenciák megoldása.
Gyakorló feladatsor
A II. ZH anyaga eddig tart. 
11.hét 2017. november 16. TDK konferencia: a csütörtöki gyakorlat elmarad
12.hét 2017. november 20. Euler-Fermat-tétel. Algoritmusok bonyolultsága (input mérete, algoritmus lépésszáma az inputméret függvényében, polinomidejű algoritmus), döntési problémák. P, NP, co-NP bonyolultsági osztályok fogalma, feltételezett viszonyuk, példa ilyen problémákra.
Gyakorló feladatsor
12.hét 2017. november 24.  Nyílt nap: a pénteki gyakorlatok elmaradnak
13.hét 2017. november 27. 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.
Gyakorló feladatsor
13.hét 2016. november 30.  8-10 óra  II. ZH   feladatok, mintamegoldás Eredmények
Beosztás:














Eredmények
14.hét 2017. december 4. Számelméleti algoritmusok: alapműveletek, (modulo m) hatványozás és az euklideszi algoritmus lépésszáma. 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 2016. december 14.  ?? óra  pótZH feladatok, mintamegoldás Eredmények
Beosztás:






Eredmények
1. vizsgahét

8-10 aláíráspótlás helyszín: 
Eredmények
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űjtemény is.
2014 őszi ZH feladatok, megoldások
2015 őszi ZH feladatok, megoldások
2016 ő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óinak.

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.


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.