Kurssiesite.WWW

Tik-76.122 Tietorakenteet ja algoritmit, Kevät 98 (3 ov)

1. Opintojakson tavoitteet

Opintojaksossa käydään läpi tärkeimmät tietorakenteet ja niiden käsittelyssä käytettävät algoritmit. Keskeisiä aihepiirejä ovat perustietorakenteet, algoritmianalyysi, etsintä, lajittelu, graafit ja merkkijonojen käsittely. Tavoitteena on ymmärtää algoritmien ja niihin liittyvien tietorakenteiden toimintaa
siinä määrin, että pystyy valitsemaan esiin tulevissa probleemoissa järkevän ratkaisumenetelmän ja soveltamaan sen käytäntöön.

2. Esitiedot

Esitietoina tarvitaan kyky ymmärtää C-kielisiä ohjelmia, koska kurssikirjassa ja luennoilla esitetyt esimerkit on kirjoitettu tällä kielellä. Kurssilla ei tarvitse toteuttaa ohjelmia, ellei osallistu vapaaehtoiseen projektiin. Kurssin kotitehtävien suorittamisessa käytetään apuna Unix-koneiden sähköpostijärjestelmää ja WWW:tä. Tarvittaessa niiden käyttö on opeteltava itsenäisesti esim. laskentakeskuksen oppaiden avulla.

3. Opetusmuodot

Kurssilla käytetään seuraavia opetusmuotoja:

Luennoilla käydään läpi kurssin keskeisin aineisto. Luentojen sisältöä on jonkin verran supistettu viime vuodesta, jolloin osa kurssivaatimuksiin kuuluvista asioista jätetään harjoitustehtävien ja itseopiskelun varaan. Luennot pidetään keskiviikkoisin klo 13-16 salissa A. Ensimmäinen luento on 21.1.98.
Koska kolmen tunnin luentoa on varsin raskas seurata keskittyneesti, useimmilla luentokerroilla järjestetään suppeita harjoituksia, joissa sovelletaan luennolla esitettyjä asioita. Samalla esitetyt asiat todennäköisesti myös opitaan paremmin. Harjoituksia tehdään luennolla pienissä 2-4 hengen ryhmissä, jolloin asioita ei tarvitse pohtia yksikseen, ellei niin halua. Luentomonisteet, jotka monistetaan heti kurssin alussa, toimivat näissä harjoituksissa kirjallisena tukimateriaalina. Harjoitusten kesto on 15-30 minuuttia kerrallaan, jonka jälkeen luennoija esittää ratkaisun tehtävään / tehtäviin.
Kurssin tuntiassistentit pitävät demonstraatioita, joissa käydään läpi kurssin kotitehtävien ratkaisuja. Demonstraatioiden ajankohdasta tiedotetaan erikseen.
Kotitehtävissä harjoitellaan tietorakenteiden ja algoritmien toimintaa sekä niiden soveltamista uusien ongelmien ratkaisuun. Kurssiin kuuluu kahdenlaisia kotitehtäviä:

Perustehtävissä perehdytään kurssilla läpikäytävien tietorakenteiden ja algoritmien toimintaan simuloimalla niitä manuaalisesti yksinkertaisella datalla. Jokaisella kurssilaisella on omat henkilökohtaiset tehtävänsä, jotka jaetaan ja palautetaan TRAKLA- / WWW-TRAKLA-järjestelmän avulla. Perustehtävät arvostelee TRAKLA-järjestelmä automaattisesti.
Sovellustehtävissä suunnitellaan ja/tai analysoidaan yksinkertaisia uusia algoritmeja, joissa perusalgoritmeja sovelletaan uusiin ongelmiin. Sovellustehtäviä ratkaistaan 2-3 hengen ryhmissä ja niiden ratkaisut arvioidaan manuaalisesti.
Osa kurssilaisista suorittaa sovellustehtävät osallistumalla koosteryhmiin. Nämä 2-3 hengen ryhmät eivät tee itse sovellustehtäviä. Sen sijaan ne kokoavat kurssin henkilökunnan ohjeiden mukaan kurssilaisten esittämistä ratkaisuvaihtoehdoista yhteenvetoja. Nämä yhteenvedot kommentteineen julkaistaan kevään aikana kaikille kurssilaisille. Koosteryhmien työmäärä vastaa suurin piirtein samaa kuin tehtävien ratkominen itse. Ryhmään kuuluvilla on mahdollisuus oppia asiaa syvällisemmin, koska he tutustuvat monenlaisiin ratkaisuihin ja oppivat arvioimaan niiden etuja ja huonoja puolia paremmin kuin muut kurssilaiset. Koosteryhmiin pääsee mukaan vain rajallinen määrä opiskelijoita.

Tentissä ratkaistaan itsenäisesti samantyyppisiä tehtäviä kuin kotitehtävissä. Tentissä on myös teoriakysymyksiä.
Projekti on vapaaehtoinen kokeilu, jossa syvennytään johonkin kurssiin liittyvään alueeseen tarkemmin ja implementoidaan algoritmeja sekä tutkitaan niiden suorituskykyä lähemmin. Projekti toteutetaan pienissä ryhmissä ja kokeiluun otetaan mukaan 10 ryhmää. Projektiin osallistujat saavat ylimääräiset 1-2 opintoviikkoa työn laajuuden mukaan ns. henkilökohtaisena opintosuorituksena.

4. Henkilökunta

Luennoijana toimii lehtori Lauri Malmi, joka on tavattavissa vastaanottoaikoina huoneessa Y237. Kurssin tuntiassistenttina toimivat TkY Petri Paavilainen ja TkY Simo Särkkä, jotka neuvovat kurssiin liittyvissä kotilaskuissa ja huolehtivat kotilaskujen käytännön järjestelyistä. Heidän vastaanottonsa pidetään huoneessa Y163 erikseen ilmoitettavina aikoina. Lisäksi assistentti Ari Korhonen huolehtii kurssilla käytetyistä TRAKLA ja WWW-TRAKLA-järjestelmistä.

5. Oppimateriaali ja tiedottaminen

Kurssikirjana on Mark Allen Weiss: Data Structures and Algorithm Analysis in C, (Benjamin/Cummings), 2nd edition. Myös vanha painos on käyttökelpoinen. Kyseisessä kirjassa esimerkkiohjelmat ovat C-kielellä, joten myös luennoilla käsiteltävät esimerkkiohjelmat on kirjoitettu C:llä. Oppikirjasta on olemassa myös erillinen painos Data Structures and Algorithm Analysis, jossa teksti on sama, mutta esimerkkiohjelmat ovat Pascal-kielellä. Tätä versiota voi myös käyttää. Joukko muitakin tietorakenteiden ja algoritmien oppikirjoja on käyttökelpoisia, esim. R. Sedgewick: Algorithms in C (Addison-Wesley), T. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms (MIT press) ja E. Horowitz, S. Sahni: Fundamentals of Data Structures (Computer Science Press). Em. kirjoja voi tiedustella päärakennuksen kirjakaupasta.

Opetusmonisteiden kautta kurssilaiset saavat luentomonisteet, hieman muuta oppimateriaalia sekä kotitehtäviiin liittyvää informaatiota. Luentomonisteet ovat sen verran pelkistetyt, että kurssin suorittaminen pelkästään niiden varassa ei ole suositeltavaa. TILAA PRUJUT 1. KIERROKSELLA.

Kurssiin liittyvistä asioista tiedotetaan luennoilla ja otaxin news-uutisryhmässä opinnot.tik.trak. Seuraa kyseistä uutisryhmää säännöllisesti. Kurssin WWW-sivulle pyritään kokoamaan kurssiin liittyvää oheismateriaalia. Sivun osoite on http://www.niksula.cs.hut.fi/~tik76122/. Kurssin ilmoitustaulu on huoneen Y163 vieressä olevalla käytävällä ja sinne ilmestyy lähinnä suoritusmerkintöjä. Tiedusteluja voi lähettää myös sähköpostitunnukselle tik76122@hut.fi, jolloin kurssin assistentit todennäköisesti vastaavat niihin päivän parin viiveellä.

6. Ilmoittautuminen

Opintojaksolle ilmoittaudutaan joko kurssin WWW-sivun kautta tai sähköpostin avulla (ei siis TOPIn kautta). Tarkemmat ohjeet sähköposti-ilmoittautumisesta tulevat kurssin uutisryhmään. Ilmoittautuminen tällä tavoin on välttämätöntä, koska kotitehtävät jaetaan sähköpostin välityksellä . Ilmoittautuminen on edellytyksenä kurssille osallistumiselle ja se tulee suorittaa maanantaihin 2.2.98 mennessä (jotta saa ensimmäiset kotilaskut ajoissa).

Ilmoittautumisen yhteydessä tulee antaa sähköpostiosoite, joka on hut.fi -domainin alueella. Jos haluaa kurssilta tulevan sähköpostin muuhun osoitteeseen,
esim. iki.fi -tunnukselle, posti tulee lähettää edelleen (.forward) sinne itse.

Koosteryhmiin voi ilmoittautua kokoamalla 2-3 hengen ryhmän ja lähettämällä ryhmän tiedot kurssitunnukselle tik76122@hut.fi. Koosteryhmät valitaan
niiden joukosta, jotka ovat ilmoittautuneet tehtävään 16.2.98 mennessä. (HUOM. Muuttunut aika).

7. TRAKLA-järjestelmä

Kurssilla käytetään WWW:tä ja/tai sähköpostia työskentelyvälineenä, käyttäen apuna tietojenkäsittelyopin laboratoriossa kehitettyä TRAKLA-/WWW-TRAKLA-järjestelmää. Käytännössä tämä tarkoittaa, että kurssin kotitehtävät jaetaan ja vastaukset palautetaan WWW-lomaketta tai sähköpostia käyttäen. WWW-TRAKLA tarjoaa mahdollisuuden ratkoa osa kotitehtävistä graafisessa muodossa, mikä on monesti kätevämpää ja havainnollisempaa kuin ratkaisujen esittäminen ja lähettäminen ASCII-tekstinä sähköpostitse.

Jokaisen kurssille osallistuvan on hankittava itselleen lupa johonkin korkeakoulun UNIX-koneeseen. Mikäli et omista vielä ko. lupaa, saat sen atk-keskuksen asiakaspalvelupisteestä (huone U133).

8. Suorittaminen ja arvosanan määräytyminen

Kurssin suorittamiseksi on läpäistävä tentti (arvioidaan asteikolla 0-5) sekä laskettava riittävä määrä kotitehtäviä. Perustehtävät jakautuvat viiteen eri tehtäväsarjaan, joista jokaisesta on saatava vähintään 25% maksimipisteistä. Perustehtäväosuuden läpäisemiseksi on kuitenkin saatava vähintään 50% kaikkien tehtävien yhteenlasketuista maksimipisteistä, jolloin niistä saa arvosanan 1. Muut arvosanat määräytyvät sen mukaan, että 60% pisteistä antaa arvosanan 2, 70% pisteistä arvosanan 3, 80% pisteistä arvosanan 4 ja 90% pisteistä arvosanan 5.

Sovellustehtävät jakautuvat kolmeen tehtäväsarjaan. Ne arvioidaan asteikolla 0 (täydennettävä), 3 (hyväksytty), 4 (hyvä), 5 (kiittäen hyväksytty).

Kurssin kokonaisarvosana määräytyy seuraavasti:

jossa T on tentin arvosana, P perustehtävien arvosana ja S sovellustehtävien arvosana.

Projekti arvioidaan kokonaan erikseen ja se ei vaikuta kurssin arvosanaan, koska siitä tulee erilliset opintoviikot.

Mikäli kotitehtävistä jompi kumpi osuus ei tule hyväksytysti suoritettua kevään aikana, järjestetään kesän ja syyskuun aikana mahdollisuus täydentää suoritusta tekemällä rästitehtäviä. Rästitehtävillä ei voi kuitenkaan korottaa kotitehtäväosuuden arvosanaa siitä mikä kevään kurssilla arvosanaksi tuli.

Kotitehtävien ja projektin aikataulusta tiedotetaan erikseen. Ensimmäinen tentti on ma 18.5.98 ja kurssilaiset voivat osallistua kaikkiin ennen 1.5.99 pidettäviin tenteihin. Kaikkiin tentteihin, myös ensimmäiseen tenttiin, tulee ilmoittautua etukäteen TOPI-järjestelmän avulla, jotta salitilaa voidaan varata riittävästi.

Tämän sivun sisällöstä vastaavat/This page is maintained by kurssin assarit, E-mail: tik76122@hut.fi.
Sivua on viimeksi päivitetty/The page has been updated 01.07.1998.
URL: http://www.niksula.cs.hut.fi/~tik76122/k98/yleista/kurssiesite.html