Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    Bevezetés a számításelméletbe 2

    A tantárgy angol neve: Introduction to the Theory of Computing 2

    Adatlap utolsó módosítása: 2018. november 28.

    Budapesti Műszaki és Gazdaságtudományi Egyetem
    Villamosmérnöki és Informatikai Kar
    Mérnök informatikus szak, BSc képzés
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZAA04   2/2/0/v 5  
    3. A tantárgyfelelős személy és tanszék Dr. Szeszlér Dávid, Számítástudományi és Információelméleti Tanszék
    A tantárgy tanszéki weboldala http://cs.bme.hu/bsz2
    4. A tantárgy előadója

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Fleiner Tamás

    egyetemi docens

    Számítástudományi és Információelméleti Tanszék

    Dr. Pach Péter Pál

    egyetemi docens

    Számítástudományi és Információelméleti Tanszék

    Dr. Recski András

    egyetemi tanár

    Számítástudományi és Információelméleti Tanszék

    Dr. Simonyi Gábor

    egyetemi tanár

    Számítástudományi és Információelméleti Tanszék

    Dr. Szeszlér Dávid

    egyetemi docens

    Számítástudományi és Információelméleti Tanszék

    Dr. Wiener Gábor

    egyetemi docens

    Számítástudományi és Információelméleti Tanszék

    5. A tantárgy az alábbi témakörök ismeretére épít A Bevezetés a számításelméletbe 1. tárgy anyaga.
    6. Előtanulmányi rend
    Kötelező:
    (TárgyEredmény( "BMEVISZAA00" , "aláírás" , _ ) = -1
    VAGY
    TárgyEredmény( "BMEVISZAA03" , "aláírás" , _ ) = -1 )


    ÉS NEM (TargyEredmeny("BMEVISZA110", "jegy", _) >= 2
    VAGY
    TárgyEredmény("BMEVISZA110", "felvétel", AktualisFelev()) > 0
    VAGY
    TargyEredmeny("BMEVISZAA01", "jegy", _) >= 2
    VAGY
    TárgyEredmény("BMEVISZAA01", "felvétel", AktualisFelev()) > 0
    VAGY
    TárgyEredmény( "BMEVISZAA01" , "aláírás" , _ ) = -1)

    ÉS (Training.Code=("5N-A8") VAGY Training.Code=("5NAA8"))

    A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

    A kötelező előtanulmányi rendek grafikus formában itt láthatók.

    7. A tantárgy célkitűzése

    A tantárgy célkitűzése a műszaki informatika tanulmányokhoz szükséges és a mérnöki alapműveltséghez tartozó egyes alapvető matematikai ismeretek elsajátítása, azok szemléletmódjának kialakítása. Ezen belül a tantárgy a gráfelmélet egyes területeire nyújt bevezetést és alapvető gráfelméleti algoritmusokat ismertet.

    A tantárgyat sikeresen teljesítő hallgató képes lesz:

    • (K3)  érteni és alkalmazni a tárgyban előkerülő fogalmakat és ismereteket;
    • (K3)  önállóan megoldani az anyaghoz kapcsolódó gyakorlati feladatokat;
    • (K2)  alkalmazni a tárgyban szereplő algoritmusokat;
    • (K3)  a későbbi tanulmányok során felismerni azokat a helyzeteket, ahol a tárgyban tanult ismeretek szerephez jutnak és sikerrel alkalmazni a tanultakat.
    8. A tantárgy részletes tematikája

    1)      Kombinatorikai alapismeretek: permutációk, variációk, kombinációk ismétlés nélkül és ismétléssel. Összefüggések a binomiális együtthatók között, Pascal-háromszög, binomiális tétel.

    2)      Gráfelméleti alapfogalmak: gráf, egyszerű gráf, fokszám, élsorozat, út, kör, összefüggő gráf, összefüggő komponens, fa, feszítőfa. Az összefüggőség eldöntése, legrövidebb út keresése (élsúlyozatlan, irányítatlan gráfban): a szélességi bejárás (BFS).

    3)      Minimális összsúlyú feszítőfa keresése: a Kruskal algoritmus. Síkbarajzolható gráf fogalma, ekvivalencia a gömbre rajzolhatósággal, Euler-féle poliédertétel.

    4)      Reláció egyszerű síkgráf éleinek és csúcsainak a száma között. A K5 és K3,3 gráfok síkba nem rajzolhatósága, Kuratowski tétele. Síkgráf duálisa, megfelelések a csúcsok/élek/tartományok száma között, kör és vágás képe.

    5)      Euler-út és Euler kör fogalma, ezek létezésének szükséges és elégséges feltétele. Hamilton-út és Hamilton-kör fogalma. Szükséges feltételek ezek létezésére: a k pont törlése után keletkező komponensek maximális száma. Elégséges feltételek: Dirac és Ore tételei.

    6)      Páros gráf fogalma, azok karakterizációja páratlan körökkel. A kromatikus szám fogalma. Mohó színezés, felső becslés a kromatikus számra a maximális fokszám függvényében. Maximális klikkméret fogalma, reláció a kromatikus számmal, Mycielski-konstrukció.

    7)      Intervallumgráfok optimális színezése. Párosítás, lefogó ponthalmaz, független ponthalmaz, lefogó élhalmaz fogalmai. Reláció a maximális párosítás és a minimális lefogó ponthalmaz mérete között. Gallai tételei.

    8)      Maximális párosítás keresése páros gráfokban, a javító utas algoritmus, annak optimalitása. Kőnig tétele a maximális párosítás és a minimális lefogó ponthalmaz méretének egyenlőségéről. Tutte tétele.

    9)      Élkromatikus szám fogalma, reláció a maximális fokszámmal, Vizing tétele, Kőnig tétele páros gráfok optimális élszínezéséről. A maximális folyam feladata: hálózat, folyam és folyam értékének fogalma, a javító utas algoritmus maximális folyam keresésére.

    10)  Hálózat st-vágásának fogalma, annak kapacitása. Ford-Fulkerson tétel, Edmonds-Karp tétel. Egészértékűségi lemma. Az éldiszjunkt, irányított s-t utak problémája, Menger vonatkozó tétele.

    11)  Az éldiszjunkt, irányítatlan s-t utak problémája, a pontdiszjunkt s-t utak problémája irányított és irányítatlan esetben is, Menger vonatkozó tételei. Többszörös pont- és élösszefüggőség fogalmai, Menger vonatkozó tételei.

    12)  A legrövidebb út keresésének problémája pozitív élsúlyokkal irányított és irányítatlan gráfban, illetve valós élsúlyokkal irányított gráfban, Dijkstra, Ford és Floyd algoritmusai.

    13)  Mélységi bejárás (DFS) irányítatlan és irányított gráfban, az irányított körök felismerése. Aciklikus irányított gráfok, topologikus rendezés. Legrövidebb és leghosszab út keresése aciklikus irányított gráfban.

    14)  Ismétlés, összefoglalás, a tanult anyagrészek rendszerezett áttekintése. A szóbeli vizsgára vonatkozó aktuális vizsgatételsor és az egyes vizsgatételekkel kapcsolatos részletes elvárások ismertetése.

    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

    A tárgyból heti 2 óra előadás és heti 2 órás kiscsoportos gyakorlat van.

    Az előadásokon az új elmélet kerül bemutatásra, ennek gyakorlása és feladatokban való alkalmazása zajlik a gyakorlatokon. A gyakorlatok mindig szorosan kapcsolódnak a megfelelő előadás anyagához, ezért azokon az  előadáson tanult anyag ismerete elvárás a hallgatóktól. Az előadásokon tárgyalt fogalmak és ismeretek begyakorlása, elmélyítése a gyakorlatokon zajlik, az itt zajló munka (beleértve a házi feladatok megoldását is) a tanulási folyamat alapvető fontosságú része. Az előadások a legtöbb esetben szorosan épülnek a korábbi hetek anyagára, ezek ismerete nélkül az új anyag általában nem követhető.
    10. Követelmények

    A szorgalmi időszakban: A félév folyamán egyetlen zárthelyit íratunk. A félévvégi aláírás megszerzésének (vagyis a vizsgára bocsátásnak) a feltétele a zárthelyin legalább 40%-os teljesítmény elérése.

    Az érvényes TVSz-nek megfelelően a tárgyból korábban megszerzett aláírás 3 évig érvényes. (Részletesebben ez azt jelenti, hogy az aláírás megszerzését követő hatodik félév vizsgaidőszakjának végéig az aláírás még érvényes.) Azok a hallgatók, akik egy korábbi félévből érvényes aláírással rendelkeznek, megkísérelhetik újból megírni a zárthelyit, hogy a korábbi eredményükön javítsanak. Erre az esetre az alábbi feltételek vonatkoznak:

    • Ha sikerül újra teljesíteni az aláíráshoz szükséges feltételt, akkor a vizsgajegybe (lásd lentebb) az így kapott eredmény számít bele (akkor is, ha ez rosszabb).
    • Ha nem sikerül újra teljesíteni az aláíráshoz szükséges feltételt, akkor az aláírás nem vész el, de a vizsgajegybe csak az aláírás megszerzéséhez szükséges minimális pontszámot számítjuk be.

    Ha egy érvényes aláírással rendelkező hallgató az aktuális félévben a zárthelyin, a pótzárthelyin vagy az aláíráspótló vizsgán 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). 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.

    A vizsgaidőszakban: Vizsgára az jelentkezhet, aki érvényes aláírással rendelkezik.

    A vizsga ebből a tárgyból szóbeli. A vizsga megkezdésekor a vizsgázó a tárgyhoz tartozó tételsorból egyetlen tételt kap, amelynek a kidolgozására (vagyis a szóbeli felelethez egy bő jegyzet készítésére) legalább 45 perc áll rendelkezésre. 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.) 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 olyan módon, hogy abba a zárthelyi eredménye 40 százalék erejéig, a szóbeli vizsga 60 százalék erejéig számít bele. Ha a szóbeli vizsga elégtelen, akkor a vizsgajegy is elégtelen (függetlenül a zárthelyik eredményétől). Ismétlő vizsga esetén a zárthelyikből származó eredmények változatlanul érvényesek. Részletesebben: a vizsgán kapott végső jegyet meghatározó pontszámot az alábbi képlettel számítjuk ki, ahol zh a zárthelyi eredménye, v pedig a szóbeli vizsgán a felelettel szerzett pontszám (amelyeknek az értéke maximálisan 60).

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

    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.

    Ha a szóbeli vizsga elégtelen, akkor a vizsgajegy is elégtelen (függetlenül a zárthelyi eredményétől). Ismétlő vizsga esetén a zárthelyiből származó eredmény változatlanul érvényes.

    A tárgyhoz tartozó vizsgatételsor félévről félévre változik, az aktuális félévre érvényes vizsgatételsor a tárgy tanszéki weboldaláról tölthető le a szorgalmi időszak utolsó hetétől.

    Elővizsga: nem lehetséges

    11. Pótlási lehetőségek

    A szorgalmi időszakban egyetlen pótzárthelyi alkalom lesz, amelyen a zárthelyi eredménye javítható vagy a hiányzás pótolható.

    A pótzárthelyin tehát a korábban megírt, eredményes zárthelyi javítása is megkísérelhető, de csak azzal a feltétellel, hogy ilyenkor mindenképpen az új pontszám lesz érvényes, akkor is, ha az rosszabb, mint az eredeti. Ez alól egy kivétel van: ha egy hallgató a normál zárthelyin legalább 40%-os teljesítményt ért el és így az aláírás feltételeit már teljesítette, de a javítónak szánt pótzárthelyin 40% alatti teljesítményt ér el, akkor a hallgató az aláírást megkapja, de a zárthelyiből származó pontszáma a 40%-os eredménynek megfelelő, minimális pontszám lesz.

    Amennyiben a zárthelyi és a pótzárthelyi segítségével sem sikerül az aláírás feltételeit teljesíteni, a vizsgaidőszak előtti pótlási héten lehetőség nyílik a zárthelyi újbóli pótlására. Ennek a második pótzárthelyi alkalomnak a neve “díjköteles pótlás”. A díjköteles pótlás megírásáért különeljárási díjat kell fizetni és azon a korábban megírt, sikeres (vagyis a 40%-os teljesítményt elérő) zárthelyi vagy pótzárthelyi eredménye már nem javítható.

    12. Konzultációs lehetőségek A vizsgák előtt konzultációs lehetőséget biztosítunk.
    13. Jegyzet, tankönyv, felhasználható irodalom

    Katona Y. Gyula - Recski András - Szabó Csaba: A számítástudomány alapjai, TypoTeX Kiadó, 2003.

    Friedl Katalin - Recski András - Simonyi Gábor: Gráfelméleti feladatok, TypoTeX Kiadó, 2006.

    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka

    Kontakt óra

    56

    Félévközi készülés előadásokra

    8

    Félévközi készülés gyakorlatokra

    21

    Felkészülés zárthelyire

    15

    Vizsgafelkészülés

    50

    Összesen

    150

    15. A tantárgy tematikáját kidolgozta

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Szeszlér Dávid

    egyetemi docens

    Számítástudományi és Információelméleti Tanszék

    IMSc tematika és módszer A plusz pontokat a hatékonyabb tanulásért és az anyag magasabb szintű, mélyebb elsajátításáért kapják a hallgatók. A gyakorlatokon más feladatokat dolgozunk fel, mint a többi kurzuson. Kevesebb bevezető, rutin, gyakorló feladat szerepel és több nehezebb, gondolkodtatóbb feladat lesz.
    IMSc pontozás Az IMSc pontokat az alábbi képlettel számítjuk ki, ahol zh a zárthelyin, v pedig a szóbeli vizsgán elmondott felelettel szerzett pontszám. (Mindkettőnek az értéke maximálisan 60.)

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

    Az IMSc pontok megszerzése a programban nem résztvevő hallgatók számára is biztosított. Az aláírás és a vizsgajegy megszerzése mindenki számára egységes követelmények szerint, a 10. pontban leírtaknak megfelelően történik, ezt az IMSc pontok nem befolyásolják.