BSc Matematika Alapszak
Tantárgyleírás
2017.
Tantárgyleírás
2017.
Számítástudomány
- Óraszám (ea+gy): 2 + 2
- Specializáció: matematikus
- Kredit (ea+gy): 3 + 2
- Számonkérés: kollokvium + gyak. jegy
- Tárgykód (ea, gy): szmtud1u0_m17ex, szmtud1u0_m17gx
- Ajánlott félév: 6
- Státusz: kötelező
- Specializáció: alk. mat.
- Kredit (ea+gy): 3 + 2
- Számonkérés: kollokvium + gyak. jegy
- Tárgykód (ea, gy): szmtud1u0_m17ex, szmtud1u0_m17gx
- Ajánlott félév: 6
- Státusz: kötelező
Óraszám
ea(+k) + gy(+k) |
Kredit
ea + gy |
Számonkérés | Specializáció | Tárgykód
ea/gy |
Ajánlott
félév |
Státusz |
---|---|---|---|---|---|---|
2 + 2 | 3 + 2 | kollokvium + gyak. jegy |
matematikus | szmtud1u0_m17ex szmtud1u0_m17gx |
6 | kötelező |
3 + 2 | kollokvium + gyak. jegy |
alk. mat. | szmtud1u0_m17ex szmtud1u0_m17gx |
6 | kötelező |
Tantárgyfelelős
Erős | Gyenge | előfeltételek |
---|---|---|
Gyakorlat | ||
Erős:
Algebra1E
(algebr1*0_m17ea)
| ||
Erős:
Véges matematika2E
(vegmat2*0_m17ea)
| ||
Erős:
Operációkutatás1E-ma
(opkut_1u0_m17ex)
| ||
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.