Yliopiston etusivulle Suomeksi På svenska In English
Helsingin yliopisto Tietojenkäsittelytieteen laitos
 

Tietojenkäsittelytieteen laitos

58131 Tietorakenteet (4 ov) syksy 2004

Sivua muutettu viimeksi Jan 30, 2005

0. Ajankohtaista

  • 21.1.05 pidetyn erilliskokeen tulokset

  • Kurssin tulokset
  • Tarkempi pistejakauma: ps pdf
  • Arvosteluperusteita: teht 1,, teht 2, teht 3. teht 4

  • 1. Asema opetuksessa

    Kurssi on cum laude approbatur -tason pakollinen neljän (4) opintoviikon luentokurssi, joka kestää koko lukukauden.

    Esitietoina vaaditaan ohjelmointitaidon alkeet jollakin ohjelmointikielellä kurssin Java-ohjelmointi laajuudessa.

    Kielen ei siis tarvitse olla Java, kurssi on kieliriippumaton.

    2. Kurssin sisältö

  • Johdanto (1 viikko)
  • mitä tarkoitetaan tietorakenteella
  • algoritmin oikeellisuuden osoittaminen
  • algoritmin vaativuuden analysointi
  • vaativuusfunktioiden kertaluokat
  • Perustietorakenteet (1 viikko)
  • lista, pino ja jono
  • periaate tietorakenteen toteuttamiseen linkitettynä rakenteena
  • hakupuut (3 viikkoa)
  • binäärihakupuut
  • tasapainoitetut puut (puna-musta-puu)
  • hajautus (1 viikko)
  • hajautusfunktion valinta
  • yhteentörmäysstrategiat
  • keko (1 viikko)
  • täydellinen binääripuu taulukkona
  • keko-operaatiot
  • prioritettijono
  • järjestäminen (2 viikkoa)
  • lomitusjärjestäminen
  • kekojärjestäminen
  • pikajärjestäminen
  • järjestelyn alaraja
  • laskemisjärjestäminen
  • lokerikkojärjestäminen
  • verkot (3 viikkoa)
  • verkon määritelmä ja toteutus
  • verkkojen läpikäyntialgoritmit
  • lyhimmät polut
  • virittävä puu
  • 3. Kurssin suorittaminen

    Kurssin suoritus koostuu kahdesta kurssikokeesta ja aktiivisesta osallistumisesta laskuharjoituksiin. Kokeissa ja laskuharjoituksissa käsitellään luennoilla esitettyjä asioita.

    Kurssikokeet on merkitty tällä sivulla olevaan aikatauluun. Koealue käsittää siihen mennessä käsitellyt asiat. Ne ilmoitetaan tällä sivulla myöhemmin.

    Kurssin voi suorittaa myös erilliskokeella. Erilliskokeen vaatimukset ovat aina viimeisimmän päättyneen luennointikerran mukaiset.

    3.1. Luennot

    Kurssilla on luentoja 14.9.-2.12. tiistaisin ja torstaisin 10-12 auditoriossa.

    Luennoijana on Matti Luukkainen.

    3.2. Laskuharjoitukset

    Kurssiin liittyy pakollisia laskuharjoituksia ajalla 20.9.- 10.12. Katso ajat opetusohjelmasta

    Tehtäviä (ryhmäharjoitustehtävät) käsitellään ohjatuissa pienryhmissä. Ensimmäisessä laskuharjoitustilaisuudessa tilaisuuteen ilmoittautuneista muodostetaan (noin) neljän  hengen pienryhmiä, joiden on tarkoitus toimia yhdessä koko kurssin ajan. Kukin ryhmä on yhteisvastuussa siitä, että se saa tehtävät ratkaistua! Tämä vaatinee pienryhmältä tapaamisia (ellei fyysisesti niin ainakin virtuaalisesti) myös laskuharjoitustilaisuuksien välillä.

    Tästä seuraa, että muissa laskuharjoitustilaisuuksissa ei voi vierailla. Kurssiin sisältyy myös "vanhan tyylin" laskareita (yksilöharjoitustehtävät) eli itsenäisesti ratkaistavia tehtäviä.

    Ryhmätehtäviä käsitellään noin kolmen viikon jaksoissa seuraavasti:

    1. Edellisen luentoviikon päätteeksi luennoija jakaa seuraavat ryhmätehtävät tämän verkkosivun kautta.

    2. Ensimmäisen ja toisen viikon laskuharjoitustilaisuudessa kukin ryhmä ratkoo edellisen viikon päätteeksi saamiaan tehtäviä yhdessä. Laskuharjoitusassistentti on paikalla auttamassa.

    3. Tämän lisäksi laskuharjotuksissa käydään normaaliin tapaan läpi mahdolliset yksilöllisesti tarkaistavat tehtävät

    4. Kolmannen viikon laskuharjoitustilaisuudessa ryhmät esittelevät ratkaisujaan toisilleen ja niistä keskustellaan.

      Lisäksi ryhmät palauttavat ratkaisunsa myös kirjallisesti laskuharjoitusassistentille. Assistentti arvioi näiden kirjallisten ratkaisujen perusteella, montako pistettä (0-3) ryhmä tältä kierrokselta saa.

      Pisteytyksen perusteena on, kuinka kelvollisen suullisen esityksen ryhmä olisi voinut tilaisuudessa antaa muille ryhmille. Ryhmä voi tutustua saamiinsa pisteisiin seuraavassa tilaisuudessa.

      Ryhmäläiset arvioivat kirjallisesti myös oman ryhmänsä toimintaa.

      Tämä tehdään siten, että ryhmä kirjoittaa kirjallisten ratkaisujensa loppuun arvion ryhmän toiminnasta tällä kierroksella. Arvioitiohje.

    Kurssin lopuksi laskuharjoitusassistentti pisteyttää (0-2 p.) ryhmän kaikki kurssin aikana tekemät arviot. Nämä pisteet vaikuttavat suoraan arvosteluun. Pisteytyksen perusteena on, kuinka asianmukaisesti ryhmä on arvionsa laatinut.

    Lisäksi, kurssin lopuksi jokainen opiskelija arvioi oman ryhmänsä toiminnan antaen arvosanan kullekin ryhmän jäsenelle itsensä mukaanlukien

    3.3. Arvostelu

    Kurssi pisteytetään ja arvostellaan seuraavasti:

  • 1. kurssikoe 21 p
  • 2. kurssikoe 25 p
  • laskuharjoitukset 12 p
  • yksilötehtävät 4 p
  • ryhmätehtävät 8 p
  • ryhmätehtäviin osallistuvien kohdalla aktiivisuus/passiivisuus +/-2
  • ryhmien kirjalliset arviot 2 p
  • 3.4. Suoritus erilliskokeella

    Tämä luentokurssi on mahdollista suorittaa myös erilliskokeella. Jokaisessa erilliskokeessa tentitään kurssi sellaisena, kuin se pidettiin edellisellä päättyneellä luentokerralla. Eri luentokerrat lienevät tosin sisällöiltään ja vaatimuksiltaan samankaltaiset. Tarkemmat erilliskoeajat selviävät kyseisen lukukauden erilliskoelistasta.

    4. Kurssimateriaali

    Kurssimateriaali koostuu

    • Kurssin kuluessa syntyvistä luentokalvoista, jotka luennoija jakaa tämän verkkosivun ja luentomapin kautta kunkin luentoviikon aluksi
    • Timo Karvin tekemästä luentomuistiinpanoista, jonka voi ostaa laitoksen monistemyynnistä ja
    • Oppikirjasta T.H.Cormen, C.E.Leiserson, R.L.Rivest ja C.Stein: Introduction to Algorithms. Second Edition. The MIT Press, 2001.
    • Hyötyä voi olla myös edellisten Tira-kurssien materiaaleista, ks. Syksy 03, Kevät 03
    • Muitakin tietorakenne-aiheisia kirjoja voi toki vilkaista, esim.
    • J.H.Kingston: Algorithms and data structures : design, correctness, analysis
    • M.A.Weiss: Data structures and algorithm analysis ja Data structures and problem solving using Java
    • A.V. Aho, J.E. Hopcroft., J.D. Ullman: Data structures and algorithms
    • A.Levitin:Introduction to the design & analysis of algorithms
    • Internetistä löytyy esim. hakusanalla data structures valtava määrä materiaalia, ohessa muutama hyödylliseksi todettu linkki:
    • 2-3-4-puusimulaattori
    • Dijkstra-simulaattori
    • MatrixPro a tool for instructors to create algorithm animations used in teaching
    • TRAKLA2 an automatic exercise system for learning data structures and algorithms

    5. Aikataulu

    aika asiat
    viikko 1, 13-27.9

  • Luentojen aiheena johdanto tietorakenteisiin sekä algoritmin oikeellisuuden sekä vaativuuden osoittamiseen

  • Luentokalvot 1-21 (pdf)
  • Karvi 2002, Luku 1
  • Cormen et all 2001., Chapters 2.1-2.2 and 3.

  • Yksilölaskari 1 (pdf)
  • Ryhmälaskari I (pdf)
  • Exercise 1 (pdf)
  • Group exercise I (pdf)

  • viikko 2, 20-24.9

  • Luentojen aiheena Pino, jono ja linkitetty lista

  • Luentokalvot 22-45 (pdf)
  • Karvi 2002, Luvut 3 ja 4
  • Cormen et all 2001., Chapters 10.1-10.2

  • Pienryhmät muodostetaan laskuharjoituksissa
  • 1. yksilöharjoitustehtävät käydään läpi
  • I ryhmäharjoitustehtäviä ratkotaan

  • viikko 3,  27.9-1.10

  • Luentojen aiheena Binäärihakupuut

  • Luentokalvot 46-66: (2/sivu)   (4/sivu)   (pdf)
  • Karvi 2002, Luvut 5.2, 5.3.2 ja 8.2, 8.3.2-8.3.4
  • Cormen et all 2001., Chapters 12.1-12.3

  • I ryhmäharjoitustehtävät käydään läpi

  • Yksilölaskari 2 (pdf)
  • Ryhmälaskari II (pdf)
  • Exercise 2 (pdf)
  • Group exercise II (pdf)

  • viikko 4,  4-8.10

  • Luentojen aiheena Punamustat puut

    Luentokalvot 67-84: (2/sivu)   (4/sivu)   (pdf)

  • Karvi 2002, Luvut 8.4.1-8.4.2
  • Cormen et all 2001., Chapters 13.1-13.3

  • 2. yksilöharjoitustehtävät käydään läpi
  • II ryhmäharjoitustehtävien ratkaiseminen aloitetaan

  • Yksilölaskari 3 (pdf)
  • Exercise 3 (pdf)

  • viikko 5, 11-15.10

  • Luentojen aiheena edelleen Punamustat puut sekä muita puiden sovelluksia

    Luentokalvot 85-106: (2/sivu)   (4/sivu)   (pdf)

  • Karvi 2002, Luvut 8.4.4, 5.3.3, 5.4.1
  • Cormen et all 2001., Chapter 13.4, 10.4

  • 3. yksilöharjoitustehtävät käydään läpi
  • II ryhmäharjoitustehtävien ratkaisemista jatketaan

  • Yksilölaskari 4 (pdf)
  • Exercise 4 (pdf)

  • viikko 6, 18-22.10

  • Luennoilla aiheina puu-rakenteen soveltaminen ongelmanratkaisuun, sekä pelipuut, torstain luennolla myös kertausta kokeeseen

    Luentokalvot 107-123: (2/sivu)   (4/sivu)   (pdf)

  • Karvi 2002, Luvut 5.6

  • 4. yksilöharjoitustehtävät käydään läpi
  • II ryhmäharjoitustehtävän kohdat 1 ja 2 käydään läpi

  • viikko 7, 25-29.10

  • Luennoilla aiheina hajautusrakenteet

    Luentokalvot 124-148: (2/sivu)   (4/sivu)   (pdf)

  • Karvi 2002, Luku 9
  • Cormen et all 2001., Chapter 11.2-11.4

  • II ryhmäharjoitustehtävän kohta 3 käydään läpi

  • Yksilölaskari 5 (pdf)
  • Ryhmälaskari III (pdf)
  • Exercise 5 (pdf)

  • Ensimmäinen kurssikoe /first course exam
    ti 26.10. klo 16-20 päärak. suuri luentosali

  • viikko 8, 1-5.11

  • Luennoilla aiheina keko

  • Luentokalvot 149-168: (2/sivu)   (4/sivu)   (pdf)
  • Karvi 2002, Luku 6.3 ja 6.4
  • Cormen et all 2001., Chapter 6.1-6.5

  • 5. yksilöharjoitustehtävät käydään läpi
  • III ryhmäharjoituksia ratkaistaan

  • Yksilölaskari 6 (pdf)
  • Exercise 6 (pdf)

  • Ylimääräinen, vapaaehtoinen ryhmälaskari (pdf)

  • viikko 9, 8-12.11

  • Luennoilla aiheina järjestäminen

  • Luentokalvot 169-191: (2/sivu)   (4/sivu)   (pdf)
  • Karvi 2002, Luku 6.1, 6.2, 6.5, 6.6
  • Cormen et all 2001., Chapter 2.3, 7.1-7.2, 8.1-8.4

  • 6. yksilöharjoitustehtävät käydään läpi
  • III ryhmäharjoituksia ratkaistaan

  • viikko 10, 15-19.11

  • Luennoilla aiheina verkkojen määritelmä, toteutus sekä läpikäynti

  • Luentokalvot 192-216: (2/sivu)   (4/sivu)   (pdf)
  • Karvi 2002, Luku 9.1-9.4
  • Cormen et all 2001., Appendix B.4, Chapters 22.1-22.4

  • III ryhmäharjoitukset käydään läpi

  • Yksilölaskari 7 (pdf)
  • Ryhmälaskari IV (pdf)
  • Exercise 7 (pdf)
  • Group exercise 4: ask your group members for translation!

  • viikko 11, 22-26.11

  • Luennoilla aiheina lyhimmät polut

  • Luentokalvot 217-240: (2/sivu)   (4/sivu)   (pdf)
  • Karvi 2002, Luku 9.4
  • Cormen et all 2001., Chapter 24.2.-24.3, 25.2

  • 7. yksilöharjoitustehtävät käydään läpi
  • IV ryhmäharjoituksia ratkaistaan

  • Yksilölaskari 8 (pdf)
  • Exercise 8 (pdf)

  • viikko 12, 29.11-3.12

  • Luennoilla aiheina verkot virittävät puut
  • torstaina ei luentoa

  • Karvi 2002, Luku 9.5
  • Cormen et all 2001., Chapter 23

  • 8. yksilöharjoitustehtävät käydään läpi
  • IV ryhmäharjoituksia ratkaistaan

  • Yksilölaskari 9 (pdf)
  • Exercise 9 (pdf)

  • viikko 13, 6-10.12

  • tiistaina ei luentoa
  • torstaina 10-12 kertausluento

  • 9. yksilöharjoitustehtävät käydään läpi
  • IV ryhmäharjoitukset käydään läpi

  • viikko 14, 13-17.12

  • Toinen kurssikoe Torstaina 16.12. klo 16-20 Exactumin salissa A111, huom: koeaika 3.5 tuntia

  • Tätä sivua ylläpitää luentojen ajan kurssin luennoija Matti Luukkainen.



    Laitoksen etusivulle | Tiedekunnan etusivulle | Yliopiston etusivulle
    Laitoksen yhteystiedot | Palaute laitokselle | Ulkonäköasetukset