460-4116/01 – Teorie her (TEH)

Garantující katedraKatedra informatikyKredity4
Garant předmětudoc. Ing. Zdeněk Sawa, Ph.D.Garant verze předmětudoc. Ing. Zdeněk Sawa, Ph.D.
Úroveň studiapregraduální nebo graduálníPovinnostpovinně volitelný
Ročník2Semestrzimní
Jazyk výukyčeština
Rok zavedení2015/2016Rok zrušení
Určeno pro fakultyFEIUrčeno pro typy studianavazující magisterské, magisterské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
SAW75 doc. Ing. Zdeněk Sawa, Ph.D.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+2
kombinovaná Zápočet a zkouška 10+0

Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi

Porozumět základním pojmům a metodám matematické teorie her. Naučit se používat tyto metody při řešení jednoduchých konfliktních a rozhodovacích situací standardního typu. Osvojení si hlavních idejí teorie her a schopnost jejich intuitivního využívání ve složitých rozhodovacích situacích (konfliktních, s náhodnými vlivy, s neúplnou informací,...). Schopnost formalizovat rozhodovací situace a procesy pomocí standardních modelů teorie her. Schopnost řešit standardní úlohy teorie her (znalost příslušných algoritmů).

Vyučovací metody

Přednášky
Cvičení (v učebně)

Anotace

Předmět seznamuje studenty se základy matematické teorie her. Studenti se dozví o různých typech her a o tom, jak je možné různé typy her matematicky formalizovat a algoritmicky řešit. Nejprve jsou diskutovány kombinatorické hry, tj. hry dvou hráčů s dokonalou informací. Dále jsou pak studovány hry ve standardním a v rozvinutém tvaru, přičemž nejprve se zaměřujeme na hry dvou hráčů s nulovým součtem (jejichž řešení se dá v případě konečných her převést na úlohu lineárního programování) a dále pak na hry s obecným součtem. U her s obecným součtem jsou pak zvlášť rozebírány nekooperativní hry, u kterých se zkoumá existence Nashových rovnovážných bodů, a dále pak kooperativní hry, u kterých navíc rozlišujeme varianty s přenosnou a nepřenosnou výhrou. Jak u her s nulovým, tak u her s obecným součtem jsou studovány varianty her rozšířené o náhodné tahy a nedokonalou informaci.

Povinná literatura:

[1] Thomas S. Ferguson – Game Theory — výukové texty k předmětu Game Theory vyučovaném na UCLA (University of California, Los Angeles), http://www.math.ucla.edu/~tom/math167.html

Doporučená literatura:

[2] Kevin Leyton-Brown, Yoav Shoham: Essentials of Game Theory: A Concise, Multidisciplinary Introduction, Morgan and Claypool Publishers, 2008. [3] Algorithmic Game Theory, edited by Noam Nisan, Tim Roughgarden, Eva Tardos and Vijay V. Vazirani, Cambridge University Press, 2007. [4] Martin J. Osborne, Ariel Rubinstein: A Course in Game Theory, MIT Press, 1994. [5] Drew Fudenberg, Jean Tirole: Game Theory, MIT Press, 1991. [6] Robert Gibbons: A Primer in Game Theory, Financial Times Prentice Hall, 1992.

Forma způsobu ověření studijních výsledků a další požadavky na studenta

Průběžná kontrola studia: Kontrolní písemka v polovině semestru. Podmínky udělení zápočtu: Kontrolní písemka v polovině semestru bude hodnocena maximálně 30 body, pro získání zápočtu je třeba získat z této písemky minimálně 10 bodů. Zkouška: Pro absolvování zkoušky je třeba ze 70 bodů získat alespoň 25.

E-learning

Další požadavky na studenta

Další požadavky na studenta nejsou kladeny.

Prerekvizity

Předmět nemá žádné prerekvizity.

Korekvizity

Předmět nemá žádné korekvizity.

Osnova předmětu

Přednášky: 1. Úvod. 2. Kombinatorické hry, grafové hry. 3. Hra NIM, Sprague-Grundyova funkce. 4. Sumy her a jejich řešení pomocí Sprague-Grundyovy funkce. 5. Hry dvou hráčů s nulovým součtem ve strategickém tvaru, maticové hry. 6. Dominované strategie, sedlový bod, smíšené strategie. 7. Řešení maticových her ve smíšených strategiích převodem na lineární programování. 8. Lineární programování (dokončení). 9. Hry dvou hráčů s nulovým součtem v rozvinutém tvaru, Kuhnův strom, náhodné tahy, hry s nedokonalou informací. 10. Hry dvou hráčů s obecným součtem ve strategickém tvaru, bimaticové hry, Nashovy rovnovážné body. 11. Kooperativní hry, hry s přenosnou výhrou. 12. Hry v koaličním tvaru. Cvičení (u tabule): 1. Jednoduché odebírací hry. 2. Kombinatorické hry, grafové hry. 3. Hra NIM, Sprague-Grundyova funkce. 4. Sumy her a jejich řešení pomocí Sprague-Grundyovy funkce. 5. Hry dvou hráčů s nulovým součtem ve strategickém tvaru, maticové hry. 6. Dominované strategie, sedlový bod, smíšené strategie. 7. Řešení maticových her ve smíšených strategiích převodem na lineární programování. 8. Lineární programování (dokončení). 9. Hry dvou hráčů s nulovým součtem v rozvinutém tvaru, Kuhnův strom, náhodné tahy, hry s nedokonalou informací. 10. Hry dvou hráčů s obecným součtem ve strategickém tvaru, bimaticové hry, Nashovy rovnovážné body. 11. Kooperativní hry, hry s přenosnou výhrou. 12. Hry v koaličním tvaru. Obsah cvičení podle osnovy přednášek.

Podmínky absolvování předmětu

Prezenční forma (platnost od: 2015/2016 zimní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodů
Zápočet a zkouška Zápočet a zkouška 100 (100) 51
        Zápočet Zápočet 30 (30) 15
                Zápočtová písemka Písemka 30  15
        Zkouška Zkouška 70 (70) 30
                Zkoušková písemka Písemná zkouška 70  30
Rozsah povinné účasti: 80% účast na cvičeních

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2021/2022 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinně volitelný stu. plán
2021/2022 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinně volitelný stu. plán
2020/2021 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinně volitelný stu. plán
2020/2021 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinně volitelný stu. plán
2019/2020 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinně volitelný stu. plán
2019/2020 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinně volitelný stu. plán
2018/2019 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinně volitelný stu. plán
2018/2019 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinně volitelný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinně volitelný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinně volitelný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinně volitelný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinně volitelný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinně volitelný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinně volitelný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku