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.




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
21
kedd 16:15-17:45 Pácsonyi Imre
?
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



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
Gyakroló 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,
Gyakroló 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.
4.hét 2014. szeptember 29. Floyd algoritmus, legszélesebb út keresése irányított és irányítatlan gráfban, 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, PERT feladat, megoldásnak algoritmusa.
5.hét 2014. október 6. 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.
5.hét 2014. október 10.  pénteki gyakorlat elmarad
6.hét 2014. október 13. 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.
6.hét 2014. október 18.  ezen a szombaton az október 24., szombati gyakorlat lesz megtartva
7.hét 2014. október 20. Többtermelős, többfogyasztós hálózatok, csúcskapacitások és irányítatlan élek visszavezetése szokásos hálózatra. Él- és pontidegen utak, minden st utat lefogó él- ill. ponthalmaz. Menger négy tétele, gráfok többszörös él- ill. pontösszefüggősége, kapcsolata a Menger tételekkel.
7.hét 2014. október 20.  18-20 óra  I. ZH
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. 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. Síkbarajzolhatóság, gömbre rajzolhatóság.
9.hét 2014. november 3. Az Euler-féle poliédertétel és következményei egyszerű, síkbarajzolható gráfokra. Kuratowski gráfok, topologikus izomorfia, Kuratowski tétele. 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.
10.hét 2014. november 10. 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.
10.hét 2014. november 11.  keddi gyakorlat elmarad
11.hét 2014. november 17. 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
11.hét 2014. november 21.  pénteki gyakorlat elmarad
12.hét 2014. november 24. 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.
12.hét 2014. november 27.  8-10 óra  II. ZH
13.hét 2014. december 1. Kongruenciák,  maradékrendszerek, Euler-Fermat-tétel, lineáris kongruenciák és diofantoszi egyenletek megoldása.
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



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.