Tietorakenteet

58131
8-10
Algoritmit ja koneoppiminen
Aineopinnot
Perustietorakenteet kuten pinot, jonot, puut ja verkot sekä niiden käsittelyalgoritmit. Esitiedot: Ohjelmoinnin jatkokurssi (Java-ohjelmointi) ja Johdatus yliopistomatematiikkaan (Johdatus diskreettiin matematiikkaan). Huom: Kurssin harjoitukset alkavat jo ensimmäisellä luentoviikolla. Kurssikirja: T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 3rd ed., MIT Press, 2009.
Vuosi Lukukausi Päivämäärä Periodi Kieli Vastuuhenkilö
2011 kevät 17.01-27.04. 3-4 Suomi Matti Luukkainen

Luennot

Aika Huone Luennoija Päivämäärä
Ma 12-14 A111 Matti Luukkainen 17.01.2011-23.02.2011
Ke 12-14 A111 Matti Luukkainen 17.01.2011-23.02.2011
Ma 12-14 A111 Matti Luukkainen 14.03.2011-27.04.2011
Ke 12-14 A111 Matti Luukkainen 14.03.2011-27.04.2011

Harjoitusryhmät

Group: 1
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
Ke 14-16 B222 Antti Laaksonen 24.01.2011—25.02.2011 Huom! Sali on vaihtunut myös periodissa IV!
Ke 14-16 B222 Antti Laaksonen 14.03.2011—29.04.2011 Huom! Sali on vaihtunut myös periodissa IV!
Group: 2
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
Ke 16-18 B222 Pekka Mikkola 17.01.2011—25.02.2011
Ke 16-18 B222 Pekka Mikkola 14.03.2011—29.04.2011
Group: 3
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
To 14-16 D122 Matti Luukkainen 17.01.2011—25.02.2011
To 14-16 D122 Matti Luukkainen 14.03.2011—29.04.2011
Group: 4
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
Pe 12-14 B222 Antti Laaksonen 17.01.2011—25.02.2011
Pe 12-14 C222 Antti Laaksonen 14.03.2011—29.04.2011

Non finnish students, contact the lecturer before hand.

Yleistä

Tärkeät linkit:

Ajankohtaista:

Luentojen etenemisaikataulu:

Pvm aihe moniste cormen2 cormen3
17.1. johdanto, oikeellisuus 1-27 5-21 5-23
19.1. oikeellisuus jatkuu, vaativuus 28-53 23-27, 41-55 23-28, 43-59
   
24.1. vaativuus jatkuu 53-83
26.1. pino ja jono, linkitetyt rakenteet 84-112 200-203 229-235
   
31.1. linkitetty lista 113-127 204-208 236-240
2.2. puu ja binäärihakupuu 128-154 1087-1090, 214-215 1176-1179, 246-247
   
7.2. binäärihakupuu jatkuu 155-168 253-263 286-298
9.2. binääripuu jatkuu, AVL-puu alkaa 169-190 Ei Cormenissa
   
14.2. AVL-puu jatkuu 191-220 Ei Cormenissa
16.2. AVL-puu jatkuu 221-232 Ei Cormenissa
   
21.2. yleisen puun esittäminen ja läpikäynti, puut ongelmanratkaisussa 233-274 214-215 246-247
23.2. kertaus kalvot
   
28.2. ensimmäinen kurssikoe klo 16-19 A111
   
14.3. hajautus 277-297 221-236 253-268
16.3. hajautus jatkuu 298-315 237-245 269-277
   
21.3. keko, kekojärjestäminen 316-342 127-132, 138-141 151-158, 162-165
23.3. järjestämisalgoritmeja 343-357 133-137, 27-36 156-161, 29-39
28.3. lisää järjestämiseen liittyvää 358-391 145-173 170-199
30.3. verkko ja sen tallennustavat, leveyssuuntainen läpikäynti 392-418 1080-1085, 525-534 1168-1172, 587-598
4.4. verkon leveyssuuntaisen läpikäynnin aikavaativuus, verkon syvyyssuuntainen läpikäynti 419-437 534-547 599-612
6.4. verkon syvyyssuuntaisen läpikäynnin sovelluksia, lyhimpien polkujen alku 438-461 547-560, 580-587, 595-613, 612-620, 643-650, 658-680,
11.4. lyhimmät polut jatkuu 462-486 629-636 693-699
13.4. verkon virittävä puu 487-515 561-579

624-642

18.4. Union-Find-rakenne, A*-algoritmi 516-548    
20.4. kertausta kalvot
   
5.5. toinen välikoe klo 9-12 A111

Laskuharjoitukset

Normaalien laskareiden lisäksi kurssilla on myös ohjelmointitehtäviä ja TRAKLA2-tehtäviä.

Normaaleissa laskareissa on viikoittain noin 5 tehtävää. Tehtävät tehdään etukäteen ja ne käsitellään laskaritilaisuuksissa.

Joka viikko on myös noin 5 ohjelmointitehtävää. Ohjelmointitehtäviin saa ohjausta TiRa-pajassa. Pajassa neuvotaan myös normaalien laskareiden tekemisessä. Paja-ajat ja muu opetus selviävät seuraavasta:

Opetusajat:

Kurssin suorittaminen

Kurssiin kuuluu kaksi välikoetta, 12 laskuharjoitusta, pajoissa tehtäviä ohjelmointitehtäviä sekä TRAKLA2-tehtäviä. Laskuharjoitukset ja pajat aloitetaan jo ensimmäisellä viikolla.

Laskuharjoituksista on mahdollista saada 16 kurssipistettä.

Kokeiden yhteenlaskettu maksimipistemäärä on 44. Läpipääsyyn vaaditaan vähintään puolet kurssin kokonaispistemäärästä eli 30, koepisteiden summan täytyy myös olla vähintään 22.

Kokeissa saa olla mukana itse tehty, käsin kirjoitettu A4-kokoinen lunttilappu. Lunttilapun tekemisessä ei siis saa käyttää tietokonetta eikä kopiokonetta.

Kesäkuun erilliskoetilaisuudessa voi uusia jomman kumman kurssikokeista tai tehdä normaalin erilliskokeen. Kurssikokeen uusiminen on mahdollista myös siinä tilanteessa, että kurssi olisi suoritettu hyväksytysti. Laskuharjoituspisteet huomioidaan arvostelussa, erilliskoevaihtoehdon suorittavilla vain niiden osalta, joille laskuharjoituspisteiden huomioiminen korottaa arvosanaa.

Kurssin suorittamisesta ja pisteytyksestä tarkemmin täällä

Kirjallisuus ja materiaali

luentokalvot. Kalvot ilmestyvät pikkuhiljaa kurssin kuluessa. Kalvot perustuvat kevään 2010 joita voi toki katsoa omalla vastuulla.

Kurssimateriaali pohjautuu suurelta osin kirjaan: T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 3rd ed., MIT Press, 2009.

Kirjan 3. painos ilmestyisyyskuussa 2009, esim. kirjastosta löytyy vain toista painosta joka sekin on käyttökelpoinen.

Kurssilla on muutamia asioita joita Cormenin kirjasta ei löydy, mm. AVL-puu ja B+-puut. Kaikissa asioissa käsittelytapa ei vastaa täysin Cormenia.