Belépés címtáras azonosítással
magyar nyelvű adatlap
Grundlagen der theoretischen Informatik
A tantárgy angol neve: Elements of the Theory of Computing (In German)
Adatlap utolsó módosítása: 2006. július 1.
Tantárgy lejárati dátuma: 2015. január 31.
Villamosmérnöki Szak
Név:
Beosztás:
Tanszék, Int.:
Dr. Recski András
egy.tanár
Számítástudományi és Információelméleti Tanszék
1. és 2. féléves matematika.
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ó.
Matematika II, kredit
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.
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.
Heti 4 óra előadás az egész évfolyamnak, és heti 2 óra kiscsoportos gyakorlat, ezt kiegészíti egy rendszeres konzultáció.
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 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 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árhelyi írásával sem tudta megszerezni, az első két vizsgaalkalommal különeljárással megszerezheti.
b. A vizsgaidőszakban:
A vizsga írásbeli és szóbeli részből áll. Az írásbeli általában 8 db 10 pontos példából áll.
Sikeres teljesítéséhez legalább 32 pont kell. Akinek az írásbeli rész nem sikerült, az nem szóbelizhet. Akinek az írásbeli vizsgája sikerült, de a szóbeli vizsgán megbukik, annak csak a szóbeli vizsgát kell megismételnie. A vizsgajegyet az alábbi három részeredmény alapján adjuk: (1) vizsgaírásbeli, (2) vizsgaszóbeli, (3) évközi munka, amely a zárthelyik eredményét is tartalmazza.
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.
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)
egy.tanár, tansz. vez.
vima2555.doc