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ó    

    Introduction ? la theorie de calcul 2

    A tantárgy angol neve: Introduction to the Theory of Computing 2 (In French)

    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
    VIMAF503 2. 2/2/0/v 5 2/2
    3. A tantárgyfelelős személy és tanszék Dr. Recski András, Számítástudományi és Információelméleti Tanszék
    4. A tantárgy előadója

    Név:

    Beosztás:

    Tanszék, Int.:

    Csima Judit

    egy. tanársegéd

    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 című tárgy 1. féléves anyaga.

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

    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.

    Ajánlott:

    Bevezetés a számításelméletbe I.

    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 és gyakorlat.

    10. Követelmények

    a. A szorgalmi időszakban:

    A szemeszter folyamán két zárthelyit iratunk. Ezek mindegyike külön-külön legalább elégséges kell, hogy legyen.

    A zárthelyik általában 8 db 10 pontos példából állnak. Az elégségeshez legalább 32 pont kell. A két zárthelyi átlaga 40% súllyal beszámít a vizsgajegybe.

    A zárthelyik pótlására az előadás-időszak utolsó hetében lehetőséget adunk. Aki az aláírást pótzárthelyi írásával sem tudta megszerezni, a vizsgaidőszak első hetében különeljárással megszerezheti.

    b. A vizsgaidőszakban:

    A vizsga csak szóbeli részből áll és 60% súllyal számít be a vizsgajegybe.

    A kreditpontok megszerzésének egyetlen feltétele az aláírás megszerzése után a vizsga legalább elégséges letétele.

    c. Elővizsga:

    Kérésre elővizsga-lehetőséget is biztosítunk az előadás-időszak utolsó hetében. Az ezen való részvétel feltétele az aláírás megléte.

    13. Jegyzet, tankönyv, felhasználható irodalom

    Katona Y. Gyula - Recski András - Szabó Csaba: Gráfelmélet, algoritmuselmélet és algebra

    Házi sokszorosítás

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

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Recski András

    egy.tanár, tsz.vez.

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

    vimaF503.rtf