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

 

 

Aktuális   

A zárthelyi április 23-án 17 órakor kezdődik. Terembeosztás (a vezetéknév kezdőbetűi szerint): A-Dö: Q I., Dr-Gu: IB 26, Gy-L: Ch Max., M-Re: K 234., Ri-Zs: K f.51.
A zh anyaga a Ford-Fulkerson tételig tart, tehát címszavakban az alábbi témaköröket tartalmazza: a kombinatorika alapjai, gráfelméleti alapfogalmak, fák, feszítőfák, síkbarajzolhatóság, Euler-séták és -körséták, Hamilton-körök és -utak, kromatikus szám, páros gráfok, intervallumgráfok, független pont- és élhalmaz, lefogó pont- és élhalmaz, Gallai tételei, párosítások páros gráfban, Kőnig, Hall és Frobenius tételei, Tutte tétele, élkromatikus szám, Vizing és Kőnig tételei, maximális folyam keresése hálózatban, Ford-Fulkerson tétel.

Az április 21-i, előadás helyett tartott gyakorlatok termei (ezeket a gyakorlatokat csak a pénteki kurzusoknak tartjuk, előadás értelemszerűen ekkor nem lesz):
11+12. kurzus (Kecskés Boglárka): IB145, 13. kurzus (Szabó Dávid): IB147, 14+15. kurzus (Richlik György): IB028, I1 kurzus (Balázs Barbara): IE216, I2 kurzus (Wiener Gábor): IB027, I3 kurzus (Varga Kitti) : IB144, Emelt kurzus (Szeszlér Dávid): IE217-1.

 

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

Előadó:

Időpont:

Helyszín:

Szeszlér Dávid  (email: szeszler_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:

Kód      Időpont               Gyakorlatvezető        Terem

11+12    Péntek, 10:15-11:45   Kecskés Boglárka       E404
13       Péntek, 10:15-11:45   Szabó Dávid            R504
14+15    Péntek, 10:15-11:45   Richlik György         E406
16       Szerda, 8:15-9:45     Richlik György         R517
17       Szerda, 8:15-9:45     Bencs Ferenc           IB146
18+21    Szerda, 8:15-9:45     Balázs Barbara         IB147
19       Szerda, 8:15-9:45     Varga Kitti            IB140
20       Szerda, 8:15-9:45     Szabó Dániel           IB139
22       Hétfő, 12:15-13:45    Drótos Márton          IB139
23+26    Hétfő, 12:15-13:45    Mihálka Zsuzsanna      IB145
24       Hétfő, 12:15-13:45    Borza Marcell          R504
25       Hétfő, 12:15-13:45    Balázs Barbara         IB146
27       Hétfő, 12:15-13:45    Oláh Gergely           IB147
28       Hétfő, 12:15-13:45    Sári András Lajos      R515
I1       Péntek, 10:15-11:45   Balázs Barbara         IB134
I2       Péntek, 10:15-11:45   Wiener Gábor           IE218
I3       Péntek, 10:15-11:45   Varga Kitti            IE219
E1       Péntek, 10:15-11:45   Szeszlér Dávid         IE217-1

Az E1 kurzuskódú, emelt szintű gyakorlatot azoknak a hallgatóknak ajánljuk, akik nehezebb feladatok megoldására vágynak; az ide járók számára a zh és minden egyéb követelmény a többiekével azonos.

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 2. gyakorlat 3. gyakorlat 4. gyakorlat 5. gyakorlat  6. gyakorlat 7. gyakorlat 8. gyakorlat 8+9. gyakorlat 9. gyakorlat

 


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 egy zárthelyi dolgozat lesz, mely 6 darab 10 pontot érő feladatból áll. Ezek közül az utolsó a többinél (szándékaink szerint) valamivel nehezebb, csillaggal jelölt feladat. A félév végi aláírást az szerzi meg (vagyis a vizsgára az jelentkezhet), aki a zárthelyin legalább 24 pontot ér el.

A szorgalmi időszakban lesz 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 a zárthelyi dolgozatot. (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.) Mindkét alkalmat lehet használni az elmulasztott zárthelyi teljesítésére vagy a már megírt, de sikertelen dolgozat eredményének a javítására (pótlás). Az első alkalom ezen kívül használható a sikeresen megírt dolgozat eredményének javítására is (javítás).  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, akkor az aláírása megmarad és a pontszáma sem csökken 24 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).

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).

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.

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 és BMEVISZAA01 kódú tárgyak aláírása érvényes az új, BMEVISZAA04 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 vizsga megkezdésekor a vizsgázó kap egyrészt a tárgyhoz tartozó tételsorból egyetlen tételt, másrészt a tárgy anyagának a zárthelyi által le nem fedett részéből egy olyan feladatot, amely az adott félévben szerepelt a tárgy előadói által készített és a tárgy honlapján közzétett feladatsorokon. Ezeknek a kidolgozására (vagyis a szóbeli felelethez egy bő jegyzet készítésére és a kiadott feladat megoldására) legalább 45 perc áll rendelkezésre. 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 és feladatró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 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árthelyin nyújtott teljesítmény 30 százalék erejéig, a szóbeli vizsga elméleti része 60 százalék erejéig, a szóbeli vizsgán kiadott feladat pedig 10 százalék erejéig számít bele. Ez részletesebben a következőt jelenti:

z= a zh (végső) pontszáma, 
v = a szóbeli vizsga elméleti részén elért pontszám, legfeljebb 60 pont,
vf = a szóbeli vizsgán kiadott feladatért kapott pont, legfeljebb 10 pont,
végső_pont =
0,6*min(50,z) + vf + 1,2*min(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ő. 

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 z a zárthelyin, v pedig a szóbeli vizsgán szerzett pontszám (legfeljebb 60).

IMSc_pont = min(25, 2*max(0,z-50) + max(0,v-50)).

 

Technikai tudnivalók a vizsgákkal kapcsolatban:


Zárthelyik:

Zárthelyi: 

április 23. (hétfő)

17.00 - 19.00

Pótzárthelyi:

május 14. (hétfő)

17.00 - 19.00

 

 

 

 

 

 


A zárthelyi és a pótzárthelyi 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 évek zárthelyi, pótzárthelyi és aláíráspótló feladatsorai, a zárthelyikhez és pótzárthelyikhez javítókulccsal (2017-ig két zárthelyi volt):


2017.

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).