projektisuunnitelma.html

Tietorakenteiden ja algoritmien oppimisympäristö LEAD

Learning Environment for Algorithms and Data structures

Projektin yleiskuvaus

1. Taustaa

Projektin taustalla on Teknillisen korkeakoulun tietojenkäsittelyopin laboratoriossa 90-luvulla tehty työ, jossa on vähitellen kehitetty apuvälineitä tietorakenteiden ja algoritmien opettamiseen.

Pohjalla oleva perusjärjestelmä, TRAKLA, kehitettiin 90-91. Sen tarkoituksena oli automatisoida kurssin Tik-76.122, Tietorakenteet ja algoritmit, kotitehtävien tarkastamista. TRAKLAn perustoiminnot ovat seuraavat:

Jokainen opiskelija ilmoittautuu kurssille sähköpostitse lähettämällä TRAKLAn osoitteeseen määrämuotoisen viestin.
TRAKLA lähettää kaikille kurssille ilmoittautuneille opiskelijoille kunkin kotilaskukierroksen tehtävät sähköpostitse.
Tehtävät on räätälöity jokaiselle opiskelijalle erikseen siten, että tehtävässä käsiteltävä data on jokaiselle henkilökohtainen, vaikka tehtävän yleisperiaate onkin sama. Tällöin vastauksen kopiointi on mahdotonta.
Tehtävät ovat luonteeltaan ei-triviaaleja. Niissä simuloidaan käsin annetun algoritmin toimintaa askel askeleelta. Esimerkki: "Lajittele merkkijono XYZ aakkosjärjestykseen käyttäen quicksort-algoritmin perusversiota. Esitä välivaiheet"
Opiskelija kirjoittaa vastauksen tiedostoon, jonka hän lähettää sähköpostitse takaisin TRAKLAlle. TRAKLA tarkistaa tuloksen vertaamalla sitä generoituun mallivastaukseen ja pisteyttää tuloksen sen mukaan, kuinka lähellä oikeaa vastausta se on.
Tarkastuksessa sallitaan pieniä poikkeamia oikeasta ratkaisusta ilman, että pisteitä sakotetaan. Lisäksi tehtävästä riippuen voidaan sallia vaihtoehtoisia ratkaisutapoja. Ideana on pyrkiä jäljittelemään manuaalista tarkastusta, jossa ratkaisusta voidaan nähdä, että "idea on oikein, vaikka toteutuksessa on virheitä".
TRAKLA ylläpitää tietokantaa saaduista pisteistä.

Järjestelmän toimivuutta on myöhemmin parannettu lisäämällä siihen joitakin uusia toimintoja. Tärkein muutos toteutettiin 96-97, jolloin sille laadittiin WWW-pohjainen käyttöliittymä, ns. WWW-TRAKLA. Ilmoittautuminen ja tehtävien tilaaminen käy sen avulla päinsä suoraan WWW-lomakkeelta. Lisäksi tehtävät esitetään graafisessa muodossa ja ne voidaan ratkaista graafista editoria (ns. TRAKLA-EDIT) käyttäen. Valmis ratkaisu palautetaan siten, että TRAKLA-EDIT lähettää ratkaisusta sähköpostiviestin TRAKLAlle tarkastusta varten.

2. Tavoitteet

2.1 Yleisperiaatteet

Projektin tavoitteena on kehittää opiskelijoita varten oppimisympäristö, jossa he voivat opiskella eri tietorakenteiden ja algoritmien toimintaa seuraavien toimintojen avulla.

Kuhunkin algoritmiin tai tietorakenteeseen liittyy teksti-/kuvamuotoinen selostus sen toiminnasta. Myös aiheeseen liittyvät luentokalvot ovat saatavilla WWW-materiaalina.
Algoritmin koodi on saatavilla pseudokielellä sekä eri ohjelmointikielillä kuten Pascalilla, C:llä, C++:lla ja Javalla
Algoritmin toiminnasta voi nähdä animaation.
Kun koodi on saatavilla, opiskelija voi muuttaa sitä ja tutkia siten algoritmin toimintaa lisää. Käyttämällä Eliot /Jeliot-työkalua muutos näkyy myös animaatiossa.
Algoritmin implementaation testaamista varten on saatavilla erilaista testidataa, joka testaa algoritmien resurssivaatimuksia parhaan tapauksen, keskimääräisen tapauksen ja pahimman tapauksen yhteydessä, mikäli mahdollista.
Opiskelija voi saada algoritmiin liittyviä tehtäviä, joita hän voi ratkaista TRAKLA-EDITin avulla tai sanallisesti.
Tehtäviin on saatavilla malliratkaisut, joita voi selata TRAKLA-EDITin avulla.
Opiskelija voi saada myös palautetta ratkaisunsa virheistä niiltä osin, kuin arvostelu on automaattista.

2.2 Pedagoginen näkemys opiskelijan työstä

Jotta järjestelmästä tulisi pedagogiselta kannalta mielekäs, sen pitäisi pystyä tukemaan seuraavien tavoitteiden saavuttamista

Algoritmin toiminnan perusidean ymmärtäminen eli kyky selittää, miten algoritmi pääpiirteissään toimii.
Algoritmin implementaation ymmärtäminen, ts. kyky pystyä toteuttamaan algoritmi itsenäisesti ohjelmointikielellä.
Ymmärrys siitä, mitkä tekijät vaikuttavat algoritmin tehokkuuteen, ts. minkälaiset syötteet ovat algoritmin kannalta hyviä, minkälaiset ongelmallisia ja miten algoritmin toimintaa voi virittää näiden kannalta.
Algoritmin suoritusajan matemaattinen analyysi ja analyyttisen tuloksen kriittinen arviointi.
Ymmärrys siitä, miten algoritmia voi muunnella eri tarkoituksiin.

Nykyinen TRAKLA / WWW-TRAKLA -järjestelmä tukee näistä tavoitteista vain ensimmäistä. Muiden tavoitteiden saavuttamista voidaan uudessa järjestelmässä tukea seuraavalla tavalla.

Algoritmin koodi on välittömästi saatavilla. Pseudokoodista on saatavilla kaksi eri hierarkkiatasoa, josta ensimmäinen sisältää vain pääkohdat (algoritmin perustoiminta) ja toinen implementaation yksityiskohtia. Varsinainen ohjelmointikielellä tehty toteutus voi mahdollisesti olla vielä kolmantena versiona. Viimeksimainitun näkyminen kaikissa tilanteissa ei ehkä ole järkevää, jos annetaan tehtäviä, missä algoritmi pitäisi implementoida. Se johtaisi vain kopiointiin vailla oppimista.
Jeliot-animaatio havainnollistaa, mitä osaa koodista ollaan kussakin tilanteessa suorittamassa. Tällöin ohjelmakoodi on tietysti saatavilla, joten implementaatiotehtävien pitää liittyä algoritmien muunnelmiin tai kokonaan uusiin algoritmeihin.
Algoritmin tehokkuuden ymmärtämistä voidaan tukea sillä tavalla, että tarjolla on testiaineistoa implementaatiota varten sekä työkaluja, joilla tehokkuutta voidaan mitata. Viimeksimainituista tarvitaan ainakin cpu-ajan mittausvälineet. Muistinkäytön monitorointi olisi samoin hyödyllinen sekä metodit, joiden avulla voidaan laskea algoritmin suorittamia operaatioita/askelia jollakin tavalla. Viimeksi mainittu voi myös tukea analyyttisten tulosten tarkastelua.
Algoritmin muunneltavuutta järjestelmä voi tukea siten, että opiskelija voi muuttaa algoritmin koodia, muodostaa siitä eri versioita ja tutkia em. välineiden avulla näiden toimintaa.

2.3 Järjestelmä opettajan kannalta

Opettajan kannalta järjestelmän tulee tukea seuraavia asioita:

Opettajan tulee helposti pystyä lisäämään ja muokkaamaan oppimateriaalia. Hänen tulee pystyä käsittelemään luento- ja oheismateriaalia siten, että muutokset ovat heti WWW:ssä saatavilla. Muokkauksen tulee olla helppoa.
Hänellä täytyy olla helppo kontrolli siihen, mikä materiaali on kulloinkin näkyvillä. Pelkkä WWW-linkkien manuaalinen päivitys ei ole riittävän kätevä ja luotettava asia kokonaisuuden kannalta. Parempi olisi se, että systeemissä olisi moduuleita, joita voisi kytkeä päälle ja pois.
Opettajan tulee helposti pystyä keräämään opiskelijoiden tuottamia vastauksia ja tuloksia ja niiden yhteenvetoja. Tämä voi olla osin täysin automaattista. Tässä tarvitaan sekä tilastoja että yksittäisen opiskelijan edistymisen seuraamista.

3. Osatavoitteet

Projektissa on monia osatavoitteita, joita voidaan viedä eteenpäin irrallaan toisista osista.

3.1 Nykyisen TRAKLA-järjestelmän päivitys

Nykyisen TRAKLAn ohjelmakoodi ei vastaa tasoltaan sitä, mitä jatkossa vaaditaan. Koodia ei voi ensinnäkään antaa kansainväliseen levitykseen, koska se on osin tehty suomeksi. Toiseksi sen ylläpidettävyys ja muunneltavuus on paikoitellen huono. Parannuksia on tehty kesällä 97, mutta työ on vielä kesken. Tavoitteena on:

Koodin kieliasun yhtenäistäminen
Koodin modularisointi paremmaksi
Koodin tulee tukea rinnakkaista käsittelyä pistetietokannan osalta.

3.2 WWW-työkalut

Koko järjestelmästä tulee siinä määrin laaja WWW-sovellus, että on perusteltua hankkia sitä varten oma serveri. Samalla mahdollisia turvallisuusongelmia voidaan rajoittaa tähän koneeseen paremmin. Nykyisessä järjestelmässä ollaan riippuvaisia muusta ylläpidosta (TRAKLA ja WWW-TRAKLA pyörivät Niksulassa) ja mahdolliset turvallisuusaukot voivat aiheuttaa harmia muille kuin TRAKLAn ylläpitäjille.

Lisäksi tarvitaan hyvät työkaluohjelmat itse WWW-dokumenttien hallintaan.

3.3 Oppimateriaalin kerääminen yhteen paikkaan

Oppimateriaali sisältää mm. luentokalvot, prujut, linkit oheismateriaaliin, jne. Tämä kaikki tulee saada yhteen paikkaan sopivasti organisoidulla tavalla.

Tässä yhteydessä tutkitaan myös, onko mahdollista käyttää joustavasti materiaalia, joka ei ole suoraan WWW:ssä saatavilla. Esimerkkinä tästä ovat Thomas Ottmannin kehittämät algoritmiopetuksen työvälineet ja animoidut luennot.

3.4 Kokonaisuuden organisointi

Jo nykyisin Tietorakenteet ja algoritmit -kurssin kotisivun alla on sangen paljon materiaalia. Kun järjestelmä tulee merkittävästi paisumaan, tulee miettiä koko organisaatio kunnolla. Minkälaisiin moduleihin tieto jaetaan? Miten taataan tiedon ja linkkien helppo päivittäminen? Minkälainen on sivujen graafinen layout?

3.5 TRAKLA-EDITin kehittäminen

TRAKLA-EDITissä on useita kehitystarpeita. Ensinnäkin sen tulee pystyä toimimaan itsenäisenä sovelluksena, joka ei kommunikoi enää sähköpostitse TRAKLAn kanssa. Toiseksi, sen tietoturvallisuus tulee miettiä tarkasti. Kolmanneksi, siihen tarvitaan suuri joukko uusia tehtäviä, joita on jo implementoitu TRAKLAssa, mutta ei vielä editorissa. Näiden lisäksi voidaan miettiä uusia tehtäviä, joita ehkä ei lainkaan kannata toteuttaa TRAKLAan, mutta joiden graafinen havainnollistaminen TRAKLA-EDITin avulla voisi olla järkevää.

TRAKLAn tulee pystyä generoimaan tehtävien malliratkaisut siten, että TRAKLA-EDIT voi esittää ratkaisun (toimintosekvenssinä, jota opiskelija voi selata edestakaisin). Lisäksi TRAKLA voi antaa palautetta opiskelijan ratkaisuissa olleista virheistä ja TRAKLA-EDITin tulee pystyä välittämään tämä palaute oikeassa kohdassa opiskelijalle näkyviin.

TRAKLA-EDITiä voidaan käyttää oppimateriaalin tukena siten, että se tarjoaa helpon mahdollisuuden esittää vuorovaikutteinen esimerkki jonkin algoritmin toiminnasta. Verrattuna tavanomaiseen algoritmianimaatioon TRAKLA-EDITin etuna on se, että algoritmia voi kelata edestakaisin ja se, että mukaan voidaan helposti lisätä tekstuaalista selostusta, joka vaiheistetaan simulaatioesimerkin kanssa. Samaa esitysmuotoa voidaan käyttää myös palautteen antamiseen opiskelijan vastauksesta.

3.6 Algoritmianimaatio

Algoritmianimaatiota on toteutettu paljonkin eri välineillä. Tämän järjestelmän kannalta keskeinen kiinnostava väline on Helsingin yliopistossa toteutettu Jeliot, joka mahdollistaa animaation automaattisen generoinnin suoraan ohjelmakoodin perusteella. Algoritmi kirjoitetaan Javalla ja kyseessä on WWW-sovellus. Tavoitteena on integroida Jeliot mukaan tähän hankkeeseen yhdeksi opiskelijan työvälineeksi.

Tämän lisäksi voidaan kerätä linkkejä hyviin animaatioesityksiin, mitä WWW:ssä on saatavilla.

3.7 Suorituskykyanalyysi

Algoritmin suorituskyky valkenee konkreettisesti, kun koodia ajaa hyvin erilaisilla syötteillä, jotka on varta vasten suunniteltu siten, että mukana on pieniä ja isoja datamääriä ja helppoja ja pahoja tapauksia algoritmin kannalta. Tätä varten tarvitaan laaja testiaineistokokoelma kaikille systeemissä mukana oleville algoritmeille. Lisäksi tarvitaan ohjelmisto, jolla uutta testidataa voidaan generoida annettujen parametrien ohjaamalla tavalla.

Suorituskyvyn mittaamiseen tarvitaan helpot kirjastorutiinit, joiden avulla cpu-aika voidaan mitata. Systeemin pitäisi myös pystyä monitoroimaan, kuinka paljon muistia on kulloinkin varattu.

Hankalampi kysymys on se, miten annetusta algoritmikoodista voitaisiin automaattisesti laskea haluttujen operaatioiden määrät. Ratkaisuna voisi olla esim. makrokirjasto, jonka avulla operaatiot algoritmikoodissa toteutetetaan. Toinen vaihtoehto voi olla koodin esiprosessointi, jolloin siitä analysoidaan halutut asiat ja generoidaan näiden perusteella varsinainen suoritettava koodi.

Kaikkien näiden tueksi tarvitaan helppokäyttöisiä tilastollisia rutiineita, jotta tulosten luotettavuutta voitaisiin arvioida.

3.8 Opettajalle kerättävä data

Kun järjestelmässä asetetaan tehtäviä, jotka ratkotaan järjestelmän alaisuudessa, vastauksista tulee saada tilastoja niin koko kurssin osanottajien kuin yksittäisen opiskelijankin suorituksista. Tämä tulee vain opettajan käyttöön, joka voi halutessaan julkistaa niistä sopivat osat.

4. Aikataulu

Projektin alustava aikataulu jaksotetaan puolivuosittain seuraavasti. Aikataulu riippuu kuitenkin projektissa mukana olevista henkilöistä ja heidän toiveistaan.

4.1 Syksy 97

Tämän jakson aikana tehdään seuraavat asiat

Perustetaan sovelluksille oma WWW-serveri, asennetaan siihen tarpeelliset työväline- ja tukiohjelmat, sekä siirretään TRAKLA ja WWW-TRAKLA pyörimään siinä.
Nykyinen kirjallinen kurssimateriaali siirretään mahdollisimman pitkälle WWW:hen saataville.
Suunnitellaan, miten koko materiaali organisoidaan siten, että se on helposti ylläpidettävissä ja käyttäjän kannalta helposti hahmotettavissa.
WWW-TRAKLAan lisätään uusia ominaisuuksia. Sen ja TRAKLAn välistä kommunikaatiota uusitaan. Suunnitellaan, miten WWW-TRAKLA saadaan mahdollisimman turvalliseksi. Siihen lisätään joukko tehtäviä, joita ei tähän mennessä ole toteutettu graafisessa muodossa

4.2 Kevät 98

Tämän jakson aikana tehdään seuraavat asiat

TRAKLA-järjestelmän koodi kirjoitetaan tarvittavin osin uudelleen siten, että sen ylläpidettävyys ja laajennettavuus paranee merkittävästi nykyisestä. Tavoitteena on erityisesti sen ongelmaton siirrettävyys ympäristöstä toiseen.
Järjestelmään integroidaan mukaan algoritmianimaatio. Tutkitaan Jeliotin sopivuus tähän tarkoitukseen.
TRAKLA-EDITiin lisätään mahdollisuus esittää malliratkaisuja vuorovaikutteisesti ja antaa palautetta opiskelijan ratkaisuista.

4.3 Kesä ja syksy 98

Tämän jakson aikana tehdään seuraavat asiat

Toteutetaan suorituskykytestausympäristö ja integroidaan se mukaan järjestelmään.
Toteutetaan tilastointi opettajaa varten.

5. Resurssit

Projektin henkilöresursseihin kuuluu assistentti Ari Korhonen, lehtori Lauri Malmi ja tutkija Veikko Siivola.