Opinto-opas

Osaamistavoitteet

- Opiskelija ymmärtää algoritmien merkityksen ja osaa analysoida yksinkertaisten algoritmien aikavaativuuden kertaluokan.
- Opiskelija osaa perustellusti valita oikean tietorakenteen (abstraktin tietotyypin) kuhunkin käyttötarkoitukseen ja käyttää sitä tehokkaasti.
- Opiskelija osaa käyttää ohjelmointikielensä vakiokirjaston tietorakenteita oikein ja tehokkaasti.
- Opiskelija osaa toteuttaa tietorakenteista listan, puun ja joukon sekä suunnitella ja toteuttaa algoritmin yksinkertaiseen ongelmaan.
- Opiskelija osaa etsiä ja perustellusti valita tarpeisiinsa oikean algoritmin ja soveltaa sitä käytännössä.
- Opiskelija tuntee yleisimmät tietorakenteet
- Opiskelija tuntee miten tietorakenteet voidaan toteuttaa erilaisilla ohjelmointikielillä.
- Opiskelija tuntee rekursion perusteet ja osaa toteuttaa rekursiivisen algoritmin

Sisältö

- Algoritmit ja aikavaativuusanalyysi.
- Abstraktit tietotyypit.
- Tietorakenteiden toteuttaminen.
- Haku- ja lajittelualgoritmit.
- Rekursiiviset algoritmitoteutukset

Esitietovaatimukset

Ohjelmointi I ja III suoritettu hyväksytysti, tai vastaavat tiedot ja taidot. Suositeltu: Ohjelmointi II suoritettu hyväksytysti, tai vastaavat tiedot ja taidot.

Oppimateriaalit

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, 3rd Ed. The MIT Press, 2009. Luentorunko.