Bevezetés a Számításelméletbe 2
2016/2017. második félév

 

 

Aktuális:

Rendszeres konzultáció: minden szerdán 14 és 15 óra között, az IB 134 teremben. Tartja: Csákány Rita.

 

 

Előadások, előadók:

Előadó:

Időpont:

Helyszín:

Pach Péter Pál  (email: ppp_KUKAC_cs.bme.hu)

Hétfő 10.15 - 12.00

 IB 027

Wiener Gábor  (email: wiener_KUKAC_cs.bme.hu)

Hétfő 10.15 - 12.00

 IB 028


Gyakorlatok, gyakorlatvezetők:

 

Kurzuskód

Időpont

Gyakorlatvezető

Terem

11 + 12

Kedd, 8:15-9:45

Richlik György

IB140

13 + 18

Kedd, 8:15-9:45

Ács Bernadett

IB146

17

Kedd, 8:15-9:45

Mihálka Éva Zsuzsanna

IB147

19

Kedd, 8:15-9:45

Szabó Réka

IB139

14 + 24

Hétfő, 12:15-13:45

Balázs Barbara

IB134

15

Hétfő, 12:15-13:45

Kecskés Boglárka

IB139

16

Hétfő, 12:15-13:45

Tőri Tünde

IB140

25

Hétfő, 12:15-13:45

Mihálka Éva Zsuzsanna

IB147

26

Hétfő, 12:15-13:45

Ács Bernadett

IB146

20

Kedd, 10:15-11:45

Szabó Dávid

IB138

21

Kedd, 10:15-11:45

Németh Gergely Dániel

IB146

22 + 27

Kedd, 10:15-11:45

Szabó Réka

IB139

23

Kedd, 10:15-11:45

Richlik György

IB140

IMSc - 1

Kedd, 8:15-9:45

Balázs Barbara

IB134

IMSc - 2

Kedd, 10:15-11:45

Wiener Gábor

IB145

A gyakorlatokra az előadók minden héten készítenek feladatsort, a gyakorlatvezetők jelentős része ezeket (is) használja az óráján.

1. gyakorlat feladatsor  2. gyakorlat feladatsor

 


Tematika, jegyzet:

Az első előadáson a kombinatorika alapjaival foglalkozunk, a további előadások témája gráfelmélet. Tantárgyi adatlap.
Javasolt jegyzetek:

   Katona-Recski-Szabó: A számítástudomány alapjai: ingyenesen letölthető e-könyv

   Friedl-Recski-Simonyi: Gráfelméleti feladatok (elsősorban gyakorlatra)

   Szélességi keresés jegyzet

 

   Javítóutas algoritmus vetítés (pdf)

 

   Mélységi keresés jegyzet

   Az élszínezésre vonatkozó Kőnig-tétel egy, az óraitól különböző bizonyítása


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

Zárthelyik, pótzárthelyik:

A félév során két zárthelyi dolgozat lesz, mindkettőn 60 pontot lehet elérni. A félév végi aláírást az szerzi meg (vagyis a vizsgára az jelentkezhet), aki az alábbi feltételek mindegyikét teljesíti:

A két zárthelyi alkalom mellett lesz még a szorgalmi időszakban egy pótzárthelyi alkalom, továbbá a vizsgaidőszak előtti pótlási héten egy második pótzárthelyi alkalom is. Ezek mindegyikén újból meg lehet írni akár az első, akár a második zárthelyi dolgozatot, de egyszerre csak az egyiket. (A dolgozat újbóli megírása természetesen nem azt jelenti, hogy a feladatsorok azonosak volnának, de mindhárom esetben ugyanazokat az anyagrészeket kérik számon és - a szándékaink szerint - a nehézségük is azonos.) A két pótzárthelyi alkalmat lehet tehát használni az elmulasztott zárthelyik teljesítésére vagy egy korábban megírt dolgozat eredményének a javítására. Ha valaki egy korábban már megírt dolgozatot teljesít újra valamelyik pótzárthelyin, akkor mindenképpen az új pontszáma lesz érvényes - akkor is, ha az rosszabb, mint a korábbi. (Ez alól egy kivétel van: a már megszerzett aláírást és az ahhoz szükséges minimális pontszámot egy balsikerű javítási kísérlettel nem lehet elveszíteni. Így ha valaki már teljesítette az aláíráshoz szükséges feltételeket, majd egy javítónak szánt pótzárthelyin annyival rosszabb eredményt ér el, hogy ezáltal az aláírása elveszne - akár azért, mert nem ért el 18 pontot, akár mert az összpontszáma 48 alá csökkenne -, akkor az aláírása megmarad és a pontszáma sem csökken 48 alá.) Ha valaki egy pótzárthelyin megjelenik (és a feladatsort átveszi), azt úgy tekintjük, hogy az illető kísérletet tett a dolgozat megírására (és így rá a fenti feltételek vonatkoznak).

A pótzárthelyiken mindenki szabadon eldöntheti, hogy az első vagy a második zárthelyit kívánja pótolni vagy javítani; annak sincs akadálya, hogy valaki mindkét pótzárthelyin ugyanannak a dolgozatnak a pótlását vagy javítását kísérelje meg.

Az első pótzárthelyire nem szükséges jelentkezni a Neptunban (sem máshol), azon mindenki a saját döntése szerint részt vehet (függetlenül attól, hogy a dolgozatot pótlási vagy javítási szándékkal írja meg).

Ha valaki a két normál zárthelyivel (tehát pótlás nélkül) sikeresen teljesítette az aláírás feltételeit és (a TVSz biztosította jogával élve) mindkét zárthelyi eredményét még a szorgalmi időszakban javítani kívánja (és így erre az első pótzárthelyi alkalom nem elegendő), az keresse meg (emailben vagy személyesen) a tárgy valamelyik előadóját legkésőbb egy héttel az első pótzárthelyi időpontja előtt.

Aláíráspótló vizsga:

A fentebb említett, a pótlási héten biztosított második pótzárthelyi alkalom a Neptunban aláíráspótló vizsga néven jelenik meg. (Ez a név tehát némileg félrevezető, itt nem egy valódi vizsgáról van szó.) Erre a második pótzárthelyi alkalomra vonatkozó szabályok az alábbiakban különböznek az elsőre vonatkozóktól:

Az aláíráspótló időpontja (körülbelül a szorgalmi időszak közepétől) a Neptunból deríthető ki. Az aláíráspótló vizsgán írt dolgozatokat még aznap kijavítjuk és biztosítjuk a megtekintésüket. (Ennek a pontos időpontját a dolgozatírás közben hirdetjük ki.) A dolgozatok eredményei (legkésőbb a következő napon) a tárgy honlapjára is felkerülnek. Aki a megtekintésen nem tud megjelenni, az a dolgozatát kérésre később is megnézheti, de ekkor a dolgozat pontozásán változtatni (esetleges adminisztrációs hibáktól eltekintve) már nem tudunk.

Változások a tárgykövetelményekben:

A tárgykövetelményekkel kapcsolatban eddig leírtak a 2015. őszi félévtől érvényesek. A tanulmányaikat korábban megkezdett hallgatók kedvéért alább összefoglaljuk, hogy a fentiek pontosan milyen változásokat jelentenek a korábban érvényes szabályokhoz képest. Az aláírás megszerzéséhez a továbbiakban

Korábbi félévben szerzett aláírás:

Az érvényes TVSz-nek megfelelően a tárgyból korábban megszerzett aláírás 3 évig érvényes. (Részletesebben ez azt jelenti, hogy az aláírás megszerzését követő hatodik félév vizsgaidőszakjának végéig az aláírás még érvényes.) Ezen az időkereten belül a régi, BMEVISZA110 kódú tárgy aláírása érvényes az új, BMEVISZAA01 kódú tárgyból is. Azok, akik egy korábbi félévből érvényes aláírással rendelkeznek és ebben a félévben is a reguláris előadást és gyakorlatot (tehát nem a vizsgakurzust) vették fel, megkísérelhetik újból megírni a zárthelyiket abból a célból, hogy a korábbi zárthelyik eredményein javítsanak, vagy az aláírás érvényességét meghosszabbítsák. Erre az esetre az alábbi feltételek vonatkoznak:

Ha egy érvényes aláírással rendelkező hallgató az aktuális félévben legalább egy zárthelyin megjelenik, azt úgy tekintjük, hogy az illető kísérletet tett az aláírás feltételeinek újbóli teljesítésére (és rá a fenti feltételek vonatkoznak, mindkét zárthelyi tekintetében). Ellenkező esetben a legutolsó olyan félévbeli teljesítményt vesszük figyelembe, amikor a hallgató megkísérelte az aláírás feltételeinek teljesítését.

Vizsga:

Vizsgára az jelentkezhet, aki érvényes aláírással rendelkezik.

A vizsga szóban zajlik, az alábbiak szerint: a tételsoron szereplő tételek közül a vizsgázó egyet kap, ezt kidolgozza (vagyis a szóbeli felelethez egy bő jegyzetet készít, ehhez legalább 45 perc áll rendelkezésére), majd szóban felel belőle. A felelet abból áll, hogy egyrészt a vizsgázó a jegyzeteire támaszkodva részletesen beszámol a húzott tételről, másrészt a vizsgáztató néhány szúrópróbaszerű, az anyag tö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.) A vizsgán az elégséges megszerzésének feltétele, hogy a vizsgázó a tételsorban vastagon szedett definíciókat, tételeket, algoritmusokat el tudja mondani és értse is azokat. Természetesen a  tételsor nem vastagon szedett részeit is tudni (és érteni) kell, ezek esetében azonban egy-két hiányosság még nem okoz bukást.

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árthelyiken nyújtott teljesítmény 40 százalék erejéig, a szóbeli vizsga 60 százalék erejéig számít bele. Ez részletesebben a következőt jelenti:

zh1 = az 1. zh (végső) pontszáma,  zh2 = a 2. zh (végső) pontszáma,
zh-król_hozott_pont
= 0,4*((max(50, zh1) + max(50,zh2)), 
v = a szóbeli vizsgán elért pontszám, legfeljebb 60 pont, legalább elégséges felelet esetén legalább 20 pont,
végső_pont = zh-król_hozott_pont + 1,2*max(50, v).

A jegyet a végső_pont határozza meg, az alábbiak szerint: 0-39: elégtelen, 40-54: elégséges, 55-69: közepes, 70-84: jó, 85-100: jeles.

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ó vagy ismétlő vizsga a TVSz szerint tehető. Javító vizsga esetén a zárthelyikből származó eredmények változatlanul érvényesek.

A tárgyhoz tartozó vizsgatételsor a félév végén letölthető. Azok számára, akik a régi típusú, BMEVISZA110 kódú BSz2 tárgyat vették fel (vizsgakurzusként), az innen letölthető tételsor érvényes.

Figyelem! A vizsgákra a Neptunban jelentkezni kell. Mivel 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 vizsgán (ebből a tárgyból) nem szükséges alkalmi ruhában megjelenni, ez a vizsga eredményét semmilyen mértékben nem befolyásolja.

További jótanácsok a vizsgára való felkészüléshez itt olvashatók.

IMSC pontok:

Az IMSc pontokat az alábbi képlettel számítjuk ki, ahol zh1 és zh2 az első, illetve második zárthelyin, v pedig a szóbeli vizsgán szerzett pontszám (legfeljebb 60).

IMSc_pont = max(20, max(0,zh1-50) + max(0,zh2-50) + max(0,v-50)).

 

Technikai tudnivalók a vizsgákkal kapcsolatban:


Zárthelyik:

Első zárthelyi: 

március 16. (csütörtök)

8.00 - 10.00

Második zárthelyi:

április 20. (csütörtök)

8.00 - 10.00

 

Első vagy második (de nem mindkét) zárthelyi pótlása: 

május 8. (hétfő)

17.00 - 19.00

 

 

 

 


A zárthelyik és pótzárthelyik technikai lebonyolításával kapcsolatban az alábbiakra hívjuk fel a figyelmet.

Mindenkinek sok sikert kívánunk!


Korábbi félévek zárthelyi feladatsorai:

Korábbi zárthelyi, pótzárthelyi és aláíráspótló feladatsorok (a zárthelyikhez és pótzárthelyikhez javítókulccsal):

 

2016.

2015. 

 

A régi (BMEVISZA110 kódú) BSz2 tárgy korábbi zárthelyi (és 2006-tól aláíráspótló) feladatsorai:

 

2014. (pontozási útmutatóval), 2013. (pontozási útmutatóval),  2012. (pontozási útmutatóval),  

2011. (pontozási útmutatóval), 2010., 2009. (pontozási útmutató), 2008., 2007., 2006., 2005., 2004.,

2003., 2002., 2001., 2000., 1999.

2006 előtti félévek aláíráspótló feladatsorai:

2006., 2005., 2004., 2003., 2002., 2001., 2000., 1999.

Gyakorló feladatok - a Katona-Recski-Szabó jegyzet régi, egyetemi kiadásának utolsó fejezete, ami az új kiadásban nem  szerepel:  pdf, postscript

Kombinatorikával, gráfelméleti alapokkal, síkbarajzolhatósággal, dualitással kapcsolatos feladatokért korábbi évek BSz1 feladatsorait érdemes böngészni (itt). Minimális súlyú feszítőfákról és szélességi keresésről szóló feladatok a Katona-Recski-Szabó jegyzet régi, egyetemi kiadásának utolsó fejezetéből itt találhatók (2.2.28-33., illetve 7.1.1-4. feladatok).