Helsingin yliopisto Tietojenkäsittelytieteen laitos
 

Tietojenkäsittelytieteen laitos

Tietoa laitoksesta:

 

Suomeksi In English

58053-7 Algoritmien suunnittelu ja analyysi (5 ov)

(Erilliskokeet)

Kevään 2004 kurssin tuloksia:

Kurssin vastuuhenkilö on Jyrki Kivinen.

Tavoitteet

Kurssilla opitaan keinoja ensin löytää algoritmi annetun ongelman ratkaisemiseksi ja sitten arvioida algoritmin tehokkuutta. Pääpaino on algoritmien resurssivaatimusten matemaattisella analyysilla. Tietorakenteet-kurssilla saatuja tietoja perustietorakenteista ja -algoritmeista syvennetään esim. verkkoalgoritmien osalta. Opiskelija saa valmiuksia ymmärtää teorettisen tietojenkäsittelytieteen eri osa-alueiden kirjallisuutta.

Asema opetuksessa

Algoritmien suunnittelu ja analyysi on pakollinen laudatur-kurssi tietojenkäsittelyn suuntautumisvaihtoehdon algoritmien erikoistumislinjalla. Se sisältää myös ohjelmistoista tai informaatiojärjestelmistä kiinnostuneille sopivaa perustietoutta.

Esitiedoiksi vaaditaan kurssien Tietorakenteet ja Laskennan teoria tiedot.

Myös matematiikan taidoista on hyötyä kurssilla, vaikka varsinaisiksi matemaattisiksi esitiedoiksi riittää esim. matematiikan approbatur.

Kirjallisuutta

Varsinaista kurssikirjaa ei ole. Kuulustelut perustuvat luennoilla esitettyyn materiaaliin. Luentojen oheismateriaaliksi suositellaan kirjaa

T. H. Cormen, C. E. Leiserson, R. E. Rivest, C. Stein: Introduction to Algorithms. MIT Press, Cambridge, MA, 2001 (Second Edition).

Sisältöluonnos

  1. Johdantoa ja matemaatisia perusteita: algoritmin käsite, funktioiden kertaluokat, rekursioyhtälöt.
  2. Algoritmien analyysin perusteita: pahimman tapauksen ja keskimääräinen vaativuus, tasoitettu vaativuus, rekursiivisten ja iteratiivisten algoritmien aikavaatimus.
  3. Algoritmien suunnittelun perusteita: osittaminen, taulukointi, ahneet algoritmit, peruutus, paikallinen etsintä.
  4. Joukkojen käsittely: binomikasat, Fibonacci-kasat, union-find-ongelma.
  5. Verkkoalgoritmit: lyhimmät polut, pienimmät virittävät puut, syvyyshaku, vahvasti yhtenäiset komponentit, pariutusongelma, verkkovuot, Eulerin kehät.
  6. Approksimointialgoritmit
  7. Satunnaisalgoritmit

Opetus keväällä 2004

Opetusta annettiin seuraavasti:

Luennot
Jyrki Kivinen 21.1.-7.5. ke 14-16, pe 10-12 A414
Harjoitusryhmät 26.1.- 7.5.
  1. Jouni Siren to 14-16 B450
  2. Jouni Siren pe 12-14 B450

Suoritusmuodot

Luentokurssi koostuu luennoista, laskuharjoituksista ja kahdesta kurssikokeesta. Maksimipistemäärä 60 pistettä jakautuu seuraavasti:

1. kurssikoe 24 pistettä
2. kurssikoe 24 pistettä
laskuharjoitukset 12 pistettä

Täysien laskuharjoituspisteiden saaminen edellyttää, että noin 75% tehtävistä on merkitty.

Kurssimateriaali

Luennot

PostScript-versiossa on neljä sivua per arkki ja se on tarkoitettu paperitulostukseen. PDF-versio lienee mukavampi näytöllä.

Laskuharjoitukset

(Malliratkaisut on poistettu näkyvistä.)


Jyrki Kivinen