Eötvös Loránd Tudományegyetem

Természettudományi Kar

Matematika Alapszak

Kötelező tantárgy

Tantárgy Adatlap

és tantárgykövetelmények

2005.

Tantárgycím: Számítástudomány

2.

Tantárgy kódja

félév

Követelmény

Kredit

Nyelv

Modul/
szakirány

 

 

6

kollokvium + gyakorlati jegy

3

magyar

mat.

 

3. A tantárgyfelelős személy és tanszék:

Grolmusz Vince, Számítógéptudományi  Tanszék, Matematikai Intézet.

 

 

4. A tantárgy előadója:

Név:

Beosztás:

Tanszék:

Gács András

egyetemi docens

Számítógéptudományi Tanszék

Király Zoltán

egyetemi docens

Számítógéptudományi Tanszék

Grolmusz Vince

egyetemi docens

Számítógéptudományi Tanszék

 

5. A tantárgy az alábbi témakörök ismeretére épít:

Lineáris algebra, elemi számelmélet, elemi gráfelmélet

6. Kötelező/ajánlott előtanulmányi rend:

Algebra 1 és Véges matematika tárgyak sikeres teljesítése.

Kollokvium csak a gyakorlat sikeres teljesítése esetén tehető.

 

7. A tantárgy célkitűzése:

A tárgy célja a számításelmélet modern alapjainak felépítése

8. A tantárgy részletes tematikája:

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.

 

9. A tantárgy oktatásának módja:

Heti 2 óra előadás, és az előadás anyagát követő, heti 1 óra feladatmegoldó gyakorlat kiscsoportos bontásban.

 

10. Követelmények

a.       A szorgalmi időszakban: Az előadás anyagának megértése. Az előadások látogatása nem kötelező, de ajánlatos.

          A gyakorlatokon a részvétel kötelező. A gyakorlati jegy megszerzéséhez két zárthelyi dolgozatot kell írni, valamint meg kell oldani a házi feladatokat.

b.       A vizsgaidőszakban: Sikeresen teljesíteni kell a kollokviumot. Az elégtelen gyakorlati jegy javítása gyakorlati jegy utóvizsgával a vizsgaidőszak során egy ízben megkísérelhető.

 

11. Pótlási lehetőségek

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.

 

12. Konzultációs lehetőségek

Rendszeres konzultációs lehetőség a hallgatók igényei szerint, az előadóval és a gyakorlatvezetővel.

 

13. Jegyzet, tankönyv, felhasználható irodalom:

 

Cormen, Leiserson, Rivest: Új algoritmusok

Lovász László: Bonyolultságelmélet, jegyzet

 

14. A tantárgy elvégzéséhez szükséges tanulmányi munka:

Az előadási anyag megértése és a vizsgára felkészülés, továbbá a házi feladatok elkészítése és a zárthelyik megírása.

 

15. A tantárgy tematikáját kidolgozta:

Név:

Beosztás:

Tanszék, Int.:

Grolmusz Vince

egyetemi docens

Számítógéptudományi Tanszék, Matematikai Intézet