Tietorakenteiden ja algoritmien oppimisympäristö LEAD

Learning Environment for Algorithms and Data structures

 
 
Tarkennettu projektisuunnitelma WWW-TRAKLAn kehittämisestä
 
 

1 Osaprojektin yleiskuvaus

Projektin tavoitteena on kehittää opiskelijoita varten oppimisympäristö, jossa he voivat opiskella tietorakenteiden ja algoritmien toimintaa. Eräs projektin kannalta keskeinen kehittämiskohde ja osa-alue on WWW-TRAKLA. Kyseessä on tietorakenteiden ja algoritmien opetukseen tarkoitettu tehtäväkokoelma ja ohjelmisto (TRAKLA), joka kykenee arvostelemaan opiskelijoiden palauttamia vastauksia automaattisesti. WWW-TRAKLAn kehittämisessä keskeinen paino on TRAKLA-järjestelmän toiminnallisuuden siirtämisessä WWW:hen ja samalla ohjelmiston päivittäminen vastaamaan paremmin tämän päivän tarpeita ja vaatimuksia. Seuraavassa on esitetty tarkennettu projektisuunnitelma siitä, kuinka WWW-pohjaista TRAKLAA ja siihen kiinteänä osana liittyvää graafista käyttöliittymään TraklaEditiä on tarkoitus kehittää.

2 Alkuperäisen projektisuunnitelman osaprojektin kuvaus

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 Tarkennettu kuvaus

Osaprojekti voidaan jakaa luontevasti useaan pienempään osaan. Seuraavassa on kuvattu nämä osuudet. Osat voidaan toteuttaa osittain rinnakkain. Yleisesti koko uusi järjestelmä kirjoitetaan Javalla ja se kommentoidaan ja dokumentoidaan englanniksi, lukuunottamatta käyttäjille tulevia ohjeita, jotka kirjoitetaan sekä suomeksi että englanniksi. Osaprojektin tulisi alustavasti olla valmiina vuoden 1998 loppuun mennessä. Kuitenkin siten, että testiversio järjestelmästä on käytössä jo syksyllä. Tällöin osa uusista tehtävistä voi olla vielä toteuttamatta. Osaprojektin suunnittelu jatkuu toukokuun loppuun saakka. Järjestelmän osien implementaatio alkaa jo toukokuussa siltä osin, kuin mahdollista.
 

3.1 C/Java-rajapinta

Koska uudistettava järjestelmä on tarkoitus toteuttaa Javalla, tulee vanhan ja uuden järjestelmän välinen rajapinta kommunikaation suhteen toteuttaa sopivasti, ottaen huomioon ainakin seuraavia seikkoja:
 
  • kommunikaatiorajapinnan toteutus
  • tietoturvakysymykset
  • järjestelmän virheistä toipuminen
  • järjestelmän suorituskyky

    • Kommunikaatiorajapinnan toteutuksessa on oleellisesti kaksi eri vaihtoehtoa. Joko Java-pohjainen toteutettava järjestelmä kommunikoi Javan natiivirajapinnan avulla vanhan järjestelmän kanssa, jolloin se voi hyödyntää vanhan TRAKLA-järjestelmän C-kielisiä osia tai uusi järjestelmä asennetaan vanhan "päälle" siten, että vanha C-kielinen TRAKLA-järjestelmä osaa sopivalla tavalla kutsua Java-pohjaisia uusia moduuleita. Valinta riippuu mm. siitä, kuinka paljon vanhasta järjestelmästä on jatkossa tarkoitus hyödyntää uudessa järjestelmässä. Aluksi on ehkä tarkoituksenmukaista pyrkiä hyödyntämään vanhaa järjestelmää mahdollisimman paljon, jolloin koko järjestelmää ei tarvitse kirjoittaa uudelleen. Tällöin uusi Java-pohjainen järjestelmä voidaan nähdä vanhan järjestelmän eräänä osana, joka toteuttaa sille asetetut vaatimukset. Keskeisimmät uudistettavat osat ovat tehtävien räätälöinti (tailor) ja niiden tarkastaminen (check).

    Tutkimus ja toteutussuunnitelma: tutkitaan, mitä eri vaihtoehtoja on olemassa C- ja Java-kielisten ohjelmien liitämiseksi toisiinsa. Samalla kartoitetaan mitä turvallisuusriskejä mahdollisesti vaihtoehtoihin liittyy ja kuinka järjestelmän virheistä toipuminen on mahdollista toteuttaa. Lisäksi on syytä tutkia eri vaihtoehtojen vaikutusta koko järjestelmän suorituskykyyn. Toteutusosassa toteutetaan joidenkin C- ja Java-kielisten ohjelmien kommunikaatiorajapinta. Tässä voidaan hyödyntää esimerkiksi TRAKLA-järjestelmän tailor-moduulia ja tutkia kuinka siitä voitaisiin kutsua Java-pohjaista tehtävän räätäliä ja/tai rakentaa Java-pohjainen "tailor", joka kutsuu TRAKLAn C-kielellä kirjoitettuja tehtäväkohtaisia tailor-moduuleja.

    AIkataulu: toukokuun loppuun mennessä

    3.2 Common tailor -luokan toteutus

    Eräs keskeinen projektin osa-alue on tehtävien räätälöinti ja sen toteutuksen implementointi. Implementaatio riippuu pitkälti kohdassa 3.1 saaduista tuloksista. Oleellista kuitenkin on, että vanhan TRAKLA-järjestelmän mukaisesta tavasta toteuttaa erillinen räätälöintiohjelma jokaiselle tehtävälle luovutaan. Uuden toteutuksen keskeisiä piirteitä ovat seuraavat:
     
  • järjestelmässä on vain yksi geneerinen tailor (räätäli), joka osaa tuottaa sopivaa dataa kaikkiin järjestelmän tuntemiin tietorakenteisiin
  • tietorakenteet nähdään järjestelmässä olioina
  • tietorakenneoliot toteuttavat tietorakennerajapinnan
  • algoritmit (algoritmiset tehtävät) ovat myös olioita, jotka kommunikoivat tietorakenteiden kanssa
  • algoritmioliot toteuttavat algoritmirajapinnan

    • Räätäliä kutsutaan sopivalla parametrillä, joka identifioi räätälöitävän tehtävän. Tehtävä muodostuu
     

  • otsikkokentästä,
  • tehtävänannosta,
  • makrokielestä,
  • tehtäväappletin määrittelystä ja
  • esimerkistä.
    • 3.2.1 Parseri
    Räätälin tehtävänä on rakentaa (parseri) HTML-muotoinen tehtävä edellä mainituista osista. Osasten esitystapa ja tallennusmuoto jätetään vielä toistaiseksi avoimeksi. Makrokielellä määritellään tehtäväpohjaan tulevat muuttuvat tiedot, kuten esimerkiksi opiskelijanumero ja tehtäväkohtainen muuttuva data. Common tailorissa tuleekin toteuttaa lisäksi eräänlainen puppugeneraattori, joka osaa tuottaa tehtäväkohtaista dataa halutulle tietorakenteella. Data on erilainen eri opiskelijoille.
    3.2.2 Puppugeneraattori
    Puppugeneraattorin tehtävänä on tuottaa sopivaa dataa, jolla tehtävien tietorakenteet alustetaan. Haasteena on toteuttaa luokka, joka kykenee tuottamaan dataa tehtävän haluamilla reunaehdoilla.

    Esimerkki: tehtävässä on tarkoitus lisätä binääriseen hakupuuhun annetut alkiot annetussa järjestyksessä.

    Tarvittavat tietorakenteet: taulukko (tai tietovuo), jossa lisättävät alkiot sekä binääripuu
    Parametrit: lisättävien alkioiden lukumäärä N
    Algoritmi: insertTree

    Tyypillisesti graafisessa esityksessä on tarkoitusenmukaista pitäytyä tapauksissa, joissa puun korkeus < 6. Tällöin, esimerkiksi jos N=10, tulee alustettavan taulukon toteuttaa reunaehto, joka riippuu tehtävän sisältämästä algoritmista. Mikä tahansa satunnainen alkioiden järjestys ei käy. Tätä varten puppugeneraattorin tulee kutsua (samaa kuin tehtävän tarkastuksessa) käytettävää algoritmia ja pyytää tätä verifioimaan käytettävä data (onko sillä ominaisuus, että puun korkeus jää < 6). Algoritmin rajapinta vaatii siis ainakin metodin isValid(), joka on algoritmikohtainen ja joka palauttaa TRUE, jos algoritmille annettu data täytti tehtävälle asetettavan datan vaatimukset.

    Edellä esitetty voitaisiin toteuttaa esimerkiksi makrolla, joka olisi vaikkapa muotoa

    $String(10, insertTree())

    joka kertoisi, että kyseiseen kohtaan tehtäväpohjaa alustetaan dataa, joka on merkkijono (alkiot ovat kirjaimia) ja joka toteuttaa insertTree() -algoritmissa määritellyt reunaehdot.

    Parserin tehtäväksi jää näinollen kutsua puppugeneraattorissa sopivaa konstruktoria, joka osaa tuottaa merkkijonoja ja välittää annetut parametrit tälle. Konstruktoreita tulee luonnollisesti olla useita samoin kuin erilaisia makroja, joilla dataa voidaan luoda. Seuraavassa on lueteltu joitain parametrejä, joita makrojen tulisi huomioida ja osata:
     

  • erilaiset merkkijonoesitykset
  • erilaiset numeromuotoiset esitykset
  • muut tietorakenteet, kuten vieruslistat, matriisit jne.
  • tehtäväkohtainen siemenluku
  • tehtäväkohtaiset erityisvaatimukset (esim. 1. alkion valinta pienemmästä joukosta kuin muiden)
  • esitysmuodon valinta
  • sama rakenne useassa eri kohdassa

    • Siemenluvun ideana on pystyä tuottamaan sama data eri tehtäviin samalle opiskelijalle (sama siemenluku eri tehtävissä) tai haluttaessa eri data (eri siemenluku eri tehtävissä). Esitysmuotomuunnokset tulee toteuttaa erillisenä luokkana, joka osaa muuntaa eri esitysmuotoja toisiksi. Esimerkiksi matriisi <-> vieruslista. Lisäksi muunnoksen tulee osata esittää sama rakenne sekä "ihmisen luettavassa" muodossa että TraklaEditille jossakin kompaktissa esitysmuodossa. Tehtäväkohtaisia erityisvaatimuksia voi toteuttaa sikäli kun ne ovat geneerisiä ja niistä on yleistä hyötyä. Esimerkiksi binääripuutehtävässä tietorakenteen alustus voi nopeutua merkittävästi, jos 1. alkio valitaan aakkoston keskeltä. Satunnaislukugeneraattorin tulee olla deterministinen, eli sama "satunnainen" rakenne tulee pystyä tuottamaan uudelleen tehtävän tarkastusvaiheessa. Lisäksi on syytä huomata, että tuotettava rakenne voi esiintyä tehtävänannossa useassa eri kohdassa, jolloin makron eri kutsukerroilla tulee makron palauttaa sama rakenne (ellei esimerkiksi siemenluvulla erikseen toisin määritellä).

    Oleellisesti kyseessä on kaksi esitysmuotoa tehtäville. Toisessa tehtävä tulee kyetä rakentamaan sanalliseen muotoon lähetettäväksi esimerkiksi sähköpostilla. Toisessa esitysmuodossa rakenteet ovat ohjelman sisäisiä. Tässä voisi ajatella, että generaattori palauttaakin tietorakenteen, joka on valmiiksi alustettu. Tietorakenteiden tulee tällöin toteuttaa tietorakennerajapinta, joka määrittelee kuinka uusi rakenne luodaan ja alustetaan.

    3.2.3 Toteutussuunnitlema ja aikataulu
    Tutkimus ja toteutussuunnitelma: tutkitaan erilaisia tehtäviä ja pyritään johtamaan niistä mahdollisimman yleinen makrokieli, johon toteutusvaiheessa joudutaan tekemään mahdollisimman vähän tehtäväkohtaisia lisäyksiä. Pohjana suunnittelussa kannattaa käyttää TRAKLAn vanhoja tehtäviä. Toteutusvaiheessa räätälöintiohjelma toteutetaan ja sitä testatataan projektin aikana kehitettyjen uusien algoritmisten tehtävien kanssa.

    Aikataulu: toteutetaan kesäkuun aikana

    3.3 Tehtävien suunnittelu ja toteutus

    Tehtävien suunnittelu ja toteutus sisältää seuraavien rajapintojen määrittelyt ja toteutukset sekä implementaatiokysymykset:
     
  • algoritmirajapinnan määrittely
  • tietorakennerajapinnan määrittely
  • rajapinnat toteuttavien algoritmien implementointi
  • rajapinnan toteuttavien tietorakenteiden implementointi
  • tehtävien esitysmuodon ja kielen suunnittelu ja toteutus

    • Algoritmit tulee siis imlementoida siten, että ne toteuttavat algoritmirajapinnan. Lisäksi niiden tulee käyttää vain tietorakennerajapinnan mukaisia tietorakenteita. Tehtävien esitysmuodon valinta riippuu pitkälti kohdassa 3.2 saaduista tulokista. Eräs tapa on toteuttaa tehtävät kuten ne on toteutettu vanhassa TRAKLA-järjestelmässä, jossa jokaiselle tehtävälle on erillinen tehtäväpohja sekä sähköpostia että WWW:tä varten (kahdella eri kielellä). Jatkossa voisi tutkia mahdollisuutta tallettaa tehtävät osina tietokantaan, josta ne voidaan tailorilla "koota" joko sähköpostia tai WWW:tä varten. SÄhköpostiversion hyödyllisyys tulee lisäksi pohtia tarkkaan, koska jatkossa tehtävien palauttaminen sähköpostilla ei ole mahdollista (tai mielekästä). Oleellista kuitenkin on, että tehtäväkohtainen informaatio tulee olla helposti konstruoitavissa sekä WWW:ssä että tehtävän tarkastusvaiheessa.

    Tutkimus ja toteutussuunnitelma: aluksi toteutetaan muutamia testiversioita erityyppisistä tehtävistä. Rajapinnat määrittyvät tarkemmin toteutusvaiheessa. Tehtävien esitysmuoto tulee lyödä lukkoon mahdollisimman varhain, kunhan suunnitteluvaihe on tarpeeksi pitkällä.

    Aikataulu: suunnitteluvaiheeseen varataan koko toukokuu, toteutus aloitetaan osin toukokuussa. Testiversio tulee olla valmis syksyllä.

    3.4 Perustietorakenteen suunnittelu ja toteutus

    Tietorakenteiden näkeminen olioina perustuu ajatukseen, jossa kaikki algoritmeissa käytettävät tietorakenteet on johdettu jostakin sopivasta geneerisestä perustietorakenteesta. Kyseisen rakenteen tarkoituksena on toteuttaa rajapinta TRAKLA:n ja TraklaEditin välille. Perusrakenteen manipulointi (käytettävä johdettu rakenne välittää kutsut perusrakenteelle) johtaa toimintosekvensiin, josta algoritmin toiminta ja vastaavasti tehtävän ratkaisu TraklaEditillä voidaan verifioida. Tehtävän tarkastus on oleellisesti tämän jälkeen näiden kahden sekvenssin vertailua. Uuden algoritmin lisääminen on tällöin helppoa, koska sitä varten ei tarvitse tehdä erikseen tarkastusohjelmaa, vaan ainostaan määritellä tarkastuksessa käytettävät perusteet.

    Tutkimus ja toteutussuunnitelma: toteutetaan aluksi testiversio, jolla pyritään kartoittamaan ajatukseen liittyvät ongelmat ja reunaehdot.  Jatkossa toteutetaan kieli, joka kuvaa perusrakenteen muutoksia.

    Aikataulu: touko-kesäkuu, kehitystyö kielen osalta jatkuu syksyyn.

    3.5 TraklaEditin mukauttaminen uuteen järjestelmään

    TraklaEditiin joudutaan tekemään lukuisia muutoksia, jotta se saadaan ymmärtämään uutta järjestelmää. Tätä työtä on tarkoitus tehdä sitä mukaa, kun järjestelmän kehitys etenee. Tarkoitus on kuitenkin hyödyntää TraklaEditissä samoja tietorakenteita, jotka toteutetaan  WWW-TRAKLAan. Tällöin esimerkiksi kohdassa 3.4 esitetyn kielen implementointi tehdään vain kerran ja tulos voidaan adoptoida TraklaEditiin suoraan. Oleellisesti TraklaEditiin tulee tällöin implementoida ainoastaan mekanismi, jolla kuvaus voidaan lähettää tarkastusta varten. Tietorakennerajapinnassa tulee ottaa huomioon TraklaEditin tarpeet. Tällöin johdettujen rakenteiden tulee toteuttaa myös graafiset ominaisuudet, jolloin sama koodi käy sekä WWW-TRAKLAan että TraklaEditiin. TraklaEdit tuleekin toteuttaa siten, että siihen voi lisätä minkä tahansa uuden tietorakenteen, joka noudattaa määriteltyä rajapintaa. Tällöin uuden tehtävän (joka käyttää jotakin ennestään tuntematonta tietorakennetta) implementaatio TraklaEditille saadaan jatkossa "ilmaiseksi".

    Aikataulu: kesä-syksy

    3.6 Tehtävien tarkastaminen

    Yleisen tehtäviä tarkastavan moduulin suunnittelu ja toteutus on keskeinen osa järjestelmää. Toteutus riippuu pitkälti kohdassa 3.4 saaduista tuloksista. Ajatuksena on, että järjestelmään voitaisiin toteuttaa geneerinen tarkastusosa, joka osaa tarkastaa minkä tahansa rajapintojen mukaisen algoritmisen tehtävän. Oleellisesti kyseessä on toteutetun kielen sekvenssien vertailu: malliratkaisua edustaa toteutetulla algoritmilla saatu vastaus, jota verrataan TraklaEditillä opsikelijan tuottamaan ratkaisuun.

    AIkataulu: syksy
     

    4 Jatkokehitys

    Muut alkuperäinen projektisuunnitelman sisältämät ajatukset TraklaEditin kehittämiseksi ovat sellaisia, että ne kannattaa toteuttaa vasta edellä esitetyn jälkeen. Tällaisia ominaisuuksia ovat esimerkiksi:
     
  • toimiminen itsenäisenä sovelluksena/vuorovaikutteiset esimerkit
  • malliratkaisujen generointi
  • opiskelijalle annettava palaute
  • tekstimuotoinen selostus
  • kaikkien TRAKLA-tehtävien implementointi

    • Kaikki edellä esitetyt, lukuunottamatta viimeistä kohtaa, pohjaavat pitkälti kohdassa 3.4 esitettyyn kieleen. Esimerkiksi tekstimuotoinen selostus voidaan liittää mukaan lisäämällä kieleen lauseita, joilla voidaan tietyssä kohtaa sekvenssiä asiaa valaista avautuvalla ikkunalla ja siinä olevalla tekstimuotoisella selostuksella. Malliratkaisujen generointi uusille tehtäville kuuluu osana kesän aikana toteutettavaa järjestelmää. Kaikkien vanhojen tehtävien implementointi ja malliratkaisujen generointi niihin jätetään myöhemmäksi. Sitä ennen tulee arvioida mitkä tehtävät ovat sellaisia, että ne kannattaa toteuttaa uuden järjestelmän mukaisesti.