BSc Matematika Alapszak
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ő
Erős Gyenge előfeltételek
Gyakorlat
Erős:
Algebra1E (mm1c1al1)
Erős:
Véges matematika2E (mm1c1vm2)
Erős:
Operációkutatás1E-m (mm1c1op3m) vagy
Operációkutatás1E-a (mm1c1op3a)
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.