Bevezetés a számításelméletbe 2 előadás, 2015/16.  1. félév
 
 

Előadó, terem, időpont

Wiener Gábor

wiener kukac cs pont bme pont hu

IB 025

kedd 10.15-12.00

 

 

 

 

Aktuális

Zh-, pótzh és pótpótzh eredmények

Konzultációk:
dec. 18. 17 óra, IB 134
;
jan. 5. 15
óra, IB 217.1;
jan. 6. 14 óra, IB 139;
jan. 12. 15 óra, IB 217.1;
jan. 13. 14 óra, IB 216.1;

jan. 19. 15 óra, IB 217.1
;
jan. 26. 15 óra, IB 217.1.

Tételsor        A régi BSz2 tárgy (BMEVISZA110) tételsora

 

2. pótzh javítókulcs

 

1. pótzh javítókulcs


2. zh javítókulcs

 

1. zh javítókulcs


Gyakorlat példasorok:
1. gyak. 2. gyak. 3. gyak. 4. gyak. 5. gyak.  6. gyak. 7. gyak. 8. gyak. 9. gyak.  11. gyak.  12. gyak. 13. gyak.

 

Változások a tárgy félévközi követelményeiben:

 

Az aláírás megszerzéséhez a továbbiakban

 

ˇ        nem szükséges, hogy a zárthelyi dolgozatok eredménye külön-külön elérje a 40%-ot. Ehelyett elegendő, ha külön-külön legalább 30%-os eredményűek és csak átlagban érik el a 40%-ot.

ˇ        nem követelmény, hogy a két zárthelyi közül legalább az egyik elsőre, pótlás igénybevétele nékül sikerüljön. Ha valakinek esetleg egyik sem sikerül (mert nem éri el a 30%-ot vagy nem vesz részt egy zárthelyin), a pótzárthelyit és az aláíráspótló vizsgát (avagy második pótzárthelyit) felhasználhatja (mégpedig tetszőleges sorrendben) a két zárthelyi pótlására, illetve javítására.

A részleteket ld. alább, a Félévközi követelmények pontnál.

 

 

A 2014/15-ös tanév tavaszi félévétől kezdve a BSz2 tárgyat jelentősen módosított tartalommal oktatjuk. Az új tárgy kódja BMEVISZAA01 (a régi tárgy kódja BMEVISZA110). Az új tematika az első előadás kombinatorika anyagán kívül kizárólag gráfelméletet tartalmaz.

A karon a BSc képzés átalakulásával kapcsolatban hozott szabályozás szerint azok a hallgatók, akik a BMEVISZA110 kódú BSz2 tárgyból egy korábbi félévből (érvényes) aláírással rendelkeznek és ebben a félévben a a BMEVISZAA01 kódú tárgyból a reguláris kurzust vették fel, eldönthetik, hogy a vizsgát a régi, vagy a megújult követelmények szerint kívánják teljesíteni. Ezt a döntést elég a vizsgán, a tétel húzása előtt közölni, de érdemes minél hamarabb meghozni. A BMEVISZA110 kódú tárgyból vizsgakurzust felvett hallgatóknak nincs ilyen döntési lehetőségük, ők a régi követelményrendszer szerint vizsgáznak.

 

Tematika

A kombinatorika alapjai, gráfelmélet.    Tantárgyi adatlap    (Régi 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

 

Félévközi követelmények 

A félév során két zárthelyi dolgozat lesz. 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:

ˇ        mindkét zárthelyin külön-külön legalább 30%-os eredményt ér el (vagyis a 60 pontból legalább 18-at megszerez);

ˇ        a két zárthelyi átlagában legalább 40%-os eredményt ér el (vagyis a két zárthelyire összesen kapható 120 pontból legalább 48-at elér).

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 egyenlő.) 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 a legalább 40%-os átlagos eredményt 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 átlagos eredménye 40% alá csökkenne -, akkor az aláírása megmarad és az átlagos eredménye sem csökken 40% alá.) 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.

Ha valaki mindkét zárthelyit már az első alkalommal (tehát pótlás nélkül) sikeresen teljesítette é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 előadóját legkésőbb egy héttel az első pótzárthelyi időpontja előtt.

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.) 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 sikerül újra teljesíteni az aláíráshoz szükséges feltételeket, akkor a vizsgajegybe az így kapott eredmény számít bele (akkor is, ha ez rosszabb).

ˇ         Ha nem sikerül újra teljesíteni az aláíráshoz szükséges feltételeket, akkor az aláírás nem vész el, de a vizsgajegybe csak az aláírás megszerzéséhez szükséges minimális pontszámot számítjuk be.

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 zh 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

Szóban zajlik, az alábbiak szerint: a tételsoron szereplő tételek közül a vizsgázó egyet kap, ezt kidolgozza, majd szóban felel belőle. Számítani kell arra is, hogy a vizsgáztató a többi tételbe is belekérdez. A vizsgán 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. A vizsgatétel kidolgozására a hallgatónak felkészülési idő áll rendelkezésére. 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 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árthelyik átlaga 40 százalék erejéig, a szóbeli vizsga 60 százalék erejéig számít bele. 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ó (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 vizsgákra a Neptunban jelentkezni kell. (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  BMEVISZAA01 kódú tárgy vizsgatételsora a félév végén letölthető (a 2014/15. tavaszi tételsor itt található, a 2015/16. őszi ettől némiképp eltérhet). A BMEVISZA110 kódú tárgy tételsora már nem fog változni: BMEVISZA110 tételsor

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.

Tanácsok vizsgára


Technikai tudnivalók a vizsgákkal kapcsolatban:

  • A szóbeli vizsgák kulturált lebonyolítását, a vizsgára való várakozás kellemesebbé tételét sorszámok kihelyezésével igyekszünk elősegíteni. A tanszéknek azonban nincs erőforrása sem arra, hogy a sorszámok kiosztását végezze, sem arra, hogy vizsga közben a soron következő sorszám nyilvántartását végezze. Arra kérjük ezért a vizsgázókat, hogy ezt önállóan szervezzék meg az alábbiak szerint:
    • Minden vizsgázó érkezéskor a következő egyetlen sorszámot tépje le. Bár ezt ellenőrizni se nem tudjuk, se nem kívánjuk, nagyon kérünk mindenkit, hogy ne tépjen egynél több sorszámot még akkor sem, ha erre olyan hallgatótársa kérné, akiről biztosan tudja, hogy a vizsgán (akár perceken belül) meg fog jelenni.
    • Kérünk minden vizsgázót, hogy ne jelentkezzen vizsgára mindaddig, amíg alacsonyabb sorszámmal rendelkező hallgatók is várnak.
    • A vizsga technikai lebonyolítását végző kollégánk nem fogja tudni számontartani, hogy milyen sorszámú hallgató kerül sorra, mindig a "következő" (vagy következő néhány) vizsgázót hívja be. Ezért kérünk mindenkit, hogy várakozás közben időnként győződjön meg arról, hogy éppen milyen sorszámú hallgató ment be vizsgázni, hogy amikor sorra kerül, rendelkezésre álljon.
    • Minden vizsgára várót bátorítunk arra, hogy szükség esetén a fentiekre nem hallgató társát udvarias, de nyomatékos formában figyelmeztesse.
  • 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. (Továbbá a különböző BSz2 kurzusok között sem tudunk szabad vizsgahelyet átcsoportosítani; hiába van az egyiken még esetleg néhány szabad hely, ha a másik betelt, akkor arra már nem lehet jelentkezni.) 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étben 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.
  • Minden szóbeli vizsga előtt tartunk konzultációt, ahol a vizsgára készülés közben felmerült kérdéseket lehet feltenni.

 

Gyakorlatok

A hallgatók az alább felsoroltak közül bármely gyakorlatot látogathatják, a következő feltételekkel. Természetesen mindenki járhat arra a gyakorlatra, amelyre a Neptunban fel van jelentkezve. Emellett  vagy ehelyett járhat más gyakorlat(ok)ra is, amennyiben az adott gyakorlat gyakorlatvezetőjével ezt megbeszéli, a zh-it azonban mindenképpen az a gyakorlatvezető javítja, akihez az illető hallgató a Neptun szerint jár.

Kurzuskód

Időpont

Gyakorlatvezető

Terem

11

Kedd, 16:15-17:45

Rácz Dániel

IB146

12

Kedd, 16:15-17:45

Tassy Gergely

IB134

13

Csütörtök, 8:15-9:45

Wiener Gábor

IB134

14

Csütörtök, 8:15-9:45

Tőri Tünde

IB145

 

Az előadó által készített feladatsorok: 1. gyak. 2. gyak. 3. gyak. 4. gyak.  5. gyak.  6. gyak. 7. gyak. 8. gyak. 9. gyak.  11. gyak.  12. gyak. 13. gyak.

 

 

 

Zh-k

 

 

 

 

 

Zh-időpontok: 1. zh: október 19. hétfő, 8.00, 2. zh: november 20. péntek, 8.00, pótzh-k: december 9., szerda 18 óra.

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

ˇ        A zárthelyikre 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 6 feladat van, mindegyik 10 pontot ér. 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 a zárthelyi előtt tudunk biztosítani.

ˇ        A zárthelyik í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 ezt igényli, gondoskodjon karóráról a dolgozat írásának idejére.

ˇ        A dolgozat írásának megkezdése után az első 30 percben a termet elhagyni nem 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.

 

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ó vizsgán (avagy második pótzárthelyin) csak az vehet részt, aki a két normál zárthelyi, illetve az első pótzárthelyi eredményei alapján még nem teljesítette az aláíráshoz szükséges feltételeket. Így az aláíráspótló csak abban az esetben használható korábban már megírt dolgozat eredményének a javítására, ha enélkül az aláírás feltételei még nem teljesülnek.

ˇ        Az aláíráspótló vizsgára a Neptunban jelentkezni kell. (Figyelem! Aki ezt elmulasztja, annak az ezen az alkalmon megszerzett aláírását nem tudjuk beírni a Neptun rendszerbe. Így nincs lehetőségünk arra, hogy az aláíráspótlón olyan hallgatónak engedélyezzük a részvételt, aki a Neptunban a jelentkezést elmulasztotta.)

ˇ        Az aláíráspótló vizsgán való részvételért (utólag) különeljárási díjat kell fizetni.

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 már a dolgozat pontozásán változtatni nem tudunk.

   

Feladatsorok

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

 

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