BME VIK - A számítástudomány alapjai

3. A tantárgyfelelős személy és tanszék Dr. Katona Gyula,

A tantárgy tanszéki weboldala www.cs.bme.hu/sza

4. A tantárgy előadója

Név:	Beosztás:	Tanszék, Int.:
Dr. Katona Gyula	egyetemi docens	Számítástudományi és Információelméleti Tanszék
Dr. Fleiner Tamás	egyetemi docens	Számítástudományi és Információelméleti Tanszék
Dr.Sali Attila	egyetemi docens	Számítástudományi és Információelméleti Tanszék
Dr. Recski András	egyetemi tanár	Számítástudományi és Információelméleti Tanszék
Dr. Mann Zoltán	egyetemi docens	Számítástudományi és Információelméleti Tanszék

7. A tantárgy célkitűzése

A villamosmérnöki tanulmányokhoz szükséges legfontosabb matematikai ismeretek elsajátítása, az algebra és diszkrét matematika szemléletmódjának kialakítása.

8. A tantárgy részletes tematikája

1. hét	leszámlálási alapfeladatok, permutáció, kombináció, variáció, binomiális tétel
	összetett leszámlálási feladatok, skatulya-elv, szita-formula
2. hét	alapvető adatstruktúrák: tömb, láncolt lista, bináris fa, kupac
	keresés lineárisan és binárisan, lépésszámok elemzése, minimum keresés, beszúrási feladat
3. hét	rendezési feladat, buborék-, kiválasztásos-, összefésüléses-, gyorsrendezés
	kupacos rendezés, rendezés bináris keresőfával, alsó korlát, ládarendezés
4. hét	gráfelméleti alapfogalmak, gráfok adatstruktúrái, szomszédossági mátrix, éllista, szomszédossági lista
	fák, alaptulajdonságaik, Prüfer-kód, minimális súlyú feszítőfa, Kruskal-algoritmus, normál-fák
5. hét	Euler- és Hamilton-körök, szükséges ill. elégséges feltételek létezésükre, legrövidebb utak keresése, BFS
	Dijkstra, Ford, Floyd algoritmusok, legszélesebb út keresése irányított és irányítatlan gráfban, legszélesebb legrövidebb és legrövidebb legszélesebb út
6. hét	hálózati folyamok, Ford-Fulkerson tétel, algoritmus maximális folyam keresésére
	folyamproblémák általánosításai, él- ill. pontidegen utak maximális száma, Menger tételei, többszörös összefüggőség
7. hét	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, párosítás tetszőleges gráfban, Tutte-tétel
8. hét	gráfok színezése, klikkszám és kromatikus szám viszonya, Mycielski konstrukció, Brooks tétel, élszínezés, Vizing tétel
	síkbarajzolható gráfok, Euler-formula, Kuratowski tétel, dualitás
9. hét	gyenge izomorfia, Whitney tételei, síkgráfok színezése, 5- és 4-szín tétel
	mélységi keresés, irányított körök keresése, alapkörrendszer (=fundamentális körrendszer), fundamentális vágásrendszer, PERT
10. hét	algoritmusok bonyolultsága, P, NP, coNP osztályok
	NP-teljes problémák, módszerek nehéz problémák kezelésére
11. hét	oszthatóság, Euklideszi algoritmus, prímek, számelmélet alaptétele, osztók száma
	tételek a prímek eloszlásáról, maradékrendszerek, Euler-Fermat-tétel
12. hét	lineáris kongruenciák és diofantoszi egyenletek megoldása, Wilson-tétel
	absztrakt algebra: művelet, félcsoport, csoport, példák csoportokra
13. hét	izomorfia, részcsoport, ciklikus csoport, mellékosztály
	Lagrange tétel, gyűrűk, polinomgyűrűk, testek, véges testek, kvaterniók, hányadostest
14. hét	kriptográfiai módszerek, nyilvános kulcsú titkosítás, RSA kódolás

9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) Heti 4 óra előadás az egész évfolyamnak, és heti 2 óra kiscsoportos gyakorlat.

10. Követelmények

Az előadások és a gyakorlatok látogatása kötelező. Az előadásokon a jelenlétet azok kezdetén és végén is a félév folyamán minden alkalommal ellenőrizzük, aláírást nem kaphat az a hallgató, aki ezek alapján az alkalmak több, mint 30%-áról hiányzott (a viszonyítási alap a ténylegesen megtartott előadások száma). A gyakorlatokon a jelenlétet minden alkalommal ellenőrizzük, 30%-ot meghaladó hiányzás esetén a tantárgyból sem aláírás sem kreditpont nem szerezhető.

A szorgalmi időszakban:

A félév folyamán két zárthelyit íratunk. A félév végi aláírás megszerzésének (vagyis a vizsgára bocsátásnak) feltétele, hogy mindkét zárthelyinek külön-külön legalább elégségesre kell sikerülnie. A zárthelyihez van egy pótlási lehetőség: ilyenkor az egyik elégtelen kijavítható, illetve az esetleges hiányzás pótolható. A pótzárthelyin gyenge, de nem elégtelen zárthelyi javítása is megkísérelhető, de csak azzal a feltétellel, hogy ilyenkor mindenképpen az új pontszám lesz érvényes, akkor is, ha rosszabb, mint az eredeti. (Ez alól egy kivétel van: a már megszerzett aláírás egy javítónak szánt, de elégtelenre megírt pótzárthelyivel nem vész el, viszont az adott zárthelyit úgy tekintjük, mintha azon a hallgató az elégségeshez szükséges minimális pontszámot érte volna el.) Amennyiben a szorgalmi időszakban nem sikerült mindkét zárthelyin (vagy a megfelelő pótzárthelyin) legalább elégségest szerezni, akkor a pótlási héten a sikertelen zárthelyi pótlására még egy lehetőség van. (Ha egyik zárthelyi sem volt sikeres, akkor a pótlási időszakban már nem lehet aláírást szerezni.)

A vizsgaidőszakban:

A tárgyból szóbeli vizsga van. A vizsga úgy zajlik, hogy a tételsoron szereplő tételek közül a vizsgázó egyet kap, ezt kidolgozza, majd szóban felel belőle. Számítani kell arra is, hogy a vizsgáztató néhány definíció, vagy tétel kimondása erejéig a többi tételbe is belekérdez. A vizsgán 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. A vizsgatétel kidolgozására a hallgatónak felkészülési idő áll rendelkezésére. 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 vizsgajegyet a két zárthelyi eredményéből és a vizsgán nyújtott szóbeli teljesítményből alakítjuk ki olyan módon, hogy abba a zárthelyik átlaga 40 százalék erejéig, a szóbeli vizsga 60 százalék erejéig számít bele. Ha a szóbeli vizsga elégtelen, akkor a vizsgajegy is elégtelen (függetlenül a zárthelyik eredményétől). Javító (ismétlő) vizsga a TVSz szerint tehető. Javító vizsga esetén a zárthelyikből származó eredmények változatlanul érvényesek.

Az aláírás a TVSz szerint 3 évig érvényes.

Amennyiben a hallgatónak már van aláírása korábbi félévből, akkor lehetősége van megkísérelni újból megszerezni az aláírást a zárthelyik újbóli megírásával.

Ha sikerült újra teljesíteni a feltételeket, akkor a vizsgajegybe ezek az eredmények számítanak bele (akkor is ha ezek összességében gyengébbek).
Ha megkísérelte, de nem sikerült megszerezni az aláírást, akkor az aláírás nem vész el, de a vizsgajegybe csak az aláírás megszerzéséhez szükséges minimális pontszámmal számítjuk be.
Ha nem kísérelte meg (nem vett részt egyetlen zárthelyin vagy pótláson sem az adott félévben), akkor a legutolsó olyan félévbeli teljesítményét vesszük figyelembe, amikor a hallgató megkísérelt aláírást szerezni.

11. Pótlási lehetőségek lásd a 10. pontot

12. Konzultációs lehetőségek A zárthelyik előtt konzultációs lehetőséget biztosítunk.

13. Jegyzet, tankönyv, felhasználható irodalom Katona Y. Gyula - Recski András - Szabó Csaba: A számítástudomány alapjai, TypoTEX Kiadó, 2003.Friedl Katalin – Recski András – Simonyi Gárbor: Gráfelméleti feladatok, TypoTEX Kiadó 2006.

14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka

Kontakt óra	84
Félévközi készülés órákra	28
Felkészülés zárthelyire	12
Házi feladat elkészítése
Kijelölt írásos tananyag elsajátítása
Vizsgafelkészülés	56
Összesen	180

15. A tantárgy tematikáját kidolgozta

Dr. Recski András	egyetemi tanár	Számítástudományi és Információelméleti Tanszék
Dr. Katona Gyula	egyetemi docens	Számítástudományi és Információelméleti Tanszék