Opintojaksot  
|Tutkinnot| |Opintokokonaisuudet| |Kaikki| |Jatko| |KV|

Opinto-opas 2007-2008

OHJ-2150 ALGORITMIEN ANALYYSI, 4 op
Analysis of Algorithms

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  
(Lukuvuoden 2007-2008 aikataulu)

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.

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

  • 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.

  • Opintojakson osasuoritusten pitää liittyä samaan toteutuskertaan.

  • Mitoitus
    OpetusmuodotTuntia
    Luennot 36
    Harjoitukset 77
    Kaikki yhteensä 113

    Opintojakson kotisivu

    Viimeksi muokattu 27.01.2007
    MuokkaajaHenri Hansen