Course Catalog 2008-2009 International Basic Pori International Postgraduate Open University |Degrees|     |Study blocks|     |Courses|

Course´s person responsible

Henri Hansen, Antti Valmari

Implementations

No implementations

Requirements

Weekly exercises, examination.
Completion parts must belong to the same implementation

Principles and baselines related to teaching and learning

-

Objectives

Kyky ymmärtää ja analysoida algoritmeja oikeellisuuden sekä ajan- ja muistinkulutuksen näkökulmasta, käsitys algoritmien todistamisesta oikeaksi, yleisimpien algoritmien hallinta.

Content

Content	Core content	Complementary knowledge	Specialist knowledge
1.	Tavallisimpien silmukkarakenteiden oikeellisuuden toteaminen, pääasiassa yksinkertaisimmat invarianttitodistukset.	Tilapropositioiden käyttö laajemmin, invarianttitekniikan kehittynyt käyttö.	Hyvin vaikeat algoritmien todistukset.
2.	Tavallisimpien yksinkertaisten silmukkarakenteiden ajankäytön analyysi, häntärekursion poisto, yksinkertaisten rekursiivisten algoritmien analysointi. Peruskäsitys tasatusta suoritusjasta.	Master-menetelmä, tasatun ajan analyysi, monimutkaisempien silmukoiden analyysi.	Laskentatehtävien kompleksisuus, eräiden tehtävien NP-kovuuden tunnistaminen.
3.	Perustavanlaatuisten algoritmien (mm. järjestämisalgoritmit, DFS, BFS) olennaiset ominaisuudet ja niiden sovelluskohteet. Käytettävän tietorakenteen vaikutukset algoritmien käyttäytymiseen.	Hieman kehittyneempiä algoritmeja. Korkean tason toteutustekniset seikat, jotka olennaisesti vaikuttavat algoritmien toimintaan: hieman vaativampi tietorakenteiden valinta.	Vaikeita algoritmeja todistuksineen, algoritmien soveltamista vaikeiden ongelmien ratkaisemiseen.

Evaluation criteria for the course

Painoarvo on tenttiosaamisessa: Kyky saada oikea vastaus selkeällä analyysilla tärkein kriteeri. Perusalgoritmien ominaisuuksisen hallinta laskevassa järjestyksessä: Analyyttinen, algoritmin suorituksen mekaaninen hallinta, ulkoaopittu.

Assessment scale:

Numerical evaluation scale (1-5) will be used on the course

Partial passing:

Completion parts must belong to the same implementation

Study material

Type	Name	Author	ISBN	URL	Edition, availability, ...	Examination material	Language
Book	Introduction to Algorithms, 2nd edition	Cormen, Leiserson, Rivest, Stein	0-262-53196-8				Suomi
Lecture slides	Algoritmien Analyysi	Henri Hansen			Julkaistaan kurssin verkkosivulla.		Suomi

Prerequisites

Correspondence of content

Last modified	23.02.2009
Modifier	Antti Valmari