Tietorakenteet ja algoritmit 2

Simo Juvaste, Tietojenkäsittelytieteen laitos, Itä-Suomen yliopisto
(Data Structures and Algorithms 2, 4cr)

Sisältö

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

Tietorakenteet ja algoritmit 2 (4 op) 175217

• Luennot 26 t, Harjoitukset 14 t
• Jatko Tietorakenteet ja algoritmit 1 kurssille. Keskimääräinen aikavaativuus, aikavaativuuksien alarajojen todistaminen. Algoritmisuunnittelustrategiat. Verkko abstraktina tietotyyppinä ja verkkoalgoritmit. Ulkoisen muistin käytön analysointi. Joukon totetuttaminen hakupuilla ja hajautuksella. Kirjallisuus: Cormen, Leiserson, Rivest: Introduction to Algorithms, Weiss: Data Structures and Algorithm Analysis in Java. Esitiedot: Tietorakenteet ja algoritmit 1.

Kurssin asema

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

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: 4-6 t
  • BF
  • ahne
  • hajoita ja hallitse
  • peruutus
  • branch and bound
  • heuristiikat
  • mjono-alg.
  • dynaaminen ohjelmointi
  • numeerinen approksimointi (matemaattiset ongelmat) (johdatus)
• Kehittyneemmät tietorakenteet 4
  • Verkot
  • B-puut
• Perusalgoritmeja: 5
  • 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 1-2
• Muuta (valinnaista) 0-2
  • online ja offline alg.
  • hahmontunnistus
  • satunnaisalg.
  • kombinatorinen optimointi

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!

Luennot 26 t

Simo Juvaste

• 3. periodilla 13.1. -- ~25.2.
  ke 14-16 T/2D106 Ei luentoa ke 17.2.!
  to 14-16 T/2D106
  Yksittäiset muutokset mahdollisia.

Harjoitukset 14 t

Simo Juvaste

• 21.1. -- ~4.3.
• Ryhmä 1: to 08-10 T/B179
  Ryhmä 2: to 10-12 T/B179

Ohjausta

• Harjoitustehtävien tekemisessä eteentuleviin ongelmiin.
• ke 24.2. klo 09-11

Loppukoe demot tehneille

• pe 26.2. 12.00-14 M101 (huom: yhdessä yleisen tentin kanssa)
  • Tulokset (28kt PNG, vain joensuu/uku/uef/.fi)

Yleiset kuulustelut

• Kalenterin mukaan

• Viimeistään kurssin alkaessa.
• Ilmeisesti ennen vuodenvaihdetta tehdyt ilmoittautumiset ovat kadonneet Oodi-päivityksessä?

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

Tietorakenteet ja algoritmit 2, ajankäyttö
Viikkoja (h/l)	7	6,5
	Viikottain	Yhteensä
Luennot	4	26
Kertaus	2	13
Harjoitukset	2	14
Tekeminen	6,5	45,5
Välikoe		2
Valmistautuminen		6
Yhteensä(t)	15,64	106,5
Yhteensä (op)		3,99
26,67

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

• Harjoitustehtäviä ja pakollisia X-tehtäviä.
• 1/3 tavallisista demoista tehtävä, harjoitusbonukset lasketaan 1/3 ylittävältä osalta.
• X-tehtävät ovat pakollisia. Vaikutus koko kurssin arvosteluun n. 40%.
• 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.
• 50% = 1, 60% = 2, 70% = 3, 80% = 4, 90% = 5.

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.
  • Monistuskulut 5 euroa.
  
  

Luennnolla esitettyjä, ei monisteessa olevia esimerkkejä, mallivastauksia, yms ohjelmanpätkiä

• Java 1.5 API
• LEDA
• Animation Aided Problem Solving
• Numerical Recipes
• The Stony Brook Algorithm Repository
• Computer Science Education Links
• JOHDATUS KORKEAKOULUMATEMATIIKKAAN (TTKK)

• javac, versio >= 1.5.0
• Kuinka tarkastat mikä java version on käytössä: kirjoita "java -version"
• java 1.5 cs:llä: /usr/local/jdk1.5.0/bin/javac ja /usr/local/jdk1.5.0/bin/java
  • Lisää .cshrc:hen rivit : "alias javac /usr/local/jdk1.5.0/bin/javac" ja "alias java /usr/local/jdk1.5.0/bin/java".
  • tai laita ko hakemisto path-polkuun ennen /usr/bin/:ta
  • tai käytä komentoa java5 ja java5c
• java 1.5 cc:llä: /opt/jdk1.5.0_02/bin/javac ja /opt/jdk1.5.0_02/bin/java
• java 1.5 omalle koneelle: http://java.sun.com/, J2SE JDK 5.0
• java 1.5 mikroluokissa: ei ole vielä asennettu

• 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 sekä cc: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
• 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 SE 1.6 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.

• Harjoitus 1 (21.1.2010)
• Harjoitus 2 (28.1.2010)
• Harjoitus 3 (4.2.2010) PDF-versio (sis kuvan)
• Harjoitus 4 (11.2.2010)
• Harjoitus 5 (18.2.2010)
• Harjoitus 6 (25.2.2010)
• Harjoitus 7 (4.3.2010)

Harjoitustehtäviä paperilla jaetaan harjoituksissa ja luennolla.

Muista täyttää opintojakson arviointilomake!

Kurssin tiedottamista varten on perustettu postituslista tkt-tra. (Voi tosin olla, että tra1 ja tra2 vaativat eri listan)

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