A számítástudomány alapjai


Ezen előadás elsősorban a villamosmérnök alapképzés (BSc program) VISZA105 Neptun-kód alatt szereplő tárgyhoz tartozik. A régi (5 éves) képzésben részt vevő  hallgatók is erre az előadásra járjanak.


A SZA  tárgyat vizsgakurzus formájában is kiírtuk azok számára, akiknek már van aláírásuk és a zárthelyiket nem kívánják újra megírni. Kérünk minden olyan hallgatót, akinek a tárgyból érvényes aláírása van és az őszi félévben csak vizsgázni szeretne (tehát gyakorlatra nem szeretne járni és a zárthelyiket nem akarja újra megírni), hogy a Neptunban ne az 1-es, illetve 2-es kurzuskódú tárgyat, hanem a 00 kódú vizsgakurzust vegye fel. (Ha pedig már korábban felvette az 1-es vagy 2-es kurzuskódú SZA előadást (és esetleg valamelyik gyakorlatot), akkor ez(eke)t a Neptunban adja le és helyette a vizsgakurzust vegye fel.) Arra is szeretnénk felhívni a tárgyat már nem először felvevő hallgatók figyelmét, hogy a múlt évben a tematikában a szokásosnál nagyobb változás következett be a 2011/2012/1 félévhez képest. A zárthelyin és a vizsgán nekik is az új anyag szerint kell felkészülniük.

A vizsgakurzushoz külön előadás nem tartozik, az erre feliratkozott hallgatókat  természetesen  a két előadás bármelyikén szívesen látjuk, a  korábbi zh-kon szerzett pontszámokat pedig magától értetődően továbbra is beszámítjuk. (ld. részletesebben lejjebb, a tárgykövetelményeknél)


Előadók:   Recski András  (recski@cs.bme.hu) és Katona Gyula Y. (kiskat@cs.bme.hu)


Előadások:

Gyakorlatok:

Kurzuskód
 Időpont
 Gyakorlatvezető
 Terem
11
 hétfő 10:15-11:45
 Tóth Géza
 		IB138
12
 hétfő 10:15-11:45 Bencs Ferenc
 		IB139
13
 hétfő 10:15-11:45 Kőrösi Attila
 		IB140
21
 hétfő 10:15-11:45 Kiss Attila
 		IB145
22
 hétfő 10:15-11:45 Csehi Csongor
 		V1103
23
 hétfő 10:15-11:45 Pácsonyi Imre
 		IB134
14
 kedd 15:15-16:45 Kabódi László
 		IB138
15
 kedd 15:15-16:45 Drótos Márton (honlap)
 		IB139
19
 kedd 15:15-16:45 Gerbner Dániel
 QBF11
10 csütörtök 15:15-16:45 Salánki Ági
 		IB145
16
 csütörtök 15:15-16:45 Tóth Géza IB138
17
 csütörtök 15:15-16:45 Csehi Csongor IB139
18
 csütörtök 15:15-16:45 Blázsik Zoltán
 		IB146
24
 csütörtök 15:15-16:45 Drótos Márton V1103
25
 csütörtök 15:15-16:45 Kőrösi Attila IB140
Rendszeres konzultáció (Domján Pál):

Összesített ZH és PZH eredmények itt 

A PPZH-ra a NEPTUNban jelentkezni kell!

 PótpótZH. terembeosztás (december 18. szerda 10-12)

   
Terem Kezdőbetű
IE007
 mindenki





Kérjük, hogy a zh-ra mindenki úgy érkezzen, hogy fejből tudja annak a gyakorlatvezetőnek a nevét, akihez a Neptun szerint jár és a dolgozaton (a saját nevén kívül) ezt a nevet tüntesse fel.  Akinek ez problémát okoz, az a dolgozat írása közben, a teremben felügyelő oktatónál lévő listáról is kaphat segítséget a gyakorlatvezető nevének kiderítésében. Felhívjuk a figyelmet arra, hogy érvénytelen minden olyan dolgozat, amin a feltüntetett gyakorlatvezető neve különbözik a Neptunáltal nyilvántartottól.

A zárthelyiken semmilyen segédeszköz nem használható. Mindig hat feladat van, mindegyik 10 pontot ér, az elégséges alsó határa 24 pont; a munkaidő 90 perc. Kérjük, hogy a zárthelyik írásakor mindenki megfelelő mennyiségű, előre összetűzött, üres lappal érkezzen és a zárthelyi írása közben csak ezeken dolgozzon. (A lapokra szabad előre felírni a nevet, a Neptun kódot és a gyakorlatvezető nevét, hogy ezzel a zárthelyi írása közben ne kelljen időt tölteni.) Akinek nincs tűzőgépe, annak szívesen összetűzzük a lapjait a zárthelyi előtt.

Felhívjuk a figyelmet arra, hogy a zárthelyi írása közben senkinél nem lehet sem bekapcsolt mobiltelefon (még elnémítva sem), sem bármely más elektronikus eszköz; kérjük, aki igényli, gondoskodjon karóráról a dolgozat írásának idejére.  Felhívjuk továbbá a figyelmet arra is, hogy a dolgozat írásának megkezdése után az első 30 percben a termet elhagyni csak rendkívül alapos indokkal lehet, ennek az időnek a letelte után pedig a késve érkező hallgatók már nem kezdhetik el a zárthelyi írását.




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

1. hét

2013. szeptember 11., szerda

Leszámlálási alapfeladatok (permutáció, variáció, kombináció), binomiális tétel. 

2013. szeptember 13., péntek

Összetett leszámlálási feladatok, skatulya-elv, szita-formula. Alapvető adatstruktúrák: tömb, láncolt lista, bináris fa
2. hét

2013. szeptember 16., hétfő

Egyetemi sportnap, gyakorlatok elmaradnak
2013. szeptember 18., szerda
 Lineáris és bináris keresés, ezek lépésszáma, minimumkeresés, beszúrási feladat. Rendezési feladat, 

2013. szeptember 20., péntek

Buborék-, kiválasztásos-, beszúrásos rendezés. Összefésüléses- és gyorsrendezés. Alsó korlát rendezés lépésszámára. Ládarendezés. 
3. hét

2013. szeptember 25., szerda

Bináris keresőfa, rendezés bináris keresőfával. Kupac, kupacos rendezés,

2013. szeptember 27., péntek

Gráfelméleti alapfogalmak, gráfok adatstruktúrái: szomszédossági mátrix, szomszédossági tömb, láncolt szomszédossági lista.
4. hét

2013. október  2., szerda

 Fák alaptulajdonságai, Prüfer-kód, minimális súlyú feszítőfa, Kruskal algoritmus. (Az I. ZH anyaga eddig tart.)

2013. október  4., péntek

 Normál fák. Euler- és Hamilton körök, szükséges és elégséges feltételek.
5. hét

2013. október 9., szerda

 Legrövidebb utak keresése, BFS, Dijkstra.
2013. október 10., csütörtök QPA szünet, gyakorlatok elmaradnak

2013. október 11., péntek

QPA szünet, előadás elmarad

6. hét 2013. október 16., szerda
 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. Hálózati folyamok.
2013. október 17. csütörtök
 I. Zárthelyi (Feladatsor megoldással)
2013. október 18., péntek Ford-Fulkerson tétel, algoritmus maximális folyam keresése. Folyamproblémák általánosításai, él- ill. pontidegen utak maximális száma, Menger tételei.
7. hét

2013. október 23., szerda

 Nemzeti ünnep, előadás elmarad

2013. október 25., péntek

Többszörös összefüggőség. Páros gráfok, párosítások, Hall-tétel, 

8. hét

2013. október 30., szerda

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

2013. november 1., péntek

Mindenszentek, előadás elmarad
9. hét

2013. november 6., szerda

Gráfok színezése, klikkméret és kromatikus szám viszonya, Mycielski konstrukció, Brooks tétel, élszínezés, Vizing tétel.

2013. november 8., péntek

 Síkbarajzolható gráfok, Euler-formula, Kuratowski tétel.
10. hét

2013. november 12., kedd

TDK konferencia, gyakorlatok elmaradnak

2013. november 13., szerda

Dualitás, gyenge izomorfia, Whitney tételei, síkgráfok színezése, 4- és 5-szín tétel.

2013. november 15., péntek

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.
(A II. ZH anyaga eddig tart.)


11. hét
 2013. november 20., szerda
 Algoritmusok bonyolultsága, P, NP és coNP osztályok

2013. november 22., péntek

 Nyílt nap (előadás elmarad)
12. hét 2013. november 27., szerda
 NP-teljes problémák,
2013. november 28. csütörtök
 II. Zárthelyi (Feladatsor megoldással)

2013. november 29., péntek

 Módszerek nehéz problémák kezelésére, Oszthatóság, maradékos osztás.
13. hét

2013. december 4., szerda

 Euklideszi algoritmus,  prímek, számelmélet alaptétele,  osztók száma. Tételek a prímek eloszlásáról, kongruenciák, 
2013. december 5. csütörtök
Pótzárthelyi   (1. Feladatsor megoldással) (2. Feladatsor megoldással)

2013. december 6., péntek

 Maradékrendszerek, Euler-Fermat-tétel, lineáris kongruenciák és diofantoszi egyenletek megoldása.
2013. december 7. szombat Absztrakt algebra: művelet, félcsoport,  csoport, példák csoportokra.
14. hét

2013. december 11., szerda

Izomorfia, részcsoport, ciklikus csoport, mellékosztály, Lagrange tétel. Gyűrűk, polinomgyűrűk, testek

2013. december 13., péntek

Kriptográfiai módszerek, nyilvános kulcsú titkosítás, RSA kódolás


Jegyzet:      Katona-Recski-Szabó: A számítástudomány alapjai   (Typotex 2002, 2003)
                           Fleiner Tamás 2009-os 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,
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 8 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.)


Korábbi félévben szerzett aláírás:
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ég van megkísérelni újból megszerezni az aláírást a zárthelyik újbóli megírásával.

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 2012/1 félévi tételsor itt tölthető le.