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: 2008. január 31.

    Budapesti Műszaki és Gazdaságtudományi Egyetem
    Villamosmérnöki és Informatikai Kar

    Műszaki Informatika Szak

    2.

    Tantárgy kódjaSzemeszterKövetelményKreditNyelvTárgyfélév
     visza11012+2+0v4magyar1/2
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZA110   2/2/0/v 4  
    3. A tantárgyfelelős személy és tanszék Dr. Szeszlér Dávid,
    A tantárgy tanszéki weboldala www.cs.bme.hu/bsz2
    4. A tantárgy előadója
    Név:Beosztás:Tanszék, Int.:
    Dr. Fleiner Tamásegyetemi docensSzámítástudományi és Információelméleti Tanszék
    Dr. Recski Andrásegyetemi tanárSzámítástudományi és Információelméleti Tanszék
    Dr. Simonyi Gáboregyetemi docensSzámítástudományi és Információelméleti Tanszék
    Dr. Szeszlér Dávidegyetemi adjunktusSzá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

    Bevezetés a számításelméletbe I. című tárgy anyaga.

    6. Előtanulmányi rend
    Kötelező:
    (TárgyEredmény( "BMEVISZA103" , "aláírás" , _ ) = -1
    VAGY
    TárgyEredmény( "BMEVIMA1235" , "aláírás" , _ ) = -1
    VAGY
    TárgyEredmény( "BMEVIMA1602" , "aláírás" , _ ) = -1 )

    ÉS
    (NEM ( TárgyEredmény( "BMEVISZAA01" , "jegy" , _ ) >= 2 )
    VAGY
    NEM (TargyEredmeny("BMEVISZAA01", "FELVETEL", AktualisFelev()) > 0))

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

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

    A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

    Ajánlott:

    Bevezetés a számításelméletbe I. tárgyból aláírás megszerzése.

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

    Az mérnökinformatikus tanulmányokhoz szükséges legfontosabb diszkrét matematikai ismeretek elsajátítása, szemléletmódjának kialakítása.

    8. A tantárgy részletes tematikája

    A) Fejezetek a gráfelméletből

                1) Gráfok pont- és élszínezése, Mycielsky konstrukciója, perfekt gráfok. Négy- és ötszíntétel.

                2) Euler- és Hamilton-tételkör.

                3) Párosítások, König, Hall és Tutte tételei. Gallai tételei.

                4) Hálózati folyamok. Menger-tételkör, magasabb összefüggőség.

                5) Aciklikus irányított gráfok, PERT-módszer.

                6) Gráfok mátrixai.

    B) A számelmélet alapjai

                1) Oszthatóság, felbonthatatlan- és prímszámok, a számelmélet alaptétele, euklideszi algoritmus.

                2) Kongruencia, maradékosztályok, Euler-Fermat tétel.

                3) Lineáris kongruenciák megoldása.

                4) Prímtesztelés, nyilvános kulcsú titkosírás.

    C) Az absztrakt algebra elemei

                1) Félcsoport, csoport fogalma.

                2) Nevezetes csoportok: ciklikus csoport, szimmetrikus csoport, diédercsoport.

                3) Csoportokkal kapcsolatos alapfogalmak: izomorfia, elem rendje, részcsoport, mellékosztály.

                4) Gyűrű és test fogalma, nevezetes példák.

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

     

    Heti 2 óra előadás az egész évfolyamnak és heti 2 órás kiscsoportos gyakorlat..

    10. Követelmények

    A szorgalmi időszakban: A félév folyamán két zárthelyit íratunk. A félévvégi aláírás megszerzésének (vagyis a vizsgára bocsátásnak) feltétele, hogy mindkét zárthelyinek külön-külön legalább elégségesre kell sikerülnie. A két zárthelyihez van egy-egy pótlási lehetőség: ilyenkor az elégtelen(-ek) kijavítható(-ak), illetve az esetleges hiányzás(-ok) pótolható(-ak). A pótzárthelyin gyenge, de nem elégtelen 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 rosszabb, mint az eredeti. (Ez alól egy kivétel van: a már megszerzett aláírás egy javítónak szánt, de elégtelenre megírt pótzárthelyivel nem vész el, viszont az adott zárthelyit úgy tekintjük, mintha azon a hallgató  az elégségeshez szükséges minimális pontszámot érte volna el.)  Amennyiben a szorgalmi időszakban nem sikerült mindkét zárthelyin (vagy a megfelelő pótzárthelyin) legalább elégségest szerezni, akkor a pótlási héten az egyik zárthelyi pótlására még egy lehetőség van. (Ha egyik zárthelyi sem volt sikeres, akkor a pótlási időszakban már nem lehet aláírást szerezni.)

     A vizsgaidőszakban:  A tárgyból szóbeli vizsga van. A vizsga úgy zajlik, hogy a tételsoron szereplő tételek közül a vizsgázó egyet kap, ezt kidolgozza, majd szóban felel belőle. Számítani kell arra is, hogy a vizsgáztató néhány definíció, vagy tétel kimondása erejéig a többi tételbe is belekérdez. A vizsgán az elégséges megszerzésének feltétele, hogy a vizsgázó az anyagban szereplő minden definíciót és tételt ki tudjon mondani, illetve tudjon értelmezni. A vizsgatétel kidolgozására a hallgatónak felkészülési idő  áll rendelkezésére. Negyvenöt perc felkészülési idő  letelte után a vizsgáztató abban az esetben is elkezdheti a vizsgáztatást, ha a hallgató még nem jelezte, hogy elkészült. A vizsgajegyet a két 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árthelyik átlaga 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).  Javító (ismétlő) vizsga  a TVSz szerint tehető.   Javító vizsga esetén a zárthelyikből származó eredmények változatlanul érvényesek.  

    Az aláírás a TVSz szerint 3 évig érvényes.

    Amennyiben a hallgatónak már van aláírása korábbi félévből, akkor lehetősége van megkísérelni újból megszerezni az aláírást a zárthelyik újbóli megírásával.

            Ha sikerült újra teljesíteni a feltételeket, akkor a vizsgajegybe ezek az eredmények számítanak bele (akkor is ha ezek összességében gyengébbek).         Ha megkísérelte, de nem sikerült megszerezni az aláírást, 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ámmal számítjuk be.         Ha nem kísérelte meg (nem vett részt egyetlen zárthelyin vagy pótláson sem az adott félévben), akkor a legutolsó olyan félévbeli teljesítményét vesszük figyelembe,  amikor a hallgató megkísérelt aláírást szerezni.   Elővizsga: lehetséges a vizsgaidőszak előtti (pótlások céljára fenntartott) héten
    11. Pótlási lehetőségek lásd a 10. pontot
    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.

    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
    Kontakt óra56
    Félévközi készülés órákra8
    Felkészülés zárthelyire6
    Házi feladat elkészítése8
    Kijelölt írásos tananyag elsajátítása0
    Vizsgafelkészülés42
    Összesen120

     

    (a tantárgyhoz tartozó tanulmányi idő körülbelüli felosztása a tanórák, továbbá a házi feladatok és a zárthelyik között (a felkészülésre, ill. a kidolgozásra átlagosan fordítandó/elvárható idők félévi munkaórában, kredit x 30 óra, pl. 5 kredit esetén 150 óra)):

    15. A tantárgy tematikáját kidolgozta
    Név:Beosztás:Tanszék, Int.:
    Dr. Recski Andrásegyetemi tanár, tanszékvezetőSzámítástudományi és Információelméleti Tanszék