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ó    

    Véges matematika villamosmérnököknek

    A tantárgy angol neve: Finite Mathematics for Electrical Engineers

    Adatlap utolsó módosítása: 2024. január 3.

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

    Villamosmérnök, MSc

    Főspecializáció C tárgy 
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZMA08   2/1/0/v 5  
    3. A tantárgyfelelős személy és tanszék Dr. Recski András,
    4. A tantárgy előadója

    Dr. Recski András prof. emeritus, SZIT

    Dr. Fleiner Tamás egyetemi tanár,  SZIT

    5. A tantárgy az alábbi témakörök ismeretére épít Számítástudomány alapjai (BSc tárgy) 
    6. Előtanulmányi rend
    Ajánlott:
    Számítástudomány alapjai (BSc tárgy) 
    7. A tantárgy célkitűzése A villamosmérnök BSc "Számítástudomány alapjai" tárgy folytatásaképp további gráfelméleti, számelméleti és algoritmuselméleti ismeretek oktatása, ezen ismeretek (elsősorban villamosmérnöki) alkalmazásainak bemutatása: A gráfelméleten belül főleg a színezési problémák (és alkalmazásaik a chip-tervezésben), a gráfok mátrix-reprezentációi (és alkalmazásaik a hálózatanalízisben), a számelmélet alapalgoritmusai (és alkalmazásaik a kriptográfiában), valamint az algoritmuselmélet legfontosabb bonyolultságosztályai. 
    8. A tantárgy részletes tematikája

    1. Pontszínezés, mohó színezés Δ+1 színnel, klikkszám és kromatikus szám kapcsolata, Mycielsky-konstrukció.  

    2. Perfekt gráfok, a gyenge és erős perfekt gráf tétel (biz. nélkül). Intervallumgráfok, Gallai tétele. Alkalmazás chip-huzalozáshoz 

    3. Élszínezés, Vizing tétele, Shannon tétele (biz. nélkül), teljes gráfok élkromatikus száma. Órarend készítése, körmérkőzések szervezése. 

    4. Ramsey-tétel, Erdős-Szekeres tétel, általánosítás kettőnél több színre, Schur-tétel. 

    5. Turán-tétel. Erdős-Simonovits tétel (biz. nélkül) 

    6. Gráfok mátrixai I. Szomszédsági és illeszkedési mátrix, Kirchhoff-Cayley tétel 

    7. Gráfok mátrixai II. Körmátrix és vágásmátrix, alkalmazások a villamos hálózatok analízisében 

    8.  A számelmélet alapfogalmai, oszthatóság, prímek. 

    9. Kongruenciák, diofantikus egyenletek, szimultán kongruenciák. 

    10. Egyszerű számelméleti algoritmusok, az euklideszi algoritmus, prímtesztelés. Az RSA 

    algoritmus 

    11.  P, NP, co-NP, jó karakterizáció, NP-teljesség.  

    12. Nevezetes NP-teljes gráfelméleti feladatok, visszavezetések. 

     

    Gyakorlatokon: Feladatmegoldások az előadásokon tanultak sorrendjében.  

    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) Előadás, egyéni feladatmegoldások. Az előadások során elsősorban a világos fogalomalkotásra törekszünk, a tételek egy részét bizonyítás nélkül közöljük. A feladatok az előadásokon elhangzott anyagokhoz kapcsolódnak, különös súlyt helyezve az algoritmikus gondolkodás fejlesztésére.
    10. Követelmények

    Szorgalmi időszakban 

    1 db zárthelyi sikeres megírása az 1.—9. anyagrészekből (min. 40%) 

    Vizsgaidőszakban 

    Szóbeli vizsga 

     

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

    A félév során lehetőséget adunk a zárthelyi pótlására. 

    A sikertelen zárthelyi a pótlási időszakban ismételten pótolható.

    12. Konzultációs lehetőségek Igény esetén előzetesen egyeztetett időpontban konzultációt biztosítunk. 
    13. Jegyzet, tankönyv, felhasználható irodalom

    Katona Gyula Y., Recski András, Szabó Csaba: A számítástudomány alapjai, Typotex, Budapest, 2002. 

    Friedl Katalin, Recski András, Simonyi Gábor: Gráfelméleti feladatok, Typotex, Budapest, 2006. 

    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
    Kontakt óra42
    Félévközi készülés órákra14
    Felkészülés zárthelyire30
    Házi feladat elkészítése14
    Kijelölt írásos tananyag elsajátítása
    Vizsgafelkészülés50
    Összesen150
    15. A tantárgy tematikáját kidolgozta Dr. Recski András prof. emeritus, SZIT