|
|
|||||||||||||||||
Opinto-opas 2010-2011
OHJ-2010 Tietorakenteiden käyttö, 5 op
|
Vastuuhenkilö
Terhi Kilamo
Opetus
| Opetusmuoto | P1 | P2 | P3 | P4 | Kesä | Toteutuskerrat | Luentoajat ja -paikat |
|
|
|
|
|
|
|
|
|
Suoritusvaatimukset
Harjoitustyöt, tentti, tietokoneharjoitus.
Osasuoritusten pitää liittyä samaan toteutuskertaan
Opetukseen ja oppimiseen liittyvät periaatteet ja lähtökohdat
-
Osaamistavoitteet
Kurssin suoritettuaan opiskelija osaa nimetä yleisimmin käytetyt järjestelyalgoritmit sekä toteuttaa ne ohjelmointikielellä. 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. Kurssilla esimerkkikirjastona on C++:n standardikirjasto, jota opiskelija osaa käyttää ohjelmien toteuttamiseen. Käytön lisäksi opiskelija osaa vertailla standardikirjaston säiliöiden tehokkuutta ja soveltuvuutta ohjelmassa käytettäväksi.
Sisältö
| Sisältö | Ydinaines | 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ö C++:n standardikirjasto | Algoritmien käyttö, iteraattorikategoriat, säiliösovittimet | Standardikirjasto ja omat tietotyypit |
| 5. | Graafin esitystapa ja graafialgoritmien keskeiset periaatteet | Leveyssuunnattu haku, syvyyssuunnattu haku, Dijkstran algoritmi | Muut algoritmit |
Opintojakson arvostelu
Kurssin arvosana muotoutuu opiskelijan ohjelmointiharjoitustyö- ja tenttimenestyksen perusteella. Läpipääsyyn vaaditaan vähintään 15 tenttipistettä sekä 18 pistettä yhteensä harjoitustöistä ja tentistä. Maksimi kokonaispistemäärä on 36. Lisäksi kurssilla odotetaan opiskelijoiden suorittavan riittävä määrä tietorakenne- ja algoritmiharjoituksia Trakla-järjestelmässä pakollisena osasuorituksena. Trakla-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 | Englanti | |||
| Kirja | Tietorakenteiden käyttö/ Utilization of Data Structures | Minna Ruuska/Terhi Kilamo (toimittanut) | ISBN 1 84479 360 5 | Juvenes-kirjakauppa | Englanti | ||
| Opintomoniste | Tietorakenteiden käyttö | Minna Ruuska | TiTe-kilta | Suomi |
Esitietovaatimukset
| Opintojakso | P/S | Selite |
| OHJ-1150 Ohjelmointi II | Pakollinen | 1 |
| OHJ-1160 Laaja ohjelmointi 2 | Pakollinen | 1 |
| MAT-21161 Algoritmimatematiikka | Pakollinen |
1 . Joko OHJ-1150 tai OHJ-1160 tulee olla suoritettuna
Esitietoketju (Vaatii kirjautumisen POPiin)
Vastaavuudet
| Opintojakso | Vastaa opintojaksoa | Selite |
|
|
|
|
|
|
|
Lisätiedot
Kurssin kotisivu: http://www.cs.tut.fi/~tiraka/
Tarkempia tietoja toteutuskerroittain
| Toteutus | Kuvaus | Opetusmuodot | Toteutustapa |
| Luennot Harjoitukset Harjoitustyöt |
Lähiopetus: 0 % Etäopetus: 0 % Itseopiskelu: 0 % |