Aplikácie teórie grafov a teórie hier v rozhodovacích problémoch

	Trenčianska Univerzita Alexandra Dubčeka v Trenčíne Fakulta Mechatroniky
	Aplikácie teórie grafov a teórie hier v rozhodovacích problémoch zadanie práce Semestrálna práca

Autor:	Ľubomír Milko
Pedagogický vedúci:	Ing. Juraj Ďuďák
Študijný odbor:	Mechatronika
Akademický rok	2009/2010

Abstrakt Táto práca obsahuje charakteristiku teórie hier a teórie grafov a následne popisuje použitie princípov z tejto oblasti v základných druhoch rozhodovacích problémov. Vo štvrtej kapitole sa podrobnejšie opisujú princípy analýzy a riešenia hier, ktoré môžu byť reprezentované hernými stromami. Posledná časť práce je venovaná implementácii rozobraných princípov voľby vhodného ťahu v doskovej hre dáma.

Abstract tu bude anstrakt v AJ

Úvod Problémy vyžadujúce správne rozhodovanie s ohľadom na následky zvoleného rozhodnutia nás sprevádzajú v takmer všetkých oblastiach ľudskej činnosti od hrania rôznych spoločenských hier až po pokročilé riadenie cestnej siete, správne ekonomické rozhodnutia alebo stratégiu vojenských konfliktov. Postupné snahy o matematickú interpretáciu a riešenie týchto problémy voľby správneho rozhodnutia vyústili v samostatné odvetvie aplikovanej matematiky s názvom teória hier. V tejto teórii sa rozhodovacie problémy znázorňujú ako množina stratégií, ktoré možno prijať a množina následkov, ktoré vzniknú v dôsledku zvolenej stratégie. Následky sú často číselnou interpretáciou daného stavu. Na praktickú interpretáciu tohto súboru množín sa využíva teória grafov. Tieto dve teórie možno použiť na vyriešenie mnohých praktických rozhodovacích problémov. Zaujímavým praktickým a názorným príkladom aplikácie môže byť aj hľadanie optimálneho ťahu v doskových hrách akou je napríklad dáma. Súčasťou tejto práce je teda aj podrobnejšia ukážka využitia teórie hier a teórie grafov v tomto type hier. Cieľom tejto práce potom je:

• charakteristika teórie hier a teórie grafov,
• popis interpretácie základných rozhodovacích problémov pomocou týchto teórií,
• praktické použitie popísaných teoretických princípov pri voľbe vhodného ťahu v doskovej hre dáma.

Zoznam použitých skratiek a symbolov

hra

strategická interakcia medzi jednotlivcami

hráč

účastník hry

minimax

algoritmus, ktorý prechádzaním herného stromu vyberá optimálny ťah v hre

pozícia

aktuálny stav hry

strom

typ grafu, využívaný na znázornenie hier v rozšírenej forme

ťah 

zvolená a uskutočnená stratégia hráča v danom bode hry