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


Aktuális:

Tételsor

A május 5.-i zárthelyi javítókulcsa.

A zárthelyi időpontja május 5. csütörtök 8.00 (figyelem: nem 8.15). A zh anyaga címszavakban: a kombinatorika alapjai, gráfelméleti alapfogalmak, fák, feszítőfák, BFS, Euler-séták és -körséták, Hamilton-utak és -körök, színezések, páros gráfok, független él- és ponthalmazok, lefogó él- és ponthalmazok, párosítások páros gráfban, folyamok és s-t vágások hálózatokban. Terembeosztás (a vezetéknevek kezdőbetűi szerint):
A – É: E1B
F – H: IB027
I – K: K155
L – Ő: E1A
P – St: E1C
Sü –Zs: KF76
Mindenkit kérünk, hogy a zh-ra vonatkozó tudnivalókat figyelmesen olvassa el, mert ezek ismeretét elvárjuk a hallgatóktól. Az eredmények a kari Moodle rendszerben lesznek elérhetők, a dolgozatokat a gyakorlatokon lehet majd megtekinteni. Az esetleges reklamációkat kizárólag a megtekintéskor lehet intézni, kivételt képez ez alól, ha a hallgató ezen nem tud megjelenni. Ez esetben a gyakorlatvezetővel egyeztetett időpontban is intézhető a reklamáció, legkésőbb a pótzh-t megelőző munkanapon.

Kérjük, hogy aki a BSz2 zh-kon valamilyen kedvezményt kíván igénybe venni és ehhez engedéllyel rendelkezik, az töltse ki ezt az űrlapot. Aki az űrlapot (érvényesen) kitöltötte, annak ezt többször természetesen nem kell megtennie, a kedvezményt igénybe veheti a feltöltés időpontja után legalább két héttel tartandó összes zárthelyin. A kitöltéshez Google fiókra van szükség, ügyeljünk rá, hogy az űrlap végén ne felejtsünk el a Submit gombra is rábökni.




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
IB028
Wiener Gábor (email: wiener_KUKAC_cs.bme.hu)
Hétfő 10.15 - 12.00
E1B


Gyakorlatok, gyakorlatvezetők:

Kurzuskód:
Gyakorlatvezető:
Időpont:
Helyszín:
11
Szabó Réka (email: szabo_KUKAC_cs.bme.hu)
Kedd, 8:15-9:45
IB138
12
Vidor Sára (e-mail: vidor.sari_KUKAC_gmail.com)
Kedd, 8:15-9:45
IB139
13
Kiss Attila (email: ttkkissatt_KUKAC_gmail.com)
Kedd, 8:15-9:45
IB145
14
Richlik György (email: richlik_KUKAC_szit.bme.hu)
Kedd, 8:15-9:45
IB140
15
Katona Dániel (e-mail: ddkatona_KUKAC_szit.bme.hu)
Kedd, 8:15-9:45
IB146
16
Borza Marcell (dleemarci97_KUKAC_gmail.com)
Kedd, 8:15-9:45
IB147
17 és 18
Kertész Gergő (email: kerteszcsgergo_KUKAC_gmail.com)
Kedd, 8:15-9:45
E306cd
19 és 20
Szabó Réka (email: szabo_KUKAC_cs.bme.hu)
Kedd, 10:15-11:45
IB138
21 és 26
Richlik György (email: richlik_KUKAC_szit.bme.hu)
Kedd, 10:15-11:45
IB140
22
Kiss Attila (email: ttkkissatt_KUKAC_gmail.com)
Kedd, 10:15-11:45
IB145
23
Schwarcz Tamás (email: schtomi97_KUKAC_gmail.gom)
Kedd, 10:15-11:45
IB146
24 és 27
Csonka Bence (email: slenhortag_KUKAC_gmail.com)
Kedd, 10:15-11:45
IB147
25
Dorogi Imre (email: imredorogi98_KUKAC_gmail.com)
Kedd, 10:15-11:45
E306cd
28
Jung Attila (email: jungattila_KUKAC_gmail.com)
Kedd, 10:15-11:45
E405
I1 (IMSc)
Varga Kitti (email: vkitti_KUKAC_math.bme.hu)
Kedd, 8:15-9:45
IB144
I2 (IMSc)
Kaszanitzky Viktória (email: kaszanitzky_KUKAC_cs.bme.hu)
Kedd, 8:15-9:45
IE218
I3 (IMSc)
Wiener Gábor (email: wiener_KUKAC_cs.bme.hu)
Kedd, 8:15-9:45
IE219
E1 (Emelt)
Szeszlér Dávid (email: szeszler_KUKAC_cs.bme.hu)
Kedd, 8:15-9:45
IE217

Az emelt szintű gyakorlatot olyan érdeklődő 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. Aki szívesen járna ide, de az időpont nem megfelelő neki, az keresse meg valamelyik előadót e-mailben vagy az előadás szünetében.

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, 5,5. gyakorlat, 6. gyakorlat 7. gyakorlat, 8. gyakorlat, 9. gyakorlat, 10. gyakorlat,

Segédanyagok:

Az első előadáson a kombinatorika alapjaival foglalkozunk, a további előadások témája gráfelmélet. Jegyzet: BSz2 jegyzet 2021/22 tavaszi félév.

Előadásvideók (MS STREAM, edu.bme.hu hozzáféréssel nézhetők): BSz2 előadások 1-6. BSz2 előadások 7-12.

A videók a 2020/21-es tanév második félévében készültek, az anyag és a tárgyalás módja tekintetében is kis mértékben eltérhetnek a jelen félévitől.

Egyéb segédanyagok:

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

Friedl-Recski-Simonyi: Gráfelméleti feladatok

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

Program a BFS és DFS algoritmusok kipróbálására. A bemenetet alkotó gráfot egy grafikus szerkesztőfelületen lehet létrehozni, illetve módosítani. A program megjeleníti a futás közben keletkező adatokat is a BSz2 jegyzetben írtaknak megfelelő módon, így segítheti az algoritmus(ok) pszeudokódjának a megértését is. A programot Szabó Bence készítette, aki a BSz2 tárgyat a 2020. tavaszi félévben végezte el. A program ezen a linken érhető el, a forráskódja pedig itt található.


Értékelés, tárgykövetelmények, vizsga (Figyelem: ez a szakasz akkor érvényes, ha a számonkérések jelenléti oktatás mellett történnek):

Zárthelyik, pótzárthelyik:

A félév során egy zárthelyi dolgozatot íratunk, melyben 6 darab 10 pontot érő feladat lesz. 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 szerez. A normál zárthelyi alkalom mellett lesz még egy pótzárthelyi alkalom, továbbá később egy pótpótzárthelyi alkalom is. A pótzárthelyi alkalmat fel lehet használni az elmulasztott zárthelyi teljesítésére vagy a már megírt dolgozat eredményének a javítására. Ha valaki a pótzárthelyin egy korábban már megírt dolgozatot teljesít újra, 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 megszerzéséhez tartozó minimális pontszámot egy balsikerű javítási kísérlettel nem lehet elveszíteni. Ha valaki a 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).

Kérjük, hogy azok a hallgatók, akik az írásbeli számonkéréseken határozattal biztosított többletidővel rendelkeznek, ezt a számonkérés előtt legalább két héttel jelezzék.

A pótzárthelyire nem szükséges jelentkezni a Neptunban (sem máshol).

A zárthelyi eredménye beszámít a tárgyból kapott végső jegybe, ennek a részleteit lásd alább.

Díjköteles pótlás:

A fentebb említett pótpótzárthelyi alkalom a Neptunban díjköteles pótlás néven jelenik meg. Erre a pótpótzárthelyi alkalomra vonatkozó szabályok az alábbiakban különböznek az elsőre vonatkozóktól:
A díjköteles pótláson írt dolgozatokat még aznap kijavítjuk és biztosítjuk a megtekintésüket. A megtekintés pontos időpontját és helyszíné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 már nem tudunk (kivéve természetesen a pontszámok téves összeadásából vagy adminisztrációs hibából adódó eseteket).

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

Azok, akik egy korábbi félévből 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. Erre az esetre az alábbi feltételek vonatkoznak:
Ha egy 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 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 zárthelyi eredményéből és a vizsgán nyújtott szóbeli teljesítményből alakítjuk ki az alábbi módon. A zárthelyin és a szóbeli vizsgán is 60 pontot lehet elérni. Ha a szóbeli vizsga elégtelen, akkor a vizsgajegy is elégtelen (függetlenül a zárthelyi eredményétől). Ellenkező esetben a következő képletet használjuk:

végső_pont = 0,8*min(50,zh) + 1,2*min(50,v),

ahol zh a zárthelyin, v pedig a szóbeli vizsgán szerzett pontszám. A végső jegy a végső pontszám alapján: 0-39: elégtelen, 40-54: elégséges, 55-69: közepes, 70-84: jó, 85-100: jeles.

Javító vagy ismétlő vizsga a TVSz szerint tehető. Javító vizsga esetén a zárthelyiből származó eredmények változatlanul érvényesek.

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

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

Az IMSc pontok a vizsgaeredményekkel együtt kerülnek be a Neptunba. Kérünk mindenkit, hogy ellenőrizze, hogy a Neptunban nyilvántartott IMSc pontszáma megfelel a valóságnak és amennyiben eltérést tapasztal, azt a lehető leghamarabb jelezze a SzIT tanszéki adminisztrációján a boltizar_KUKAC_cs.bme.hu emailcímen.

Technikai tudnivalók a vizsgákkal kapcsolatban:


Zárthelyik:


Zárthelyi:
május 5. (csütörtök) 8 óra

Pótzárthelyi:
május 24. (kedd)
Pótpótzárthelyi (a Neptunban jelentkezni kell rá!):
június 1. (szerda)


A zárthelyin a megoldások indoklásakor csak az előadásokon elhangzott tételekre és állításokra (és persze a középiskolában tanult, az alapszintű anyagba tartozó ismeretekre) lehet bizonyítás nélkül hivatkozni.

Technikai tudnivalók a zárthelyik lebonyolításával kapcsolatban:

Mindenkinek sok sikert kívánunk!


Korábbi félévek zárthelyi feladatsorai és pontozási útmutatói :


2017-ig a tárgyból két zárthelyit írattunk. A régi (BMEVISZA110 kódú) BSz2 tárgy (melynek anyaga némileg eltért a mostanitól) korábbi zárthelyi feladatsorai és pontozási útmutatói: