Tietorakenteet ja algoritmit II

Simo Juvaste, Matti Nykänen, Tietojenkäsittelytieteen laitos, Itä-Suomen yliopisto
(Data Structures and Algorithms II, 3cr)

English language version of this page (and course) can be found here

Sisältö

Virallinen kurssikuvaus
Alustava sisällönkuvaus
Aikataulu
Ilmoittautuminen
Arvostelu
Kuormittavuus
Materiaali/kirjallisuus
Luentojen tallenteet
WWW-linkkejä
Käytettävät kääntäjät
Tietorakennekirjasto
Harjoitukset
Tutorointi
Harjoitustyöt

Opinto-oppaan mukainen kurssikuvaus

Tietorakenteet ja algoritmit II (3 op) 3621318

Luennot 20 t, Harjoitukset 12 t
Osaamistavoitteet: Opiskelija osaa analysoida myös rekursiivisia algoritmeja sekä kokeellisesti mitata ja extrapoloida ohjelmien aikavaativuutta. Opiskelija ymmärtää graafien peruskäsitteet, erilaisten graafien ominaisuudet ja graafien käytön tietorakenteina. Opiskelija ymmärtää yleisimpien graafialgoritmien toimintaperiaatteen ja osaa laatia sekä analysoida yksinkertaisia graafialgoritmeja. Opiskelija tuntee erilaiset algoritmistrategiat ja osaa soveltaa niitä. Opiskelija osaa käyttää massamuistia tehokkaasti ja analysoida massamuistia käyttävien algoritmien aikavaativuuden
Sisältö: Monimutkaisempien algoritmien aikavaativuus, graafit tietorakenteina ja niiden käyttö, algoritmistrategiat ja massamuistin tietorakenteet.
Oppimateriaalit: Cormen, Leiserson, Rivest: Introduction to Algorithms
Edellytykset: Tietorakenteet ja algoritmit I

Kurssin asema

aineopintojen pakollinen kurssi pääaineopiskelijoille
erään aineopintojen keskeisimmän kurssin toinen osa

Kurssin sisältö

Tarpeelliset esitiedot

Aikavaativuusanalyysin perusteet (kertaluokat, aikavaativuuden analysointi algoritmista)
Perustietorakenteet (lista, pino, jono, puu, binääripuu, hajautus)
Kohtuullinen ohjelmointitaito Javalla, geneeriset kokoelmat

Käsiteltävät asiat (ei aivan käsittelyjärjestyksessä)

Analyysin perusteet (kertausta, jatkoa): 5 t
- kertaluokkien, aikavaativuuden laskemisen kertaus
- empiirinen tehokkuuden mittaus
- rekursiorelaatiot rekursiivisten alg. analyysissa
- tasoitettu vaativuus
- aikavaativuuden alarajan todistaminen
Strategiat: 5 t
- BF
- ahne
- hajoita ja hallitse
- peruutus
- branch and bound
- heuristiikat
- mjono-alg.
- dynaaminen ohjelmointi
Kehittyneemmät tietorakenteet 3 t
- Verkot
- B-puut
Perusalgoritmeja: 5 t
- leveys- ja syvyyssuunt. haku
- lyhin polku (Dijkstra ja Floyd)
- transitiivinen sulkeuma
- minimaalinen verkon virittävä puu (Prim ja Kruskal)
- topologinen järjestys
Ulkoisen muistin algoritmit 2 t

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 edelleen!

Aikataulu ja toteutus keväällä 2018

Aikataulu keväällä 2018

Joensuu: Simo Juvaste

Kuopio: Matti Nykänen

Katso Kuopion ohjelma päivityksineen Oodista/Lukarista ja seuraa sähköposti-ilmoituksia. Muutokset ilmoitetaan heti kun tiedetään.

Joensuun luennot 19.3. -- 8.5.2018

19.03.18 MA 12:00-14:00 TB180
20.03.18 TI 12:00-14:00 TB180
26.03.18 MA 12:00-14:00 TB180
09.04.18 MA 12:00-14:00 TB180
10.04.18 TI 12:00-14:00 TB180
16.04.18 MA 12:00-14:00 TB180
23.04.18 MA 12:00-14:00 TB180
24.04.18 TI 12:00-14:00 TB180
07.05.18 MA 12:00-14:00 TB180
08.05.18 TI 12:00-14:00 TB180

Harjoitukset 28.3. -- 14.5.2018

28.03.18 KE 12:00-14:00 TB180
12.04.18 TO 12:00-14:00 TB180
19.04.18 TO 12:00-14:00 TB180
26.04.18 TO 12:00-14:00 TB180
03.05.18 TO 12:00-14:00 TB180
14.05.18 MA 12:00-14:00 TB180

28.03.18 KE 14:00-16:00 TB180
12.04.18 TO 14:00-16:00 TB180
19.04.18 TO 14:00-16:00 TB180
26.04.18 TO 14:00-16:00 TB180
03.05.18 TO 14:00-16:00 TB180
14.05.18 MA 14:00-16:00 TB180

Harjoitustehtäväohjausta:

Joensuussa alkaen ti 27.3. klo 14-16 T/B247, ti 10.4. klo 14-16 T/B247, ti 17.4. klo 14-16 T/B247, ti 24.4. klo 14-16 T/B247, ke 2.5. 13-15 T/B247, ke 9.5. 14-16 T/B247
Kuopiossa ke 18.4. 10-12 F213.

Kurssikuulustelu harjoitukset tehneille

18.5. klo 12:00 -- 16:00 M100 (Joensuu) / SN200 (Kuopio)
Uusintakuulustelu 12.6. 12:00 -- 16:00 M100 (Joensuu) / SN100 (Kuopio)

Yleiset kuulustelut

Kalenterin mukaan

Ilmoittautuminen Web-oodilla

Viimeistään kurssin alkaessa.

Ajankäyttö / kuormittavuus

Keskimääräiselle opiskelijalle, keskimääräiseen arvosanaan:

Tietorakenteet ja algoritmit II, ajankäyttö

Viikkoja (h/l) 6 5

Viikottain Yhteensä

Luennot 4 20

Kertaus 1.2 6

Harjoitukset 2 12

Tekeminen 6 36

Loppukoe
2

Valmistautuminen
4

Yhteensä(t) 14.2 80

Yhteensä (op)
3.00

26.67

Kuormittavuus vaihtelee viikosta toiseen ja opiskelijasta toiseen. Erinomaiseen arvosanaan voi tarvita enemmän työtä.

Arvostelu keväällä 2018

Opiskelijat äänestivät ensimmäisellä luennolla:

Pakolliset arvosteltavat harjoitustehtävät, kuulustelu, demoista bonusta.

Harjoitusten seassa on 2-3 pakollista X-tehtävää.
X-tehtävät lähetetään etukäteen sähköpostilla ja ne arvostellaan.
Kullakin opiskelijalla on oltava oma ratkaisu, kopioita ei hyväksytä.
Kurssikuulusteluun osallistuakseen opiskelijan on lähetettävä kaikki X-tehtävät.
X-tehtävät muodostavat 30-40% (riippuen niiden määrästä) kurssin arvostelusta.
Loput 60-70% arvostelusta kurssikuulustelusta (jossa jätetään vähemmälle painolle ne käytännöllisemmät asiat jotka X-tehtävissä tuli testattua).
Tavallisista harjoitustehtävistä "vaaditaan" 1/3. 1/3 ylittävästä osuudesta max 10% bonusta.
Jos tehtävät jäävät alle 1/3, vastaavasti miinusta. Tehtävien tekemiseen siis vahvasti kannustetaan, mutta ei pakoteta kovalla rajalla.

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 ja X-tehtävien perusteella.

Aiemmilla kursseilla tehtyjen harjoitusten määrä ja kuulustelutulos ovat korreloineet vahvasti.

50% = 1, 60% = 2, 70% = 3, 80% = 4, 90% = 5.

Materiaali/kirjallisuus

Kirjallisuus

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.
- PDF luentorunko 2018 (vain uef.fi) (1.3Mt, 68s), sama löytyy myös allakuvatussa luentonauhoitusten hakemistosta salasanan takaa, mutta myös uef.fi:n ulkopuolelta.
- PDF -versio 2014 monisteesta (mustavalko) (vain uef.fi) (500kt, 96s)

Kevään 2016 luentojen nauhoitukset:

Video- ja materiaalihakemisto. 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.
TraII_2016_luentoX.mp4 on alkuperäinen MP4 tiedosto (H.264 / AVC / MPEG-4 AVC / MPEG-4 part 10; AAC) ~700Mt/kpl 1376x444 resoluutio). TraII_2016_luentoX_pieni.mp4 on tiivistetympi 1024x328 resoluutio, n. 95Mt/kpl.

Näitä voi katsoa vaikka mplayer:llä komennolla
mplayer http://tunnus:salasana@cs.uef.fi/pages/sjuva/traII_vid/TraII_2016_luento1.mp4

2016 luentojen aiheet

1. 4.4. Kurssin tavoittet ja sisältö, aikavaativuuskertaus, rekursiivinen aikavaativuus Fibonacci-esimerkin ylärajatarkasteluun saakka.
2. 6.4. Fib alarajatarkastelu, rekursiopuu, sanapituusesimerkki, kokeellinen aikavaativuusanalyysi
3. 11.2. Kokeellisen aikavaativuuden kertaus, extrapolointi, päätöspuu, johdanto verkkoihin, verkon operaatiot
4. 13.4. Syvyyssuuntainen haku, kehän etsiminen, Dijkstran algoritmi
5. 18.4. Dijkstra kertaus, Floyd, topologinen lajittelu, vahvasti yhtenäiset komponentit (ei algoritmia), suuntaamaton verkko, minimipainoinen virittävä puu (Primin algoritmi)
6. 20.4. Kruskalin algoritmi, leveyssuuntainen haku, leikkaussolmut, sovitus, maksimivirta
7. 25.4 Verkon toteuttaminen, algoritmistrategiat (ahne, hajoita-ja-hallitse, dynaaminen ohjelmointi, tasoitettu aikavaativuus)
8. 27.4. Algoritmistrategiat (haun rajoittaminen, satunnaistetut algoritmit), merkkijonon haku
9. 2.5. Ulkoinen muisti, puskurointi, ulkoinen lajittelu
10. 4.5. Joukon toteutus massamuistiin (organisointitapoja, hajautus, B-puu)

Luennolla esitettyjä, ei monisteessa olevia esimerkkejä, mallivastauksia, harjoitustehtävien pohjia, yms ohjelmanpätkiä

WWW-linkkejä TRA-materiaaliin

Käytettävät kääntäjät

javac, versio >= 1.5.0
Kuinka tarkastat mikä java version on käytössä: kirjoita "java -version"
java 1.7 cs:llä: javac, java (hakemistossa /usr/bin)

Tietorakennekirjasto

Käytämme samaa tietorakennekirjastoa kuin TRA1 kurssilla (myös verkkojen toteutukset tulossa).
Harjoituksissa kirjastoa käytetään cs ja cc -koneilla.
Kirjasto on asennettu cs:lle:
- ajaminen: traj Ohjelma
Yleisemmin (kun java = java6/7/8, 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.
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ä.
- Luokat sisältävä .jar paketti (Java8).
- Dokumentaatio online
Vanhoja versioita:
Dokumentaatio online
Tästä voit ladata kirjaston ja dokut:
- Luokat sisältävä jar -paketti (35kt) (päivitetty viimeksi Mon Feb 4 21:05:33 EET 2008 , korjattu silmukka verkon läpikäynnissä, lisätty AdjustablePriorityQueue)
- Luokat sisältävä jar -paketti (35kt) Java SE6/7 versio.
  - Uudessa versiossa mukana verkot, lista totetuttaa Iterable:n, prioriteettijonossa pieniä tyyppimuunnoksia, ListNode:n operaatioissa nimimuutoksia.
- tra.jar:n ja Dokumentaation (HTML) sisältävä zip -paketti (142kt) (2007 versio), ei sisällä yo 2008 korjauksia.

Harjoitukset

Harjoitus 1 (28.3.2018)
Harjoitus 2 (12.-13.4.2018)
Harjoitus 3 (19.-20.4.2018) (sisältää pakollisen X-tehtävän)
Harjoitus 4 (26.4.2018)
Harjoitus 5 (3.5.2018) (sisältää pakollisen X-tehtävän)
Harjoitus 6 (14.5.2018) (sisältää pakollisen X-tehtävän)

Harjoitustehtäviä paperilla jaetaan harjoituksissa ja luennolla.

Luennolla esitettyjä, ei monisteessa olevia esimerkkejä, mallivastauksia, harjoitustehtävien pohjia, yms ohjelmanpätkiä

Harjoitustyö

Kurssin aiheista voi tehdä parityön.

Last modified Mon May 7 11:59:17 EEST 2018 SJ

Tietorakenteet ja algoritmit II, ajankäyttö
Viikkoja (h/l)	6	5
	Viikottain	Yhteensä
Luennot	4	20
Kertaus	1.2	6

Harjoitukset	2	12
Tekeminen	6	36

Loppukoe		2
Valmistautuminen		4

Yhteensä(t)	14.2	80
Yhteensä (op)		3.00
26.67