Opinto-opas 2015-2016

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

Lisätiedot

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

Vastuuhenkilö

Terhi Kilamo, Matti Rintala

Opetus

Toteutuskerta 1: TIE-20100 2015-01

Opetusmuoto P1 P2 P3 P4 Kesä
Luennot
Harjoitukset
Harjoitustyöt
Verkkotyöskentely




 




 
 2 h/vko
 2 h/vko
 35 h/per
 1 h/vko
+2 h/vko
+2 h/vko
+35 h/per
+1 h/vko




 

Luentoajat ja -paikat: Keskiviikko 10 - 12 TB104 , Keskiviikko 10 - 12 TB111

Suoritusvaatimukset

Riittävästi pisteitä, joita kertyy viikkoharjoituksista, luennoista, viikkoesseistä, verkkotehtävistä ja harjoitustöistä. Tentti.
Osasuoritusten pitää liittyä samaan toteutuskertaan

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 

Ohjeita opiskelijalle osaamisen tasojen saavuttamiseksi

Kurssin arvosana muotoutuu opiskelijan ohjelmointiharjoitustyö- ja tenttimenestyksen perusteella. Hyväksyttyyn kokonaissuoritukseen vaaditaan jokaisen pakollisen osasuorituksen hyväksytty suoritus. Maksimi kokonaispistemäärä on 36. Lisäksi kurssilla odotetaan opiskelijoiden suorittavan riittävä määrä tietorakenne- ja algoritmiharjoituksia byTheMark-järjestelmässä pakollisena osasuorituksena. byTheMark-suoritus arvostellaan hyväksytty/hylätty eikä sillä ole muuta suoraa vaikutusta kurssin arvosanaan. Aktiivinen osallistuminen kurssin harjoituksiin korottaa hyväksyttyä kurssiarvosanaa yhdellä. Hylättyä arvosanaa ei voi aktiivisella osallistumisella korottaa.

Arvosteluasteikko:

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

Osasuoritukset:

Osasuoritusten pitää liittyä samaan toteutuskertaan

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    



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  

Viimeksi muokattu 15.01.2016