Algoritmien suunnittelu ja analysointi (syksy 2007)

• Tietojenkäsittelytieteen syventävien opintojen (IV-V vuosi) kurssi (3 ov/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.)

• 32 tuntia luentoja (ma 3.9. - ti 23.10.07)

• 7*2 tuntia harjoituksia (13.9.-26.10.07)

• kaksi välikoetta: ensimmäinen ke 3.10 klo 8-10 salissa E26/27 ja toinen lopputentin yhteydessä ke 31.10 klo 8-10 salissa E26/27. Ilmoittautukaan tentteihin Wossikan kautta.

Arvosana määräytyy kaavalla

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

Vaihtoehtoisesti kurssin voi suorittaa tentillä. Lopputentti on ke 31.10.07 klo 8-12 salissa E26/27. 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 23.11.2007 klo 8-12 Suuressa luentosalissa.

Kurssimateriaali

Kurssin varsinainen sisältö ilmenee luentomonisteesta "Algoritmien suunnitteluja analysointi (ASA), Syksy 2007", jota voi ostaa KUTOP-kahviosta (Microteknia, IT-talon 3. krs, ma-to 8.45-16.00, pe 8.45-13.15). Hinta on noin 3 EUR. (Syksyn 2006 versio on oleellisilta osin samanlainen, 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

Harjoitustehtävät

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

1. harjoitus (13. ja 14.9.)
2. harjoitus (20. ja 21.9.)
3. harjoitus (28.9.)
4. harjoitus (4.10.)
5. harjoitus (12.10.)
6. harjoitus (18.10.)
7. harjoitus (25.10.)

Oletetut esitiedot

• Tietorakenteet ja algoritmit
• Ohjelmoinnin ja laskennan teoria
• matematiikan approbatur

Kurssikysely

Kurssipalautteen yhteenveto kommentteineen löytyy täältä. Kiitokset palautteen antajille.

Aiempien vuosien kurssipalautteiden yhteenvetoja:

• ASA 2006
• ASA 2005
• ASA 2004
• ASA 2003
• ASA 2002
• ASA 2001
• ASA 2000