A számítástudomány alapjai

2019/20 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. 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.

A két kurzushoz természetesen külön tételsorok tartoznak: egy, a félév végére kialakuló 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
kedd 12:15-13:45
Horváth Bálint
IB138
12 kedd 12:15-13:45 Telekes Márton
IB139
13
kedd 12:15-13:45 Tóth Sára IB140
14
kedd 12:15-13:45 Vékássy Áron
IB145
15
kedd 12:15-13:45 Katona Dániel
E407
16
csütörtök 10:15-11:45 Horváth Bálint IB138
18
csütörtök 10:15-11:45 Rábai Domonkos IB140
19
csütörtök 10:15-11:45 Schwarcz Tamás
IB145
20
csütörtök 10:15-11:45 Nguyen Tuan Hai
IB146
I1 (IMSC)
kedd 12:15-13:45 Fleiner Tamás
IE218
I2 (IMSC)
péntek 8:15-9:45 Fleiner Tamás
IB134

Ütemterv:

1.hét
2019. szeptember 10.
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
2019. szeptember 12. Egyetemi Sportnap: a csütörtöki gyakorlatok elmaradnak.
2.hét 2019. szeptember 17. Gráfelméleti alapfogalmak. Gráfok fokszámösszege, fák egyszerűbb tulajdonságai.
Gyakorló feladatsor
3.hét 2019. szeptember 24. Minimális költségű feszítőfa, Kruskal algoritmus. Legrövidebb utak és gráfbejárás  fogalma, BFS.
Gyakorló feladatsor
4.hét 2019. október 1. Schönherz Qpa: az előadás és a gyakorlatok elmaradnak.
5.hét 2019. október 8. A BFS tulajdonságai, legrövidebb utak fája. Dijkstra, Ford és Floyd algoritmusai.
Gyakorló feladatsor
6.hét 2019. október 15. 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. PERT feladat, megoldásnak algoritmusa.
Gyakorló feladatsor
7.hét
2019. október 22.
Alapkörrendszer (fundamentális körrendszer), fundamentális vágásrendszer.
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.
8.hét 2019. október 29. Gráfok színezése, klikkméret és kromatikus szám viszonya. Hálózati folyamok, Ford-Fulkerson tétel, algoritmus maximális folyam keresése, Edmonds-Karp tétel.
Gyakorló feladatsor 
2019. november 1. Mindenszentek: a pénteki gyakorlat elmarad.
9.hét 2019. november 5. 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. Független/lefogó pont-/élhalmazok, Kőnig és Gallai tételei. Páros gráf fogalma, jellemzése. Párosítások, Kőnig és Hall tétei.
Gyakorló feladatsor 
2019. november 7. 8-10 óra I. ZH feladatok, mintamegoldás 
Terembeosztás (vezetéknév kezdőbetűje szerint):

K234 E1B
CHMax
A-Ke
Ki-Kü
L-Zs

10.hét 2019. november 12. TDK konferencia: az előadás és a gyakorlatok elmaradnak.
11.hét 2019. november 19. 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.
Gyakorló feladatsor
12.hét 2019. november 26. 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.
A II. ZH anyaga eddig tart. 
Gyakorló feladatsor
2019. november 29. Nyílt nap: a pénteki gyakorlat elmarad
13.hét 2019. december 3. 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 NP-teljessége.
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.
Gyakorló feladatsor
2019. december 5. 8-10 óra  II. ZH   feladatok, mintamegoldás
Terembeosztás (vezetéknév kezdőbetűje szerint):

K234
E1B
CHMax
A-Ke
Ki-Kü
L-Zs

2019. december 7. Munkanapáthelyezés miatt: pénteki gyakorlat
14.hét 2019. december 10. 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).
Gyakorló feladatsor
Pótlási hét 2019. december 18.
10-12 óra pótZH feladatok, mintamegoldás
Terembeosztás (vezetéknév kezdőbetűje szerint):
Q1





2020. január 3.
10-12 aláíráspótlás, IB028

2019. december ??. 10-12 IB134
Konzultáció

2020. január ??.
10-12 IB134
Konzultáció

2020. január ??.
10-12 IB134
Konzultáció

2020. január ??. 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
2018 ő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.

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 ö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. Ezzel szemben az "aláíráspótló vizsgán" csak az vehet részt, aki ebben a félévben még nem szerzett aláírást, de egyetlen ZH sikeres megírásával az aláírás megszerezhető. Az aláíráspótló vizsgát csak az írhatja meg, aki arra előzetesen jelentkezik a neptunban.

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

A TVSZ 2019-es változása nyomán a megszerzett aláírások érvényességének korábbi 6 féléves korlátozása megszűnt, így akinek a korábbi szabályok szerint 2019 szeptemberében érvényes aláírása volt, annak azt később már nem kell újra megszereznie.

Szóbeli 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 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 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.