Október - 2019
H K S C P S V
  01 02 03 04 05 06
07 08 09 10 11 12 13
14 15 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31  

Tantárgyi program 2019/2020


I. Alapadatok

A tantárgy kódja:2SZ31NAK01M
A tantárgy megnevezése (magyarul):Számítástudomány közgazdasági alkalmazásokkal
A tantárgy neve (angolul):Computer Science with Applications to Economics
A tanóra száma
(Előadás + szeminárium /gyakorlat/egyéb):
2+2
Kreditérték:5
Becsült hallgatói munkaóra: (kpx30)150
A tantárgy meghirdetésének gyakorisága:őszi félév, évente
Az oktatás nyelve:magyar
Előtanulmányi kötelezettségek:nincsen
A tantárgy típusa:
Tantárgyfelelős tanszék:Matematika Tanszék
A tantárgyfelelős neve:Dr. Tasnádi Attila

II. A tantárgy célja (a fenntarthatóság szempontjai)

A tantárgy célja:
A számítógép matematikai modelljének megismerése. Algoritmikusan eldönthetetlen problémákkal való szembesül. Algoritmikusan nehéz problémák felismerése. A számítástudomány és a közgazdasági mechanizmustervezés határterületének elsajátítása.

A fenntarthatóság szempontjai:
N


IV. A tantárgy tervezett tanulási eredményei (fejlesztendő szakmai kompetenciák)

Tudás:
A hallgatók ismerjék meg a számítástudomány magasabb szintű minőségi eredményeit, valamint a hálózatok számítástudományi és közgazdaságtani határterületét. Ehhez szükséges a BSc képzésben már röviden, elsősorban példákon keresztül szemléltetett kiszámíthatóság- és bonyolultságelmélet alaposabb tárgyalása. Egy rövid bevezetést adunk a matematikai logikába. Tárgyaljuk az internet és az internetes kereskedelem által felvetett bonyolultságelméleti és közgazdasági mechanizmustervezési problémákat (szolgáltatók közötti költségfelosztás, kombinatorikus aukciók stb.).

Tananyag leírása:
1. A Turing-gép és ekvivalens definíciói. A Turing-gép "programozhatóságáról". Az egy és k≥2 szalagos Turing-gép közötti viszony.
2. Rekurzív és rekurzíve felsorolható nyelvek, illetve rekurzív és parciálisan rekurzív függvények. Az univerzális Turing-gép és a megállási probléma. Néhány további algoritmikusan eldönthetetlen probléma
3. A RAM-gép és a Turing-gép ekvivalenciája. Kolmogorov-bonyolultság és alkalmazáasai.
4. Az itéletkalkulus, kielégíthetőségük és érvényesség, Boole-függvények és Boole-hálózatok.
5. Az elsőrendű predikátumkalkulus szintaxisa, a modell, az axiómák, a bizonyítás. A Gödel-teljességi tétel.
6. A kompaktsági tétel, az egész számok axiomatizálása és Gödel inkomplettségi tétele.
7. Nem determinisztikus Turing-gép, NP nyelvosztály, NP-beli nyelvek, a Karp-redukció és az NP-teljesség fogalma.
8. A SAT-nyelv, Cook–Levin-tétel, további NP-teljes problémák.
9. NP-teljes problémák kezelése. Példák közelítő- és véletlen algoritmusokra.
10. A közgazdasági mechanizmustervezés alapfogalmai és alapvető eredményei. A Vickrey-Clarke-Grooves-féle mechanizmus.
11. Néhány egyszerű algoritmikus mechanizmustervezési probléma. Az anarchia ára. Braess paradoxona.
12. Kombinatorikus aukciók és alkalmazásaik. A győztes meghatározási probléma.


Képesség:
Algoritmikusan nehéz problémák felismerése
Algoritmikusan nehéz problémák megoldása kis méretű problémákra, közelítéssel, véletlen algoritmusokkal és lágy számítási módszerekkel
Mechanizmustervezés alkalmazása


Attitűd:
Matematikai érettség
Formalizálás iránti igény


Szakspecifikus tanulási eredmények (opcionális)

Szak/képzés megnevezése:


Tudás:


Képesség:


Attitűd: