Tietojenkäsittelytieteen laitos

581378-4 Algoritmisen tietojenkäsittelyn perusteet

Harel, David: Algorithmics: The Spirit of Computing (Second Edition). Addison-Wesley 1992. [ISBN 0-201-50401-4]

Kurssin aikataulu on seuraava:

aika ja paikka	aihe
27.10. 10-12 A217	Ensimmäinen luento. Hallinnolliset järjestelyt käsiteltiin kalvoilla 1-5.
01.11. 12-14 A217	Luento.
03.11. 10-12 A217	Luento.
06.11. 12-14 A217	Ensimmäiset laskuharjoitukset. Niiden tehtävät perustuvat kalvoihin 6-43.
08.11. 12-14 A217	Luento.
10.11. 10-12 A217	Luento.
13.11. 12-14 A217	Toiset laskuharjoitukset. Niiden tehtävät perustuvat edellisten kalvojen lisäksi kalvoihin 44-79.
15.11. 12-14 A217	Luento. Peruttu sairastapauksen vuoksi!
17.11. 10-12 A217	Luento.
20.11. 12-14 A217	Kolmannet laskuharjoitukset. Niiden tehtävät perustuvat edellisten kalvojen lisäksi kalvoihin 80-102, laitoskirjastomme käyttöön ja kurssikansiosta löytyvään Philip Wadlerin artikkeliin. Malliratkaisu tehtävään 1 (idea Pekka Kilpeläisen): Osoitetaan (vihjeen mukaan) että Primin algoritmin kasvattama puu on koko ajan osa syöteverkon jostakin minimaalisesta virittävästä puusta. Edetään induktiolla yli algoritmin silmukan suorituksen. Lukijan kannattaa piirtää kuv(i)a! Osoitetaan ensin että ensimmäinen algoritmin valitsema kaari eli koko verkon halvin kaari kuuluu johonkin pienimpään virittävään puuhun. Olkoon T sellainen pienin virittävä puu joka ei sisällä ensin valittavaa kaarta e. Olkoon P puun T se (yksikäsitteinen) polku joka kulkee kaaren e päätepisteiden välillä. Jos polun P mikä tahansa kaari poistetaan ja e lisätään, saadaan uusi virittävä puu T' joka ei ole kalliimpi kuin T, ja T' sisältää kaaren e. Osoitetaan sitten, että algoritmin kasvattaessa puutaan se pysyy osana jotakin pienintä virittävää puuta. Olkoon T algoritmin tähän mennessä kasvattama epätyhjä puu ja e mikä tahansa kaari jonka algoritmi voisi lisätä siihen seuraavaksi saaden seuraavan puunsa T'. Jos T' on edelleen osa samaa pienintä virittävää puuta T'' kuin T, niin mitään ei tarvitse osoittaa. Muuten e ei kuulukaan puuhun T''. Olkoon x se kaaren e solmu joka kuuluu puuhun T ja y se toinen solmu. Olkoon P puun T'' se polku joka kulkee näiden solmujen x ja y välillä. Polku P ei ole kokonaan puussa T, koska muuten algoritmi ei olisi tarjonnut kaarta e. Kun siis kuljetaan polkua P solmusta x alkaen, löytyy jossakin vaiheessa kaari e' jonka alkusolmu on vielä puussa T mutta loppusolmu ei enää ole. Kaari e' ei voi olla halvempi kuin kaari e koska muuten algoritmi olisikin tarjonnut kaarta e' kaaren e sijasta. Vaihtamalla kaari e' kaareen e saadaan korkeintaan yhtä kallis virittävä puu kuin T'' joka sisältää puun T'.
22.11.2000 12-14 A217	Luento.
24.11.2000 10-12 A217	Luento.
27.11.2000 12-14 A217	Neljännet laskuharjoitukset. Niiden tehtävät perustuvat edellisten kalvojen lisäksi kalvoihin 103-147. Valitettavasti kalvon 140 esimerkkikuva on erillisenä PostScript-tiedostona.
30.11.2000 12-14 A216	Luento. HUOM! Aika ja paikka muuttunut.
01.12.2000 10-12 A217	Luento.
04.12.2000 12-14 A217	Viidennet ja viimeiset laskuharjoitukset. Niiden tehtävät perustuvat edellisten kalvojen lisäksi kalvoihin 148-192. Valitettavasti kalvon 192 esimerkkikuva on erillisenä PostScript-tiedostona. Tehtävässä 4 tarvittava lähde löytyy sekä kurssikansiosta että laitoskirjastosta.
08.12.2000 10-12 A217	Viimenen luento. Kurssi päättyi kalvoihin 193-244.
15.12.2000 10-14 Auditorio	Ainoa välikoe. Koealue käsittää luennot eli kurssikirjan luvut 1-2, sivut 68-71 luvusta 3, luvut 4-9, sivut 265-281 ja 289-291 luvusta 10, sivut 309-310, 313-319 ja 322-331 luvusta 11 sekä luvun 12. Vapaaehtoisista laskuharjoituksista kerätyt lisäpisteet otetaan huomioon tässä kokeessa. Kurssin tulokset ovat nähtävissä verkossa omalla käyttäjätunnuksellasi ja salasanallasi sekä salin A413 ilmoitustaululla.
19.01.2001 16-20 Auditorio	Ensimmäinen loppukoe. Loppukokeiden koealue on sama kuin välikokeessakin. Vapaaehtoisista laskuharjoituksista kerätyt lisäpisteet otetaan huomioon vielä tässä loppukokeessakin, mutta ei enää sitä seuraavissa loppukokeissa.
27.03.2001 16-20 Auditorio	Toinen loppukoe.

Sähköisen materiaalin saat aikatauluun sijoitettujen linkkien kautta PDF-muodossa.

Muu materiaali ilmestyy salissa A412 olevaan kurssikansioon jonka nykyinen sisältö on seuraava:

1. Luennoilla näytetyt kurssikirjan kuvat.
2. Laskuharjoituksissa käsiteltävä oheismateriaali.

Edellisen luentokerran (syyslukukauden 1999) kotisivu antaa lisätietoja kurssista.

Kurssin luennoija Matti Nykäsen yhteystiedot ovat: sähköposti matti.nykanen@cs.helsinki.fi, huone C481, ja puhelin 191 44237.