Tietorakenteet ja algoritmit 1
Simo Juvaste, Tietojenkäsittelytieteen laitos, Joensuun yliopisto
(Data Structures and Algorithms 1, 5 cr)
Sisältö
Opinto-oppaan mukainen kurssikuvaus
Tietorakenteet ja algoritmit 1 (5 op) 175211
- Luennot 32 t, Harjoitukset 16 t
- Johdatus algoritmien vaativuuteen. Tietojenkäsittelyssä tavallisimmin
käytetyt tietorakenteet ja niiden hyödyntäminen. Tietorakenteiden käyttäminen
ja toteuttaminen Java-kielellä. Kirjallisuus: Cormen, Leiserson, Rivest:
Introduction to Algorithms, Weiss: Data Structures and Algorithm Analysis in
Java. Esitiedot: Ohjelmointi.
Kurssin asema
- aineopintojen pakollinen kurssi
- aineopintojen keskeisimpiä kursseja
Kurssin sisältö
Tarpeelliset esitiedot
- Kohtuullinen ohjelmointitaito Javalla.
- 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 keväällä 2009
Luennot 32 t Simo Juvaste
- 2.3. -- 28.4.
ma 12-14 T2/D106
ti 14-16 T2/D106
Harjoitukset 16 t Simo Juvaste
- Ryhmä 1: to 10-12 T/B179
Ryhmä 2: to 12-14 T/B179
- Myös 16.4., mutta ei 30.4. vaan ma 4.5. 12-14 T2/D106 (molemmat ryhmät).
Ohjausta
- Harjoitustehtävien tekemisessä eteentuleviin ongelmiin.
- ke klo 10-12 T2/D102 (luentosalia vastapäätä oleva pienempi luokka).
- Myös ke 8.4. ja ke 29.4., mutta ei 15.4.
Kurssin loppukoe
Yleiset kuulustelut
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 keväällä 2009
- Noin 40-50% pakollisista X-tehtävistä, loput loppukokeesta. Muista harjoituksista bonusta 1/3 ylittävästä osasta.
Materiaali/kirjallisuus
Kirjallisuus
- Liang: Introduction to Java Programming, comprehensive 7th edition
- 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, n. 100 sivua
Luennnolla
esitettyjä, ei monisteessa olevia esimerkkejä, mallivastauksia, 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
- java 1.5 cc:llä: /usr/local/jdk1.5.0_16/bin/javac /usr/local/jdk1.5.0_16/bin/java
- 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 ja cc -koneilla.
- Kirjasto on asennettu cs:lle:
kääntäminen: trajc Ohjelma.java
- ajaminen: traj Ohjelma
- cc:llä:
Kopioi alta tra.jar itsellesi cc:lle.
- /usr/local/jdk1.5.0_16/bin/javac -cp tra.jar:. Ohjelma.java
- /usr/local/jdk1.5.0_16/bin/java -cp tra.jar:. Ohjelma
- Tai tee siitä alias
- alias trajc /usr/local/jdk1.5.0_16/bin/javac -cp tra.jar:.
- alias traj /usr/local/jdk1.5.0_16/bin/java -cp tra.jar:.
- Nämä voi laittaa komentokuoreen oletuksiksi, esim .cshrc
- tra.jar:n voi toki laittaa muuallekin.
- 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 ;
- Dokumentaatio online
- Tästä voit ladata kirjaston ja dokut:
Harjoitukset
Harjoitustehtäviä paperilla jaetaan harjoituksissa ja luennoilla.
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ö
- Kurssin aiheista voi tehdä parityön. Lisäinformaationta myöhemmin.
Last modified
Tue Mar 15 13:15:59 EET 2011
SJ
