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


Távoktatás:

Kedves Hallgatók! 2020. március 23-án megkezdjük a távoktatást, mely alapvetően (= ha a technika közbe nem szól) MS Teams-en keresztül fog történni. Minden órát az eredeti órarendi időpontban tartunk meg, ennek a részleteiről mindenki üzenetet fog kapni (vagy már kapott is) a Neptunban és a Neptunban regisztrált e-mail címére. Elképzelhető, hogy - internetelérés hiányában, egészségügyi vagy egyéb okból - az online órákat nem mindenki tudja követni, ezért - és az online oktatás hatékonyságát növelendő - a hátralévő anyagrészekről részletes jegyzetet készítünk, melyet e honlapról lehet letölteni. A számonkérések módjáról később közlünk információt; a megváltozott körülményeket természetesen messzemenően figyelembe fogjuk venni. A félév hátralévő részére mindenkinek sikeres távokulást, jó munkát és jó egészséget kívánunk!

ÉLŐ ELŐADÁS: márc. 30, hétfő 10.15. Csatlakozás az előadáshoz (edu.bme.hu regisztrációval)

Előadások: Az online előadások hatékonysága minden bizonnyal nem éri majd el az élő verzióét, ezért ezek során elsősorban az anyag alapszintű megértésére helyezzük a hangsúlyt. Ez részletesebben a következőket jelenti:
azt kérjük a hallgatóktól, hogy az előadást megelőzően olvassák el és próbálják megérteni a honlapra feltöltött előadásjegyzetet, az online előadáson pedig az anyag legfontosabb részeit fogjuk átvenni, szükség esetén kérdésekre is részletesen válaszolva (melyeket a Teams chat ablakában lehet majd írásban feltenni; azt kérjük, hogy kamerát és mikrofont az előadáson csak akkor használjanak a hallgatók, ha ez okvetlen szükséges, alapvetően ezeket tartsák kikapcsolva). Ez azzal fog járni, hogy egyes hosszadalmasabb bizonyításokat a jegyzetből kell majd megtanulni.

Gyakorlatok: Az eddigiektől eltérően már a gyakorlatok előtt közzétesszük a közös példasort is, sőt egy külön dokumentumban rövid segítségeket adunk az egyes feladatokhoz, azokat segítendő, akik önállóan dolgozzák fel a példasort, de valamelyik feladat megoldásánál nem tudnak elindulni vagy kifogynak az ötletekből. A gyakorlatok után pár nappal a feladatok egy (nagyobbik) részének megoldásai is fel fognak kerülni a honlapra.
UPDATE: A gyakorlatok a visszajelzések alapján nagyjából zökkenőmentesen és a vártnál hatékonyabban zajlanak, így a rövid segítségeket és a feladatmegoldásokat csak a 6. heti példasorhoz tesszük közzé, a továbbiakban ez már kontraproduktív lenne. Feladatmegoldásokat továbbra is lehet találni a korábbi zárthelyik pontozási útmutatóiban és a segédanyagok közt szereplő Friedl-Recski-Simonyi példatárban.

  • 6. gyakorlat, 6. gyakorlat segítségek, 6. gyakorlat megoldások

  • Jegyzet (6-7. előadás), 7. gyakorlat



  • 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
    IB027 MS TEAMS


    Gyakorlatok, gyakorlatvezetők:

    Kurzuskód:
    Gyakorlatvezető:
    Időpont:
    Helyszín:
    11
    Héger Tamás (email: heger_KUKAC_caesar.elte.hu)
    Kedd, 10:15-11:45
    E404 MS TEAMS
    12
    Borza Marcell (dleemarci97_KUKAC_gmail.com)
    Kedd, 10:15-11:45
    E406 MS TEAMS
    13
    Horváth Bálint (email: hbalintt96_KUKAC_gmail.com)
    Kedd, 10:15-11:45
    IB139 MS TEAMS
    14
    Richlik György (email: richlik_KUKAC_szit.bme.hu)
    Kedd, 10:15-11:45
    IB140 MS TEAMS
    15
    Kertész Gergő Csaba (email: kerteszcsgergo_KUKAC_gmail.com)
    Kedd, 10:15-11:45
    IB145 MS TEAMS
    16
    Balázs Barbara (email: bbarbara_KUKAC_cs.bme.hu)
    Kedd, 10:15-11:45
    IB146 MS TEAMS
    17
    Szabó Dávid (email: dzsabo_KUKAC_cs.bme.hu)
    Kedd, 10:15-11:45
    IB147 MS TEAMS
    18
    Mihálka Zsuzsanna (email: mihalka_KUKAC_cs.bme.hu)
    Kedd, 10:15-11:45
    E405 MS TEAMS
    19
    Almási Péter (email: almasipeti715_KUKAC_gmail.com)
    Kedd, 10:15-11:45
    E403 MS TEAMS
    20+24
    Drótos Márton (email: drotos_KUKAC_cs.bme.hu
    Szerda, 8:15-9:45
    IB145 MS TEAMS
    21
    Bencs Ferenc (email: hun.fertoo_KUKAC_gmail.com)
    Szerda, 8:15-9:45
    IB138 MS TEAMS
    22
    Horváth Bálint (email: hbalintt96_KUKAC_gmail.com)
    Szerda, 8:15-9:45
    IB139 MS TEAMS
    23
    Richlik György (email: richlik_KUKAC_szit.bme.hu)
    Szerda, 8:15-9:45
    IB140 MS TEAMS
    25
    Katona Dániel (email: ddkatona_KUKAC_szit.bme.hu)
    Szerda, 8:15-9:45
    IB146 MS TEAMS
    26
    Szabó Dávid (email: dzsabo_KUKAC_cs.bme.hu)
    Szerda, 8:15-9:45
    IB147 MS TEAMS
    27
    Gujgiczer Anna (email: gujgiczer.anna_KUKAC_gmail.com)
    Szerda, 8:15-9:45
    E405 MS TEAMS
    I1 (IMSc)
    Balázs Barbara (email: bbarbara_KUKAC_cs.bme.hu)
    Szerda, 8:15-9:45
    IB144 MS TEAMS
    I2 (IMSc)
    Varga Kitti (email: vkitti_KUKAC_math.bme.hu)
    Szerda, 8:15-9:45
    IE218 MS TEAMS
    I3 (IMSc)
    Wiener Gábor (email: wiener_KUKAC_cs.bme.hu)
    Szerda, 8:15-9:45
    IE219 MS TEAMS
    E1 (Emelt)
    Szeszlér Dávid (email: szeszler_KUKAC_cs.bme.hu)
    Szerda, 8:15-9:45
    IB134 MS TEAMS

    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, 6. gyakorlat, 7. gyakorlat,

    Segédanyagok:

    Tematika, jegyzet:

    Az első előadáson a kombinatorika alapjaival foglalkozunk, a további előadások témája gráfelmélet. 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 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).

    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.

    A tárgyhoz tartozó tavalyi vizsgatételsor letölthető innen. A friss tételsor a félév végén lesz elérhető.

    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 8. (péntek)
    8:00 - 10:00
    Pótzárthelyi:
    május 25. (hétfő)
    Pótpótzh (a Neptunban jelentkezni kell rá!):
    június 3. (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.
    Mindenkinek sok sikert kívánunk!

    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: