Algoritmien suunnittelu ja analysointi (syksy 2002)

• Tietojenkäsittelytieteen syventävien opintojen (III-V vuosi) kurssi (3 ov)
• pakollinen tietojenkäsittelytieteen ja informaatiotekniikan linjoilla, valinnainen ohjelmistotekniikan linjalla

• oppia algoritmien analysoinnin menetelmiä ja (niiden kautta) tehokkaiden algoritmien suunnittelun menetelmiä
• tutustua joihinkin keskeisiin algoritmisiin ongelmiin, algoritmeihin ja tietorakenteisiin
• oppia ymmärtämään ja hyödyntämään tietojenkäsittelyongelmien täsmällisiä formulointeja
• saada perusteltu käsitys muutamista tietojenkäsittelyteorian keskeisistä aiheista (ratkeamattomuus, NP-täydellisyys)
• saavuttaa algoritmisen tietojenkäsittelykirjallisuuden lukutaito

2. välikoe pidetään ke 6.11. klo 12 - 16 salissa L2. Koealue: Luennolla ja harjoituksissa käsitellyt asiat vastaten luentomonisteen lukuja 4.3 - 8.2 ja 8.4 - 9.1.

Kurssin suorittaminen

Kurssiin kuuluvat seuraavat osat:

• 32 tuntia luentoja (3.9.-24.10, Microteknian sali MT2)

Luennot alkavat tiistaina 3.9 klo 10. Kurssin luennoi prof. Pekka Kilpeläinen.

• harjoituksia 7 * 2 tuntia (16.9.-28.10.) Harjoitusryhmää 1 vetää Pekka Kilpeläinen ja harjoitusryhmää 2 yliassistentti Tarja Lohioja.

• välikokeet: ensimmäinen to 3.10. klo 8-10, MT2, toinen ke 6.11. klo 12-16, L2.

Kurssin aikataulu on saatavilla kurssikohtaisista lukujärjestyksistä.

Arvosana määräytyy kaavalla (V1+V2+H)/3, missä Vi muodostuu välikokeen i=1,2 pisteistä muodossa 16*(pisteet/max_pisteet)-4 ja H=12*(HarjPisteet/MaxHarjPisteet). Alin hyväksytty arvosana on 3.

Vaihtoehtoisesti kurssin voi suorittaa tentillä. Ensimmäinen uusintatentti järjestetään ke 4.12.2001 klo 12-16, MTA. Ensimmäisessä uusintatentissä 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ä.

Kurssimateriaali

Kurssikirja: Penttonen, M, Johdatus algoritmien suunnitteluun ja analysointiin. Otatieto, 1997.

Luentomoniste "Johdatus algoritmien suunnitteluun ja analysointiin" on ostettavissa Microteknian neuvonnasta hintaan 2,70 EUR. (Huom: syksyn 2002 versio!)

Huom: Sekä kurssikirja että luentomoniste ovat hyvin tiiviitä ja soveltuvat siten lähinnä luentojen seuraamisen tueksi.

Suositeltavaa oheiskirjallisuutta

Harjoitustehtävät

Kurssille on perustettu toinen laskuharjoitusryhmä, joka kokoontuu ensimmäisen kerran ti 17.9. klo 8 salissa MT 1.

Harjoitus 1 (16.9. ja 17.9): Postscript * PDF
Harjoitus 2 (23.9 ja 24.9.): Postscript * PDF
Harjoitus 3 (30.9 ja 1.10.): Postscript * PDF
Harjoitus 4 (7.10 ja 8.10.): Postscript * PDF
Harjoitus 5 (14.10 ja 15.10.): Postscript * PDF
Harjoitus 6 (23.10 ja 24.10.): Postscript * PDF
Harjoitus 7 (28.10.): Postscript * PDF

Oletetut esitiedot

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

(tai vastaavat tiedot). Erityisesti matemaattinen induktio on hyödyllinen taito .

Kurssikysely

Vastatkaa (kurssin loppupuolella!) kurssikyselyyn ja palauttakaa lomake luennolla tai harjoituksissa tai toisen kerroksen palautelaatikkoon, kiitos!

• Kurssikyselylomakkeen PDF-versio
• Kurssikyselylomakkeen Postscript-versio

Palaute on opetuksen kehittämiseksi arvokasta!

Kurssipalautteen yhteenveto