Borromeo gyűrűk
BSc Matematika Alapszak
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ő
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.