Kvadratické rovnice na slovech
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.
