Tietorakenteet ja algoritmit 1
TiteWiki
Sisällysluettelo |
Kurssin perustiedot
- Nimi: Tietorakenteet ja algoritmit 1
- Koodi: KTE1317
- Aika: 27.08.2007 - 21.12.2007
- Suoritus: pakollinen
- Luokittelu: koulutusohjelman ammattiopinnot, ohjelmointitekniikka
- Laajuus: 3 op
- Oppitunteja/viikko: 4
- Arvostelu: 0-5
- Oma arvosana: 5
- Arvostelupvm: 02.01.2008
- Läsnäolopakko: ei
- Opettaja: Martti Ylä-Jussila
Virallinen kuvaus (scp.fi, opinto-opas 2005-2006)
Tavoite
Opintojakso jälkeen opiskelijalla on valmiudet yleisimpien tietorakenteiden ja niiden käsittelyrutiinien suunnitteluun sekä STL:n käyttöön.
Sisältö
Algoritmien suunnittelun periaatteita ja ongelmaratkaisun strategioita. Algoritmien tehokkuuden arviointi. Abstraktit tietorakenteet: lista, jono, pino, rengas, puut ja graafit. Lajittelualgoritmeja. STL:n käyttö.
Opetusjärjestelyt
Luentoja ja harjoituksia.
Oppimateriaali
Luentomonisteet. Kurssilla ei ole varsinaista oppikirjaa, mutta tukimateriaalina käytetään teoksia Kokkarinen ja Ala-Mutka: Tietorakenteet ja Algoritmit, Suomen ATK-Kustannus, Cormen, Leiserson, Rivest & Stein: Introduction to algorithms, McGraw-Hill. Robert Sedgewick: Algorithms in C, Addison-Wesley.
Hyväksymisvaatimukset
Harjoitukset ja välikokeet tai tentti.
Oma kuvaus
Opetusjärjestelyt
Neljä tuntia viikossa ja tällä kertaa jopa pysyttiin siinä. Viittaan siihen, että aiemmin saman opettajan kursseilla on hieman lipsuttu virallisista tuntimääristä ylöspäin. Nyt paikalla olivat kuitenkin vain ohjelmoinnin suuntautumisvaihtoehdon oppilaat, joten aika kai riitti paremmin pienemmällä porukalla.
Oppitunnit menivät niin, että välillä katseltiin kalvoilta teoriaa, joka oli koottu useista eri kirjoista. Itselle ei kirjoja tarvinnut hankkia, vaan kaikki löytyi sähköisessä muodossa. Välillä sitten tehtiin ns. tuntitehtäviä, eli kaivettiin Microsoft Visual C++ 6.0 esille ja alettiin kokeilla asioita käytännössä opettajan luomien valmiiden esimerkkiohjelmien avulla. Muutamaan otteeseen tehtiin myös kynällä ja paperilla tehtäviä, mistä oli apua etenkin erilaisten lajittelualgoritmien toiminnan hahmottamisessa.
Kurssi pääsi loppumaan hieman etuajassa. Mutta koska heti seuraavassa periodissa jatketaan Tietorakenteet ja algoritmit 2 -kurssin parissa, ei oppitunteja jätetty pitämättä, vaan ne käytettiin jo seuraavan kurssin asioihin.
Sisältö
Kurssissa oli kahdeksan välikoetta ja niihin opiskeltiin asioita seuraavista aihepiireistä:
- yleisesti algoritmien suunnittelusta
- rekursio ja iteraatio
- tietorakenteet (lineaarinen lista, pino, jono, pakka, toteutustavat, ketjurakenteet, taulukot, puut)
- lajittelu
- ohjelman tehokkuus
Saattaa näyttää vähäiseltä, mutta etenkin tietorakenteiden käsittely vei pitkään.
Välikokeiden ohella kurssiin sisältyi neljä jaksotehtävää. Onneksi niitä oli vain neljä, sillä nyt pystyi keskittymään parempien ratkaisujen luomiseen, kun aikaa oli enemmän. Jaksotehtävät olivat järjestyksessään seuraavat:
- Konversio. Määrämuotoisen tekstitiedostotietokannan muuntaminen tietueittain binääritiedostoksi. Myös virheellisten rivien automaattinen erityiskäsittely.
- Sokkelo. Ohjelma, joka simuloi rotan kulkemista sokkelossa. Pääpointtina rekursiivisen peruuttavan aliohjelman opettelu.
- Binääripuun piirto. Binääripuun piirtäminen näytölle ASCII-merkeillä pystysuuntaisesti. Saattaa vaikuttaa aluksi yksinkertaiselta, mutta ei ehkä olekaan sitä.
- Lajittelu. Suurien binääritiedostojen ulkoinen lajittelu ja tehokkuuden mittaaminen eri tietuemäärillä. Erittäin mielenkiintoinen tehtävä.
Koe/muu arvostelu
Välikokeita siis kahdeksan kappaletta, jotka tulivat aina eteen parin viikon välein. Tahti kuulostaa pahalta, mutta vaikeapa kurssin asioita olisi muutenkaan tentata - harvemmalla tahdilla kokeisiin tulisi niin paljon eri asioita, että niihin lukeminen vaikeutuisi huomattavasti. Jotkut kokeista olivat vaikeampia, jotkut helpompia. Lukematta en ainakaan minä voinut kuvitella selviäväni.
Kokeiden ohella arvosteluun vaikuttivat jaksotehtävät. Niihin täytyi kirjoittaa itse koodin lisäksi jaksotehtävän dokumentointi, jossa selitettiin ongelma, sen ratkaisu ja esitettiin ohjelman rakenne- ja vuokaaviot. Jaksotehtävien palautuksien välillä oli aikaa kuukausi, tosin valitettavan usein tekeminen jäi sinne viimeisille päiville :)
Todellinen hyöty oppimisen kannalta
Kurssi ei tarjonnut koodillisesti niin paljoa uutta, mutta eipä ollut tarkoituskaan: opeteltiin käyttämään tuttua koodia uusilla, tehokkailla tavoilla. Esimerkiksi erilaiset tietorakenteet käytiin nyt huomattavasti tarkemmin läpi kuin aiemmin ja lajittelualgoritmit olivat muutamaa lukuunottamatta täysin uusia tuttavuuksia. Jaksotehtävistä täytyy nostaa esille sokkelo ja lajittelu, jotka olivat erittäin mielenkiintoisia. Paljon hyvää asiaa!
Arvosanat kurssille (0-5)
- Toteutus: 4
- Opetus: 5
- Hyödyllisyys: 5
- Oma suoritus: 5
