# Zkouška 28.6.2010

<{ForumPost(poster="mrwep", timestamp=2010-06-28 16:16:30)}>
Dneska šlo o písmenka.  
  
Na vstupu jsme dostali slovo $\leq 100$ znaků dlouhé složené z písmen anglické abecedy (26), a dále pak seznam substitučních pravidel, kterých je také maximálně 100. Substituce jsou buď 1 písmeno za 1 písmeno (a->b) nebo 1 písmenko za 2 (a->bc).  
Výstupem má být množina písmen, ze kterých jde dané slovo vystavět. Paměti máme 1MB.  
Trochu vysvětlení: ve výstupní množině jsou ta písmena, z kterých postupnými substitucemi může vzniknout slovo na vstupu.  
Příklad:  
abac  
a->b  
a->c  
a->ab  
c->ac  
Výstup: a, c  
  
Osobně nevím, jestli jsem volil správný způsob řešení, tak raději nebudu kazit.  
A když by někdo nastínil, jak by se to mělo řešit, bylo by to hezké.
<{/ForumPost}>

<{ForumPost(poster="Martina", timestamp=2010-06-29 12:10:39)}>
Úloha šla řešit dynamickým programováním. Nejdřív je dobré si vygenerovat všechna substituční pravidla, která mění 1 písmeno za 2 (a která lze složit z těch zadaných). No a pak si všimneme, že na začátku máme jedno písmeno, to se nám změní na dvě a ta dvě si pak žijí nezávislý život a z každého vystavíme jednu část výsledného slova. Jenže nevíme, kde ten řez mezi nimi je...  
  
Tolik komentář, teď algoritmus: ve výsledném slově si určíme pro každou dvojici po sobě následujících písmen, z jakých jednotlivých písmen ji můžeme vytvořit. Pak totéž uděláme pro trojice, čtveřice.... Jak? Úsek délky *n* můžeme (*n-1*) způsoby rozdělit na dva kratší a pro ty generující písmena známe a použijeme odvozená pravidla zmiňovaná v úvodu.  
  
Stačí na to 300kB a při nadsazených odhadech vyjde asi 10^12 instrukcí, což při taktovací frekvenci 1GHz odpovídá asi 15 minutám.  
  
Martina
<{/ForumPost}>

<{ForumPost(poster="mrwep", timestamp=2010-06-30 11:26:04)}>
A vřele doporučuji umět B-stromy, je to hrozně příjemná a jednoduchá otázka, a padá velice často. Dneska jsem koukal na papír kde měl poznámky k těm, co byli dnes předemnou, a snad každého se na ně ptal, a skoro všichni dostali za 4, tak se opravdu vyplatí je umět.
<{/ForumPost}>