Tietorakenteet ja algoritmit
Simo Juvaste, Tietojenkäsittelytieteen laitos, Joensuun yliopisto
(Data Structures and Algorithms, 3 cu)
Sisältö
Opinto-oppaan mukainen kurssikuvaus
Tietorakenteet ja algoritmit (3 ov) 173201
- Luennot 40 t, Harjoitukset 20 t
- Tietojenkäsittelyssä tavallisimmin käytetyt tietorakenteet ja niiden
hyödyntäminen. Kirjallisuus: Aho, Hopcroft, Ullman: Data Structures and
Algorithms. Esitiedot: Ohjelmoinnin peruskurssi.
Kurssin asema
- cum lauden pakollinen kurssi!
- cum lauden keskeisin kurssi!
Kurssin uudistuminen
Syksyn 2004 kurssi on viimeinen kerta kun tätä kurssia luennoidaan. Keväästä 2005 alkaen kurssi pidetään uusien tutkintovaatimusten mukaisina TRA1 ja TRA2 -kursseina.
Kurssin sisältö
Tarpeelliset esitiedot
- Kohtuullinen ohjelmointitaito Pascalilla tai C:llä, erityisesti dynaamisilla
tietorakenteilla (osoittimilla).
- Kykyä ratkoa yksinkertaisia matemaattisia lauseita ja lausekkeita
Käsiteltävät asiat
- Algoritmien aikavaativuuden arviointi
- Abstraktit tietorakenteet ja niiden käyttö
- Abstraktien tietorakenteiden toteutus
Kielipolitiikka
- Kurssin luennointikieli on Pascal-pohjainen algoritminotaatio (pseudokieli)
- Jos osallistujien kielitaito ja halukkuus sen mahdollistavat, niin
- Yksi harjoitusryhmä pidetään C-kielellä (ilmoitetaan myöhemmin)
- Myös tentissä ja harjoitustyössä voi käyttää Pascalin ohella
C-kieltä.
- C-ryhmän perustaminen on vaakalaudalla osanottajien vähyyden vuoksi.
Tavoite
- Nostaa ohjelmien ja ohjelmoijien abstraktiotasoa!
Alustava aikataulu syksyllä 2004
Luennot 40 t Simo Juvaste
- 13.9. -- 15.11.
ma 12-14 Louhela-sali
ti 12-14 Louhela-sali
Harjoitukset 20 t Simo Juvaste
- 22.9. -- 25.11.
- Ryhmä 1: Peruttu osanottajien puutteessa
Ryhmä 2: ke 16-18 T/B180 (Pascal)
Ryhmä 3: to 08-10 T/B180 (Pascal)
Ryhmä 4: to 10-12 T/B180 (Pascal)
Ohjausta
- ke 08-10 T/B178
- Harjoitustehtävien tekemisessä eteentuleviin ongelmiin.
Välikokeet
Yleiset kuulustelut
Arvostelu syksyllä 2004
- 2004 arvostelu:
- 60 harjoitustehtävää, 1/3 (= 20) vaaditaan 2. välikokeeseen
osallistumiseksi.
- ((h-20)/(hmax-20))*15% bonusta harjoitustehtävistä välikokeiden kautta
suorittaville. Eli bonukset lasketaan vain vähimmäisosan ylittävältä
osuudelta. Bonukset lasketaan tarkasti, ei siis mitään pyöristyksiä
puoleen tai kokonaiseen pisteeseen.
- Syksy 2004: max on 60, hmax = 60, 1/3 = 20, bonusmax = 9, eli kustakin 20 ylittävästä tehtävästä 0,225 p bonusta välikoepisteisiin.
- Esim. 35 demotehtävää = (35-20)*0.225 = 3,375p.
- Harjoitusbonuksia jaetaan vain harjoituksissa läsnäolijoille, niitä ei siis saa lähettämällä lähettämällä ratkaisuja etukäteen sähköpostilla tms olipa syy mikä tahansa.
Muutamalta harjoituskerralta poissaolon pisteet eivät ole ratkaisevia kurssin
läpäisyn kannalta, jollei pääse useimpiin harjoituksiin, niin yleinen
kuulustelu on oikea ratkaisu. Oppimisen (ja kurssin läpäisyn) kannalta on
tärkeintä tehdä tehtäviä, arvosanahan määräytyy kokeiden perusteella.
- 48% = 1-, 54% = 1, ..., 90% = 3
- Demopisteet tarkastettavaksi (vain joensuu.fi)
Materiaali/kirjallisuus
Kirjallisuus
- Aho, Hopcroft, Ullman: Data Structures and Algorithms tai vastaava,
- Weiss: Data Structures and Algorithm Analysis [in C | Pascal | C++ | Java, | jne]
- Cormen, Leiserson, Rivest: Introduction to Algorithms
- Knuth: The Art of Computer Programming
- Luentomoniste (Epsilon/Rekursio myy)
- 10.9.2003 versio (4+130 s) sisältää aiempien lisäksi valinnan, kantalukulajittelun, virheiden korjauksia ja muutaman lisäkuvan.
- Vanhoja versioita:
- 5.9.2000 versio (4+125 s) sisältää aiempiin nähden lisää asiaa ulkoisesta
muistista, virheiden korjauksia ja muutaman lisäkuvan.
Havaittuja (oleellisia) virheitä
- 2.9.1999 versio (4+118 s) Havaittuja
(oleellisia) virheitä
- 8.3.2000 versio (4+122 s) sisältää edelliseen nähden lähinnä virheiden
korjauksia ja muutaman lisäkuvan.
Havaittuja (oleellisia) virheitä
- Vanha Asko Niemeläisen moniste (1997, 4+96 s) käy myös, joskin siihen
kannattaa hankkia täydennyskappale (1997 -> 2.9.2000) Epsilonilta.
Päivitysliitteen PDF versio (127 kt)
Luennnolla
esitettyjä, ei monisteessa olevia esimerkkejä, mallivastauksia, yms ohjelmanpätkiä
WWW-linkkejä TRA-materiaaliin
Käytettävät kääntäjät
- Pascal: gpc (cs & cc)
- C: gcc (cs & cc)
Tietorakennekirjasto
- Kurssin ensimmäinen 80% keskittyy tietorakenteiden käyttämiseen ja vasta
viimeisillä viikoilla pureudumme toteutukseen.
- Huonona puolena tässä on, että harjoituksia (tai esimerkkejä) ei
sellaisenaan voi oikeasti kääntää ja kokeilla tietokoneella.
- Ratkaisuna olemme kehittäneet abstraktien tietorakenteiden kirjaston C:llä
ja Pascalilla (tekeillä: Java).
- Nyt harjoitukset voi tehdä ja kokeilla koneella.
- Harjoituksissa kirjastoa käytetään cs ja cc -koneilla.
- Kirjastosta on www-sivulla jaossa myös Linux-versiot (gpc ja gcc), sekä Windows/DJGPP -versiot. Tuoreet tulollaan.
- Borland|MS|etc -Pascal/C:lle versiota ei vielä ole (siirto Borland-sukuisille Pascaleille mahdotonta).
- Java -versio tekeillä, itse kirjasto melkein valmis, dokumentaatio ja testaus hieman vaiheessa.
- Kirjaston käyttöön liittyvä tietoisku ja käyttödemonstraatio tulee
noin toisella viikolla.
- Kirjasto on asennettu sekä cs, että cc -koneille.
- Tästä voit ladata paketteja eri alustoille.
- Pascal-versio, gpc kääntäjä sekä Linux, että Windows: tra04.zip: ZIP paketti (28Mt), tai tra04.iso: CD-image poltettavaksi (28Mt)
- GPC asennusohje Linuxille.
- Jakelussa on ainakin Linuxille ja Win32/DJGPP:lle C ja Pascal -versiot.
- Vanhempia versioita:
- Dokumentaatiosivu
- Vaihtoehtoiset dokumentaatiot (ilman takuuta ja ylläpitoa) (kiitokset TJ doku kurssille 2001):
Harjoitukset
Harjoitustehtäviä paperilla jaetaan luennolla ja R:n kopilla T/B350.
Postituslista
Kurssin tiedottamista varten on perustettu postituslista tkt-tra.
- Listalle liittyminen:
- lähetä sähköpostia osoitteeseen
majordomo@joensuu.fi, otsikoksi ei tarvitse
laittaa mitään, varsinaiseksi rungoksi teksti subscribe tkt-tra
Jos haluat postin muuhun osoitteeseen, kuin mistä lähetät, käytä muotoa
subscribe tkt-tra tunnus@kone.domaini.fi tms. Listan ylläpitäjän on vielä hyväksyttävä käsin nämä liittymiset, joten posti ei ala kulkea välittömästi.
- Listalta eroaminen:
- lähetä sähköpostia osoitteeseen
majordomo@joensuu.fi, otsikoksi ei tarvitse
laittaa mitään, varsinaiseksi rungoksi teksti unsubscribe tkt-tra
- Sähköpostin lähettäminen listan kaikille lukijoille
- lähetä sähköpostia osoitteeseen
tkt-tra@joensuu.fi
Harjoitustyö
- Kurssiin liittyy erillinen harjoitustyö (2 ov,
173211), joka on parasta tehdä välittömästi varsinaisen kurssin
suorituksen jälkeen.
Syksyllä 2005 töitä ohjaa Matti Tedre
-
harjoitustyösivu
Last modified
Tue Aug 23 12:00:53 EEST 2005
SJ