Kvadratické rovnice na slovech

Titulní stránka

Miroslav Olšák, srpen 2013

Jako každý student snažící se projít studiem bez zbytečných zdržování jsem vypracoval svou bakalářskou práci. Práce se týká kvadratických rovnice na slovech a zkoumá, jak moc mohou být nejmenší řešení delší oproti původní rovnici. Více může práci přiblížit:

Abstrakt: Práce se zabývá řešitelnosti kvadratických rovnic na slovech. V upravené podobě opakuje výsledky Robsona a Diekerta a navazuje na otázku jednoduše exponenciální meze na velikost nejkratšího řešení kvadratických rovnic. Kladná odpověď na tuto otázku by znamenala, že je řešitelnost kvadratických rovnic na slovech NP úplný problém. Hypotézu o jednoduše exponenciální mezi se dokázat nepodařilo, ale podařilo se například zúžit třídu rovnic, kterým je třeba se věnovat, a dále ukázat, že se stačí zabývat mezí pro nejkratší proměnnou. V závěru práce je ukázáno chování jisté konkrétní rovnice a dále vysvětlena dualita dvou přístupů ke kvadratickým soustavám.

Práce je ve formátu PDF ke stažení ZDE.

TeXové zdrojáky (včetně maker CUstyle a OPmac) jsou ke stažení ZDE.

Pokud máte k práci dotazy, můžete mě kontaktovat e-mailem (mirek zavináč olsak tečka net) nebo přes jabber (valsorim zavináč jabbim tečka cz).

Krom lehce "otravného" psaní matematického textu jsem si v průběhu psaní bakalářky s kvadratickými rovnicemi "hrál". K tomuto účelu jsem si napsal jeden backtrack eq_solver, který řeší rozumně malé balancované 2-soustavy o jedné rovnici. Dalším programem je program slova, který pomocí knihovny ncurses zobrazuje procházku po řešení 2D rovnice.

Diplomová práce: Součiny Fréchetovských prostorů

Program eq_solver Program slova