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ä |
|
|
|
|
|
|
|
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:
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 |