58131 Tietorakenteet (4 ov) kevät 2004

Sivua muutettu viimeksi Sep 03, 2004

0. Ajankohtaista

4.6.2004 pidetyn erilliskokeen tulokset

Kurssin tulokset

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. Näin ollen tämän luennointikerran mukaisia erilliskokeita järjestetään kesällä 2004.

3.1. Luennot

Kurssilla on luentoja 19.1.-7.4. maanantaisin ja keskiviikkoisin 14-16 auditoriossa.

Luennoijana on Matti Luukkainen.

3.2. Laskuharjoitukset

Kurssiin liittyy pakollisia laskuharjoituksia ajalla 26.01.- 23.04. 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:

Edellisen luentoviikon päätteeksi luennoija jakaa seuraavat ryhmätehtävät tämän verkkosivun kautta.
Ensimmäisen ja toisen viikon laskuharjoitustilaisuudessa kukin ryhmä ratkoo edellisen viikon päätteeksi saamiaan tehtäviä yhdessä. Laskuharjoitusassistentti on paikalla auttamassa.
Tämän lisäksi laskuharjotuksissa käydään normaaliin tapaan läpi mahdolliset yksilöllisesti tarkaistavat tehtävät
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 22 p

2. kurssikoe 24 p

laskuharjoitukset 12 p (yksilötehtävien pisteet ja ryhmäpisteet +/-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 (verkossa).

4. Kurssimateriaali

Kurssimateriaali koostuu

Timo Karvin tekemästä luentomuistiinpanoista, jonka voi ostaa laitoksen monistemyynnistä
Kurssin kuluessa syntyvistä luentokalvoista, jotka luennoija jakaa tämän verkkosivun ja luentomapin kautta kunkin luentoviikon aluksi
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:
Java models binääripuusimulointiin
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 4, 19-23.1

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)

viikko 5, 26-30.1

Luentojen aiheena Pino, jono ja linkitetty lista

Luentokalvot 22-42 (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 6,     2-6.2

Luentojen aiheena Binäärihakupuut

Luentokalvot 43-63 (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)

viikko 7,   9-13.2

Luentojen aiheena Punamustat puut

Luentokalvot 64-81 (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)

viikko 8, 16-20.2

Luentojen aiheena edelleen Punamustat puut sekä muita puiden sovelluksia

Luentokalvot 82-103 (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

viikko 9, 23-27.2

Luennoilla aiheina mm. puu-rakenteen soveltaminen ongelmanratkaisuun, sekä pelipuut

Luentokalvot 104-120 (pdf)
Karvi 2002, Luvut 5.6

II ryhmäharjoitustehtävät käydään läpi

Yksilölaskari 4 (pdf)

viikko 10,    1-5.3

Luennoilla aiheina hajautusrakenteet

Luentokalvot 121-145 (pdf)
Karvi 2002, Luku 9
Cormen et all 2001., Chapter 11.2-11.4

4. yksilöharjoitustehtävät käydään läpi

Yksilölaskari 5 (pdf)

Ensimmäinen kurssikoe perjantaina 5.3. 16-20 Päärakennuksen salissa 1
Kokeen tulokset
Arvosteluperusteita ja ratkaisuja: teht 1,, teht 2, teht 3. teht 4

viikko 11, 8-12.3

Luennoilla aiheina keko

Luentokalvot 146-165 (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

Yksilölaskari 6 (pdf)
Ryhmälaskari 3 (pdf)

viikko 12, 15-19.3

Luennoilla aiheina järjestäminen

Luentokalvot 166-188 (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 13, 22-26.3

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

Luentokalvot 189-213 (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 4 (pdf)

viikko 14, 29.3-2.4

Luennoilla aiheina lyhimmät polut

Luentokalvot 214-237 (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)

viikko 15,    5-7.4

Luennoilla aiheina verkot virittävät puut
HUOM: keskiviikkona 7.4. ei ole 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)

8-14.4 pääsiäisloma, ei opetusta

viikko 16, 15-16.4

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

viikko 17, 19-23.4

Keskiviikkona 21.4. klo 14-16 Auditoriossa kertausluento

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

viikko 18

Toinen kurssikoe tiistaina 27.4. klo 16-20 Porthania I -salissa,
huom: koeaika 3.5 tuntia
Arvosteluperusteita ja ratkaisuja: teht 1 teht 2, teht 3, teht 4

aika	asiat
viikko 4, 19-23.1	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)
viikko 5, 26-30.1	Luentojen aiheena Pino, jono ja linkitetty lista Luentokalvot 22-42 (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 6, 2-6.2	Luentojen aiheena Binäärihakupuut Luentokalvot 43-63 (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)
viikko 7, 9-13.2	Luentojen aiheena Punamustat puut Luentokalvot 64-81 (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)
viikko 8, 16-20.2	Luentojen aiheena edelleen Punamustat puut sekä muita puiden sovelluksia Luentokalvot 82-103 (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
viikko 9, 23-27.2	Luennoilla aiheina mm. puu-rakenteen soveltaminen ongelmanratkaisuun, sekä pelipuut Luentokalvot 104-120 (pdf) Karvi 2002, Luvut 5.6 II ryhmäharjoitustehtävät käydään läpi Yksilölaskari 4 (pdf)
viikko 10, 1-5.3	Luennoilla aiheina hajautusrakenteet Luentokalvot 121-145 (pdf) Karvi 2002, Luku 9 Cormen et all 2001., Chapter 11.2-11.4 4. yksilöharjoitustehtävät käydään läpi Yksilölaskari 5 (pdf) Ensimmäinen kurssikoe perjantaina 5.3. 16-20 Päärakennuksen salissa 1 Kokeen tulokset Arvosteluperusteita ja ratkaisuja: teht 1,, teht 2, teht 3. teht 4
viikko 11, 8-12.3	Luennoilla aiheina keko Luentokalvot 146-165 (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 Yksilölaskari 6 (pdf) Ryhmälaskari 3 (pdf)
viikko 12, 15-19.3	Luennoilla aiheina järjestäminen Luentokalvot 166-188 (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 13, 22-26.3	Luennoilla aiheina verkkojen määritelmä, toteutus sekä läpikäynti Luentokalvot 189-213 (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 4 (pdf)
viikko 14, 29.3-2.4	Luennoilla aiheina lyhimmät polut Luentokalvot 214-237 (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)
viikko 15, 5-7.4	Luennoilla aiheina verkot virittävät puut HUOM: keskiviikkona 7.4. ei ole 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)
	8-14.4 pääsiäisloma, ei opetusta
viikko 16, 15-16.4	8. yksilöharjoitustehtävät käydään läpi IV ryhmäharjoituksia ratkaistaan
viikko 17, 19-23.4	Keskiviikkona 21.4. klo 14-16 Auditoriossa kertausluento 9. yksilöharjoitustehtävät käydään läpi IV ryhmäharjoitukset käydään läpi
viikko 18	Toinen kurssikoe tiistaina 27.4. klo 16-20 Porthania I -salissa, huom: koeaika 3.5 tuntia Arvosteluperusteita ja ratkaisuja: teht 1 teht 2, teht 3, teht 4

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