Algoritmien suunnittelu ja analysointi (syksy 2006)

• Tietojenkäsittelytieteen syventävien opintojen (III-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)

Kurssin suorittaminen

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

• 32 tuntia luentoja (ti 5.9.06 - ke 25.10.06)

• 7*2 tuntia harjoituksia (14.9.-30.10.06)

• kaksi välikoetta: ensimmäinen ti 3.10 klo 16-18 salissa E16-17 ja toinen lopputentin yhteydessä pe 3.11 klo 12-14 suuressa luentosalissa. Ilmoittautukaan tentteihin Wossikan kautta.

Arvosana määräytyy kaavalla

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

Vaihtoehtoisesti kurssin voi suorittaa tentillä. Lopputentti on pe 3.11.06 klo 12-16 suuressa luentosalissa. 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 kuitenkin vähintään puolet kokeen maksimipistemäärästä.

Uusintatenteissä harjoituspisteitä ei enää huomioida. Ensimmäinen uusintatentti järjestetään ma 4.12.2006 klo 8-12 salissa E26-27.

Kurssimateriaali

Kurssin varsinainen sisältö ilmenee luentomonisteesta "Algoritmien suunnitteluja analysointi (ASA), Syksy 2006", jota voi ostaa KUTOP-kahviosta (Microteknia, IT-talon 3. krs, ma-to 8.45-16.15, pe 8.45-13.15). Hinta on noin 3 EUR.

Luentomonisteessa havaittuja virheitä:

• s. 42, r. -5: '36' p.o. '54'.
• s. 82, r. 2: 'n/2' p.o. 'log n'.
• s. 95-96: "(Floyd-)Warshallin algoritmi" p.o. "Floyd-Warshallin algoritmi" tai "Floydin algoritmi"; Juuri Floyd esitti k.o. lyhimmät polut laskevan algoritmin v. 1962 Warshallin vastaavan, saavutettavuuden laskentaan liittyvän idean pohjalta.
• s. 148, r. 4: 'osoittaa SAT ...' p.o. 'osoittaa KNM ...'.
• s. 159, r. 2: '4, 4' p.o. '4, 3'.
• s. 170, kuva 18: '10*4' puun juuressa p.o. '10*10'.

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

1. harjoitus (14. ja 15.9.)
2. harjoitus (21.9.)
3. harjoitus (2.10.)
4. harjoitus (12.10. ja 13.10.)
5. harjoitus (19.10. ja 20.10.)
6. harjoitus (26.10.)
7. harjoitus (30.10.)

Oletetut esitiedot

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

Kurssikysely

Kurssikyselyyn vastasi yhdeksän opiskelijaa; kiitokset heille.

• Palautteen yhteenveto

Aiempien vuosien kurssipalautteiden yhteenvetoja:

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