Perustietorakenteet,kuten pinot, jonot, puut ja verkot, sekä niiden käsittelyalgoritmit.

Laskuharjoitusohjaukset pidetään pajamuotoisina ja osallistuminen niihin on vapaata. Voit ilmoittautua mihin tahansa laskuharjoitusryhmään riippumatta siitä, mihin ohjaustilaisuuksiin aiot osallistua.
International students, please contact the lecture before the course begins.

Ilmoittaudu
11.12.2017 klo 09:00 - 2.5.2018 klo 23:59

Aikataulu

Kurssi kestää koko kevätlukukauden (periodit III ja IV).

Luennot: ma, ke 10-12 A111

Kurssilla on kahden tyyppisiä viikoittaisia harjoitustehtäviä: Moodlessa tehtäviä tavanomaisia laskuharjoituksia ja TMC-järjestelmällä tehtäviä ohjelmointiharjoituksia. Kummankin tyyppisiin tehtäviin annetaan ohjausta pajamuotoisesti: opiskelija voi osallistua mihin ohjaustilaisuuksiin haluaa niin monta kertaa kuin katsoo aiheelliseksi. Ohjauksissa läsnäolo on täysin vapaaehtoista, ja harjoitustehtävistä saatavat pisteet määräytyvät tietokoneella palautetuista ratkaisuista.

Laskuharjoitusohjaukset (Moodle-tehtävät): ma 12-14 D123, ti 10-12 D123, ti 12-14 D122, ti 14-16 D123

Aiemmin ilmoitetusta poiketen ma 15.1. ja ti 16.1. ei ole laskuharjoitusohjauksia. Ensimmäiset Moodle-tehtävien ohjaukset ovat ma 22.1. ja ti 23.1., ja ensimmäisen tehtäväsarjan palautuksen määräaika on ke 24.1. klo 10.00.

Ohjelmointipajoista (TMC) ilmoitetaan erikseen kurssin TMC-sivulla https://www.cs.helsinki.fi/group/tirapaja/k18/.

PäivämääräAikaOpetuspaikka
Ma 15.1.2018
10:15 - 12:00
Ke 17.1.2018
10:15 - 12:00
Ma 22.1.2018
10:15 - 12:00
Ke 24.1.2018
10:15 - 12:00
Ma 29.1.2018
10:15 - 12:00
Ke 31.1.2018
10:15 - 12:00
Ma 5.2.2018
10:15 - 12:00
Ke 7.2.2018
10:15 - 12:00
Ma 12.2.2018
10:15 - 12:00
Ke 14.2.2018
10:15 - 12:00
Ma 19.2.2018
10:15 - 12:00
Ke 21.2.2018
10:15 - 12:00
Ma 26.2.2018
10:15 - 12:00
Ke 28.2.2018
10:15 - 12:00
Ma 12.3.2018
10:15 - 12:00
Ke 14.3.2018
10:15 - 12:00
Ma 19.3.2018
10:15 - 12:00
Ke 21.3.2018
10:15 - 12:00
Ma 26.3.2018
10:15 - 12:00
Ke 28.3.2018
10:15 - 12:00
Ma 9.4.2018
10:15 - 12:00
Ke 11.4.2018
10:15 - 12:00
Ma 16.4.2018
10:15 - 12:00
Ke 18.4.2018
10:15 - 12:00
Ma 23.4.2018
10:15 - 12:00
Ke 25.4.2018
10:15 - 12:00
Ma 30.4.2018
10:15 - 12:00
Ke 2.5.2018
10:15 - 12:00

Muu opetus

15.01. - 26.02.2018 Ma 12.15-14.00
12.03. - 26.03.2018 Ma 12.15-14.00
09.04. - 30.04.2018 Ma 12.15-14.00
Jyrki Kivinen
Opetuskieli: suomi
16.01. - 27.02.2018 Ti 10.15-12.00
13.03. - 27.03.2018 Ti 16.15-18.00
10.04. - 24.04.2018 Ti 16.15-18.00
Marcus Leivo
Opetuskieli: suomi
16.01. - 27.02.2018 Ti 12.15-14.00
13.03. - 27.03.2018 Ti 12.15-14.00
10.04. - 24.04.2018 Ti 12.15-14.00
Hannu Kärnä
Opetuskieli: suomi
16.01. - 27.02.2018 Ti 14.15-16.00
13.03. - 27.03.2018 Ti 14.15-16.00
10.04. - 24.04.2018 Ti 14.15-16.00
Joonas Sarapalo
Opetuskieli: suomi
22.01. - 26.02.2018 Ma 16.15-18.00
12.03. - 26.03.2018 Ma 16.15-18.00
09.04. - 30.04.2018 Ma 16.15-18.00
Opetuskieli: suomi

Materiaalit

Kurssin luento- ja harjoitusmateriaalit ilmestyvät ensisijaisesti Moodleen. Kurssiin liittyy myös TMC-järjestelmällä tehtäviä ohjelmointiharjoituksia. Tarkemmat ohjeet löytyvät kurssin Moodle-alueelta.

Kurssimateriaalia voi selata Moodle-alueella vierailijana ilman rekisteröitymistä, mutta kurssille osallistuminen edellyttää rekisteröitymistä erikseen myös Moodle-alueelle.

Kurssin sisältö ja esitystapa perustuvat kirjaan
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 3rd ed., MIT Press, 2009.
Tämä kirja on erittäin suositeltava oheislukemisto, mutta kurssi ei täysin noudata sitä. Kokeissa ym. edellytettävä materiaali määräytyy Moodlessa julkaistavien luentomateriaalien mukaan.

Muu

Kurssin suorittaminen

Kurssiin kuuluu kaksi pakollista kurssikoetta. Kokeet ovat periodien III ja IV koeviikoilla. Tarkista kokeiden tarkempi ajankohta laitoksen koeaikataulusta. Kokeessa saa olla mukana yhdelle A4-arkille itse käsin kirjoitettu "lunttilappu", jonka molemmilla puolilla saa olla tekstiä. Kokeiden lisäksi kurssisuoritukseen kuuluu harjoitustehtävien tekeminen.

Kurssin maksimipistemäärä on 60 ja jakautuu osasuorituksille seuraavasti:
a) kaksi kurssikoetta: kumpikin 22 pistettä, eli yhteensä 44 pistettä
b) tavalliset laskuharjoitukset: 8 pistettä
c) ohjelmointitehtävät (TMC): 8 pistettä.
Kurssin hyväksyttyyn suoritukseen vaaditaan noin 30 pistettä ja korkeimpaan arvosanaan 5/5 vaaditaan noin 50 pistettä. Lisäksi hyväksymiseen vaaditaan, että kahden kurssikokeen yhteispistemäärä on vähintään 22 (eli puolet maksimista). Laskuharjoitukset eivät ole pakollisia, mutta parhaisiin arvosanoihin pääseminen edellyttää luonnollisesti, että myös harjoituksista saa pisteitä.

Ohjelmointitehtävät tehdään TMC-järjestelmällä ja tarkastetaan automaattisesti. Tavallisest laskuharjoitustehtävät palautetaan sähköisessä muodossa Moodleen ja arvostellaan siellä. Tehtäviä on tarjolla enemmän kuin mitä tarvitaan maksimipistemäärään (8+8 pistettä). Tarkemmat ohjeet tehtävien palauttamisesta, pisteytyksestä jne. tulevat Moodleen.

Sekä ohjelmointitehtävien että tavallisten laskuharjoitusten ohjaus järjestetään pajamuotoisesti. Läsnäolo ei ole pakollista. Opiskelija voi oman harkintansa mukaan olla osallistumatta ohjaukseen tai käydä yhdessä tai useammassa ryhmässä. Ohjausajat on ilmoitettu kohdassa "Aikataulu".

Palaute

Tietorakenteet ja algoritmit, kevät 2018
Yhteenveto opiskelijapalautteesta ja muita kommentteja

1. Tilastoja

Kurssin eri osiin osallistui opiskelijoita seuraavasti:
- ilmoittautuneita: 261
- Moodle-tehtävät: 257 (jostain tehtävästä saatu pisteitä)
- TMC-tehtävät: 258 (ainakin yksi tehtävä ratkaistu)
- 1. kurssikoe: 161
- 2. kurssikoe: 136.
Kurssin hyväksytysti suorittaneita opiskelijoita oli 119.
Arvosanajakauma oli
- 5/5: 26 opiskelijaa
- 4/5: 28 opiskelijaa
- 3/5: 20 opiskelijaa
- 2/5: 23 opiskelijaa
- 1/5: 22 opiskelijaa.

2. Yhteenveto opiskelijapalautteesta

Palautetta kerättiin kurssin lopuksi tietojenkäsittelytieteen
oletusarvoisella kyselylomakkeella. Vastauksia tuli 51. Tämä on
kohtuullinen määrä, mutta kurssin osallistujamäärään nähden voisi olla
suurempikin. Mahdollisesti kurssin arvostelun viivästyminen
(Moodle-tehtävien tarkastamisen takia) on vähentänyt vastaajien
määrää. Vastauksissa oli monivalintavastausten lisäksi ilahduttavan
paljon vapaamuotoisia kommentteja. Palautteen keräysmenettelyn takia
on luultavaa, että palautetta on tullut lähinnä kurssin loppuun asti
aktiivisesti mukana pysyneiltä.

Lomakkeen numeeristen kysymysten vastausten keskiarvot olivat
- kurssin tavoitteet olivat selvät: 3,9
- materiaali tuki oppimistavoitteiden saavuttamista: 3,5
- toiminta kurssilla tuki oppimistavoitteiden saavuttamista: 3,5
- arviointi mittasi tavoitteiden saavuttamista: 3,8
- kurssi oli työläs: 4,8
- kokonaisarvosana: 3,7.
Kokonaisarvosana annettiin asteikolla 1-5. Muissa kohdissa vastaus 1
tarkoitti "olen eri mieltä" ja 5 "olen samaa mieltä" annetusta
väitteestä.

Myös vapaamuotoisessa palautteessa korostui kurssin työläys. Sekä
tehtävien vaikeusettä määrä mainittiin työmäärää lisäävinä. Etenkin
TMC-tehtäviin toivottiin enemmän perustehtäviä ja loivempaa
vaikeustason nousukäyrää. Muuten tehtävät ja kurssin muukin sisältö
koettiin kiinnostavaksi ja hyödylliseksi.

Luennoista ja luentomateriaalista tuli sekä myönteistä että kielteistä
palautetta. Luennoista toivottiin enemmän konkreettista apua sen
tyyppiseen ongelmanratkaisuun, mitä etenkin TMC-tehtävissä tarvittiin.
Luentomateriaalia pidettiin yleisesti ottaen riittävän hyvänä.

3. Luennoijan kommentit

Kurssin kokeminen työlääksi oli tiedossa kurssin aiemmilta
luennointikerroilta. Aiempaan verrattuna kurssin opintopistemäärä oli
nostettu kahdeksasta kymmeneen niin, että kurssin sisältöä oli
kasvatettu lähinnä ottamalla joitain kurssin loppupuolella aiemmin
ylikurssina esitettyjä asioita mukaan varsinaiseen kurssialueeseen.
Kurssin todellista työmäärää yritettiin arvioida vapaaehtoisen
viikoittaisen kyselyn avulla, mutta vastaajamäärä jäi pieneksi etenkin
ensimmäisen viikon jälkeen. Kyselyssä ilmoitetut tuntimäärät olivat
keskimäärin noin 15 prosenttia yli opintopistemäärän mukaan arvioidun
viikoittaisen työmäärän. Opiskelijat olivat käyttäneet huomattavan
suuren osan ajasta TMC-tehtäviin, ja tulostakin tästä oli syntynyt,
sillä vastanneet olivat keskimäärin tehneet jopa jonkin verran enemmän
TMC-tehtäviä kuin arvosanatasoa 5/5 vastaavat neljä tehtävää viikossa.

TMC onkin formaattina varmaan paljon koukuttavampi kuin Moodle tai
luennot. Vaikka TMC on myös erittäin opettavainen työkalu, kurssin
päätavoitteiden saavuttamiseksi kohtuullisella työmäärällä voisi olla
hyvä siirtää ajankäytön painopistettä hieman pois TMC:stä. Ei ole
ihan selvää, miten tämä toteutettaisiin. Nykyiset TMC-tehtävät
painottuvat tarkotuksella algoritmiseen ongelmanratkaisuun Javan
valmiita ratkaisuja hyödyntäen. Kurssilla pseudokoodina esitettyjen
algoritmien suoran kääntämisen Javalle ei ole ajateltu olevan kovin
keskeinen kurssilla harjoiteltava asia; ehkä tämäkin vaatisi vielä
enemmän opiskelua, kun pohjana oletetaan vain ohjelmoinnin perus- ja
jatkokurssi. TMC-tehtävät eivät kuitenkaan edellytä erityisen
tehokasta Java-toteutusta: jos perusalgoritmi on oikein, niin minkä
tahansa järkevän Java-toteutuksen pitäisi toimia vaaditussa ajassa.
(Pari opiskelijaa oli kommentoinut, että aikarajan saavuttaminen oli
vaatinut kohtuuttomasti koodin optimointia. Opettajien kanssa tästä
keskustellessa emme keksineet, mistä tässä voisi johtua, ellei se
sitten liity TMC-palvelimen oikuttelemiseen ylikuormituksen takia.)

Harjoitustehtäviin liittyvä konkreettinen ohjaus ongelmanratkaisussa
on kurssin nykyisessä formaatissa suunniteltu tapahtuvaksi pajoissa,
ei luennoilla. Tämä tuntuu toimivan melko huonosti, koska
ohjaustilaisuuksissa käy vain hyvin pieni osa opiskelijoista, vaikka
tehtävät koetaankin vaikeaksi. Tästä on keskusteltu paljon opettajien
kesken, mutta kukaan ei ole keksinyt, mikä systeemissä on vikana.
Syksyllä on tarkoitus kokeilla hieman toisenlaista järjestelyä:
otsikolla "Algoritmipaja" annetaan aina (suunnilleen) samaan aikaan
samassa paikassa ohjausta ja ryhmätyöskentelyä yhteisesti kaikille
algoritmipuolen peruskursseille (Tietorakenteet ja algoritmit,
Laskennan mallit, mahdollisesti Design and Analysis of Algorithms).

Kurssimateriaalissa on tapahtumassa merkittävä parannus, kun Antti
Laaksosen laatima suomenkielinen kurssikirja on nyt saatavilla
osoitteessa https://github.com/pllk/tirakirja . Kirja on ensimmäistä
kertaa käytössä syksyn 2018 kurssilla, joten siihen varmaan tulee
päivityksiä ja lisäyksiä kokemusten kertyessä.

Asiaa ei juuri sivuttu tämänkertaisissa opiskelijapalautteissa, mutta
muissa keskusteluissa tulee säännöllisesti esille kurssin jakaminen
kahteen osaan sekä koealueen jakaminen useampaan minitenttiin.
Minitentit ovat pitkälti järjestelykysymys, jota voidaan harkita
tulevilla luennointikerroilla. Kurssin jakaminen puolestaan
edellyttäisi muutosta tutkinnon rakenteeseen, joka juuri syksyllä 2017
uusittiin kokonaan. Kurssin nykyiseen muotoon päädyttiin pitkän
harkinnan ja keskustelujen jälkeen katsottiin palvelevan parhaiten
sitä, että opiskelijat suorittavat koko kurssi heti ensimmäisenä
opiskeluvuonna. Myös pilkkomisella on etunsa, mutta asia on
ajankohtainen aikaisintaan seuraavan opetussuunnitelman muutoksen
yhteydessä.

Helsingissä 19. elokuuta 2018
Jyrki Kivinen

Kuvaus

  • Tietojenkäsittelytieteen kandiohjelma vastaa opintojaksosta
  • Opintojakso kuuluu tietojenkäsittelytieteen aineopintoihin (pakollinen oman koulutusohjelman opiskelijoille)
  • Opintojakso on tarjolla myös muiden koulutusohjelmien opiskelijoille

Esitietovaatimuksena on Ohjelmoinnin perus- ja jatkokurssi sekä Johdatus yliopistomatematiikkaan, tai vastaavat tiedot.

Opintojaksolla opittuja menetelmiä sovelletaan opintojaksolla Aineopintojen harjoitustyö: Tietorakenteet ja algoritmit.

Opintojakson jälkeen opiskelija

  • osaa laatia algoritmeja soveltaen opintojaksolla esitettyjä perustekniikoita ja tietorakenteita sekä toteuttaa ne Java-kielellä
  • osaa analysoida algoritmin aika- ja tilavaativuutta O-merkinnän avulla ja perustella algoritmin oikeellisuuden esim. silmukkainvarianttia käyttäen
  • tuntee yksityiskohtaisesti erilaisten hakemistorakenteiden toteutukset
  • osaa toteuttaa tärkeimmät järjestämisalgoritmit ja tuntee niiden aikavaativuudet
  • tuntee verkkojen peruskäsitteet ja osaa toteuttaa tärkeimmät polunetsintään ja virittäviin puihin liittyvät algoritmit
  • käyttää opintojaksolla esitettyjä peruskäsitteitä (esim. hakemistot, verkot, järjestäminen) osana monimutkaisempien laskennallisten ongelmien ratkaisua ja valita tunnetuista algoritmeista tilanteeseen sopivan esim. aikavaativuuden perusteella

Ensimmäisen opiskeluvuoden kevätlukukausi

Opintojakso pidetään joka kevät koko lukukauden mittaisena (periodit III-IV). Opintojakso voidaan lisäksi järjestää muinakin ajankohtina esim. itseopiskeluversiona.

Opintojakson tarkempaa sisältöä päivitetään tarpeen mukaan. Keskeisiä aihealueita ovat esim.

  • algoritmien suunnittelun ja analyysin perustekniikoita: rekursio, silmukkainvariantti, iso-O-merkintä, iteratiivisten ja rekursiivisten algoritmien aika- ja tilavaativuus
  • järjestämisalgoritmit: lisäysjärjestäminen, lomitusjärjestäminen, pikajärjestäminen
  • perustietorakenteet: pino, jono, lista
  • hakemistorakenteet: hajautustaulu, hakupuut
  • verkot eli graafit: peruskäsitteet, polunetsintä, virittävät puut

Opintojakso perustuu laitoksella laadittuun luentomateriaallin. Suositeltu oheislukemisto on Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms.

Opiskelja tutustuu opintojakson aiheisiin luennoilla ja perehtymällä itsenäisesti opintojakson materiaaliin, oheislukemistoon ja esim. verkosta löytyvään lisämateriaaliin. Opiskelija syventää osaamistaan tekemällä muodoiltaan ja vaativuudeltaan vaihtelevia harjoitustehtäviä, mitä tuetaan ohjatuilla harjoitustilaisuuksilla.

Sekä harjoitustehtävät että kirjalliset kuulustelut otetaan arvostelussa huomioon. Kuulusteluilla on suurin vaikutus arvosanaan, mutta hyväksytty suoritus edellyttää myös ennalta ilmoitetun vähimmäismäärän tehtyjä harjoitustehtäviä.

Arvosteluasteikko on 1-5.

Opintojaksoon kuuluu luentoja, laskuharjoituksia ja kirjallisia kuulusteluja. Laskuharjoituksia voidaan tehdä itsenäisesti, pienryhmässä tai opettajan ohjaamassa tilaisuudessa. Osa harjoituksista voi olla tietokoneella suoritettavia ohjelmointitehtäviä. Harjoitustilaisuuksissa on läsnäolovelvollisuus silloin, kun tilaisuuden muoto edellyttää sitä.

Vaihtoehtoisesti opintojakson voi suorittaa erilliskokeella, jolloin siihen kuuluu ainoastaan kirjallinen kuulustelu.