November - 2017
H K S C P S V
  01 02 03 04 05
06 07 08 09 10 11 12
13 14 15 16 17 18 19
21 22 23 24 25 26
27 28 29 30  

Tantárgy adatlap

Számítástudomány közgazdasági alkalmazásokkal

Tantárgy adatlap letöltése: Letöltés

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
A tantárgy meghirdetésének gyakorisága: őszi félév, évente
Az oktatás nyelve: magyar
Előtanulmányi kötelezettségek: 
A tantárgy típusa: kötelező
Tantárgyfelelős tanszék: Matematika Tanszék
A tantárgyfelelős neve: Dr. Tasnádi Attila

A tantárgy szakmai tartalma: A hallgatók ismerjék meg a számítástudomány magasabb színtű mínő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.).

Évközi tanulmányi követelmények: Három félévközi dolgozat (egyenként 20 pontosak), amelyek közül a legjobb két eredmény alapján a következőképpen adódik a félévközi jegy:
0-15 elégtelen, 16-21 elégséges, közepes 22-27, jó 28-34 és 35-40.
A szemináriumokon való részvétel kötelező.

Vizsgakövetelmény: Vizsgajegy.

Az értékelés módszere: A félévközi jegy (1/3) és a félévvégi szóbeli vizsgán szerzett jegy (2/3) súlyozott számtani átlaga, ha a szóbeli vizsga jegy legalább elégséges. Elégtelen félévközi, vagy elégtelen szóbeli vizsga esetén a vizsgajegy is elégtelen. Ismétlő vizsgán csak a szóbeli jegy javítható.

Tananyag leírása: 1. Ismétlések: az O és Θ jelölések, a formális nyelv. 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. A lineáris gyorsítási tétel. Rekurzív és rekurzíve fölsorolható 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. A monotonitás, a vétómentesség és Maskin tétele.
12. Néhány egyszerű algoritmikus mechanizmustervezési probléma. Az anarchia ára. Braess paradoxona.
13. Kombinatorikus aukciók és alkalmazásaik. A győztes meghatározási probléma.
14. A sávszélesség igazságos felosztása.

Órarendi beosztás: NEPTUN szerint.

Kompetencia leírása: 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.

Félévközi ellenőrzések: Három félévközi dolgozat.

A hallgató egyéni munkával megoldandó feladatai: Aktív órai részvétel, továbbá a félévközi dolgozatokra és a szóbeli vizsgára való felkészülés.

Szak neve: Gazdaságinformatikus MSc.

Irodalomjegyzék:
Kötelező irodalom:

  • Rónyai Lajos, Ivanyos Gábor, Szabó Réka (1999): Algoritmusok, Typotex.
  • Papadimitriou Christos H. (1999): Számítási bonyolultság, Novadat.

Ajánlott irodalom:

  • Ferenczi Miklós (2002): Matematikai logika, Műszaki Könyvkiadó.
Ajánlott irodalmak:
Ferenczi Miklós (2002): Matematikai logika, Műszaki Könyvkiadó.
Megtalálható a Központi Könyvtárban
Kötelező irodalmak:
Rónyai Lajos, Ivanyos Gábor, Szabó Réka (1999): Algoritmusok, Typotex.
Megtalálható a Központi Könyvtárban, 2005 Kiadás
Papadimitriou Christos H. (1999): Számítási bonyolultság, Novadat.
Megtalálható a Központi Könyvtárban

 
A tantárgy oktatói:

Bednay Dezső

Utolsó módosítás: 2017-09-10 15:41:29

Kurzusok

Kurzus kódTipusFélévOktatói
EElmélet2017/18/1Bednay Dezső
GGyakorlat2017/18/1Bednay Dezső


A "Tantárgyfelelős tanszék", a tantárgyfelelős neve a tantárgy oktatói és a kurzusinformációk automatikusan frissülnek a tanulmányi rendszerünk alapján.