KSVI MFF UK Praha

Jin´ e programov´ an´ı Tom´aˇs Holan ? [email protected] KSVI MFF UK Praha

Abstrakt V prvn´ım roˇcn´ıku studia informatiky na MFF UK Praha vˇsichni studenti absolvuj´ı u ´vodn´ı kurs programov´ an´ı. V tomto kursu se sezn´ am´ı se z´ akladn´ımi pojmy, algoritmy, datov´ ymi strukturami, technikami a se zp˚ usobem, jak analyzovat u ´lohu shora. Posledn´ı pˇredn´ aˇska tohoto kursu potom b´ yv´ a vˇenov´ ana tomu, jak ˇreˇsit u ´lohy, kter´e jsou pro takov´ y zp˚ usob programov´ an´ı pˇr´ıliˇs tˇeˇzk´e. Tento text shrnuje obsah t´eto posledn´ı pˇredn´ aˇsky. Postupnˇe jsou pˇredkl´ ad´ any probl´emy, kter´e jsou pro obvykl´ y postup pˇr´ıliˇs sloˇzit´e a jsou demonstrov´ any alternativn´ı zp˚ usoby jejich ˇreˇsen´ı.

1

,,Klasick´ e” programov´ an´ı

Jako klasick´e programov´ an´ı ch´apeme takov´e zp˚ usoby programov´an´ı, jak´e jsou vyuˇcov´ any v z´ akladn´ıch kursech na vysok´ ych ˇskol´ach a jak´e dobˇre vystihuje origin´ aln´ı n´ azev knihy [1]: ,,Algorithms + Data Structures = Programs”. Tento zp˚ usob je charakteristick´ y snahou pochopit probl´em, rozdˇelit jeho ˇreˇsen´ı na menˇs´ı ˇc´ asti podle postupu ˇreˇsen´ı nebo podle r˚ uzn´ ych pˇr´ıpad˚ u hodnot vstupn´ıch dat a tyto ˇc´asti potom ˇreˇsit pomoc´ı urˇcit´e standardn´ı v´ ybavy algoritm˚ u (vyhled´ av´ an´ı, tˇr´ıdˇen´ı...), meta-algoritm˚ u (rekurse, dynamick´e programov´ an´ı) a datov´ ych struktur. Nˇekter´e u ´lohy jsou ovˇsem na tento postup pˇr´ıliˇs obt´ıˇzn´e, velik´e, neuchopiteln´e. V n´ asleduj´ıc´ıch kapitol´ ach si uk´aˇzeme nˇekolik takov´ ych u ´loh spolu s n´avody, jak je ˇreˇsit ,,jinak”.

2

Probl´ em na u ´ vod: Vodovodn´ı baterie

P´ akov´ a vodovodn´ı baterie obsahuje dvˇe hladk´e keramick´e destiˇcky. Prvn´ı destiˇcka je pevn´ a a jsou v n´ı tˇri otvory napojen´e na pˇr´ıtok studen´e vody, pˇr´ıtok tepl´e vody a odtok. Druh´ a destiˇcka je pohybliv´a a je v n´ı prohlubeˇ n. Zved´ an´ım p´ aky se pohybliv´a destiˇcka posouv´a nad pevnou destiˇckou a jej´ımi otvory, takˇze voda m˚ uˇze prohlubn´ı prot´ekat z otvor˚ u napojen´ ych na pˇr´ıtok studen´e a tepl´e vody do otvoru napojen´eho na odtok. Vˇetˇs´ı zvednut´ı p´aky pˇritom zp˚ usobuje vˇetˇs´ı posuut´ı a t´ım vˇetˇs´ı pr˚ utok vody. Ot´ aˇcen´ım p´ aky se mˇen´ı smˇer, kter´ ym se bude pohybliv´a destiˇcka posouvat a t´ım lze ovlivˇ novat, zda a jakou mˇerou bude prohlubeˇ n pˇri posunu destiˇcky ?

ˇ ˇc´ıslo 201/02/1456 Tato pr´ ace byla podporov´ ana grantem GA CR

Obr´ azek 1. P´ akov´ a vodovodn´ı baterie

zasahovat nad oba pˇr´ıtoky a nad odtok a tedy jak´a bude v´ ysledn´a teplota tekouc´ı vody. Pˇrirozen´ y poˇzadavek na p´akovou baterii je, aby nastaven´a teplota vody, z˚ ustala zachov´ ana bez ohledu na to, jak moc vody prot´ek´a. Tedy aby pomˇer ploch ˇc´ ast´ı otvor˚ u pˇripojen´ ych na pˇr´ıtoky, zakryt´ ych prohlubn´ı v pohybliv´e destiˇcce, i pˇri r˚ uzn´e u ´rovni posunut´ı prohlubnˇe z˚ ust´aval stejn´ y. Probl´ em: Jak´y tvar by mˇely m´ıt otvory a prohlubeˇ n? Tento probl´em uv´ ad´ıme jako pˇr´ıklad probl´emu, na kter´ y nevystaˇc´ıme s ,,klasick´ ym” programov´ an´ım. Jeho ˇreˇsen´ı zat´ım odloˇz´ıme.

3

´ Uloha 1: Nakreslen´ı grafu

Zad´ an´ı: Napiˇste program, kter´y nakresl´ı zadan´y graf. Graf je neorientovan´y, bude zad´ an jako seznam vrchol˚ u a hran, hrany budou kresleny jako u ´seˇcky a nakreslen´ı m´ a b´yt hezk´e. V zad´ an´ı se uv´ ad´ı, ˇze hrany budou kresleny jako u ´seˇcky, jde tedy pouze o urˇcen´ı polohy jednotliv´ ych vrchol˚ u. Zad´ an´ı je pomˇernˇe neurˇcit´e, nen´ı tˇeˇzk´e pˇredstavit si nakreslen´ı grafu, kter´e hezk´e nen´ı — kde se budou hrany zbyteˇcnˇe kˇr´ıˇzit, budou proch´azet vrcholy, nˇekter´e vrcholy budou pˇr´ıliˇs bl´ızko u sebe — a naopak urˇcit´a nakreslen´ı urˇcit´ ych graf˚ u, kter´ a hezk´ a budou. Krom tˇechto extr´em˚ u vˇsak z˚ ust´av´a urˇcit´a neurˇcit´a oblast. Kdybychom tuto u ´lohu ˇreˇsili ,,klasicky”, m˚ uˇzeme se napˇred omezit na ˇreˇsen´ı pro souvisl´e komponenty grafu a potom testovat, zda se nejedn´a o nˇekter´ y zvl´ aˇstn´ı pˇr´ıpad, kter´ y um´ıme hezky nakreslit – kruˇznice, strom, cesta. . . Takov´e ˇreˇsen´ı ovˇsem bude pracn´e a st´ale bude z˚ ust´av´at mnoho graf˚ u, pro kter´e ˇz´adn´e ˇreˇsen´ı m´ıt nebudeme. Zkusme proto tuto u ´lohu ˇreˇsit jinak. Rada 1.: M´ ate-li u ´ lohu, kterou nechcete nebo neum´ıte ˇ reˇ sit. . . . . .ˇ reˇ ste jinou u ´ lohu!

Pˇredstavme si, ˇze vrcholy grafu odpov´ıdaj´ı bod˚ um, kter´e se odpuzuj´ı silou klesaj´ıc´ı se ˇctvercem vzd´ alenosti. Naopak hrany p˚ usob´ı jako guma nebo pruˇziny a pˇritahuj´ı pˇr´ısluˇsn´e vrcholy silou rostouc´ı se ˇctvercem vzd´alenosti. Program, kter´ y m´ a hledat nakreslen´ı grafu (souvisl´e komponenty, tento krok z klasick´eho ˇreˇsen´ı si ponech´ ame) bude pracovat tak, ˇze na zaˇc´atku body rozm´ıst´ı n´ ahodnˇe a potom opakovanˇe v kaˇzd´em kroku vˇzdy pro jeden bod vypoˇcte vektory pˇritaˇzliv´ ych a odpudiv´ ych sil a polohu bodu uprav´ı ve smˇeru dan´em souˇctem tˇechto sil. Polohy bod˚ u, ve kter´ ych se tento pohyb ust´al´ı, nebo kter´e se alespoˇ n uˇz nebudou pˇr´ıliˇs mˇenit, pouˇzijeme jako v´ ysledn´e polohy vrchol˚ u grafu.

4

´ Uloha 2: H´ ad´ an´ı obr´ azku

Tato u ´loha je umˇel´ a, slouˇz´ı jen k tomu, abychom mohli pˇredv´est dalˇs´ı techniku ˇreˇsen´ı u ´loh. Pozdˇeji uvid´ıme, ˇze stejnou technikou lze ˇreˇsit i u ´lohy opravdovˇejˇs´ı. M´ ame napsat program, kter´ y uh´adne obr´azek uloˇzen´ y v jin´e ˇc´asti programu (a zadan´ y uˇzivatelem pˇri startu programu). Takov´ yto typ u ´loh je pomˇernˇe ˇcast´ y — nev´ıme pˇresnˇe, co m´ ame dˇelat a jedin´e, co se dozv´ıd´ame je, ˇze to, co dˇel´ame, nen´ı spr´ avnˇe. Pokud se n´ am ale dost´av´a informace, jak moc to nen´ı spr´avnˇe, m´ ame nap˚ ul vyhr´ ano. M˚ uˇzeme totiˇz pouˇz´ıt druhou radu: Rada 2.: M´ ate-li u ´ lohu, kterou nechcete nebo neum´ıte ˇ reˇ sit. . . . . . zapojte pˇ rirozen´ y v´ ybˇ er!

Technika, kterou chceme pouˇz´ıt, se naz´ yv´a genetick´y algoritmus a lze ji vysvˇetlit opravdu jednoduˇse — m´ame-li hledat ˇreˇsen´ı a m´ame k disposici ohodnocovac´ı funkci, kter´ a kaˇzd´ y pˇredloˇzen´ y pokus o ˇreˇsen´ı ohodnot´ı, potom budeme postupovat tak, ˇze si vytvoˇr´ıme urˇcitou mnoˇzinu ˇreˇsen´ı, neboli populaci, ze zaˇc´ atku vytvoˇrenou n´ ahodnˇe. Kaˇzd´ y prvek populace nech´ame ohodnotit ohodnocovac´ı funkc´ı a potom ze souˇcasn´e populace vytvoˇr´ıme populaci novou, novou generaci. Pˇritom prvky nov´e generace budou nˇekter´e prvky star´e populace, v´ ybˇer se prov´ ad´ı n´ ahodnˇe, ale s pˇrihl´ednut´ım k ohodnocen´ı jednotliv´ ych prvk˚ u, takˇze ti jedinci populace, kteˇr´ı maj´ı lepˇs´ı ohodnocen´ı, maj´ı vyˇsˇs´ı pravdˇepodobnost, ˇze se objev´ı i v dalˇs´ı generaci — a d´ale tak´e nˇekter´e nov´e prvky vznikl´e pomoc´ı operac´ı kˇr´ıˇzen´ı a mutace. Kˇr´ıˇzen´ı znamen´ a, ˇze nov´eho jedince sloˇz´ıme ze dvou jedinc˚ u star´e populace — a opˇet s pˇrihl´ednut´ım k ohodnocen´ı, takˇze u ´spˇeˇsnˇejˇs´ı jedinci maj´ı vˇetˇs´ı ˇsanci vyv´est potomky. Mutace oznaˇcuje n´ ahodnˇe vniklou chybu, s urˇcitou pravdˇepodobnost´ı pozmˇen´ıme nˇekter´ y u ´daj nebo u ´daje v popisu jedince. K ˇcemu je mutace dobr´a uvid´ıme za chv´ıli.

Ze st´ avaj´ıc´ı populace tedy vznik´a populace nov´a, z n´ı zase nov´a a pˇri vytv´aˇren´ı nov´ ych populac´ı maj´ı vˇzdy vˇetˇsi ˇsanci pˇreˇz´ıt jedinci nebo jejich ˇc´asti (kˇr´ıˇzen´ı), kteˇr´ı dosahovali lepˇs´ıho ohodnocen´ı. Postupnˇe by se tedy v populaci mˇeli vyskytovat jedinci, kteˇr´ı se budou v´ıce a v´ıce pˇribliˇzovat hledan´emu ˇreˇsen´ı. N´ aˇs program, kter´ y ˇreˇs´ı u ´lohu h´ad´an´ı obr´azku, pouˇz´ıv´a zjednoduˇsenou versi genetick´eho algoritmu — krok vypad´a tak, ˇze z populace jen odstran´ıme prvek s nejhorˇs´ım hodnocen´ım a nahrad´ıme ho nov´ ym prvkem vytvoˇren´ ym zkˇr´ıˇzen´ım dvou nejlepˇs´ıch jedinc˚ u a pouˇzit´ım mutace. Tento zjednoduˇsen´ y zp˚ usob je snazˇs´ı naprogramovat (i kdyˇz ani stˇr´ıd´an´ı cel´ ych populac´ı nen´ı tˇeˇzk´e naprogramovat) a nav´ıc m´ame zaruˇceno, ˇze nem˚ uˇzeme ztratit jiˇz nalezen´e ˇreˇsen´ı s vysok´ ym ohodnocen´ım (protoˇze ztr´ac´ıme vˇzdy jen nejhorˇs´ı ˇreˇsen´ı). Za toto zjednoduˇsen´ı plat´ıme ”ztr´atou v´ ykonu”, protoˇze vlastnˇe v kaˇzd´e nov´e generaci je jen jeden nov´ y prvek, zat´ımco u vytv´aˇren´ı cel´e nov´e populace by mohlo b´ yt nov´ ych jedinc˚ u v´ıce a t´ım by byla i vˇetˇs´ı ˇsance rychleji naj´ıt lepˇs´ı ˇreˇsen´ı. Ohodnocovac´ı funkce je jednoduch´a, jedinec-obr´azek je bod po bodu porovn´an s (tajn´ ym) c´ılov´ ym obr´ azkem, za kaˇzd´ y uh´adnut´ y bod je hodnocen´ı zv´ yˇseno, za kaˇzd´ y neuh´ adnut´ y bod je hodnocen´ı sn´ıˇzeno (coˇz je zbyteˇcn´e, mohlo by z˚ ustat stejn´e). Kˇr´ıˇzen´ı prob´ıh´ a tak, ˇze kaˇzd´ y bod obr´azku nov´eho jedince je n´ahodnˇe vybr´an od jednoho nebo od druh´eho rodiˇce. Mutace potom znamen´ a n´ahodnou zmˇenu n´ahodnˇe vybran´eho bodu. Na pravdˇepodobnosti mutace z´aleˇz´ı, jak rychle (a zda v˚ ubec) genetick´ y algoritmus najde ˇreˇsen´ı. Kdyby mutace neexistovala (kdyby jej´ı pravdˇepodobnost byla rovna nule), nemohla by se v populaci objevit ˇz´adn´a nov´a informace. Naopak pokud je pravdˇepodobnost mutace pˇr´ıliˇs vysok´a, zmutovan´ı jedinci mutac´ı ztr´ acej´ı informaci, kterou z´ıskali od sv´ ych pˇredk˚ u. Nˇekdy se ovˇsem m˚ uˇze vyplatit pravdˇepodobnost mutace mˇenit v pr˚ ubˇehu v´ ypoˇctu, napˇr´ıklad na zaˇc´ atku nastavit pravdˇepodobnost vyˇsˇs´ı a po tom, co uˇz byla dosaˇzena urˇcit´ a kvalita ˇreˇsen´ı, mutaci sn´ıˇzit. Genetick´e algoritmy tedy pˇredstavuj´ı metodu, jak hledat ˇreˇsen´ı, pokud dok´ aˇzeme kaˇzd´ y pokus o ˇreˇsen´ı popsat pomoc´ı dat (gen) a pokud m´ame k dispozici ohodnocovac´ı funkci. Jejich u ´spˇeˇsnost je r˚ uzn´a, z´aleˇz´ı zejm´ena na tom, jak spojit´ y je vztah mezi genem a ohodnocen´ım.

5

´ Uloha 2’: Brouˇ cci

Genetick´ y algoritmus si uk´ aˇzeme jeˇstˇe na dalˇs´ıch pˇr´ıkladech. V tomto pˇr´ıkladu nem´ ame jasn´e zad´ an´ı, pokud bychom ho pˇrece chtˇeli zformulovat, znˇelo by asi takto:

Zad´ an´ı: Mˇejme d´ an svˇet, ve kter´em ˇzij´ı brouˇcci. Brouˇcci se umˇej´ı pohybovat (otoˇcit se doprava nebo doleva nebo udˇelat krok), vid´ı (pˇred sebe a do stran) a jejich potravou jsou (ostatn´ı) brouˇcci. Najdˇete algoritmus, kter´ym se m´ a brouˇcek ˇr´ıdit, aby nezahynul hlady ani nebyl seˇzr´ an. Kdyˇz brouˇcek nem´ a ˇz´ adnou pamˇet’, lze jeho algoritmus popsat pomoc´ı funkce (CoJeV levo, CoJeV epredu, CoJeV pravo) → T ah Tuto funkci m˚ uˇzeme nahradit tabulkou. Populace brouˇck˚ u je v programu viditeln´a, brouˇcek je zn´azornˇen ˇsipkou otoˇcenou ve smˇeru pohledu brouˇcka, barva urˇcuje, kolik brouˇck˚ u jiˇz brouˇcek snˇedl. V´ yvoj neprob´ıh´ a po kolech, ale jednotliv´ı brouˇcci se stˇr´ıdaj´ı v taz´ıch a vˇzdy, kdyˇz poˇcet brouˇck˚ u klesne pod urˇcitou mez, jsou vytvoˇreni nov´ı brouˇcci z neju ´spˇeˇsnˇejˇs´ıch ˇclen˚ u populace (rodiˇce se nemusej´ı setkat). Pokaˇzd´e, kdyˇz je vytv´ aˇren nov´ y brouˇcek, program vypisuje v´ ykon (poˇcet seˇzran´ ych brouˇck˚ u) a algoritmus jeho rodiˇce — nej´ uspˇeˇsnˇejˇs´ıho (ˇzij´ıc´ıho) brouˇcka. Pred sebou: Napravo: Nalevo N: Nalevo B:

NIC N B < > < >

BROUK N B ^ > ^ X

Obr´ azek 2. Pˇr´ıklad algoritmu, kter´ y dok´ azal seˇzrat 22 brouˇck˚ u

Zobrazen´ y algoritmus bychom slovy mohli popsat tˇreba takto: – je-li pˇred tebou brouˇcek a napravo nic, jdi dopˇredu (ˇzer) – je-li napravo brouˇcek, otoˇc se doprava s v´ yjimkou pˇr´ıpadu, ˇze je brouˇcek i pˇred tebou i nalevo, pak nedˇelej nic – nen´ı-li brouˇcek pˇred tebou ani napravo, otoˇc se doleva.

6

´ Uloha 2”: Brouˇ cci s pamˇ et´ı

Brouˇcci v minul´em pˇr´ıkladu nemaj´ı ˇz´adnou pamˇet, jejich algoritmy tedy pˇredstavuj´ı pˇr´ımoˇcar´e rozhodov´ an´ı na z´akladˇe toho, co vid´ı. Jak by se zmˇenilo chov´an´ı a hlavnˇe schopnosti brouˇck˚ u, kdyby si mohli pamatovat? Pamˇet’ brouˇck˚ um pˇrid´ ame tak, ˇze krom informace, co pr´avˇe vid´ı, budou m´ıt informaci o tom, v jak´em jsou stavu. Stav bude promˇenn´a z rozsahu jedna aˇz maxim´ aln´ı povolen´ y poˇcet stav˚ u. Algoritmus brouˇcka bude tedy opˇet moˇzn´e vyj´adˇrit funkc´ı a tabulkou, pouze funkci pˇribude jeden parametr a tabulce dalˇs´ı rozmˇer a v´ ysledkem funkce a obsahem pol´ıˇcka v tabulce bude nejenom akce, kterou m´a brouˇcek prov´est, ale tak´e u ´daj, do kter´eho stavu m´a pˇrej´ıt.

Schopnosti brouˇck˚ u budeme mˇeˇrit tak, ˇze budou sb´ırat potravu v bludiˇsti, a budeme vyhodnocovat, kolik potravy se kter´emu brouˇckovi podaˇrilo nal´ezt. Kaˇzd´e pol´ıˇcko bludiˇstˇe m˚ uˇze obsahovat potravu, nepr˚ uchodnou zed’ nebo nic — tedy pr´ azdn´ y prostor, kter´ ym lze proj´ıt. Abychom ovˇeˇrili vˇsestrannost algoritmu, kter´ y brouˇcek m´a, budeme kaˇzd´eho brouˇcka testovat na deseti bludiˇst´ıch, kter´a se liˇs´ı mnoˇzstv´ım potravy, zd´ı a pr´ azdn´ ych pol´ıˇcek. Z kaˇzd´eho bludiˇstˇe urˇc´ıme, kolik procent potravy brouˇcek naˇsel a v´ ysledky (jako procenta nalezen´e potravy) za jednotliv´a bludiˇstˇe budeme skl´ adat s t´ım, ˇze nejhorˇs´ı v´ ysledek se bude zapoˇc´ıt´avat s pˇetin´asobnou vahou. Bludiˇstˇe jsou vygenerov´ ana n´ahodnˇe, ale pro vˇsechny brouˇcky stejn´a. Hvˇezdiˇcky oznaˇcuj´ı potravu, p´ısmena M pˇrek´aˇzky a mezery voln´ y prostor, ˇc´ısla nad kaˇzd´ ym bludiˇstˇem ud´avaj´ı poˇcet hvˇezdiˇcek. Bludiˇstˇe je na toroidu, takˇze nejpravˇejˇs´ı sloupec soused´ı s nejlevˇejˇs´ım sloupcem a prvn´ı ˇr´adek soused´ı s posledn´ım ˇr´ adkem. Souhrnn´e v´ ysledky brouˇcka pouˇzijeme jako ohodnocovac´ı funkci pro genetick´ y v´ ybˇer v populaci brouˇck˚ u. Naˇse zkoum´ an´ı skonˇcilo u dvou resp. tˇr´ı stav˚ u, protoˇze uˇz dva stavy staˇcily k tomu, aby brouˇcek dok´ azal sebrat vˇsechny dostupn´e hvˇezdiˇcky kromˇe dvou, pˇri tˇrech stavech potom vˇsechny hvˇezdiˇcky aˇz na jednu.

7

Vsuvka: Historka o magnetofonu

Na u ´vod k dalˇs´ı radˇe uvedeme nejdˇr´ıve jednu historku. Pˇredstavme si, ˇze m´ame magnetofon s poˇc´ıtadlem zaznamen´avaj´ıc´ım ot´aˇcky nav´ıjec´ıho kotouˇce. Zad´ an´ı: Napiˇste program, kter´y dok´ aˇze vz´ ajemnˇe pˇrev´ adˇet stav poˇcitadla magnetofonu a odehran´y ˇcas. Historka z n´ azvu kapitoly spoˇc´ıv´a v tom, ˇze jsme zmˇeˇrili pr˚ umˇer nav´ıjec´ıho kotouˇce, tlouˇst’ku p´ asky, vyj´adˇrili d´elku nav´ıjen´e p´asky. . . — a dostali cosi nepouˇzitelnˇe nepˇresn´eho. T´ım tento pokus skonˇcil. Po ˇcase n´ as napadlo nestarat se o vˇeci, jako je nav´ıjec´ı kotouˇc nebo tlouˇst’ka p´ asky a prostˇe zkusit nˇejak aproximovat funkci urˇcuj´ıc´ı vztah mezi ot´aˇckami a ˇcasem. Line´ arn´ı ten vztah nen´ı, tak jsme zkusili kvadratickou funkci. Kvadratickou funkci m˚ uˇzeme vyj´adˇrit jako y = Ax2 + Bx + C a potˇrebujeme tedy jednom urˇcit hodnoty A, B a C. K urˇcen´ı tˇechto hodnot a k urˇcen´ı cel´e kvadratick´e funkce staˇc´ı zn´at hodnotu funkce ve tˇrech bodech. Nulov´emu ˇcasu odpov´ıdaj´ı nulov´e ot´aˇcky, zjistili jsme jeˇstˇe stav poˇc´ıtadla po pˇrevinut´ı cel´e kazety (45 minut) a uprostˇred. Vypoˇcten´e

koeficienty urˇcily funkci — kter´a, na rozd´ıl od p˚ uvodn´ıho v´ ypoˇctu, d´avala velice pˇresn´e v´ ysledky! A to pˇresto, ˇze tento v´ ypoˇcet nemˇel nic spoleˇcn´eho s t´ım, co vztah mezi poˇc´ıtadlem a ˇcasem vytv´aˇr´ı, ˇz´adn´a tlouˇst’ka p´asky, ˇz´adk´ y pr˚ umˇer nav´ıjec´ıho kotouˇce. . . Pomohlo pod´ıvat se na probl´em jako na ˇcernou skˇr´ınku, nemyslet na to, co je uvnitˇr a jen sledovat jeho chov´an´ı. Rada 3.: M´ ate-li u ´ lohu, kterou nechcete nebo neum´ıte ˇ reˇ sit. . . . . . zkuste se na ni pod´ıvat z odstupu!

8

´ Uloha 3: Rozpozn´ av´ an´ı p´ısmen

Tato u ´loha souvis´ı se zn´ amou u ´lohou rozpozn´av´an´ı p´ısma (OCR). Pˇredpokl´ad´ame, ˇze uˇz byly nalezeny oblasti textu, oddˇeleny ˇr´adky i jednotliv´e znaky a nyn´ı je tˇreba rozpozn´ avat p´ısmena. Zad´ an´ı: Napiˇste program, kter´y bude rozpozn´ avat p´ısmena zadan´ a jako bitov´ a mapa. Pˇredpokl´ adejme, ˇze m´ ame d´an rastrov´ y obr´azek, pro jednoduchost jsou jeho body pouze ˇcern´e nebo b´ıl´e. Naˇs´ım u ´kolem je pro dan´ y obr´azek urˇcit, jak´ y znak je na nˇem zobrazen. Tato u ´loha b´ yv´ a ˇreˇsena mnoha ,,klasick´ ymi” zp˚ usoby, ukaˇzme si jedno jin´e ˇreˇsen´ı a pˇred n´ım dalˇs´ı radu: Rada 4.: M´ ate-li u ´ lohu, kterou nechcete nebo neum´ıte ˇ reˇ sit. . . . . . omezte se na ˇ reˇ sen´ı v urˇ cit´ em tvaru!

Naˇse, ponˇekud naivn´ı, ˇreˇsen´ı bude zaloˇzeno na u ´vaze, ˇze je-li p´ısmen 26, je to m´enˇe neˇz 25 a tedy pro rozliˇsen´ı jednotliv´ ych p´ısmen si staˇc´ı z cel´eho rastru vˇs´ımat pouze pˇeti bod˚ u. Algoritmus rozpozn´ an´ı potom bude trivi´aln´ı, barvy onˇech pˇeti bod˚ u mohou tvoˇrit celkem 32 kombinac´ı a nahl´ednut´ım do tabulky pro kaˇzdou kombinaci zjist´ıme, o jak´e p´ısmeno se jedn´a. Zb´ yv´ a n´ am jin´ au ´loha, jak naj´ıt spr´avn´ ych pˇet bod˚ u. Neˇreˇs´ıme tedy uˇz u ´lohu rozpozn´av´an´ı znak˚ u, ˇreˇs´ıme u ´lohu, jak nal´ezt pˇetici bod˚ u na obd´eln´ıku dan´ ych rozmˇer˚ u, kter´a m´a tu vlastnost, ˇze pro kaˇzd´e z dvaceti ˇsesti p´ısmen d´ av´ a jinou kombinaci ˇcern´e a b´ıl´e barvy. Zp˚ usob, jak takovou pˇetici nal´ezt uˇz zn´ame — hled´ame vlastnˇe deset ˇc´ısel x1 , y1 , x2 , y2 . . . x5 , y5 , pro kter´a plat´ı F (x1 , y1 , x2 , y2 . . . x5 , y5 ) = 0

, kde funkce F je funkce, kter´a pro jakoukoliv pˇetici bod˚ u, neboli desetici sv´ ych parametr˚ u, spoˇcte poˇcet chyb–koliz´ı, pˇr´ıpad˚ u, kdy dvˇe r˚ uzn´a p´ısmena dala stejnou kombinaci barev. Funkci F je snadn´e spoˇc´ıtat i naprogramovat a protoˇze v n´ı m´ame ohodnocovac´ı funkci, m˚ uˇzeme naˇse body naj´ıt pomoc´ı genetick´eho algoritmu. Pozn´ amka: Genetick´ y algoritmus nen´ı jedin´a moˇznost a nijak to neznamen´a, ˇze u ´lohu rozpozn´ av´ an´ı znak˚ u ˇreˇs´ıme pomoc´ı genetick´eho algoritmu! Genetick´ y algoritmus pouˇzijeme pouze jednou, v dobˇe tvorby naˇseho rozpozn´avac´ıho programu, aby n´ am nalezl vhodn´e koeficienty; ostatnˇe kdybychom mˇeli dost trpˇelivosti, dok´azali bychom je zˇrejmˇe naj´ıt i prost´ ym mechanick´ ym prohled´an´ım vˇsech pˇetic bod˚ u. Tato u ´loha je samozˇrejmˇe zjednoduˇsen´a, pˇredpokl´ad´ame jen jeden typ p´ısma, nepˇredpokl´ ad´ ame chyby, hled´an´ı bezkolizn´ı pˇetice tak´e m˚ uˇze trvat dlouho. . . ale nic n´ am nebr´ an´ı m´ısto pˇetice hledat tˇreba desetici bod˚ u a nav´ıc si tˇreba do ohodnocovac´ı funkce pˇredepsat, ˇze poˇc´ıt´a kolize i pˇri zmˇenˇe jedn´e hodnoty — tj. ˇze poˇzadujeme, aby se kombinace v bodech liˇsila ne alespoˇ n v jedn´e, ale tˇreba ve tˇrech hodnot´ ach. T´ım z´ısk´ame odolnost v˚ uˇci chybˇe — i kdyˇz nˇekde bude m´ısto ˇcern´e b´ıl´ a nebo m´ısto b´ıl´e ˇcern´a, naˇse body budou st´ale spr´avnˇe urˇcovat p´ısmeno. Zrovna tak nemus´ıme vyhodnocovat na dvaceti ˇsesti p´ısmenech, ale m˚ uˇzeme m´ıt testovac´ı data, kde budou p´ısmena r˚ uzn´ ych znakov´ ych sad nebo r˚ uznˇe zmrzaˇcen´ a, zaˇsumˇen´ a atd. Pokud algoritmus nebude konvergovat, m˚ uˇzeme zvyˇsovat poˇcet bod˚ u.

9

´ Uloha 4: Obchodov´ an´ı s akciemi

Ukaˇzme si jeˇstˇe jeden pˇr´ıklad na hled´an´ı ˇreˇsen´ı v urˇcit´em tvaru. Bude se t´ ykat obchodov´ an´ı s akciemi, konkr´etnˇe rozhodov´an´ı, zda v urˇcit´e situaci akcie urˇcit´eho druhu koupit nebo prodat nebo drˇzet. Moˇzn´ a jsme uˇz nˇekde slyˇseli ”Akcie klesaj´ı, mus´ım je prodat!” a jindy zase ”Akcie klesaj´ı, je ˇcas nakupovat”, ze stejn´ ych podm´ınek r˚ uzn´e z´avˇery. A moˇzn´a bychom chtˇeli zn´ at ,,ta spr´ avn´a” pravidla. Zad´ an´ı: Napiˇste program, kter´y nalezne pravidla pˇrin´ aˇsej´ıc´ı pˇri obchodov´ an´ı s akciemi nejvˇetˇs´ı zhodnocen´ı. Vstupn´ı informace pravidel jsou kurs a objem obchodov´ an´ı dnes a ve tˇrech okamˇzic´ıch v minulosti – pˇred 2, 20 a 100 obchodn´ımi dny. Pravidla budeme hledat geneticky (rada ˇc´ıslo 2). Prvkem populace bude obchodn´ık, kter´ y m´ a urˇcitou soustavu pravidel, jak obchodovat. Ohodnocen´ı t´eto soustavy pravidel-gen˚ u probˇehne tak, ˇze obchodn´ıkovi d´ame urˇcit´e mnoˇzstv´ı penˇez, nech´ ame ho, podle jeho pravidel, obchodovat na skuteˇcn´ ych u ´daj´ıch z praˇzsk´e bursy a uvid´ıme, jak se mu podaˇr´ı danou v´ ychoz´ı ˇc´astku zhodnotit. Omez´ıme se na pravidla v urˇcit´em tvaru (rada ˇc´ıslo 4 a zad´an´ı u ´lohy).

Mohli bychom ohodnocovat samostatn´a pravidla, ale m´ısto toho bude m´ıt kaˇzd´ y obchodn´ık pravidel v´ıce a kaˇzd´emu pravidlu pˇriˇrad´ıme urˇcitou v´ahu. Mohli bychom vyb´ırat pravidlo s nejvˇetˇs´ı v´ahou ale t´ım bychom ztr´aceli v´ yhodu toho, ˇze m´ ame v´ıce pravidel. M´ısto toho vyhodnot´ıme vˇsechna pravidla a u tˇech, kter´ a maj´ı splnˇen´e pˇredpoklady, pˇripoˇcteme jejich v´ahu k v´aze akce, kterou doporuˇcuj´ı. Tedy jak´esi hlasov´an´ı, kde r˚ uzn´a pravidla maj´ı r˚ uznˇe siln´ y hlas, ale i na tom, kdo m´ a hlas nejslabˇs´ı, m˚ uˇze nˇekdy z´aviset v´ ysledn´e rozhodnut´ı. Rada 5.: M´ ate-li u ´ lohu, kterou nechcete nebo neum´ıte ˇ reˇ sit. . . . . . a potˇ rebujete-li vyb´ırat mezi v´ıce moˇ znostmi. . . . . . pˇ rihl´ ednˇ ete k r˚ uzn´ ym hledisk˚ um. . . . . . pˇ riˇ rad’te jim v´ ahy. . . . . . a nechte je hlasovat! (Spr´ avn´ e v´ ahy m˚ uˇ zete naj´ıt geneticky.)

Typ pravidla potom bude: type TGen = record Hodnota: real; case integer of 20: (A2:array[0..2] of { nakup, prodej, drzet } array[1..MaxDozadu] of record prahK, vahaK, prahO, vahaO: real; end); 21: (DNK: array[1..DelkaGenu] of real) end; Pro kaˇzdou z akc´ı a pro kaˇzd´ y den v minulosti, se kter´ ym m˚ uˇzeme srovn´avat, m´ ame dvˇe podm´ınky, jednu pro objem a jednu pro kurs, pˇriˇc´ıtaj´ıc´ı svou v´ahu k v´ aze t´eto akce, pokud pomˇer kursu resp. objemu tehdy a dnes pˇrekroˇcil dan´ y pr´ ah. Pro pr´ ah vˇetˇs´ı neˇz 1.00, napˇr´ıklad 1.10 to pˇritom znamen´a, ˇze pomˇer je vˇetˇs´ı neˇz hodnota prahu, pro pr´ah menˇs´ı neˇz 1.00, napˇr´ıklad 0.95 to znamen´a, ˇze pomˇer je menˇs´ı neˇz hodnota prahu. T´ım se zbavujeme nutnosti ud´avat znam´enko nerovnosti. V deklaraci je vidˇet, ˇze se z´aroveˇ n na celou genetickou informaci m˚ uˇzeme d´ıvat jako na pole hodnot typu real, coˇz n´am usnadn´ı kˇr´ıˇzen´ı a mutaci. Napˇr´ıklad z u ´daj˚ u o obchodov´an´ı s akciemi Komerˇcn´ı banky za obdob´ı od 5.4.1994 do 19.6.2002 byla nalezena pravidla zhodnocuj´ıc´ı poˇc´ateˇcn´ı vklad v´ıce neˇz sedmin´ asobnˇe.

Pozor: Nen´ı zaj´ımav´e, ˇze pouˇzijeme-li data za osm let obchodov´ an´ı s jedn´ım druhem akci´ı, dok´ aˇzeme naj´ıt mnoˇzinu n´ akup˚ u a prodej˚ u, kter´ a poˇc´ ateˇcn´ı investici nˇekolikr´ at zn´ asob´ı. Zaj´ımav´e je, ˇze dok´ aˇzeme naj´ıt pravidla, pˇri jejichˇz dodrˇzen´ı lze poˇc´ ateˇcn´ı investici takto zhodnotit! Pozor 2: Pˇrenositelnost takto nauˇcen´ych pravidel na jin´y cenn´y pap´ır nebo i na stejn´y cenn´y pap´ır v jin´em ˇcase. . . je velice ˇspatn´ a.

10

´ Uloha 5: Vodovodn´ı baterie

Uˇz v´ıme, jak hledat odpovˇed’ na ot´azku poloˇzenou v u ´vodu. Gen bude tvoˇren dvˇema maticemi (obr´azky, bitov´ ymi mapami) popisuj´ıc´ım´ı ˇ a barva znamen´a nic, ˇcerven´a pˇr´ıtok tepl´e, modr´a pˇr´ıtok stuobˇe destiˇcky. Sed´ den´e, ˇzlut´ a odtok, ˇcern´ a prohlubeˇ n. (Pokud vid´ıte obr´azek bez barev.. ˇcernou pozn´ ate, ˇsed´ a je ten odst´ın ˇsed´e, kter´ y je v lev´e i prav´e polovinˇe obr´azku, modr´a a ˇcerven´ a se vyskytuj´ı pouze v lev´e polovinˇe obr´azku a to symetricky, a ˇzlut´a je ta zb´ yvaj´ıc´ı barva v lev´e polovinˇe obr´azku.) Hledat budeme geneticky, vyhodnocovac´ı funkce hodnot´ı odchylku vypoˇcten´ ych pr˚ utok˚ u od kˇrivky poˇzadovan´ ych pr˚ utok˚ u pˇri r˚ uzn´ ych pootoˇcen´ıch a posunech.

Obr´ azek 3. V´ ysledn´e tvary a pr˚ utoky

Do ohodnocovac´ı funkce jsme zapomnˇeli pˇridat podm´ınku, ˇze otvory maj´ı b´ yt souvisl´e. . . tuto u ´pravu ponech´av´ame ˇcten´aˇri.

11

Z´ avˇ er

Uvedli jsme nˇekolik technik, jak postupovat pˇri ˇreˇsen´ı u ´loh pˇr´ıliˇs obt´ıˇzn´ ych pro standardn´ı zp˚ usoby ˇreˇsen´ı. Jednotliv´e techniky jsou presentov´any na ˇreˇsen´ı sedmi u ´loh. Pln´ y text, obr´ azky a zdrojov´e texty lze naj´ıt na adrese http://ksvi.mff.cuni.cz/~holan/jinak

Reference 1. Niklaus Wirth: Algoritmy a ˇstrukt´ ury u ´dajov, ALFA, Bratislava 1988