TIE-20100 Tietorakenteet ja algoritmit, 5 op
Data Structures and Algorithms
Vastuuhenkilö
Matti Rintala
Opetus
| Toteutuskerta | Periodi | Vastuuhenkilö | Suoritusvaatimukset |
| TIE-20100 2018-01 | 3 - 4 |
Matti Rintala |
Kurssin arvosana muodostuu pisteistä, joita kertyy viikkoharjoituksista, luennoista, viikkoesseistä, verkkotehtävistä ja harjoitustöistä. Hyväksyttyyn kokonaissuoritukseen vaaditaan jokaisen pakollisen osasuorituksen hyväksytty suoritus. Tämän lisäksi kurssin tentti pitää suorittaa hyväksytysti. |
Osaamistavoitteet
Kurssin suoritettuaan opiskelija osaa nimetä yleisimmin käytetyt algoritmien suunnitteluperiaatteet. Opiskelija tunnistaa perustietorakenteet ja yleisimmät niiden käsittelyyn tarvittavat algoritmit. Opiskelija osaa selittää, mihin asymptoottisen suorituskyvyn analyysi perustuu sekä osaa arvioida yksinkertaisten ohjelmien ajan- ja muistinkäyttöä. Lisäksi opiskelija osaa selittää ohjelmointikielten kirjastojen käyttämisen edut ja rajoitteet ottaen huomioon myös kielten väliset erot.
Sisältö
| Sisältö | Ydinsisältö | Täydentävä tietämys | Erityistietämys |
| 1. | Asymptoottisen tehokkuuden käsitteen ja kertaluokkamerkintöjen ymmärtäminen | Hajoita- ja hallitse -tyyppisten algoritmien logaritmisen suoritusajan ymmärtäminen | Vaikeammat suoritusaikalaskut |
| 2. | Tärkeimmät järjestämisalgoritmit, neliöllisten ja O(n log n)- järjestämisalgoritmien välinen ero | Yksittäiset algoritmit | |
| 3. | Listat, hajautustaulu, binäärihakupuu | Puna-musta puu, muut puurakenteet | Harvinaisemmat tietorakenteet |
| 4. | Kirjastojen tietorakenne- ja algoritmitoteutukset: sopivan tietorakenteen valinta ja käyttö Ohjelmointikielten kirjastototeutukset | ||
| 5. | Graafin esitystapa ja graafialgoritmien keskeiset periaatteet | Leveyssuunnattu haku, syvyyssuunnattu haku, Dijkstran algoritmi | Muut algoritmit |
| 6. | Algoritmien suunnitteluperiaatteet: pala kerrallaan, hajoita ja hallitse, muunna ja hallitse | Ahneus | Dynaaminen ohjelmointi |
Oppimateriaali
| Tyyppi | Nimi | Tekijä | ISBN | URL | Lisätiedot | Tenttimateriaali |
| Kirja | Introduction to Algorithms, Second Edition | Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein | 0-262-03293-7 | Ei | ||
| Kirja | Introduction to the Design & Analysis of Algorithms, 2nd ed. | Anany Levitin | 0321358287 | Ei | ||
| Opintomoniste | Tietorakenteet ja algoritmit | Terhi Kilamo | jaetaan kurssin kotisivuilla | Kyllä |
Esitietovaatimukset
| Opintojakso | P/S | Selite |
| MAT-02650 Algoritmimatematiikka | Suositeltava | |
| TIE-02201 Ohjelmointi 2: Perusteet | Pakollinen | |
| TIE-02402 Ohjelmointi 3: Tekniikat | Suositeltava |
Tietoa esitietovaatimuksista
Kurssilla vaaditaan ohjelmoinnin peruskurssin tasoista C++-ohjelmointiosaamista
Vastaavuudet
| Opintojakso | Vastaa opintojaksoa | Selite |
| TIE-20100 Tietorakenteet ja algoritmit, 5 op | OHJ-2010 Tietorakenteiden käyttö, 5 op | |
| TIE-20100 Tietorakenteet ja algoritmit, 5 op | TIE-20106 Data Structures and Algorithms, 5 op |