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.