A számítástudomány alapjai


Ezen 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 a kurzust vegyék fel. A régi tantervben szereplő VISZA105 kódú, 6 kredites tárgyból csak vizsgakurzust indítunk, de kizárólag azok számára, akik már aláírással rendelkeznek ez utóbbi tárgyból. Tehát az új tárgyat kell felvennie és később akkreditáltatnia minden olyan hallgatónak, aki a régi képzésben kezdett, ám még nincs aláírása a régi, 6 kredites tágyból. Továbbá, tekintettel arra, hogy az új tárgy kevesebb kreditet ér, a hiányzó krediteket is pótolni kell szükség esetén majd valamilyen választható tárggyal.

ZH pontszámok

Bővített vizsgatematika a felkészüléshez (VISZAA02)
Vizsgatematika, amit a vizsgán használni fogunk (VISZAA02)

A 2013/14 évi tételsor itt tölthető le, ez érvényes a vizsgakurzusosok vizsgáján (VISZA105).



Előadók:   Katona Gyula Y. (kiskat@cs.bme.hu) és  Fleiner Tamás (fleiner@cs.bme.hu)


Előadás:

Gyakorlatok:

Kurzuskód
 Időpont
 Gyakorlatvezető
 Terem
11
 péntek 8:15-9:45
 Varga Kitti
 		IB134
12
 péntek 8:15-9:45 Lenger Dániel
 		IB138
13
 péntek 8:15-9:45 Herskovics Dávid
 		IB139
14
 péntek 8:15-9:45 Drótos Márton
(honlap) 		QBF10
15
 péntek 8:15-9:45 Marussy Kristóf
 		QBF11
16
 kedd 16:15-17:45 Rácz Dániel
 		IB147
17
 kedd 16:15-17:45 Papp László
 		QBF10
18
 kedd 16:15-17:45 Soltész Dániel
 		QB104
23 szerda 14:15-15:45 Papp László
 		QBF10
24
 szerda 14:15-15:45 Nguyen Hai
 QBF11
25
 szerda 14:15-15:45 Soltész Dániel
 QB104
26
 szerda 14:15-15:45 Vidor Sára
 		IB134
27
 szerda 14:15-15:45 Bencs Ferenc
 IB147

PPZH, Konzultáció, vizsga

Dátum
Terem
2014. december 17. 8:15-9:45
 Aláíráspótló
 IB028 !!
2014. december 19. 10:15-11:45 Konzultáció
 IB134
2014. december 22. 8:30-
 Vizsga
 IB026
2015. január 5. 14:15-15:45 Konzultáció IB134
2015. január  6. 8:00- Vizsga QBF09
2015. január 9. 10:15-11:45 Konzultáció IB134
2015. január  12. 8:30- Vizsga IB025
2015. január 14. 14:15-15:45 Konzultáció IB134
2015. január  15. 8:00- Vizsga IB025
2015. január 16. 14:15-15:45 Konzultáció IB134
2015. január  19. 8:30- Vizsga IB025
2015. január 23. 14:15-15:45 Konzultáció IB134
2015. január  26. 8:30- Vizsga IB025


A tervezett előadások rövid kivonata:
(A VISZA105 kódú régi tárgy tartalma itt érhető el.)

A 2013/14 évi tételsor itt tölthető le, ez érvényes a vizsgakurzusosok vizsgáján.

Az e félévi tételsor csak félév végére alakul ki.

1.hét
 2014. szeptember 8.
 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 2014. szeptember 15. 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
 2014. szeptember 17.  szerdai gyakorlat elmarad
3.hét 2014. szeptember 22. 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 2014. szeptember 29. Floyd algoritmus, legszélesebb út keresése irányított és irányítatlan gráfban. Gyakorló feladatsor
5.hét 2014. október 6. Legszélesebb legrövidebb és legrövidebb legszélesebb út. 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
5.hét 2014. október 10.  pénteki gyakorlat elmarad
6.hét 2014. október 13. 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.
6.hét 2014. október 18.  ezen a szombaton az október 24., pénteki gyakorlat lesz megtartva
7.hét 2014. október 20. 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 2014. október 20.  18-20 óra  I. ZH feladatok, mintamegoldás
7.hét 2014. október 24.  a pénteki gyakorlat október 18.-án, szombaton lesz megtartva
8.hét 2014. október 27. 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 2014. november 3. 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 2014. november 10. 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
10.hét 2014. november 11.  keddi gyakorlat elmarad
11.hét 2014. november 17. Kongruenciák,  maradékrendszerek, lineáris kongruenciák és diofantoszi egyenletek megoldása.  Gyakorló feladatsor A II. ZH anyaga eddig tart.
11.hét 2014. november 21.  pénteki gyakorlat elmarad
12.hét 2014. november 24. 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, coNP bonyolultsági osztályok fogalma, feltételezett viszonyuk, példa ilyen problémákra. Gyakorló feladatsor
12.hét 2014. november 27.  8:15-9:45 óra  II. ZH feladatok, mintamegoldás
13.hét 2014. december 1. 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, HAMÚT
14.hét 2014. december 8. 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.
14.hét 2014. december 8.  18-20 óra  pótZH feladatok, mintamegoldás


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:

Feladatgyűjtemény:  Friedl-Recski-Simonyi: Gráfelméleti feladatok   (Typotex 2006)

Letölthető feladatsor: postscript, PDF,
Ezek a régi tematikához készültek:
2011 őszi ZH feladatok, megoldások
2012 őszi ZH feladatok, megoldások

Animációk gyűjteménye


Értékelés, tárgykövetelmények, vizsga

A kari vezetés rendelkezésének megfelelően az előadásokon és a gyakorlatokon is kötelező a részvétel. Akinek a dékáni utasításban és a tárgy adatlapján meghatározottnál (ebben a félévben 4 előadásnál ill.  3 gyakorlatnál) több hiányzása bizonyítható, az a rendelkezés értelmében nem szerezhet aláírást a tárgyból. Mindezen túl a tárgy kreditje sem szerezhető meg abban az esetben, ha valaki felveszi a gyakorlatot, de a  látogatására vonatkozó előírást nem teljesíti.


Zárthelyik, pótzárthelyik:

A félév során két zárthelyi lesz. Mindkét zárthelyi 6, egyenként 10 pontot érő feladatból áll, időtartama 90 perc. Elégséges osztályzat 40%-os teljesítménytől, azaz 24 ponttól jár. A félévvégi aláírás megszerzésének, azaz a vizsgára bocsátásnak az óralátogatáson túl az a feltétele, hogy külön-külön mindkét zárthelyi legalább elégséges legyen.

A 2007. őszén életbe lépett, 2008 februárjában módosított, jelenleg hatályos TVSz-nek (illetve az ahhoz a BME Oktatási Igazgatósága által közzétett értelmezésnek) megfelelően,  a két zárthelyi közül legalább az egyiket már az első alkalommal (pótlás nélkül) sikeresen kell megírni, és pótolni legfeljebb csak egyet lehet. Ezért a szorgalmi időszak alatt összesen egy pótzárthelyi alkalom lesz, ahol vagy az első, vagy a második (de nem mindkét) zárthelyin elért eredmény javítható vagy pótolható.

A pótzárthelyin a korábban megírt, eredményes zárthelyi javításakor az újonnan kapott pontszám lesz érvényes, kivéve, ha az eredményes zárthelyi javítása elégtelen. Ekkor a megfelelő zárthelyit az elégségeshez szükséges minimális pontszámmal (konkrétan 24 ponttal) vesszük figyelembe.

A kijavított zárthelyi és pótzárthelyi dolgozatokba betekintést biztosítunk.

Aláíráspótló vizsga:

Amennyiben valamelyik zárthelyi elsőre eredményes, ám a másik még a pótzárthelyin sem sikerül, úgy (különeljárási díj megfizetése mellett) marad még egy utolsó lehetőség a vizsgaidőszak előtti pótlási héten a mindaddig eredménytelen zárthelyi újbóli pótlására. Ez a második pótzárthelyi alkalom a TVSz-ben "aláíráspótló vizsga" néven szerepel annak ellenére, hogy ez természetesen nem valódi vizsga.

Mindez tehát azt jelenti, hogy ha valaki a két zárthelyi közül mindkettőn elégtelent ír (vagy nem jelenik meg), akkor ebben a félévben már semmilyen módon nem szerezheti meg az aláírást. Ha viszont valaki a két zárthelyi közül legalább az egyiket már elsőre eredményesen írja meg, akkor a másik zárthelyit összesen akár három alkalommal (a zárthelyin, a pótzárthelyin, illetve az aláíráspótló vizsgán) is megpróbálhatja teljesíteni. Az aláíráspótló zárthelyi helyszínét és időpontját később tűzzük ki. A kijavított dolgozatokba később betekintést biztosítunk.

Figyelem! Az aláíráspótló vizsgán történő zárthelyi pótlásra kizárólag a Neptunban lehet jelentkezni. (Aki ezt elmulasztja, annak az ekkor megszerzett aláírását nem tudjuk a Neptunba könyvelni. Ezért nem tudjuk olyan hallgatónak engedélyezni a pótlást, aki a Neptun-jelentkezést elmulasztotta. A jelentkezések és lemondások a vizsgát megelőző napon 12 órakor lezárulnak.)



Vizsga:

Vizsgára csak az jelentkezhet, aki érvényes aláírással rendelkezik. A vizsgákra a Neptunban kell jelentkezni. 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 a jelentkezést elmulasztotta. 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, amihez hozzáadódik a vizsgán szerezhető  legfeljebb 60 pont. Ha a vizsgán 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 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.

A 2013/14 évi tételsor itt tölthető le, ez érvényes a vizsgakurzusosok vizsgáján.

Az e félévi tételsor csak félév végére alakul ki.