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 2012-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.


Kialakult a vizsgatematika, amit a szóbelin használunk.


Előadók:  Fleiner Tamás (fleiner@cs.bme.hu)  és Recski András (recski@cs.bme.hu) 

Előadás:

Gyakorlatok:

Kurzuskód
Időpont
Gyakorlatvezető
Terem
11
péntek 10:15-11:45
Kovács István
V1109
12
péntek 10:15-11:45 Csehi Csongor
IB140
13
péntek 10:15-11:45 Sári András
IB145
14
péntek 10:15-11:45 Drótos Márton
IB146
15
péntek 10:15-11:45 Kecskés Boglárka
IB147
16
szerda 8:15-9:45 Mann Zoltán
IB138
17
szerda 8:15-9:45 Kovács István E405
18
szerda 8:15-9:45 Mihálka Éva
IB139
19 szerda 8:15-9:45 Berkes Bence
IB145
21 szerda 8:15-9:45 Csehi Csongor IB140
22 szerda 8:15-9:45 Fleiner Tamás
QA202
23 szerda 8:15-9:45 Simonyi Gábor
QB104
24
péntek 10:15-11:45 Simonyi Gábor QB104
25
péntek 10:15-11:45 Nguyen Hai
QBF11
26
péntek 10:15-11:45 Fleiner Tamás
QBF10
E1 (emelt szint)
szerda 8:15-9:45 Katona Gyula
IB134
E2 (emelt szint)
péntek 10:15-11:45 Katona Gyula IB134
Az emelt szintű gyakorlatot azoknak ajánljuk, akik a tárgy iránt érdeklődnek és kicsit magasabb szintű feladatokra vágynak. Akik ide járnak, azok számára a ZH és minden egyéb tárgykövetelmény ugyanaz, mint a többieknek.


A tervezett előadások rövid kivonata:

1.hét
2015. 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
Gyakorló feladatsor
2.hét 2015. szeptember 14. 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
2015. szeptember 16.  Egyetemi sportnap: a szerdai gyakorlat elmarad
3.hét 2015. szeptember 21. 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, Dijkstra Ford algoritmus. Gyakorló feladatsor
4.hét 2015. szeptember 28. Floyd algoritmus, legszélesebb út keresése irányított és irányítatlan gráfban. Gyakorló feladatsor
5.hét 2015. október 5. Mélységi keresés, irányított körök keresése, alapkörrendszer (fundamentális körrendszer), fundamentális vágásrendszer, Gyakorló feladatsor
6.hét 2015. október 12. PERT feladat, megoldásnak algoritmusa. 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.
7.hét 2015. október 19. 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 2015. október 22.  8-10 óra  I. ZH feladatok, mintamegoldás
Beosztás:
A-Ba
Be-C
D-F
G-Kiss
Kl-L
M
N-R
S-Sza
Sze-Tor
Tóth-W
Z
IB025
E1A
IB026
KF51
E1C
F2E
KF76
K174
IE007
F29
IB027
Eredmények
7.hét 2015. október 23.  Nemzeti ünnep: a pénteki gyakorlat elmarad
8.hét 2015. október 26. 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 
9.hét 2015. november 2. 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
10.hét 2015. november 9. 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
A 10. feladat szereplői kitalált alakok. Bárminemű egyezés a valósággal kizárólag a véletlen műve.
11.hét 2015. november 16. Kongruenciák,  maradékrendszerek, lineáris kongruenciák megoldása.  Gyakorló feladatsor A II. ZH anyaga eddig tart.
12.hét 2015. november 23. 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 2015. november 26.  8-10 óra  II. ZH   feladatok, mintamegoldás
Beosztás:
A-Ba
Be-Cs
D-F
G-Kl
Ko-L
M
N-R
S-Szi
Szk-T
U-Zs
IB025
E1A
IB026
KF51
E1C
K174
Q-II
F29
F2E
IE007
Eredmények
12.hét 2015. november 27.  Nyílt nap: a pénteki gyakorlat elmarad
13.hét 2015. november 30. 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
A bulvármédia is kidolgozott egy vázlatot a fenti témáról. Annak érdemes ebből  a forrásból készülni, aki nagyon gyorsan szeretné letudni a szóbelit, és ezt követően másodszorra is szívesen megpróbálkozna a vizsgával. Azok számára, akik inkább az órán elhangzottakat tanulják meg, komoly kihívás annak a mondatnak a megkeresése a fenti vázlatban, amelyik a legtöbb sületlenséget tartalmazza. (Ez a probléma ugyanis egyáltalán nem polinomikus.)
14.hét 2015. december 7. 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 2015. december 7.  17-19 óra  pótZH feladatok, mintamegoldás
Beosztás:
A-F
G-K
L-R
S-Zs
St F nagy
Q-I
E1B
K 2.34
Eredmények
Pótlási hét
2015. december 18.
10-12 óra aláíráspótlás helyszín: IB028
Konzultáció (IB134, 10-12)

2016. január 8. Konzultáció (IB134, 10-12)

2016. január 15. Konzultáció (IB134, 13-15)

2016. jaunár 22.
Konzultáció (IB134, 14-16)

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







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

                           Fleiner Tamás  digitális jegyzete: http://www.cs.bme.hu/~fleiner/jegyzet/  

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
A régi tematikához hasznos lehet:
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 dékáni utasításban és a tárgy adatlapján meghatározottnál (ebben a félévben 3-nál) több hiányzása bizonyítható, az a rendelkezés ill. a TVSz 14§(3) értelmében nem szerezhet sem aláírást, sem kreditet a VISZAA02 tárgyból.

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árthelyikre osztályzatot nem adunk, hanem az azokon szerzett pontszámokat konvertáljuk aláírásra ill. a szerzett összpontszámot beszámítjuk a vizsgajegybe. A zárthelyi megírásakor az alábbi szabályok betartását szigorúan megköveteljük.

Kérjük, hogy mindazon hallgatók, akikre a dolgozatíráskor speciális szabályokat kell alkalmazni, ezt jelezzék a tárgy előadóinak legkésőbb egy héttel a dolgozatírás előtt.

A félév végi aláírást az szerzi meg (vagyis a 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ótzárthelyi 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 30%-ot (azaz 18 pontot), akár mert az összpontszáma 40% (azaz 48 pont) alá csökken), akkor ettől az aláírása még megmarad és a vizsga eredményébe 40%-os eredmény 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 jelentkezni a neptunban, 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 (emailben 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 gyakorlaton betekintést biztosí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 2015. ő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. Az aláírás megszerzéséhez a továbbiakban

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 kell rendelkezni. 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 imént 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 definíciót és tételt ki tudjon mondani, illetve tudjon értelmezni. Számítani kell arra, 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 16 és 40 közötti "hozott pontszámot"  számítunk ki, ami a két ZH összpontszámának a harmada (vagy ha ez kevesebb 16-nál, akkor 16) és ehhez hozzáadódik a 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áltozatlanul érvényesek.

A vizsgákat megelőző munkanapokon tartott 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 a 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.


Tanácsok vizsgára


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 vizsgalkalommal 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), 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ó helyekre. 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.