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ó    

    Bases de la science de calcul

    A tantárgy angol neve: Elements of the Theory of Computing (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

    Villamosmérnöki Szak

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VIMAF010 4. 4/2/0/v 8 1/1.
    3. A tantárgyfelelős személy és tanszék Dr. Recski András,
    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

    1. és 2. féléves matematika.

    6. Előtanulmányi rend
    Kötelező:
    TárgyEredmény( "BMETE901918" , "aláírás" , _ ) >0 VAGY TárgyEredmény( "BMETE901918" , "felvétel" , _ ) >0 VAGY TárgyEredmény( "BMEVIDH8007" , "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:

    Matematika II, kredit

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

    A villamosmérnöki tanulmányokhoz szükséges legfontosabb matematikai ismeretek elsajátítása, az algebra és diszkrét matematika szemléletmódjának kialakítása.

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

    A) Kombinatorikai alapfogalmak, leszámolások.

    B) Fejezetek a gráfelméletből

    1) Gráfelméleti alapfogalmak, út, kör, fa, irányított gráfok

    2) Síkbarajzolhatóság, dualitás, gyenge izomorfia

    3) Gráfok mátrixreprezentációi

    4) Párosítások, Kőnig tétel, magyar módszer, hálózati folyamok, Menger tételei

    5) Gráfelméleti algoritmusok. Legrövidebb út, párosítás, folyam, fakeresés, alapkör rendszer generálása, kritikus út módszere.

    C) Rendezési algoritmusok, adatstrukturák, számelméleti algoritmusok, a kriptográfia alapelemei.

    D) Algoritmusok komplexitása. P,NP,NP-teljes problémák.

    E) Az absztrakt algebra elemei. Csoportok, gyűrük, testek, hálók, Boole algebrák.

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

    Heti 4 óra előadás az egész évfolyamnak, és heti 2 óra kiscsoportos gyakorlat, ezt kiegészíti egy rendszeres konzultáció.

    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 Gyula-Recski András-Szabó Csaba: Gráfelmélet, algoritmuselmélet és algebra

    (házi sokszorosítás)

    Gács Péter-Lovász László: Algoritmusok Tankönyvkiadó, 1991 (42317) (ajánlott)

    Rényi Alfréd: Dialógusok a matematikáról (ajánlott)

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

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Recski András

    egy.tanár, tansz. vez.

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

    vimaF010doc