A számítástudomány alapjai


Ez az előadás elsősorban a villamosmérnök alapképzés (BSc program) VISZAA02 neptun-kód alatt szereplő, 4 kredites tárgyhoz tartozik. A szakot ebben a félévben kezdő hallgatók ezt az elméleti kurzust és egy hozzá tartozó gyakorlatot vegyenek fel. Ugyanehhez a tárgyhoz vizsgakurzus is tartozik. Ezt azok vehetik fel, akik már rendelkeznek VISZAA02 aláírással és nem akarnak ismét aláírást szerezni. A 6 kredites VISZA105 kódú tárgyhoz is tartozik vizsgakurzus. Erre azok jelentkezhetnek, akik rendelkeznek érvényes (azaz 2013-nál nem régebbi) VISZA105 aláírással. Az ezen kurzust felvevő hallgatók a 2013-as tételsorból vizsgáznak. Minden olyan hallgatónak, aki még a régi képzésben kezdett, de nem szerezte meg a VISZA105 aláírást, az új, VISZAA02 kurzust érdemes felvenni, teljesíteni, majd akkreditáltatni, valamint gondoskodni arról, hogy a hiányzó 2 kreditet valamilyen választható tárgyból megszerezze.



Előadások:

Kurzuskód
Időpont
Előadó
Terem
1
hétfő 8:15-10:00 Recski András
(recski@cs.bme.hu)
IB028
2
hétfő 8:15-10:00 Fleiner Tamás
(fleiner@cs.bme.hu)

IB027

Gyakorlatok:

Kurzuskód
Időpont
Gyakorlatvezető
Terem
11
szerda 8:15-9:45
Drótos Márton IB138
12
szerda 8:15-9:45 Nguyen Hai IB139
13
hétfő 10:15-11:45 Nguyen Hai IB145
14
péntek 8:15-9:45 Kaszanitzky Viktória
IB147
15
hétfő 10:15-11:45 Fleiner Tamás
IB138
16
péntek 8:15-9:45 Mihálka Zsuzsanna IB138
17
péntek 8:15-9:45 Berkes Bence IB139
18
hétfő 10:15-11:45 Sári András
IB134
19 hétfő 10:15-11:45 Paulovics Zoltán
IB140
20 hétfő 10:15-11:45 Kecskés Boglárka
IB146
21 hétfő 10:15-11:45 Tőri Tünde
IB147
I1 (IMSC)
szerda 8:15-9:45 Recski András
IB134
I2 (IMSC)
péntek 8:15-9:45 Fleiner Tamás
IB134
Rendszeres
konzultáció

kedd 14:15-15:00 Csákány Rita
IB134
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
2016. szeptember 5.
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 2016. szeptember 12. Gráfelméleti alapfogalmak. Gráfok fokszámösszege, fák egyszerűbb tulajdonságai. Minimális költségű feszítőfa.
Gyakorló feladatsor
2. hét
2016. szeptember 14.  Egyetemi sportnap: a szerdai gyakorlatok elmaradnak
3.hét 2016. szeptember 19. Kruskal algoritmus, helyességének bizonyítása, normál fák definíciója, megkeresésének módja. Legrövidebb utak keresése, BFS. Gyakorló feladatsor
4.hét 2016. szeptember 26. Dijkstra, Ford és Floyd algoritmus, legszélesebb út keresése irányított és irányítatlan gráfban. Gyakorló feladatsor
5.hét 2016. október 3. 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
5.hét 2016. október 7. SCH QPA: a pénteki gyakorlatok elmaradnak
6.hét 2016. október 10. Euler-séta és körséta, létezésének szükséges és elégséges feltétele (összefüggő gráf esetén).  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 2016. október 15.
(szombat)
Munkarend-változás
Gráfok színezése, klikkméret és kromatikus szám viszonya. Páros gráf fogalma. Hálózati folyamok, Ford-Fulkerson tétel, algoritmus maximális folyam keresése, egészértékűségi lemma. Gyakorló feladatsor  
7.hét 2016. október 17. 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. Gyakorló feladatsor 
7.hét 2016. október 20.  8-10 óra  I. ZH feladatok, mintamegoldás
Beosztás:






















Eredmények
8.hét 2016. október 26. Független/lefogó pont-/élhalmazok, Kőnig és Gallai tételei. 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
9.hét 2016. október 31. Az előadás munkarend változás miatt elmarad.
10.hét 2016. november 7. 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). 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. Gyakorló feladatsor
11.hét 2016. november 14. Kongruenciák,  maradékrendszerek, lineáris kongruenciák megoldása.  Gyakorló feladatsor A II. ZH anyaga eddig tart.
12.hét 2016. november 21. 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 2016. november 24.  8-10 óra  II. ZH   feladatok, mintamegoldás
Beosztás:




















Eredmények
12.hét 2016. november 25.  Nyílt nap: a pénteki gyakorlatok elmaradnak
13.hét 2016. november 28. 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
14.hét 2016. december 5. 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
14.hét 2016. december 5.  17-19 óra  pótZH feladatok, mintamegoldás
Beosztás:








Eredmények
Pótlási hét
2016. december ??.
 aláíráspótlás helyszín: ??
Konzultáció (??, ??)

(A VISZA105 kódú régi tárgy tartalma itt érhető el.)







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

                           Fleiner Tamás  digitális jegyzete

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
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 VISZAA02 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 hat darab, egyenként 10 pontot érő feladatból áll, időtartama 90 perc. 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 alkalom mellett lesz még a szorgalmi időszakban egy pótzárthelyi, továbbá a vizsgaidőszak előtti pótlási héten egy aláíráspótló vizsga fedőnevű, újabb pótlási alkalom is. 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 összpntszá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 szorgalmi időszakban tartott 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 részben a 2015. őszi félévtől, részben mostantó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.
Korábbi félévben szerzett aláírás:

Az aláírás a TVSz szerint 3 évig (pontosabban a megszerzését követő  6 félévben) érvényes. Amennyiben egy hallgatónak van érvényes VISZAA02 aláírása, felveheti most is a gyakorlatot. Ezáltal lehetősége lesz az aláírás újbóli megszerezésére a zárthelyik újbóli megírásával és az óralátogatási kötelezettség ismételt teljesítésével. Ekkor az alábbi három eset valamelyike valósul meg.
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 félév végére kialakuló 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 definíciót és tételt pontosan ki tudjon mondani, illetve tudjon értelmezni. Azonban a kevésbé fontos definíciók és tételek esetében, amelyekre nem épül további fogalom, egy-két apró hiba még elfogadható. Mindezen túl 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 20-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.