Opinto-opas 2008-2009 Perus Perus Pori KV Jatko Avoin |Tutkinnot|     |Opintokokonaisuudet|     |Opintojaksot|

Opintojakson vastuuhenkilö

Henri Hansen, Antti Valmari

Toteutuskerrat

	Luentoajat ja -paikat	Kohderyhmä, jolle suositellaan
Toteutus 1	Per 4, 5 : Torstai 14 - 17, TB111

Suoritusvaatimukset

Weekly exercises, examination.
Osasuoritusten pitää liittyä samaan toteutuskertaan

Opetukseen ja oppimiseen liittyvät periaatteet ja lähtökohdat

-

Tavoitteet

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

Sisältö

Sisältöalue	Ydinaines	Täydentävä tietämys	Erityistietämys
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.

Opintojakson arvostelu

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.

Arvosteluasteikko:

Opintojaksolla käytetään numeerista arviointiasteikkoa (1-5)

Osasuoritukset:

Osasuoritusten pitää liittyä samaan toteutuskertaan

Oppimateriaali

Tyyppi	Nimi	Tekijä	ISBN	URL	Painos,saatavuus...	Tenttimateriaali	Kieli
Kirja	Introduction to Algorithms, 2nd edition	Cormen, Leiserson, Rivest, Stein	0-262-53196-8				Suomi
Luentokalvot	Algoritmien Analyysi	Henri Hansen			Julkaistaan kurssin verkkosivulla.		Suomi

Esitietovaatimukset

Vastaavuudet

Tarkempia tietoja toteutuskerroittain

	Kuvaus	Opetusmuodot	Toteutustapa
Toteutus 1			Lähiopetus: 0 % Etäopetus: 0 % Itseopiskelu: 0 %

Viimeksi muokattu	23.02.2009
Muokkaaja	Antti Valmari