Algoritmien suunnittelu ja analysointi (syksy 2003)

• 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

Kurssin suorittaminen

Kurssille on suositeltavaa ilmoittautua laitoksen kurssi-ilmoittautumissivun kautta. Ilmoittautua voi kuitenkin myös luennolla.

Kurssiin kuuluvat seuraavat osat:

• 32 tuntia luentoja (2.9.-16.10, Microteknian sali MT2)

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

• harjoituksia 7 * 2 tuntia (MT2, 12.9.-23.10.) Ensimmäistä harjoitusryhmää vetää Pekka Kilpeläinen ja toista assistentti Konstantin Hypponen.

• kaksi välikoetta: ensimmäinen ma 29.9. klo 14-16 Microteknian Auditoriossa, toinen ma 20.10. klo 12-14 salissa E16-17.

Kurssin aikataulu on saatavilla kurssikohtaisista lukujärjestyksistä.

Arvosana määräytyy kaavalla

 
    katto(6*(V1+V2)+ 4*H -4) , 

missä Vi on välikokeesta i=1,2 saatujen pisteiden suhteellinen osuus (Pisteet_i/MaxPisteet_i) ja H=(HarjPisteet/MaxHarjPisteet). Funktion katto(x) arvo on pienin vähintään x:n suuruinen kokonaisluku. (Esim. katto(11,1) = katto(12) = 12.) Harjoitustehtävien osuus arvosanasta on siis 25%. Kurssia ei kuitenkaan voi läpäistä pelkällä harjoitustehtävien merkkaamisella, vaan välikokeista on saatava yhteensä vähintään puolet niiden maksimipistemäärästä (eli (Pisteet1+Pisteet2)/(MaxPisteet1+MaxPisteet2) >= 0,5). Alin hyväksytty arvosana on 3.

Vaihtoehtoisesti kurssin voi suorittaa tentillä. Lopputentti järjestetään to 30.10.2003 klo 12-16, SL. 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 pe 28.11. klo 12-16 salissa E16/17.

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 2003 versio!)

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

Suositeltavaa oheiskirjallisuutta

Harjoitustehtävät

Harjoitus 1 (12.9): Postscript * PDF
Harjoitus 2 (19.9.): Postscript * PDF
Harjoitus 3 (25.9.): Postscript * PDF
Harjoitus 4 (3.10.): Postscript * PDF
Harjoitus 5 (10.10.): Postscript * PDF
Harjoitus 6 (17.10.): Postscript * PDF
Harjoitus 7 (23.10.): Postscript * PDF (Tehtävässä 6 mainittu kurssipalautelomake löytyy laitoksen kurssipalautesivulta.)

Oletetut esitiedot

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

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

Kurssikysely

Kurssikyselyyn vastasi 11 opiskelijaa. [Syksyn 2003 kurssipalautteen yhteenvetosivu]
Lisäksi yksi itseopiskelija antoi palautetta sähköpostitse.

Aiempien vuosien kurssipalautteiden yhteenvetoja:

• ASA 2000
• ASA 2001
• ASA 2002