BME VIK - Véges matematika villamosmérnököknek

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 óra	42
Félévközi készülés órákra	14
Felkészülés zárthelyire	30
Házi feladat elkészítése	14
Kijelölt írásos tananyag elsajátítása
Vizsgafelkészülés	50
Összesen	150

15. A tantárgy tematikáját kidolgozta Dr. Recski András prof. emeritus, SZIT