TIE-20100 Tietorakenteet ja algoritmit, 5 op
Data Structures and Algorithms

Lisätiedot

Kurssin kotisivu: https://www.cs.tut.fi/~tiraka/

Vastuuhenkilö

Matti Rintala

Opetus

Toteutuskerta Periodi Vastuuhenkilö Suoritusvaatimukset
TIE-20100 2016-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-02200 Ohjelmoinnin peruskurssi Pakollinen    
TIE-02400 Ohjelmoinnin tekniikat Suositeltava    



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  

Päivittäjä: Kilamo Terhi, 19.09.2016