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

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

    Adatlap utolsó módosítása: 2006. július 1.

    Tantárgy lejárati dátuma: 2015. január 31.

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

    Műszaki Informatika Szak

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VIMA1236 1 2/2/0/v 5 1/2
    3. A tantárgyfelelős személy és tanszék Dr. Csákány Rita,
    4. A tantárgy előadója

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Sali Attila

    egyetemi docens

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

    Dr. Simonyi 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

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

    6. Előtanulmányi rend
    Kötelező:
    TárgyEredmény( "BMEVIMA1235" , "aláírás" , _ ) >0 VAGY TárgyEredmény( "BMEVIMA1205" , "aláírás" , _ ) >0 VAGY TárgyEredmény( "BMEVIMA1601" , "aláírás" , _ ) >0 VAGY TárgyEredmény( "BMEVIMA1602" , "aláírás" , _ ) >0

    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 informatikusmérnöki 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

    Gráfok pont- és élszínezése, Mycielsky konstrukciója, perfekt gráfok. Négy- és ötszíntétel. Euler- és Hamilton-tételkör. Szélességi és mélységi keresés, legrövidebb út kereső algoritmusok. Párosítások, Hall és Tutte tételei. Gallai tételei. Hálózati folyamok. Menger-tételkör, magasabb összefüggőség. A mélységi keresés alkalmazásai, topológiai rendezés, PERT-módszer. Számelmélet (oszthatóság, a számelmélet alaptétele, euklideszi algoritmus, kongruencia, maradékosztályok, Euler-Fermat tétel, lineáris kongruenciák megoldása, prímtesztelés, nyilvános kulcsú titkosírások) Absztrakt algebra (félcsoport, csoport, rend, nevezetes csoportok, részcsoport, normálosztó, faktorcsoport, gyűrű, test, nevezetes példák pl. kvaterniók, testbővítések)

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

    (előadás, gyakorlat, laboratórium):

    Előadás és gyakorlat.

    10. Követelmények

    a. A szorgalmi időszakban:

    A félév folyamán két zárthelyit iratunk.

    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 a félév utolsó hetében: 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 leviszi a zárthelyikből származó pontszámot az elégségeshez szükséges minimális pontszám szintjére.)

    Amennyiben a pótlás sem sikerül, már csak ismétlő vizsga (gyakIV) jelleggel lehet megszerezni az aláírást, és így a vizsgázás jogát. Ennek módja, hogy a vizsgaidőszakban egy újabb zárthelyit kell legalább elégségesre megírni. (Ez a zárthelyi a félév teljes anyagához kapcsolódó feladatokat tartalmazhat függetlenül attól, hogy a szorgalmi időszakban melyik zárthelyi nem sikerült.) A vizsgaidőszakban két gyakIV alkalmat hirdetünk meg (ezek közül az egyiket várhatóan az első héten), de a két alkalom közül mindenki csak az egyiken próbálkozhat. Így ha valaki az első alkalommal megpróbált aláírást szerezni, de ez nem sikerült, annak sajnos a második alkalommal már nem lesz lehetősége erre. A gyakIV-kre a Neptunban jelentkezni kell.

    Ha a gyakIV jelleggel megírt zárthelyi eléri a legalább elégséges szintet, akkor egy későbbi vizsgaalkalommal lehet vizsgázni. Ha valaki az aláírást gyakIV-vel szerzi meg, akkor ezt a vizsgán úgy számítjuk be, mintha mindkét zárthelyin az elégségeshez szükséges minimális pontszámot érte volna el. Ha a gyakIV sem sikerül, akkor a félév sajnos sikertelen.

    b. 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, illetve 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).

    Aki elégtelenre vizsgázik, egy ízben ismétlő vizsgát tehet. Ez a pótlási lehetőség szükség esetén az olyan hallgatót is megilleti, aki az aláírást gyakIV-vel szerezte meg. Ismétlő vizsga esetén a zárthelyikből származó eredmények változatlanul érvényesek.

    1. Elővizsga: nincs rá lehetőség.
    11. Pótlási lehetőségek

    lásd a 10. pontot.

    12. Konzultációs lehetőségek

    A zárthelyik 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

    (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)):

    Kontakt óra

    60

    Félévközi készülés órákra

    15

    Felkészülés zárthelyire

    10

    Házi feladat elkészítése

    15

    Kijelölt írásos tananyag elsajátítása

    0

    ..

    Vizsgafelkészülés

    50

    Összesen

    150

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

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Recski András

    egyetemi tanár, tanszékvezető

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