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


Aktuális:

Kérjük, hogy aki a BSz2 zh-n valamilyen kedvezményt kíván igénybe venni és ehhez engedéllyel rendelkezik, az töltse ki ezt az űrlapot. Aki az űrlapot a félév során (é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.

2. előadáskurzus 8. feladatlap: Feladatok, Google Forms link.

A 2. előadáskurzus korábbi feladatlapjai


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
Vincze András (email: andrasvincze01_KUKAC_gmail.com)
Kedd, 10:15–11:45
IB138
12
Gehér Panna (email: geher.panni_KUKAC_gmail.com)
Kedd, 10:15–11:45
IB139
13
Almási Nóra (email: almasinori_KUKAC_gmail.com)
Kedd, 10:15–11:45
IB140
14
Szabó Réka (email: szabo_KUKAC_cs.bme.hu)
Kedd, 10:15–11:45
IB141
15
Richlik György (email: richlik_KUKAC_szit.bme.hu)
Kedd, 10:15–11:45
IB142
16
Horváth Hanna Szabrina (email: horvath.hanna.szabrina23_KUKAC_gmail.com)
Kedd, 10:15–11:45
IB145
17
Garami Bence (email: garamibence_KUKAC_gmail.com)
Kedd, 10:15–11:45
IB146
18
Banczik Zoltán (email: zoltan.banczik_KUKAC_gmail.com)
Kedd, 10:15–11:45
IB147
19
Telekes Márton (email: telekesmarton_KUKAC_gmail.com)
Kedd, 10:15–11:45
E406
20
Uzonyi Ákos (email: uzonyi.akos_KUKAC_gmail.com)
Kedd, 10:15–11:45
E405
21
Almási Nóra (email: almasinori_KUKAC_gmail.com)
Kedd, 12:15–13:45
IB140
22
Szabó Réka (email: szabo_KUKAC_cs.bme.hu)
Kedd, 12:15–13:45
IB141
23
Richlik György (email: richlik_KUKAC_szit.bme.hu)
Kedd, 12:15–13:45
IB142
24+26
Balázs Barbara (email: bbarbara_KUKAC_cs.bme.hu)
Kedd, 12:15–13:45
IB139
25
Szeszlér Dávid (email: szeszler_KUKAC_cs.bme.hu)
Kedd, 12:15–13:45
IB138
27
Garami Bence (email: garamibence_KUKAC_gmail.com)
Kedd, 12:15–13:45
IB146
28
Dúcz Ákos (email: akos.ducz_KUKAC_gmail.com)
Kedd, 12:15–13:45
IB147
29
Gujgiczer Anna (email: gujgiczer.anna_KUKAC_gmail.com)
Kedd, 12:15–13:45
E306cd
30
Süveges Márton (email: suvegesmarton_KUKAC_gmail.com)
Kedd, 12:15–13:45
IB145
I1 (IMSc)
Balázs Barbara (email: bbarbara_KUKAC_cs.bme.hu)
Kedd, 10:15–11:45
IB144
I2 (IMSc)
Varga Kitti (email: vkitti_KUKAC_math.bme.hu)
Kedd, 10:15–11:45
IE219
I3 (IMSc)
Kabódi László (email: kabodi.laszlo_KUKAC_vik.bme.hu)
Kedd, 10:15–11:45
IE218
E1 (Emelt)
Szeszlér Dávid (email: szeszler_KUKAC_cs.bme.hu)
Kedd, 10:15–11:45
IE217-1

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 félév anyaga részletesen április 1-ig:

1. hét február 10. Gráfelméleti alapfogalmak, 1. rész (1. fejezet): részgráf, komplementer (1.1. fejezet), gráfok izomorfiája (1.2. fejezet), irányított gráfok (1.5. fejezet)
február 11. 1. gyakorlat
2. hét február 17. Gráfelméleti alapfogalmak, 2. rész (1. fejezet): összefüggőség, komponens (1.3. fejezet), fa, feszítőfa (1.4. fejezet)
február 18. 2. gyakorlat
3. hét február 24. Euler-séták és Euler-körséták (4. fejezet), Hamilton-utak és Hamilton-körök (5. fejezet)
február 25. 3. gyakorlat
4. hét március 3. Szélességi keresés (2. fejezet, algoritmus vetítés), minimális összsúlyú feszítőfa (3. fejezet)
március 4. 4. gyakorlat
5. hét március 10. Gráfok színezése, 1. rész (6. fejezet): páros gráfok (6.1. fejezet), mohó színezés (6.2. fejezet), klikkszám és kromatikus szám (6.3. fejezet)
március 11. 5. gyakorlat
6. hét március 17. Gráfok színezése, 2. rész (6. fejezet): Zykov-konstrukció (6.14. tétel), intervallumgráfok (6.4. fejezet); Párosítások (7. fejezet)
március 18. 6. gyakorlat
7. hét március 24. Független ponthalmaz és lefogó élhalmaz (7.1. fejezet)
március 25. 7. gyakorlat
8. hét március 31. Párosítások páros gráfban, 1. rész (7.2. fejezet): javítóutas algoritmus (algoritmus vetítés), Kőnig-tétel (7.18. következmény)
április 1. 8. gyakorlat
9. hét április 7. Párosítások páros gráfban, 2. rész (7.2. fejezet): Hall-tétel (7.22. tétel), Frobenius-tétel (7.24. következmény), teljes párosítás létezése reguláris páros gráfban (7.25. következmény); Gráfok élszínezése (8. fejezet)
április 8. 9. gyakorlat
10. hét április 14.
április 15.
április 17–27. Tavaszi szünet
11. hét április 28.
április 29.
12. hét május 5.  
18:00 Zárthelyi
május 6.
13. hét május 12.  
18:00 Pótzárthelyi
május 13.
14. hét május 19.
május 20.
június 4. Pótpótzárthelyi



Segédanyagok:

A félév során végig gráfelmélettel foglalkozunk. Az alábbi online jegyzet tartalmazza a tárgy teljes anyagát, sőt, valamivel többet is.

Jegyzet: BSz2 jegyzet.

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


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

Zárthelyik, pótzárthelyik:

A félév során egy zárthelyi dolgozatot íratunk, melyben 6 darab 10 pontot érő feladat szerepel majd. 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). A zárthelyi és a pótlások eredményei a kari Moodle felületen jelennek meg.

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 és máshol sem (a pótpótzárthelyire ellenben igen, ld. alább).

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 még a megtekintés előtt felkerülnek a kari Moodle felületre. 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,9: elégtelen, 40-54,9: elégséges, 55-69,9: közepes, 70-84,9: jó, 85-100: jeles. A vizsgáztató a vizsga végső eredményét közli a hallgatóval.

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.

A tételsor a félév végén lesz letölthető erről a honlapról. Tájékoztatásul alább mellékeljük a legutóbbi félév tételsorát, az új tételsor ettől nem fog sokban különbözni. BSz2 tételsor 2023/24. tavasz

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

Időpontok

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: