BSc Matematika Alapszak
Tantárgyleírás
2013.
Tantárgyleírás
2013.
Számítástudomány
Óraszám ea/gy |
Kredit ea/gy |
Számonkérés | Szakirány | Tárgykód ea/gy |
Ajánlott félév |
Státusz |
---|---|---|---|---|---|---|
2 + 2 | 2 + 3 | kollokvium + gyak. jegy |
matematikus | mm1c1cs6m mm1c2cs6m |
6 | kötelező |
alk. mat. | mm1c1cs6a mm1c2cs6a |
6 | kötelező |
Tantárgyfelelős
Erős | Gyenge | előfeltételek | |
---|---|---|---|
Gyakorlat | |||
Erős:
Algebra1E
(mm1c1al1)
| |||
Erős:
Véges matematika2E
(mm1c1vm2)
| |||
Erős:
| |||
Előadás | |||
Gyenge:
a gyakorlat
|
Megjegyzések
- Pótlási lehetőség: A félév végén, indokolt esetben, a gyakorlatvezető döntése alapján egy javító zárthelyi dolgozat írására van lehetőség.
A tematikát kidolgozta:
Szükséges előismeretek
Lineáris algebra, elemi számelmélet, elemi gráfelmélet
A tantárgy célkitűzése
A tárgy célja a számításelmélet modern alapjainak felépítése
Irodalom
- Lovász László: Algoritmusok bonyolultsága. Jegyzet.
Tematika
- Alapvető rendezési, kiválasztási és gráf-algoritmusok. Dinamikus programozás.
- A számítógépek egy absztrakt modellje: A Turing-gép. Példák Turing-gépre. Church tézis. A palindrómák, ezeket elfogadó 1 és 2 szalagos Turing-gép. Az univerzális Turing gép definíciója és létezése.
- k-szalagos Turing gép szimulálható 1 szalagossal. Rekurzív és rekurzíve felsorolható nyelvek. Majdnem minden nyelv nem-rekurziv, és még csak nem is rekurzíve felsorolható. A rekurziv - és rekurzíve felsorolható nyelvek alapvető tulajdonságai. A megállási probléma. Idő-bonyolultsági osztályok. A P osztály. Artúr-Merlin játék. Az NP-osztály. co-NP. Példák NP-beli nyelvekre.
- A PRIM nyelv, Polinomiális redukció, NP-teljesség. Boole-formulák. A SAT nyelv.
- Cook tétele: a SAT NP-teljes. További NP-teljes nyelvek.