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ájus 18., 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

  • 7. gyakorlat

  • 8. gyakorlat

  • 9. gyakorlat

  • 10. gyakorlat

  • 11. gyakorlat

  • 12. gyakorlat

  • Jegyzet (6-13. előadás, a 13. előadás anyaga a 7. pontnál kezdődik), 13. 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, 8. gyakorlat, 9. gyakorlat, 10. gyakorlat, 11. gyakorlat, 12. gyakorlat, 13. 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: