|
|
OHJ-2150 ALGORITMIEN ANALYYSI, 4 op
|
Opintojakson vastuuhenkilö
Henri Hansen
Opettajat
Henri Hansen, Tutkija, Ohjelmistotekniikka, TF210
Luentoajat ja -paikat
Per IV,V: Keskiviikko 14 - 17, TB111
Toteutuskerrat
Toteutus 1
| Periodi 1 | Periodi 2 | Periodi 3 | Periodi 4 | Periodi 5 | Kesä | Opetuskieli | |
| Luento | - | - | - | 3 h/vko+ | 3 h/vko | - | Vain suomeksi |
| Harjoitus | - | - | - | 2 h/vko+ | 2 h/vko | - | Vain suomeksi |
| Tentti | Suomeksi, pyydettäessä englanniksi | ||||||
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. |
Suoritusvaatimukset
Laskuharjoitukset, tentti.
Opintojakson arviointikriteerit
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.
Esitiedot
| Tunnus | Nimi | OP | P/S |
| OHJ-2010 | Tietorakenteiden käyttö | 5 | Pakollinen |
| OHJ-2100 | Ohjelmistotieteen perustyökaluja | 5 | Pakollinen |
Huomautuksia
Kurssit OHJ-2010, OHJ-2150 ja OHJ-2200 vastaavat
yhdessä vanhaa kurssia 8100310.
| Viimeksi muokattu | 24.02.2005 |
| Muokkaaja | Kirsti Ala-Mutka |