Algoritmien suunnittelu ja analysointi (syksy 2008)

• Tietojenkäsittelytieteen syventävien opintojen (IV-V vuosi) kurssi (6 op)
• pakollinen tietojenkäsittelytieteen linjalla, valinnainen ohjelmistotekniikan sekä tieto- ja tietoliikennetekniikan linjoilla

Kurssin tavotteita:

• oppia algoritmien analysointimenetelmiä ja tehokkaiden algoritmien suunnittelumenetelmiä
• tutustua joihinkin keskeisiin algoritmisiin ongelmiin ja niiden ratkaisualgoritmeihin
• oppia ymmärtämään ja hyödyntämään tietojenkäsittelyongelmien täsmällisiä formulointeja
• saada käsitys algoritmisen tietojenkäsittelyn rajoituksista (ratkeamattomuus, NP-täydellisyys)
• saavuttaa algoritmisen tietojenkäsittelykirjallisuuden lukutaito

Kurssin suorittaminen

Kurssille ilmoittaudutaan Wossikan kautta. (Jälki-ilmoittautuminen luennolla.)

• 34 tuntia luentoja (ma 1.9. - ti 21.10.08)

• 8*2 tuntia harjoituksia (4.9.-23.10.08)

• kaksi välikoetta: ensimmäinen ti 30.9 klo 8-10 salissa E26/27 ja toinen lopputentin yhteydessä ke 29.10 klo 8-10 salissa L22. Ilmoittautukaa tentteihin Wossikan kautta.

Arvosana määräytyy kaavalla

    pyöristys(6*K + 2*H - 2,5) ,

Vaihtoehtoisesti kurssin voi suorittaa tentillä. Lopputentti on ke 29.10.08 klo 8-12 salissa L22. Ilmoittautukaa lopputenttiin Wossikan kautta. Lopputentissä harjoituspisteet voidaan huomioida siten, että arvosanaksi tulee parempi niistä, jotka määräytyisivät (a) pelkistä tenttipisteistä tai (b) sekä tentin että harjoitusten pisteistä. Kummassakin vaihtoehdossa kurssin läpäisemiseen vaaditaan vähintään puolet kokeen maksimipistemäärästä.

Uusintatenteissä harjoituspisteitä ei enää huomioida. Ensimmäinen uusintatentti järjestetään pe 28.11.2008 klo 8-12 Suuressa luentosalissa.

Kurssimateriaali

Kurssin varsinainen sisältö ilmenee luentomonisteesta "Algoritmien suunnitteluja analysointi (ASA), Syksy 2008", jota voi ostaa KUTOP-kahviosta (Technopolis, IT-talon 3. krs, ma-to 8.45-16.00, pe 8.45-13.15). Hinta on noin 3 EUR. (2006 ja 2007 versiot ovat oleellisilta osin samanlaiset, mutta sitä vanhemmat kurssimonisteet eivät täysin vastaa kurssin sisältöä.)

Kurssikirja: Penttonen, M, Johdatus algoritmien suunnitteluun ja analysointiin (Otatieto, 1997). Seuraamme valikoiden myös kirjan Levitin, A, Introduction to the design and analysis of algorithms, second intl ed (Addison-Wesley, 2006) jäsentelyä ja sisältöä.

Huom: Sekä kurssikirja että luentomoniste ovat hyvin tiiviitä ja soveltuvat siten lähinnä luentojen seuraamisen tueksi. (Ks. myös Ian Craw'n huomautus luentomuistiinpanojen ja luentojen suhteesta.)

• Suositeltavaa oheiskirjallisuutta
• Pieni kaavakokoelma. Tämän saa ottaa ilman lisämerkintöjä mukaan välikokeeseen, jos arvelee siitä olevan apua.

Harjoitustehtävät / Exercises

Kurssin harjoitustehtävät ilmestyvät tähän harjoituksia edeltävällä viikolla.

1. harjoitus (4.9.) (English version)
2. harjoitus (12.9.) (English version)
3. harjoitus (19.9.) (English version)
4. harjoitus (26.9.) (English version)
5. harjoitus (6.10.) (English version)
6. harjoitus (10.10.) (English version)
7. harjoitus (16.10.) (English version)
8. harjoitus (23.10.) (English version)

Oletetut esitiedot

• Tietorakenteet ja algoritmit
• Laskennan teoria (tai ainakin Laskennan perusmallit)
• matematiikan approbatur

Kurssikysely

Kurssipalautteen yhteenveto sekä kommenttejani palautteeseen löytyy täältä. Kurssikyselyyn vastasi kuusi opiskelijaa; kiitokset heille.

Aiempien vuosien kurssipalautteiden yhteenvetoja:
2007 2006 2005 2004 2003 2002 2001 2000