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


Aktuális:

Új! Vizsgatételsor

Új! Minden vizsgahéten a vizsgák előtt konzultációt tartunk. Az ezeken való részvétel természetesen a legkevésbé sem feltétele a sikeres vizsgázásnak: ezeken semmi olyasmi nem derül ki, ami az előadásokon ne hangzott volna el. A részvétel azok számára lehet hasznos, akikben a vizsgára készülés közben az anyaggal kapcsolatos kérdések merültek fel és ezekre szeretnének választ kapni. A konzultációk időpontjai és helyszínei:
jún. 9. 11:15–12:45, IB134
jún. 16. 14:15–15:45, IB134
jún. 23. 15:15–16:45, IB134
jún. 30. 14:15–15:45, IB134

Új! A június 2-i pótzárthelyi feladatai és pontozási útmutatója

Új! A május 21-i zárthelyi feladatai és pontozási útmutatója

Szeretnénk felhívni mindenki figyelmét, hogy a BSz2 pótpótzh és az Algel pótpótzh is ugyanazon a napon lesz (de különböző idősávban). Tudjuk, hogy ez így szerencsétlen (és próbáltuk elérni, hogy ne így legyen), de a számonkérések ütemezésére közvetlen ráhatásunk nincsen.

Visszajelzés a BSz2 gyakorlatokról – a május 2-án kiküldött kérdőív eredményei

Információk azoknak, akik a BSz2 zh-kon valamilyen kedvezményt kívánnak igénybe venni:
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.

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

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


A félév anyaga részletesen május 29-ig:

1. hét febr. 16. Gráfelméleti alapfogalmak, 1. rész (1. fejezet): a gráf fogalma (1.1. fejezet), részgráf, komplementer (1.2. fejezet), gráfok izomorfiája (1.3. fejezet), irányított gráfok (1.6. fejezet).
febr. 17. 1. gyakorlat
2. hét febr. 23. Gráfelméleti alapfogalmak, 2. rész (1. fejezet): összefüggőség, komponens (1.4. fejezet), fa, feszítőfa (1.5. fejezet).
febr. 24. 2. gyakorlat
3. hét márc. 2. Szélességi keresés (2. fejezet, algoritmus vetítés). Legrövidebb utak (11. fejezet): Dijkstra-algoritmus (11.2. fejezet, algoritmus vetítés).
márc. 3. 3. gyakorlat
4. hét márc. 9. Euler-séták és Euler-körséták (4. fejezet), Hamilton-utak és Hamilton-körök (5. fejezet).
márc. 10. 4. gyakorlat
5. hét márc. 16. 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árc. 17. 5. gyakorlat
6. hét márc. 23. 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 eleje).
márc. 24. Elmarad a gyakorlat (Simonyi Konferencia miatt).
7. hét márc. 30. Független ponthalmaz és lefogó élhalmaz (7.1. fejezet).
márc. 31. 6. gyakorlat
– ápr. 2–12. Tavaszi szünet
8. hét ápr. 13. 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).
ápr. 14. 7. gyakorlat
9. hét ápr. 20. 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).
ápr. 21. 8. gyakorlat
10. hét ápr. 27. A maximális folyam feladat, 1. rész (9. fejezet): a javítóutas algoritmus maximális folyam keresésére (9.1. fejezet).
ápr. 28. 9. gyakorlat
11. hét máj. 4. A maximális folyam feladat, 2. rész (9. fejezet): a javítóutas algoritmus vizsgálata (9.2. fejezet), egészértékűségi lemma (9.17. lemma), a folyamprobléma változatai (9.3. fejezet). (Az előadásokat tekintve eddig tart a zárthelyi anyaga.)
máj. 5. 10. gyakorlat
12. hét máj. 11. Diszjunkt utak, többszörös összefüggőség, 1. rész (10. fejezet): éldiszjunkt utak (10.1. fejezet), pontdiszjunkt utak (10.2. fejezet).
máj. 12. 11. gyakorlat (A gyakorlatokat tekintve eddig tart a zárthelyi anyaga.)
13. hét máj. 18. Diszjunkt utak, többszörös összefüggőség, 2. rész (10. fejezet): többszörös összefüggőség (10.3. fejezet). Minimális összsúlyú feszítőfa (3. fejezet).
máj. 19. 12. gyakorlat
máj. 21. 8:00 Zárthelyi: Feladatok és pontozási útmutató
14. hét máj. 25. Elmarad az előadás (pünkösdhétfő miatt).
máj. 26. 13. gyakorlat
– jún. 2. 10:00 Pótzárthelyi
– jún. 10. 10:00 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

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


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

Előadó: Email: Időpont: Helyszín:
Szeszlér Dávid szeszler_KUKAC_cs.bme.hu Hétfő, 10:15–12:00 IB028
Wiener Gábor wiener_KUKAC_cs.bme.hu Hétfő, 10:15–12:00 Q-I


Gyakorlatok, gyakorlatvezetők:

Kurzuskód: Gyakorlatvezető: Email: Időpont: Helyszín:
11 Kabódi László kabodi.laszlo_KUKAC_vik.bme.hu Kedd, 10:15–11:45 IB138
12 Csonka Bence slenhortag_KUKAC_gmail.com Kedd, 10:15–11:45 IB139
13 Hizsnyan Bálint hizsnyan.b_KUKAC_gmail.com Kedd, 10:15–11:45 IB140
14 Gaskó Botond botond.gasko_KUKAC_edu.bme.hu Kedd, 10:15–11:45 IB141
15 Furmann Bálint furmann.balint_KUKAC_edu.bme.hu Kedd, 10:15–11:45 IB142
16 Kun Ferenc Ágoston kunagoston_KUKAC_gmail.com Kedd, 10:15–11:45 IB145
17 Telbisz Csanád csanadtelbisz_KUKAC_edu.bme.hu Kedd, 10:15–11:45 IB146
18 Richlik György richlik_KUKAC_szit.bme.hu Kedd, 10:15–11:45 IB147
19 Csákány Rita csakany_KUKAC_cs.bme.hu Kedd, 10:15–11:45 E407
20 Telekes Márton telekesmarton_KUKAC_gmail.com Kedd, 10:15–11:45 E406
21+23 Benis Erzsébet benis.erzsebet03_KUKAC_gmail.com Kedd, 12:15–13:45 IB138
22 Csonka Bence slenhortag_KUKAC_gmail.com Kedd, 12:15–13:45 IB139
24 Szabó Réka szabo_KUKAC_cs.bme.hu Kedd, 12:15–13:45 IB141
25+27 Uzonyi Ákos uzonyi.akos_KUKAC_gmail.com Kedd, 12:15–13:45 IB142
26 Szeszlér Dávid szeszler_KUKAC_cs.bme.hu Kedd, 12:15–13:45 IB145
28 Richlik György richlik_KUKAC_szit.bme.hu Kedd, 12:15–13:45 IB147
29 Héger Tamás heger_KUKAC_cs.bme.hu Kedd, 12:15–13:45 IB140
30 Csákány Rita csakany_KUKAC_cs.bme.hu Kedd, 12:15–13:45 E407
I1 (IMSc) Varga Kitti vkitti_KUKAC_cs.bme.hu Kedd, 10:15–11:45 IB144
I2 (IMSc) Szabó Réka szabo_KUKAC_cs.bme.hu Kedd, 10:15–11:45 IE218
I3 (IMSc) Vidor Sára vidor.sari_KUKAC_gmail.com Kedd, 10:15–11:45 IE219
E1 (Emelt) Szeszlér Dávid 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.


É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áról és helyszínéről Neptun üzenetben értesítjük a díjköteles pótláson résztvevőket a dolgozat napján, legalább egy órával a megtekintés előtt. 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.

Vizsgaté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,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:

A zárthelyikre való felkészüléshez használható a tárgyhoz tartozó feladatgyűjtemény és a korábbi évek zárthelyi feladatsorai (az ott részletezett szempontok figyelembevételével). Természetesen figyelni kell arra, hogy az egyes tanévekben változhat az anyag sorrendje vagy a dolgozatok időpontja, ezért a zárthelyik anyaga nem azonos; értelemszerűen olyan feladatokat érdemes keresni, amelyek az épp aktuális zárthelyi anyagához tartoznak.

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: