Co je to programování
Stojím si za tvrzením, že programování je matematika a tak mne mírně
znervózňují zoufalci toužící \"naučit se Céčko\" ve snaze státi se programátorem
(tj. bytostí konající programování). Před jistou dobou jsem řešil jistý problém
(určení zda je daná konfigurace hracího pole piškvorek ve stavu výhry jednoho z
hráčů) a nalezl jsem řešení, které mne neuspokojilo (lineární prohledávání
prostoru) a tak jsem problém opustil. Teď jsem ovšem nalezl algoritmus, který
toto řeší velmi hezky (resp. nalezl jsem podobný algoritmus, který jsem
zobecnil - je ovšem velmi pravděpodobné, až jisté, že nejsem autorem, ale
pouze znovuobjevitelem) - tyto algoritmy zde popíšu. Tímto se budu snažit
dosáhnout dvou věcí. Jednak presentaci samotných algoritmů, jednak podpořit mé
tvrzení o jednotě matematiky a programování.
Poznámka: 1) v textu budu používat české názvy, přestože jsem proti jejich
používání (trénuju do školy - Honzík je kapku demagog) 2) matematické symboly
jsou pouze zhruba (its ascii, man
Rabin-karpův algoritmus
Tito pánové objevili algoritmus na rozpoznání podřetězce v řetězci (pattern
matching). Algoritmus je popsán následovně:
předpokládejme, že máme abecedu A = [0,1...9] (pozn. protože lze nalézt bijekci
mezi formálním symbolem, zde číslem, a libovolným objektem, neubírá tento
předpoklad na obecnosti) nad kterou definujeme vzor P[1..m] jemuž odpovídá
hodnota p a text T[1..n]. Nechme t být hodnotou řetezce T[s+1..s+m] o délce m.
Je zjevné, že t=p právě tehdy (a jedině tehdy!) když T[s+1..s+m]=P[1..m].
Pokud jsme schopni vypočítat p v čase O(m) a všechna t v čase O(n) pak jsme
schopni nalézt všechna s pro která platí, že podřetězec odpovídá vzoru.
Hodnota p se dá spočítat v čase O(m) použitím Hornerova pravidla takto:
p = P[m]+10(P[m-1]+10(P[m-2]+...+10(P[2]+10P[1])...))
obdobně lze spočítat hodnotu t0 pro T[1..m] v čase O(m), následující hodnoty
t1, t2 .. t(n-m) lze spočítat v čase O(n-m). Stačí si uvědomit, že t(s+1) lze
spočítat z ts takto:
t(s+1) = 10(ts-10exp(m-1)*T[s+1])+T[s+m+1], tj. v konstatním čase.
Jde o algoritmus velmi elegantní, rychlý a jednoduchý.
Můj problém a jeho řešení
Mé odpanění v oblasti funkcionálního programování proběhlo na hracím motoru hry
piškvorky. V závěrečné fázi jsem narazil na problém jak identifikovat výhru v
dané konfiguraci hracího pole. Napadlo mne to prohledávat do hloubky
(koneckonců šlo o odpanění, ne), ale toto řešení jsem jaksi nedomyslel a tak
jsem ho posléze zavrhl. Na problém jsem pozapomněl až do doby, kdy jsem se
dozvědel o výše presentovaném Rabin-karpově algoritmu. Hned mi bylo jasné, že
to půjde použít i pro můj problém. Vymyslel jsem tedy následující:
mějme abecedu A = [0,1,2] nad kterou definujeme vzor P[1..m,1..n] s hodnotou p
a text T[1..k,1..l]. Hodnota t bude kvalifikovat řetězec T[r+1..r+m,s+1..s+n].
Opět je zjevné, že t=p pouze tehdy, když si budou příslušné řetězce odpovídat.
Jsme schopni spočítat p v čase O(m*n) a t00 (pro T[1..m,1..n]) také v čase
O(m*n). Analogicky další t dostaneme v čase O(k*l-m*n) použitím:
t(r+1,s) = 3(trs-3exp(m-1)*(suma pro i = s do s+n z T[r+1,i]))+
(suma pro i = s do s+n z T[r+m+1,i]) a obdobně
t(r,s+1) = 3(trs-3exp(n-1)*(suma pro i = r do r+m z T[i,s+1]))+
(suma pro i = r do r+m z T[i,s+n+1]
omlouvam se za hrozné grafické vyjádření, ale jsem líný udělat to jako obrázek
a tak trpte...
Algoritmus tuším bude fungovat (samozřejmě jsem se neobtěžoval to zkoušet -
jsem teoretik) a snad i docela dobře.
Zajímavost
V hlavě mám řešení, které jsem ještě neformalizoval, nicméně nástin mám a
neodolám ho zde nepresentovat (z nechutně zištných důvodů).
Každému políčku hrací plochy přiřadíme dle jeho polohy komplexní číslo (v
podstatě souřadnice). Dle stavu políčka (prázdné, křížek, kolečko) toto
komplexní číslo vynásobíme koeficientem: 1 pro křížek, -1 pro kolečko a 0 pro
prázdné. Při (určitém) kolapsu z dvourozměrné matice na jednorozměrné pole nám
tedy vznikne jistá komplexní funkce jedné proměnné. Z této funkce se snad dá
nějak vyextrahovat pomocí nějaké transformace informaci o obsahu vzorku. Chtěl
bych tedy požádat ať ten, kdo o tomhle něco ví nebo ho něco napadlo ať se mi
ozve.
Závěr
Nejsem moc inteligentní a tak to těžko posoudím, ale odhadl bych, že většina z
vás by nic jako je Rabin-karpův algoritmus nevymyslela. Tj. nevymyslel by ani
algoritmy z něj odvozené (což je neskonale jednodušší). Další věc je, jak jste
si možná všimli, že jsem nepoužil žádný programovací jazyk a řešení je vlastně
hotové (převod z takto formalizovaného zápisu do strojově vykonatelné podoby je
věc mechanická). Tímto tedy apeluji na vás, človíčky utrácející velké peníze za
knihy typu \"Mistrovství v něčem\" atd., zanechte toho - o tom programování není.
Programování je proces sestávající se z identifikace problému, identifikaci
řešení a jeho následné formalizaci. Není to o Céčku nebo Linuxu...
neologism
P.S. ocením když mne informujete o cizích slovech, které jsem v tomto článku
použil a nevšiml si jich.. díki!neologism
