Tapaus 4: Purku – Kadonnut eXä löydetty

Tädää.

Viime viikon tapauksessa kyseessä ollut robotin tekoäly ja labyrinttien läpäiseminen algoritmien avulla oli tuottanut OLOilijoillemme mukavaa päänvaivaa. Saimme purun aikana nauttia niin Simpsonien yhdestä jaksosta esitetystä pätkästä kuin iki-ihanalla CmapToolsilla tehdystä käsitekartasta.

Aivan aluksi pääsimme nauttimaan allekirjoittaneen tekemistä mokkapaloista samalla, kun Jaakko esitteli meille miten Tremaux’n algoritmi toimii. Algoritmin ideana oli että labyrinttia ratkaistaessa käytäisiin sama reitti vain maksimissaan kaksi kertaa ja ratkaisija ikään kuin piirtäisi viivaa takanaan, jota aina palattaisiin taaksepäin umpikujaan tai tuttuun risteykseen saapumisen yhteydessä. Uusissa risteyksissä tai tilanteissa, joissa taaksepäin ei enää voi palata mutta vaihtoehtoja siirtymissuunnille on useita, arvotaan jollain periaatteella kääntymissuunta ja jatketaan sinne matkaa.

Hanna oli etsinyt meille tietoa siitä, että mitä ihmettä algoritmit ylipäänsä ovat. Lopputulos oli että algoritmi on ikään kuin keittokirjan resepti, jossa jokainen askel on määritelty. Lisätään kattilaan ensin vesi, keitetään se kiehuvaksi, lisätään nuudelipussi ja annetaan olla 5 minuuttia ja saadaan valmista opiskelijaruokaa. Pääsimme tämän jälkeen ihastelemaan Paulin tekemää käsitekarttaa erään tapauksessa annetun labyrintin ratkaisemisesta. Myös Emmi oli selvittänyt, millä periaatteella toinen labyrintti saataisiin ratkaistua.

Seuraavaksi saimme kuulla erinäisistä lajittelualgoritmeistä Annukan ja Kaisan selittämänä. Tutuiksi tulivat niin hidas mutta hyvin yksinkertainen ja laajalti tunnettu bubblesort kuin myös selection sort, joka etsii pienimmän vertailukohteen järjestämättömien joukosta ja siirtää sen järjestettyyn joukkoon viimeiseksi. Insertion sort puolestaan oli tekniikka, jossa meillä on järjestämättömien ja järjestettyjen arvojen joukko ja aina kun järjestettyyn joukkoon lisätään jokin arvo järjestämättömien joukosta, tarkistetaan mihin väliin se sijoittuu ennen asettamista.

Kaisan kertomana tutustuimme lomituslajitteluun (engl. merge sort) sekä pikalajitteluun (engl. quicksort). Lomituslajittelussa ideana oli jakaa arvojoukko kahteen/useampaan ryhmään, valita porukoista pienimmät luvut ja verrata valittuja keskenään, ja siirtää pienempi arvoista järjestettyjen lukujen joukkoon. Pikalajittelussa ryhmästä arvoja valitaan keskimmäinen ja siirretään se ryhmän vasemmalle tai oikealle puolelle riippuen sen suuruudesta. Tämän jälkeen keskeltä jaon jälkeen saaduista kahdesta joukosta valitaan taas keskimmäinen ja suoritetaan sama tarkistus ja siirto vasemmalle tai oikealle puolelle. Tätä jatketaan niin pitkään, kunnes annettu arvojoukko on järjestetty.

Tämän jälkeen saimme kuulla Aarnen näkemyksen aiheesta ”Random – uhka vai mahdollisuus?” joka alkoi toteamuksella ettei täysin randomissa labyrintin läpäisytavassa ole paljoa järkeä eikä siitä seuraisi mitään hyvää. Kuitenkin satunnaisuutta voidaan fasilitoida vaikkapa aluksi arpomalla paikka, mihin halutaan mennä ja vasta sen jälkeen kun ollaan päästy kyseiseen paikkaan, alettaisiin varsinaista algoritmia suorittamaan. Lopputulema: random on hyvin rajallisesti mahdollisuus.

Miikka pääsi lopulta tutkimaan että miten ihmeessä voimme Robottiturnausta varten tehtävän robotin koodauksen jakaa osiin ja miten pystymme kaikki osallistumaan sen tekoon edes jotenkin. Esille tuli ajatus että on tärkeää että tehtävienjako ja esitietojen jako tehdään kunnolla. Kaikkien pitää olla samalla viivalla koodausta aloittaessa. Miikka tiesi että on olemassa joku softa, jolla voi nähdä muidenkin koodin ja ”olisi hyvä että muut pystyvät kommentoimaan toisten koodia ja kertomaan kuinka paskaa se on”. Ryhmäläisten keskuudessa kannattaisi kuulemma miettiä eri henkilöiden vahvuuksia eri osa-alueiden hoitamisen yhteydessä.

Niiin ja vielä itse allekirjoittanut. Minä pääsin taas isolle ruudulle selittämään ja näyttämään, miten robotin testausta varten tehty turnauskäyttöliittymä toimii ja miten sen valmiit robotit käyttäytyvät. Vähän .class tiedostoja decompilaamalla olin selvittänyt, miten huijarirobotti huijasi kopioimalla itseään useaan kertaan ja antamalla näiden näkymättömien kopioiden uurastaa ja lopulta siirtyä itse täysin oikeaan suuntaan ja että JuoppoRobotti tosiaan toimi täysin satunnaisesti ja meni ties minne. Välillä kävi niinkin hassusti että satunnainen lähestymistapa melkein voitti mutta kyllä se huijari sieltä aina ohi posotti.

Vastaa

Täytä tietosi alle tai klikkaa kuvaketta kirjautuaksesi sisään:

WordPress.com-logo

Olet kommentoimassa WordPress.com -tilin nimissä. Log Out / Muuta )

Twitter-kuva

Olet kommentoimassa Twitter -tilin nimissä. Log Out / Muuta )

Facebook-kuva

Olet kommentoimassa Facebook -tilin nimissä. Log Out / Muuta )

Google+ photo

Olet kommentoimassa Google+ -tilin nimissä. Log Out / Muuta )

Muodostetaan yhteyttä palveluun %s