|
|
|||||||||||||||||
Opinto-opas 2014-2015
TIE-20100 Tietorakenteet ja algoritmit, 5 op
|
Lisätiedot
Kurssin kotisivu: http://www.cs.tut.fi/~tiraka/
Vastuuhenkilö
Terhi Kilamo
Opetus
| Opetusmuoto | P1 | P2 | P3 | P4 | Kesä | Toteutuskerrat | Luentoajat ja -paikat |
|
|
|
|
|
|
|
|
|
Suoritusvaatimukset
Harjoitustyöt, tentti, verkkotehtäviä
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 | Painos,saatavuus... | Tenttimateriaali | Kieli |
| Kirja | Introduction to Algorithms, Second Edition | Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein | 0-262-03293-7 | Ei | Englanti | ||
| Kirja | Introduction to the Design & Analysis of Algorithms, 2nd ed. | Anany Levitin | 0321358287 | Ei | Suomi | ||
| Opintomoniste | Tietorakenteet ja algoritmit | Terhi Kilamo | jaetaan kurssin kotisivuilla | Kyllä | Suomi |
Esitietovaatimukset
| Opintojakso | P/S | Selite |
| MAT-02650 Algoritmimatematiikka | Suositeltava | |
| TIE-02200 Ohjelmoinnin peruskurssi | Pakollinen |
Esitietoketju (Vaatii kirjautumisen POPiin)
Vastaavuudet
| Opintojakso | Vastaa opintojaksoa | Selite |
|
|
|
|
|
|
|
Tarkempia tietoja toteutuskerroittain
| Toteutus | Kuvaus | Opetusmuodot | Toteutustapa |
| Kurssilla käsitellään yleisimmin käytettyjä tietorakenteita ja algoritmeja. Kurssin aikana tutustaan erilaisiin algoritmien suunnitteluperiaatteisiin ja algoritmiten suorituskyvyn analyysiin. | Luennot Harjoitukset Harjoitustyöt |
Lähiopetus: 0 % Etäopetus: 0 % Itseopiskelu: 0 % |