Suomeksi In English

58053-7 Algoritmien suunnittelu ja analyysi (5 ov)

(Erilliskokeet)

Kevään 2004 kurssin tuloksia:

• 1. kurssikoe 9.3.: tehtävät, ratkaisuja (myös PDF), tulokset.
• 2. kurssikoe 10.5.: tehtävät, ratkaisuja.
• lopputulokset
• Kurssikyselyyn on tullut 14 vastausta (tilanne 24.5.); kiitos vastanneille!

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ä.

• sivut 1-31: PDF, PS
• sivut 32-50: PDF, PS
• sivut 51-69: PDF, PS
• sivut 70-88: PDF, PS
• sivut 89-104: PDF, PS
• sivut 105-120: PDF, PS
• sivut 121-136: PDF, PS
• sivut 137-148: PDF, PS
• sivut 149-164: PDF, PS
• sivut 165-178: PDF, PS
• sivut 179-198: PDF, PS
• sivut 199-216: PDF, PS
• sivut 217-231: PDF, PS
• sivut 232-250: PDF, PS
• sivut 251-275: PDF, PS
• sivut 276-291: PDF, PS
• sivut 292-309: PDF, PS
• sivut 310-321: PDF, PS
• sivut 322-343: PDF, PS
• sivut 344-359: PDF, PS
• sivut 360-379: PDF, PS
• sivut 380-387: PDF, PS

Laskuharjoitukset

(Malliratkaisut on poistettu näkyvistä.)

• Harjoitus 1 (29.-30.1.): tehtävät PS, PDF; ratkaisut
• Harjoitus 2 (5.-6.2.): tehtävät PS, PDF; ratkaisut
• Harjoitus 3 (12.-13.2.): tehtävät PS, PDF; ratkaisut
• Harjoitus 4 (19.-20.2.): tehtävät PS, PDF; ratkaisut
• Harjoitus 5 (26.-27.2.): tehtävät PS, PDF; ratkaisut
• Harjoitus 6 (4.-5.3.): tehtävät PS, PDF; ratkaisut
• Harjoitus 7 (11.-12.3.): tehtävät PS, PDF; ratkaisut
• Harjoitus 8 (18.-19.3.): tehtävät PS, PDF; ratkaisut
• Harjoitus 9 (25.-26.3.): tehtävät PS, PDF; ratkaisut
• Harjoitus 10 (1.-2.4.): tehtävät PS, PDF; ratkaisut
• Harjoitus 11 (15.-16.4.): tehtävät PS, PDF; ratkaisut
• Harjoitus 12 (22.-23.4.): tehtävät PS, PDF; ratkaisut
• Harjoitus 13 (29.-30.4.): tehtävät PS, PDF; ratkaisut
• Harjoitus 14 (6.-7.5.): tehtävät PS, PDF; ratkaisut