| Opintojaksot | |||||
| |Tutkinnot| | |Opintokokonaisuudet| | |Kaikki| | |Jatko| | |KV| | |
|
|
|
|||||||||||
OHJ-2150 ALGORITMIEN ANALYYSI, 4 op
|
Opintojakson vastuuhenkilö
Henri Hansen
Luentoajat ja -paikat
Per IV,V: Torstai 14 - 17, TB111
Toteutuskerrat
| Periodi 1 | Periodi 2 | Periodi 3 | Periodi 4 | Periodi 5 | Kesä | |
| Luento | - | - | - | 3 h/vko | 3 h/vko | - |
| Harjoitus | - | - | - | 2 h/vko | 2 h/vko | - |
| Tentti | ||||||
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
Oppimateriaali
| Tyyppi | Nimi | Tekijä | ISBN | URL | Painos,saatavuus... | Tenttimateriaali | Kieli |
| Luentokalvot | Algoritmien Analyysi | Henri Hansen | Julkaistaan kurssin verkkosivulla. | Kyllä | Suomi | ||
| Kirja | Introduction to Algorithms, 2nd edition | Cormen, Leiserson, Rivest, Stein | 0-262-53196-8 | http://mitpress.mit.edu/algorithms/ | Ei ole |
Esitiedot
| Tunnus | Nimi | OP | P/S |
| OHJ-2010 | OHJ-2010 Tietorakenteiden käyttö | 5 | Pakollinen |
| OHJ-2100 | OHJ-2100 Ohjelmistotieteen perustyökaluja | 5 | Pakollinen |
Esitietoketju (Vaatii kirjautumisen TTY Intranetiin)
Huomautuksia
Kurssit OHJ-2010, OHJ-2150 ja OHJ-2200 vastaavat yhdessä vanhaa kurssia 8100310.
| Opetusmuodot | Tuntia |
| Luennot | 36 |
| Harjoitukset | 77 |
| Kaikki yhteensä | 113 |
| Viimeksi muokattu | 27.01.2007 |
| Muokkaaja | Henri Hansen |