Tietorakenteet ja algoritmit I
Simo Juvaste, Tietojenkäsittelytieteen laitos, Itä-Suomen yliopisto, Joensuun kampus
Matti Nykänen, Kuopio campus.
(Data Structures and Algorithms I, 5 cr)
English language version of this page (Spring 2017 course) can be found here
At Fall 2017: main course will be in Finnish, but if there are enough non-Finnish students, we can organize English sessions as well.
Sisältö
Opinto-oppaan mukainen kurssikuvaus
Tietorakenteet ja algoritmit I (5 op) 3621313
- Luennot 32 t, Harjoitukset 16 t
- Osaamistavoitteet: Opiskelija ymmärtää algoritmien merkityksen ja osaa analysoida yksinkertaisten algoritmien aikavaativuuden kertaluokan. Opiskelija osaa valita oikean tietorakenteen (abstraktin tietotyypin) kuhunkin käyttötarkoitukseen ja käyttää sitä tehokkaasti. Opiskelija osaa toteuttaa yleisimmät tietorakenteet sekä suunnitella ja toteuttaa algoritmin yksinkertaiseen ongelmaan.
- Sisältö: Algoritmien aikavaativuus ja kertaluokkatarkastelu. Yleisimpien tietorakenteiden ominaisuudet, oikea käyttö sekä toteutus.
Kurssin asema
- aineopintojen pakollinen kurssi
- aineopintojen keskeisimpiä kursseja
Kurssin sisältö
Tarpeelliset esitiedot
- Kohtuullinen ohjelmointitaito Javalla (suositellaan: Ohjelmointi II).
- Kykyä ratkoa yksinkertaisia matemaattisia lauseita ja lausekkeita
Käsiteltävät asiat
- Analyysin perusteet: 6
* Algoritmien suunnittelu ja toteutusperiaatteista
* asymptoottinen aika- ja tilavaativuusanalyysi
* paras, keskimääräinen, pahin tapaus
* O, o, Omega, theta
* kompleksisuusluokat
* aika vs. tila
* rekursiorelaatiot rekursiivisten alg. analyysissa (alustavasti)
- Perustietorakenteet 13
* Koteloinnin periaate, toteutustavat 2
* Lista sukulaisineen 3
* Puut 4
* Verkot (kevyesti) 1
* Joukot 3
* Oikean tietorakenteen valinta 2
- Perustietorakenteiden toteuttaminen 6
- Perusalgoritmeja: 7
* järjestämisalgoritmit (selection, insertion, quicksort, heapsort,
mergesort) aikavaativuuksineen Yksinkertaiset O(n^2)
lajittelualgoritmit ovat hyviä esimerkkejä jo ohjelmoinnin
kursseilla. Nopeammat TR1, ulkoisessa muistissa TR2. 3
* hajautus + törmäyksen välttämisstrategiat 2
* binäärihakupuut 2
Kielipolitiikka
- Kurssin luennointikieli on Java-pohjainen algoritminotaatio (pseudokieli)
- Harjoitukset tehdään pääsääntöisesti Javalla käyttäen tietorakennekirjastoa apuna.
Tavoite
- Nostaa ohjelmien ja ohjelmoijien abstraktiotasoa!
Aikataulu syksyllä 2017
Kuopion opetus, Simo Juvaste / Matti Nykänen, katso aikataulut WebOodi/Lukari
Päivitetään tähänkin myöhemmin.
Muutoksia:
-
viikon 37 luennot ke 12-16 (putkeen) E16/17.
-
viikon 37 harjoitukset (2. harjoitukset) ma 18.9. klo 10-12 E16/17 (molemmat ryhmät yhdessä)
-
3. ja 4. harjoitukset niputettuna ke 27.9. R1: 10-13 E24 ja R2: 13-16 E16/17.
-
Luennot viikoilla 37 ja 38 korvataan luentonauhoituksilla, katso alla.
-
Ohjaukset ke 20.9. klo 11-12 ja ti 26.9. 11-12 salissa F213.
-
- Lokakuussa: R1 harjoitukset: ke 08-10 salissa E26, paitsi ke 25.10. salissa F213.
- Lokakuussa: R2 harjoitukset: ke 4.10. klo 10-12 (E26), muuten klo 12-14 (salit
11.10. E25, 18.10. E26 ja 25.10. F213).
- Luentoja tukeva ydinasioiden, kertauksen, kyselyiden, jne luento
ke 4.10. klo 12-14 (epävirallinen), ke 11.10. 10-12 F211, ke 18.10. ja
25.10. E16/17.
- Harjoitustehtävien tekemiseen tukea tiistaina 3.10. F213 (etänä,
yhteiset näytöt ja yhteistä piirtämistä Smartilla). Jos tälle on
tarvetta, niin jatketaan. Jollei, niin ei jatketa.
- Täysmittaisista Joensuun luennoista tulee nauhoitukset kuten tähänkin
asti.
Luennot 32 t Joensuun kampus: Simo Juvaste
Harjoitukset 16 t Joensuun kampus: Simo Juvaste
- 8.9. - 27.10.
- Ryhmä 1: pe 08-10 TB180 (paitsi to 26.10. 08-10 TB180)
Ryhmä 2: to 08-10 TB180 (paitsi 26.10. klo 12-14 TB180)
Ohjausta
- Harjoitustehtävien tekemisessä eteentuleviin ongelmiin.
- Tarvittaessa.
- Joensuussa jatkossa tiistaisin 10-11 mikroluokassa TB247, Kuopiossa ti 11-12 F213.
Kurssikuulustelu
- pe 27.10. 12:00 -- 16:00, sali OTS100 (Joensuu, Otsola) / SN100 (Kuopio)
Muista ilmoittautua Oodin kautta
- Uusintakuulustelu pe 17.11. 12:00 -- 16:00, sali OTS100 (Joensuu) / CA101 (Kuopio)
Ilmoittautuminen Oodin kautta
Yleiset kuulustelut
- Web-Oodissa, alkaen pe 17.11. (kurssikuulustelun uusinnan yhteydessä, ilmoittaudu kurssikuulusteluun).
Ajankäyttö / kuormittavuus
Keskimääräiselle opiskelijalle, keskimääräiseen arvosanaan:
|
|
8 |
|
Viikottain |
Yhteensä |
| Luentoja |
4 |
32 |
| Kertaus |
2 |
16 |
|
|
|
| Harjoitukset |
2 |
16 |
| Valmistautuminen |
7 |
56 |
|
|
|
| Tentit |
|
4 |
| Valmistautuminen |
|
9 |
|
|
|
| Yhteensä(t) |
16,63 |
133 |
| Yhteensä(op) |
|
4,99 |
| 26,67 |
|
|
Kuormittavuus vaihtelee viikosta toiseen ja opiskelijasta toiseen. Erinomaiseen arvosanaan voi tarvita enemmän työtä.
Arvostelu syksyllä 2017
- Sovittiin yhdessä ensimmäisellä luennolla (Joensuussa ja Kuopiossa).
- Kurssikuulustelu ja sen uusintakuulustelu: Arvosana
määräytyy noin 40% pakollisista X-tehtävistä (noin 3 kpl),
loput loppukokeesta. Muista harjoituksista max 10% bonusta 1/3
ylittävästä osasta, vastaavasti miinusta 1/3 alittavasta osasta.
- Yleinen kuulustelu: vain kuulustelun pisteet.
Materiaali/kirjallisuus
Kirjallisuus
- Liang: Introduction to Java Programming, comprehensive 7th edition (tai myöhempi).
- Weiss: Data Structures and Algorithm Analysis [in C | Pascal | C++ | Java, | jne]
- Cormen, Leiserson, Rivest: Introduction to Algorithms
- Knuth: The Art of Computer Programming
- Luentorunko, kalvojen tekstit A4:lle muotoiltuna:
- PDF luentorunko 2017 (vain uef.fi) (1.2Mt, 101s), sama löytyy myös allakuvatussa luentonauhoitusten hakemistosta salasanan takaa, myös uef.fi:n ulkopuolelta.
- Vanha tekstimuotoinen luentomoniste:
- Luentojen nauhoitukset:
- Leikatut versiot (poistettu alun sähläys ja lopun tyhjä) onnistuneesti nauhoitetuista luennoista löytyvät Täältä. Käyttäjätunnus on tämän kurssin nimen ensimmäisen sanan (alkaa t-kirjaimella) viisi ensimmäistä kirjainta ja salasana on tämän kurssin nimen toisen pidemmän sanan (alkaa a-kirjaimella) viisi ensimmäistä kirjainta. Kaikki pienillä kirjaimilla.
-
- 2017 tallennukset ovat MP4(h264) tiedostoja 1920x560 resoluutio, ~1.7Gt/kpl tai _pieni 1024x298 resoluutio, ~170Mt/kpl.
- 2017 tallennukset löytyvät myös UEFAD-tunnuksilla media.uef.fi palvelimelta.
- 2012/3: _ed.wmv on alkuperäinen WMV tiedosto (1376x444 resoluutio, ~720Mt/kpl (90min))
- _pieni.mp4 on kutistettu MP4 tiedosto (800x258 resoluutio, ~190Mt/kpl (90min))
- Näitä voi katsoa vaikka mplayer:llä komennolla
mplayer http://tunnus:salasana@cs.uef.fi/pages/sjuva/traI_vid/TraI_2013_luento9_ed.wmv
- Luentojen aiheet 2017 (uudet tallenteet tulee luennoista 6-16)
- 1. 1.9. Kurssin alkuasiat, johdanto abstraktioon, adt pikaisesti
- 2. 4.9. Lyhyt kertaus, johdanto aikavaativuuteen, O-notaatio, funktioiden luokittelu
- 3. 5.9. Omega, Theta, o, funktioiden vertailu, aikavaativuuden laskeminen algoritmista
- 4. 11.9. Lyhyt kertaus aikavaativuudesta, Johdatus ADT, lista, java.util.LinkedList. Vector lyhyesti
- 5. 12.9. Kertaus Vector, kertaus LinkedList, TraLinkedList
- 6. 18.9. Pino, jono, pakka, rengas, taulukko, yhteenveto peräkkäisrakenteista.
- 7. 19.9. Johdanto puurakenteisiin, binääripuu, haku sisäjärjestetystä binääripuusta
- 8. 25.9. Sisäjärjestettyyn binääripuuhun lisäys, seuraaja, edeltäjä, poisto, AVL-puu
- 9. 26.9. Yleinen puu (kohdasta 57:28 alkaen), Joukko abstraktina tietotyyppinä, TraSet, java.util.Set pikaisesti
- 10. 2.10. Joukkokertaus, relaatio ja kuvaus, monilista, prioriteettijono, laukku
- 11. 3.10. Verkko käsitteenä. Lajittelu ongelmana, yksinkertaiset lajittelualgoritmit, pikalajittelu
- 12. 9.10. Pikavalinta, lomituslajittelu, kaukalo&;kantalukulajittelu, johdatus toteuttamiseen, kotelointi
- 13. 10.10. Parametrointi, Javan kokoelmajärjestelmä, listan taulukkopohjainen toteutus
- 14. 16.10. Listan dynaaminen linkitetty toteutus, iteraattorien toteutus
- 15. 17.10. Listan erikoistapauksien toteutus, joukon toteuttaminen, hajautus
- 16. 23.10. Hajautuskertaus, puun toteuttaminen, prioriteettijonon toteuttaminen, kasalajittelu joukon puutoteutukset, iteraattorien toteutus (kertaus),
- Sain pyynnön kirjata kunkin aiheen alkamisajan johonkin näkyviin. En nyt itse mahdottomasti haluasi itseäni katsella, eikä olisi joutavaa aikaakaan. Mutta jos näitä joku katselee kynä tai näppäimistö esillä, niin otan vastaan tietoja kunkin asian (esim. kohdan) alkamishetkestä luennoilla ja voin niitä yo. sisältöluetteloon lisätä.
- Luentojen aiheet (2013)
- Asioiden jakautuminen luennolle kutakuinkin sama kuin 2012.
- 2012 puutteelliset nauhoitukset on nyt paikattu (luennot 3, 7, 8, 9, 13 ja 14). Tallennukset löytyvät samasta paikasta kuin 2012 nauhoitukset.
- Luentojen aiheet (2012)
- 1. 4.9. Kurssin alkuasiat, johdanto algoritmeihin, abstraktioon ja abstrakteihin tietotyyppeihin
- 2. 5.9. Johdanto aikavaativuuteen, ylärajatarkastelu, aikavaativuusfunktioiden luokittelu
- 3. 10.9. Alarajatarkastelu, aikavaativuuden laskeminen algoritmista (2012: luentonauhoituksesta puuttuu toinen kanava)
- 4. 11.9. Kertaus aikavaativuuden laskemisesta. Kokoelmien parametrointi, abstrakti lista, java.util.LinkedList
- 5. 17.9. LinkedList kertaus, TraLinkedList, pino
- 6. 18.9. Jono, pakka, rengas, taulukon eri versiot ja niiden käyttö
- 7. 24.9. Johdanto puihin, yleinen puu (2012: 45min luento, tallennus puuttuu)
- 8. 25.9. Yleisen puun esimerkkejä, binääripuu melkein loppuun (2012: 100min luento, nauhoituksesta
puuttuu 20min alusta)
- 9. 1.10. Kertaus binääripuusta, seuraaja sisäjärjestyksessä, Poisto binääripuusta. Joukko ja sen operaatiot, ml.
sanakirja (2012: nauhoituksesta puuttuu 25min alusta sekä toinen näyttö)
- 10. 3.10. Kuvaus, prioriteettijono, monilista, laukku. Johdanto verkkoihin.
- 11. 8.10. Lajittelu ongelmana, yksinkertaiset lajittelut, pikalajittelu
- 12. 9.10. Pikavalinta, lomituslajittelu, kaukalolajittelu. Kotelointi ja parametrointi (ei Javan
parametrointia)
- 13. 15.10. Parametrointi Javalla, listan taulukkototeutus (2012: nauhoituksessa kamera suunnattu väärin)
- 14. 16.10. Listan dynaaminen toteutus, listan erikoistapaukset, puun toteutus (2012: nauhoituksesta
puuttuu toinen näyttö)
- 15. 22.10. Joukon toteuttamisvaihtoehdot, hajautus, prioritettijonon toteuttaminen
- 16. 23.10. Joukon puutoteutus (AVL-puu), läpikäyntien toteutus
Luennnolla
esitettyjä, ei monisteessa olevia esimerkkejä, mallivastauksia, harjoitusten pohjia, yms ohjelmanpätkiä
WWW-linkkejä TRA-materiaaliin
Käytettävät kääntäjät
- javac, versio >= 1.5.0
Miksi uusin Java, miksei 1.4.X ei kelpaa?
Java 1.5 (tai JSE5.0) tarjoaa juuri tälle kurssille:
- Geneeriset kokoelmat
- foreach -toiston
- Automaattiset muunnokset perustyypeistä vastaaviin olioihin.
- Helpompi syötteen lukeminen käyttäjältä.
- Kuinka tarkastat mikä java version on käytössä: kirjoita "java -version"
- java 1.5 cs:llä: /usr/local/bin/java5c
- Lisää .cshrc:hen rivit : "alias javac /usr/local/bin/java5c" ja "alias java /usr/local/bin/java5".
- tai laita ko hakemisto path-polkuun ennen /usr/bin/:ta
- tai käytä komentoa java5 ja java5c
- Vastaavasti java6c, java6, java7c, java7
- java 1.5 omalle koneelle: http://java.sun.com/, J2SE JDK 5.0
- java 1.5 mikroluokissa: ei ole vielä asennettu
Tietorakennekirjasto
- Harjoituksissa kirjastoa käytetään cs -koneella.
- Kirjasto on asennettu cs:lle:
kääntäminen: trajc Ohjelma.java
- ajaminen: traj Ohjelma
- Yleisemmin (kun java = java5, ja polku/tra.jar on paikka josta tra.jar löytyy)
- kääntäminen: javac -cp polku/tra.jar:. Ohjelma.java
- ajaminen: java -cp polku/tra.jar:. Ohjelma
- Windowsissa : tilalla ehkä pitää olla ;
- Eclipse:ssä:
- Projektissa hiiren 2-napilla Build Path -> Configure Build Path -> (Java Build Path ->) Libraries -> Add External JARs -> valitse alta lataamasi tra2017.jar, Order and Export valitse tra2017.jar.
- Using IntelliJ IDEA:
- For project: File -> Project Structure -> Libraries -> + -> choose downloaded file tra2017.jar.
- Using Netbeans (not checked, instructions are approximate!)
- For project: File -> Project Properties -> Libraries -> Add jar/directory -> choose downloaded file tra2017.jar.
- Dokumentaatio online
- Tästä voit ladata kirjaston ja dokut:
- 2017 versio: muutettu Set -> TraSet, AdjustablePriorityQueue on dokumentoitu. Alla on vanha fi.joensuu.cs.tra paketti ja uusi fi.uef.cs.tra paketti yhdessä yhteensopivuuden vuoksi. Vanha paketti jää jossain vaiheessa pois käytöstä.
Harjoitukset
Harjoitustehtäviä paperilla jaetaan harjoituksissa.
Luennnolla
esitettyjä, ei monisteessa olevia esimerkkejä, mallivastauksia, harjoitusten pohjia, yms ohjelmanpätkiä
Harjoitustyö
- Kurssin aiheista voi tehdä parityön. Lisäinformaatiota myöhemmin.
Last modified
Mon Oct 23 17:59:33 EEST 2017
SJ