Bevezetés a számításelméletbe I.

Bevezetés a számításelméletbe I.
VISZA103
2011/2012. második félév

Jegyzet:      Katona-Recski-Szabó: A számítástudomány alapjai   (Typotex 2002, 2003)
                          Digitális jegyzet: http://www.cs.bme.hu/~fleiner/jegyzet/

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

A tárgy egy féléves, heti két óra előadással és heti két óra gyakorlattal. A kari vezetés rendelkezésének megfelelően a gyakorlatokon 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 3 gyakorlatnál) több hiányzása bizonyítható, az a rendelkezés értelmében ebben a félévben nem szerezhet sem aláírást sem pedig kreditet a tárgyból. Érdemes ezt a szabályt jól megérteni, mert rengeteg kellemetlenség származhat a félreértelmezéséből.

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őtartamuk egyaránt 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 dolgozatíráshoz (az aláíráspótló vizsgát is beleértve) feltétlenül szükséges egy arcképes igazolvány a személyazonosság igazolására. Felhívjuk a figyelmet, hogy a diákigazolvány nem okmány, személyazonosításra nem alkalmas. A hallgató felelőssége még, hogy jól, ám nem piros színnel író tollon kívül tűzőkapoccsal összetűzött, üres papírokkal rendelkezzék a dolgozatírás megkezdésekor. A dolgozatot író hallgatónak ezekre előzőleg a nevét, neptun kódját és neptun szerinti gyakorlatvezetője nevét érdemes a jobb felső sarokba felírnia, hiszen ennek hiányában a dolgozatot nem értékeljük.

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.

Az aláírás a TVSz szerint 3 évig érvényes, kivéve a 2007. szeptember 1. előtt szerzett aláírásokat, amik 5 évig érvényesek. (Tehát annak nem muszáj most aláírást szereznie, aki 2008 decemberben vagy azt követően ill. annak, aki 2006 december és 2007 május között szerzett aláírást.) 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.

Ha sikerült újra teljesíteni a feltételeket, akkor a vizsgajegybe ezek az eredmények számítanak bele (akkor is a rosszabbak). A most szerzett aláírás érvényessége 3 év, tehát a 2015-ös tavaszi félévben használható fel utoljára.)
Ha a hallgató sikertelen kíséreletet tett az aláírásszerzésre, akkor a korábbi aláírásának érvényessége nem változik, de a vizsgajegy meghatározásakor csak az aláírás megszerzéséhez szükséges minimális pontszámot vesszük figyelembe.
Ha az adott hallgató nem kísérelte meg az aláírásszerzést (azaz nem vett részt egyetlen zárthelyin vagy pótláson sem az adott félévben), akkor a fenti rekurzív definíciót a legutolsó olyan félévre alkalmazzuk, amikor az illető megkísérelt aláírást szerezni.

Vizsga, konzultáció:

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 nem tudunk olyan hallgatót vizsgáztatni, aki a jelentkezést elmulasztotta.

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ó (előző félévivel azonos) 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 percfelkészülési időt biztosítunk. Ennek 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ó. Nem győzzük hangsúlyozni, hogy a vizsgán elsősorban a tananyag megértését, az összefüggések átlátását mérjük, így pl a hivatalos jegyzet betűhű visszaadása önmagában kevés a sikerhez.

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.

Vizsgával kapcsolatos technikai tudnivalók:

A vizsgázáshoz feltétlenül szükséges egy arcképes igazolvány a személyazonosság igazolására. Felhívjuk a figyelmet, hogy a diákigazolvány nem okmány, azonosításra nem alkalmas. A vizsgázó dolga még, hogy üres papírokat és jól író tollat is hozzon magával, a tételsoron kívül semmi mást sem tudunk biztosítani.
A szóbeli vizsgák limitjét - a tanszék erőforrásainak korlátossága miatt - a vizsgaidőszak során nem fogjuk tudni megemelni (és további vizsgaalkalmat sem fogunk tudni kiírni). Ha tehát valamelyik vizsga limitje betelt, akkor szóbelizni csak a következő alkalommal lehet; ha pedig ilyen már nincs, akkor csak a következő félévben. Emiatt kérünk mindenkit, hogy:

a vizsgaidőszakját előre tervezze meg (tapasztalatunk szerint az első néhány hét BSz vizsgáin általában bőségesen maradnak helyek, a limitek csak az utolsó két héten szoktak betelni);
ha valaki úgy érzi, hogy valamelyik szóbelin mégsem kíván vagy tud részt venni, akkor a többi hallgató érdekében mielőbb jelentkezzen le.

Minden szóbeli alkalomhoz nyitunk a Neptunban várólistát. (Ha tehát valamelyik vizsgáról egy hallgató lejelentkezik, akkor a listára automatikusan felkerül a várólista élén álló jelentkező.) Felhívjuk azonban a figyelmet arra, hogy azokat a hallgatókat, akik a vizsga napjáig a várólistán maradtak (tehát nem kerültek át a vizsgázók listájára), a szóban forgó vizsganapon nem tudjuk levizsgáztatni (az eredmény beírását a Neptun nem is engedné).
A szóbelikre való jelentkezés akkor zárul, ha a következő hallgató hívásakor már senki nem jelentkezik vizsgára. Kérünk mindenkit, hogy ezt vegye figyelembe: amennyiben valaki később érkezne, nem fog már tudni levizsgázni.
A vizsgákat megelőző munkanapokon tartott konzultációkon 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 az előadások ütemezését tartalmazó, fenti táblázatban található.
A vizsgán kizárólag a vizsgázó hallgató tárgyi tudását értékeljük. Ezért 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 fent leírtakat részletezzük az alábbiakban. Ú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.

14	Richlik György	QB104
15	Varga Kitti	IB 134
16	Fleiner Tamás	IB 138
17	Szabó Péter	IB 139

11	Csákány Rita	IB 134
12	Fleiner Tamás	IB 138
13	Szabó Péter	IB 139

2010. őszi félév (pontozási útmutatókkal)	2009. őszi félév	2008. őszi félév	2007. őszi félév
2006. őszi félév	2005. őszi félév	2004. őszi félév	2003. őszi félév
2002. őszi félév	2001. őszi félév	2000. őszi félév	1999. őszi félév

2005. őszi félév	2004. őszi félév	2003. őszi félév	2002. őszi félév
2000. őszi félév	1999. őszi félév