• Loppukoe 11.11.11 on arvosteltu. Yhdeksän osallistui kokeeseen, ja heistä seitsemän läpäisi kurssin. Arvosteluun voi ja kannattaa tutustua laitoksen kansliassa.

• Kurssille on perustettu Moodle-sivu, jota voidaan käyttää foorumina kurssiin liittyville tiedotteille, keskusteluille ja chateille. Kurssin Moodle-avain on ASA2011.

Materials for International Students

• Pointers to sources of information in English textbooks
• Exercise assignments are posted below, normally roughly a week before the exercise session, also in English.
• Hand-out copies of slides
• The arrangemets of the course are similar to the previous years. They can be found in English on the Fall 2010 course homepage.
• A Moodle page has been created as a forum of news, discussions and chats related to the course. The course key, in case that the system asks you, is ASA2011.

Algoritmien suunnittelu ja analysointi (syksy 2011)

• Tietojenkäsittelytieteen maisteriopintojen (IV-V vuosi) kurssi (6 op)
• pakollinen medialaskennan suuntautumisvaihtoehdossa, valinnainen ohjelmistotekniikan ja kehitys- ja opetusteknologian opiskelijoille.

Kurssin tavoitteita:

• oppia menetelmiä, joilla voi analysoida algoritmeja ja suunnitella tehokkaita algoritmeja
• tutustua muutamiin keskeisiin algoritmisiin ongelmiin ja niiden ratkaisuihin
• saavuttaa perusteltu käsitys algoritmisen tietojenkäsittelyn rajoituksista (ratkeamattomuus, NP-täydellisyys)
• saavuttaa algoritmisen kirjallisuuden lukutaito

Käytännön järjestelyt

Ilmoittautukaa kurssille WebOodissa. Luennolla voi lisäksi jälki-ilmoittautua.

Kontaktiopetus

• 34 tuntia luentoja (to 1.9. - ma 31.10.11)

Luennot pidetään salissa MT2, ensimmäinen to 1.9. klo 12.

• 8*2 tuntia harjoituksia (9.9. - 2.11.11)

Luennot ja harjoitukset pitää professori Pekka Kilpeläinen.

• Loppukoe perjantaina 11.11 klo 12 - 16 salissa MT2. Ilmoittautukaa loppukokeeseen WebOodissa.

Arvosana määräytyy kaavalla

    round(6*K + 2*H - 2,5) ,

missä K on saatujen koepisteiden osuus niiden maksimista ja H on ratkaistujen harjoiteustehtävien osuus niiden kokonaismäärästä. Alin hyväksytty arvosana on 1 ja korkein 5. Huomatkaa, että harjoitusaktiivisuus muodostaa 25 % arvosanasta. Läpäisemistä varten täytyy saada vähintään puolet koepisteistä. Esimerkkejä arvostelukaavan tuottamista arvosanoista löytyy täältä.

Vaihtoehtoisesti kurssin voi suorittaa uusintatentillä, joka järjestetään pe 2.12.2011. Ilmoittautukaa uusintatenttiin WebOodissa. Myös uusintatentistä on saatava vähintään puolet koepisteistä kurssin läpäisemiseksi. Harjoitusaktiivisuutta ei huomioida uusintatenteissä.

Kurssimateriaali

Kurssin sisältö ilmenee suomenkielisestä luentomonisteesta "Algoritmien suunnittelu ja analysointi (ASA), Syksy 2011" (pääosin sama kuin vuonna 2010). Ainejärjestö Serveri myy luentomonisteita toimistossaan Technopoliksen D-siiven 1. kerroksessa hintaan noin 3 Euroa (Serverin jäsenille ja muille euron enemmän). Kirjoittakaa nimenne luentomonisteen tilauslistaan. Lista löytyy kurssin alkuun saakka Serverin toimiston edessä olevalta ilmoitustaululta, ja kierrätän sitä vielä ensimmäiselle luennolla. (Aiempien vuosien luentomonisteet ovat oleellisilta osin samanlaisia. Uusimmassa on päivitetty "syvän rekursion" analysointiin liittyvää lausetta 2.3 yleistämällä sen tulosta ja yksinkertaistamalla sen todistusta.)

Oppikirjoja: Kurssin aiheet on pääosin valittu kirjoista Penttonen, M, Johdatus algoritmien suunnitteluun ja analysointiin (Otatieto, 1997), ja Levitin, A, Introduction to the design and analysis of algorithms, second intl ed (Addison-Wesley, 2006). Yksityiskohtaisempia viitteitä kurssilla käsiteltyjen asioiden lähteisiin kansainvälisissä oppikirjoissa on annettu täällä.

Huom: Penttosen oppikirja, luentomoniste sekä kalvokopiot (alla) ovat ensisijaisesti tarkoitettuja luentojen seuraamisen tueksi ja siksi tarkoituksella varsin tiiviitä. Itseopiskelu onnistunee paremmin mainittuja kansainvälisiä oppikirjoja lukien.

• Oheiskirjallisuutta
• Pieni kaavakokoelma.

Kalvokopioita

(Edellisvuotisten englanninkielisten kalvojen kopioita, jollei toisin mainita)

1. Introduction
2. Analysis methods (päivitetty 2011-08-31)
3. Algorighm desing patterns I
   • Brute force
   • Divide-and-conquer
   • Decrease-and-conquer
4. Transform and Conquer
5. Heaps and Heapsort
6. Space-Time Tradeoffs
7. Greedy Method
   • for completeness, a proof of correctness for Prim's algorithm (extra material)
   • similarly, for completeness and as extra material, a proof that we can get 1/2 approximations using the greedyKnapsack procedure
8. Dynamic Programming
9. Limitations of Computing
10. Random Access Machine
11. Turing Machine
12. Comparison of TM and RAM models
    • a note for justifying the claim that we can perform integer division by a Turing machine in quadratic time (extra material)
13. NP-completeness
14. Solving hard problems

Harjoitustehtävät / Exercises

Julkaisen harjoitustehtävät tässä normaalisti noin viikkoa ennen harjoitustilaisuutta.

1. harjoitus (9.9.) (English version)
2. harjoitus (15.9.) (English version)
3. harjoitus (22.9.) (English version)
4. harjoitus (30.9.) (English version)
5. harjoitus (6.10.) (English version)
6. harjoitus (13.10.) (English version)
7. harjoitus (27.10.) (English version)
8. harjoitus (2.11.) (English version)

Oletetut esitiedot

• Tietorakenteet ja algoritmit
• Laskennan teoria (tai Laskennan perusmallit)
• Matematiikan perusopinnot (tai hyvin hallittu lukiomatematiikka), varsinkin diskreetti matematiikka

(tai vastaava perehtyneisyys)

Kurssipalaute

Kuusi osallistujaa antoi kurssipalautetta, kiitos siitä heille: palautteen tilastollinen ja sanallinen yhteenveto. WebOodista pitäisi löytyä muutamia kommenttejani palautteeseen; ainakin yritin syöttää sen sinne.

Aiempien vuosien opiskelijapalautetta:
2010: Numeerinen yhteenveto, Sanallinen palaute;
2009; 2008; 2007; 2006; 2005; 2004; 2003; 2002; 2001; 2000