Temata diplomovych a doktorskych praci vypsana J. Matouskem v r. 2001
Perfektni dlazdeni simplexu
Pravouhly rovnostranny trojuhelnik se da rozkrojit na dva mensi shodne
pravouhle rovnostranne trojuhelniky. Jak je tomu
s krajenim simplexu ve vyssi dimenzi? Chteli bychom nejaky d-dimenzionalni
simplex S rozkrajet na k shodnych mensich simplexu, z nichz kazdy je
zmensenou kopii S. Ptame se, pro jaka d a k je to mozne. To je asi
obecne beznadejne tezka otazka, ale neni tezke zacit studovat nejake
specialni pripady. Pro zacatek je treba tez prozkoumat existujici
literaturu s pribuznymi vysledky. Zminena otazka, a jeji jiste zobecneni,
zajimave souvisi s ochranou internetu proti jistemu typu utoku.
Kombinatoricka diskrepance: vypocetni experimenty
Necht S_1,...S_m jsou podmnoziny konecne mnoziny X. Obarvime-li kazdy bod
X cervene nebo modre, meri diskrepance tohoto obarveni maximalni "nevyvazenost",
coz je maximum z absolutnich hodnot vyrazu (pocet cervenych bodu v S_i
- pocet modrych bodu v S_i) pres vsechna i. Pro dana S_i hledame co nejlepsi
obarveni. Cilem diplomove prace je navrhnout a implementovat metody pro
hledani zajimavych mnozinovych systemu z hlediska diskrepance, specialne
pro urceni diskrepance malych systemu (krome probrani vsech obarveni prichazeji
v uvahu metody celociselneho programovani ci branch-and-bound). V pripade
zajmu diplomanta lze zkouset resit i nektere z cetnych otevrenych problemu
v teorii kombinatoricke diskrepance.
Geometricka diskrepance
Teorie diskrepance pojednava o "co nejrovnomernejsim" rozlozeni n bodu
v dane oblasti, napriklad v jednotkovem ctverci v rovine. Zadavatel v teto
oblasti pracuje (a napsal o ni tez knihu).
Pro diplomovou praci by prichazely v uvahu implementace a testovani
algoritmu pro generovani rovnomerne rozlozenych mnozin. Pro doktorskou
praci se nabizi rada teoretickych otazek ruzne obtiznosti.
Viditelnost ve specialnich mnohouhelnicich
Bud X nejaky, ne nutne konvexni, mnohouhelnik v rovine. Na bodech X jako
vrcholech muzeme definovat (nekonecny) graf "neviditelnosti: body
x a yjsou spojeny hranou prave kdyz usecka xy nelezi cela v X. Zadavatel
spolu s Pavlem Valtrem studovali vselijake vlastnosti tohoto grafu. Cilem
teto teoreticky zamerene diplomove prace je studium nekterych otevrenych
otazek: specialne v pripade, kdy X je tzv. "plot", t.j. zdola je ohranicen
jedinou useckou, ze stran svislymi useckami, a shora grafem po castech
linearni funkce.
Vnorovani konecnych metrickych prostoru
Mejme nejaky konecny metricky prostor; to znamena, mame nejaky soubor objektu
a pro kazde dva objekty je dana jejich vzdalenost (coz muze byt napriklad
nejaka mira nepodobnosti, treba mezi brouky, retezci DNA, a podobne). Zajima
nas priblizna reprezentace takoveho metrickeho prostoru napriklad v rovine
(nebo v jinem zajimavem prostoru). To znamena, kazdemu objektu bude odpovidat
bod v rovine, a euklidovske vzdalenosti techto bodu by mely byt blizke
zadanym vzdalenostem objektu. Takovou reprezentaci zpravidla neni mozne
udelat presne, a v takovem pripade nas zajima minimalni mozne "zkresleni"
pro dany konecny metricky prostor. Siroke (teoreticke) tema pro doktorskou
praci , jednodussi otazky lze resit i v praci diplomove.
Simplicialni rozklady
Danou n-bodovou mnozinu P v rovine chceme rozlozit na r casti, kazda velikosti
priblizne n/r, a kazdou z casti umistit do nejakeho trojuhelnika, a to
takovym zpusobem, aby libovolna primka protinala pokud mozno malo techto
trojuhelniku. Asymtoticky je znam optimalni vysledek, nicmene nektere pribuzne
otazky zustavaji nedoreseny, a take by bylo zajimave zjistit co nejlepsi
hodnoty konstanty umernosti ve znamych odhadech. Vhodne jako stredne narocna,
teoreticky zamerena diplomova prace.