Grafy, hry, optimalizace, algoritmy, teoretická informatika (G²OAT)

Ve skupině G²OAT se zabýváme diskrétní optimalizací. Zkoumáme složitost grafových a jiných problémů, herních mechanismů a kombinatorických her. Navrhujeme efektivní algoritmy. Využíváme prostředků klasické teorie složitosti, parametrizované složitosti, teorie grafů nebo například celočíselné lineární programování.

Čemu se skupina věnuje?

Navrhujeme přesné polynomiální, parametrizované a mírně exponenciální algoritmy, aproximační algoritmy či kombinatorické hry, jejichž ekvilibria představují efektivní řešení daného problému. Ukazujeme dolní meze pro časovou složitost algoritmu řešícího daný problém. Mezi výsledky naší výzkumné skupiny patří i čistě kombinatorické, tedy popisující vlastnosti objektů či vztahy mezi nimi, například z oblasti Ramseyovské teorie.

Problémy, kterými se zabýváme, jsou veškeré diskrétně modelované optimalizační úlohy. Jde o širokou škálu problémů – od grafových přes rozvrhovací či problémy z oblasti Social Choice až po strategie pro kombinatorické hry. V řadě algoritmů používáme výsledky týkající se celočíselného lineárního programování.

Činnost skupiny se dotýká těchto témat

Kontaktní osoba

RNDr. Ondřej Suchý, Ph.D.

Kde nás najdete?

Výzkumná skupina Grafy, hry, optimalizace, algoritmy, teoretická informatika
Katedra teoretické informatiky
Fakulta informačních technologií
České vysoké učení technické v Praze

Budova A, 12. patro
Thákurova 7
Praha 6 – Dejvice
160 00

Za obsah stránky zodpovídá: doc. Ing. Štěpán Starosta, Ph.D.