Huomaa! Kurssikuvaus vahvistetaan kahdeksi lukuvuodeksi (1.8.2018-31.7.2020) kerrallaan ja esimerkiksi osaamistavoitteet, arviontimenetelmät ja keskeinen sisältö pysyvät pääsääntöisesti samana. Kullakin toteutuskerralla voidaan kuitenkin kurssiesitteen avulla tarkentaa ja muuttaa kurssin toteutustapaa, kuten kontaktiopetuksen järjestämistapaa, arviointimenetelmien painotusta tai materiaaleja.
OSAAMISTAVOITTEET
Kurssin suoritettuasi osaat määritellä, vertailla ja toteuttaa perustietorakenteita ja algoritmeja sekä nimetä ja valita niitä esim. hakurakenteiksi, järjestämisongelmaan ja verkon läpikäyntiin. Lisäksi kykenet tunnistamaan ja esittelemään tarkemmin annetun tietorakenteen tai algoritmin sekä osaat antaa esimerkkejä niiden toiminnasta. Pystyt myös keskustelemaan muista keskeisistä tietorakenteista ja algoritmeista käyttäen alan tyypillistä terminologiaa.
Laajuus: 5
Aikataulu: 08.09.2020 - 18.12.2020
Vastuuopettaja (voimassa 01.08.2020-31.07.2022): Ari Korhonen
Vastuuopettaja (koskee tätä kurssikertaa): Ari Korhonen
Kurssin yhteystiedot (voimassa 12.08.2020-21.12.2112):
Laskuharjoitukset: Juuso Ahlroos, Iikka Frestadius, Ella Hakala, Emil Hiitola, Lionel Irrmann, Katariina Tuovinen ja Ville Vehniainen. Assistentit ovat tavattavissa laskuharjoitustilaisuuksissa.
Pääassistentti: Artturi Tilanterä.
Luennot: Ari Korhonen
Vastaanottoajat: sovi aika lähettämällä sähköpostia osoitteeseen cs-a1141@aalto.fi. Luennoija on tavattavissa Zoomin välityksellä tai T-talon huoneessa A138 (jos kampus on auki). Puh. 050-383 1363.
Kurssin CEFR-taso (koskee tätä kurssikertaa):
Opetuskieli ja suorituskielet (voimassa 01.08.2020-31.07.2022):
Opetuskieli: suomi
Suorituskielet: suomi, ruotsi
SISÄLTÖ, ARVIOINTI JA KUORMITTAVUUS
Sisältö
Voimassa 01.08.2020-31.07.2022:
Lineaariset tietorakenteet, puurakenteet ja verkot. Haku- ja järjestämismenetelmiä. Algoritmianalyysin perusteet.
Koskee tätä kurssikertaa:
Opintojakson suoritettuasi ja...
...omaksuttuasi aina välttämättömän aineksen (A) osaat 1) määritellä käsitteitä kuten minimaalinen virityspuu; 2) määritellä abstrakteja tietotyyppejä kuten pino, jono, hakurakenne ja prioriteettijono; 3) kertoa niiden erilaisista toteutustavoista; 4) nimetä keskeisiä tietorakenteita ja algoritmejä esim. hakurakenteiksi, järjestämisongelmaan sekä verkon läpikäyntiin; 5) tunnistaa ja esitellä tarkemmin annetun tietorakenteen ja algoritmin; 6) antaa esimerkkejä annetun algoritmin toiminnasta; ja 7) keskustella myös muista keskeisistä tietorakenteista ja algoritmeistä käyttäen alan tieteellisiä termejä (ml. iso O -notaatio)
...omaksuttuasi edellisten lisäksi myös usein tarpeellisen aineksen (B) osaat 1) vertailla tietorakenteiden toteutuksia; 2) vertailla algoritmeja niiden analyyttisten ominaisuuksien (kuten esimerkiksi suoritusnopeus) suhteen; 3) valita joukosta sopivan tietorakenteen ja algoritmin eri tilanteissa; 4) toteuttaa tietorakenteita ja algoritmeja ohelmistojen toteuttamiseksi;
...omaksuttuasi edellisten lisäksi vielä joskus hyödyllisen aineksenkin (C) osaat 1) toteuttaa tietorakenteita ja algoritmeja useilla vaihtoehtoisilla tavoilla; 2) yhdistellä tietorakenteita ja algoritmeja suorituskyvyn parantamiseksi; 3) vertailla eri toteutustapojen analyyttisiä ominaisuuksia sekä matemaattisesti että empiirisesti; 4) perustella ja valita sopivin vaihtoehto tiettyyn sovellukseen; 5) suunnitella ja toteuttaa ohjelmistoja modulaarisesti jakamalla laajempi ohjelmisto pienemmiksi osakokonaisuuksiksi, jotka voidaan toteuttaa tunnetuilla tietorakenteilla ja algoritmeilla.
Toteutus, työmuodot ja arvosteluperusteet
Voimassa 01.08.2020-31.07.2022:
Kotitehtävät, harjoitustyö ja tentti.
Koskee tätä kurssikertaa:
Kurssin sisältö on seuraavassa jaettu kolmeen osaan, joista "aina välttämätön aines" kuvaa läpipääsyyn edellytettäviä minimivaatimuksia tiedoille ja taidoille (tehtävissä taso A, arvosana 1/5). Tällä tasolla opiskelijan tulee kyetä mainitun tietorakenteen tai algoritmin toiminnan selittämiseen sanallisesti (osoituksena ymmärtämisestä) ja käyttäen apuna esimerkkiä (koodinlukutaito riittävällä yksityiskohtien tasolla). Esimerkeissä tulee olla niin paljon yksityiskohtia, että myös tietorakenteen tai algoritmin analyyttiset ominaisuudet käyvät ilmi. Esimerkkitehtävässä lähtökohtana voisi olla vaikkapa pikajärjestämismenetelmän ohjelmakoodi, josta kyseisen algoritmin toiminta pitäisi kyetä selittämään käyttäen apuna sopivia esimerkkejä. Opiskelijan tuottamista esimerkeistä tulisi käydä ilmi miksi ko. algoritmin pahimman tapauksen aikavaativuus on neliöllinen vaikka se keskimäärin toimiikin "n log n" ajassa.
Edellä mainittu ei kuitenkaan riitä niiden opiskelijoiden kohdalla, jotka lukevat enemmän tietotekniikkaa (kurssi kuuluu sivuaineen pakollisiin kursseihin). Jos TRAK on jollekin tulevalle kurssille esitietovaatimuksena on em. tietojen ja taitojen lisäksi hallittava myös "usein tarpeellinen aines" (tehtävissä taso B, arvosana 3/5). Tällä tasolla opiskelijan tulee kyetä myös tuottamaan koodia ja näin soveltamaan oppimiaan asioita uusien yksinkertaisten algoritmien kehittämiseen. Esimerkkitehtävä voisi olla vaikkapa uuden algoritmin kirjoittaminen verkon yhtenäisten komponenttien löytämiseen. Tämä edellyttää sekä käsitteellistä ymmärrystä (verkon yhtenäinen komponentti) että sopivan kurssilla opetetun algoritmin soveltamista (esim. syvyyssuuntainen haku) annetun uuden ongelman ratkaisuun. Myös kyky vertailla kahta samaa laskennallista ongelmaa ratkovaa algoritmia keskenään on tärkeä taito. Esimerkkinä voisi olla vaikkapa kolmen eri järjestämismenetelmän (esim. pikajärjestämismenetelmä, kekojäjestäminen ja lomitusjärjestäminen) vertailu keskenään annettujen kriteerien (esim. stabiilius, muistin kulutus ja aikakompleksisuus) perusteella.
Erityisesti sivuaineopiskelijoille suositellaan lisäksi ainakin joitain asioita sarakkeesta "joskus hyödyllinen aines" (tehtävissä taso C). Sarakkeet vastaavat siis karkeasti arvosanatavoitteita 1-2, 3 ja 4-5, vastaavasti.
Aihepiiri A: Aina välttämätön aines B: Usein tarpeellinen aines C: Joskus hyödyllinen aines Perustieto-rakenteet ja algoritmit Abstraktien tietotyyppien (ADT) pino ja jono toiminnan ymmärtäminen (LIFO- ja FIFO-periaate); joidenkin näiden sovellusten (esim. DFS ja BFS) ja analyyttisten ominaisuuksien tunteminen. Pinon ja jonon soveltaminen johonkin laskennalliseen ongelmaan (esim. infix-postfix -muunnos tai lyhimmän reitin etsiminen painottamattomassa verkossa). Aihepiirin syventäminen esim. toteuttamalla pinoja ja jonoja eri tavoin (mm. (sirkulaarisena) taulukkona ja linkitetyn listan avulla). Talletus-rakenteet Linkitetyn listan, binääripuun ja verkon määritelmät; puiden läpikäyntialgoritmien (esi-, sisä-, jälki- ja tasojärjestys) toiminnan ymmärtäminen Puiden toteutustapoja (mm. binääripuu ja yleinen puu sekä täydellisen binääripuun toteuttaminen taulukolla), verkkojen esittäminen tietorakenteina (vieruslista ja vierusmatriisi); binääripuiden läpikäyntialgoritmien toteutukset Tehokkaan tietorakenteen valinta annettuun sovellukseen; erilaiset puiden läpikäyntialgoritmien toteutukset (binääripuu, yleinen puu, rekursiivinen ja ei-rekursiivinen) Järjestämis-menetelmät Järjestämisongelman määrittely; joidenkin yleiskäyttöisten j-menetelmien nimeäminen ja niiden analyyttisten ominaisuuksien tunteminen. Jonkin rekursiivisen (esim. quicksort tai mergesort) ja ei-rekursiivisen (esim. lisäysjärjestäminen tai kekojärjestäminen) j-menetelmän toteutus, analyysi ja keskinäinen vertailu. Syvällisempi j-menetelmien tuntemus ja kyky valita tehokas menetelmä annettuun sovellukseen. Hakurakenteet ADT:n hakurakenne määrittely; joidenkin hakurakenteiden analyyttisten ominaisuuksien tuntemus ja vertailu (esim. järjestetty taulukko vs. binäärinen hakupuu). Tasapainotettujen hakupuiden (esim. AVL-puu ja B-puu) ja hajautusmenetelmien (esim. ketjutettu hajautus ja lineaarinen kokeilu) tuntemus; näiden ominaisuuksien vertailu Syvällisempi hakurakenteiden tuntemus ja kyky valita tehokas menetelmä annettuun sovellukseen. Prioriteettijonot ADT:n prioriteettijono määrittely; binäärikeon operaatioiden analyyttisten ominaisuuksien tunteminen Binäärikeon toteutus (taulukko) ja sen vastaavan binääripuu-esitysmuodon tuntemus; lisäys- ja suurimman alkion poistoalgoritmien toteutus ja analyysi Lineaarisessa ajassa toimiva BuildHeap algoritmi; kekojärjestäminen Verkko-algoritmit Verkon läpikäyntialgoritmien toiminnan ymmärtäminen (DFS, BFS). Käsitteet minimaalinen virityspuu ja verkon lyhimmin poluin virittävä puu. Verkon läpikäyntialgoritmien toteutus; Primin ja Dijkstran algoritmit; Omien pienten algoritmien kirjoittaminen (esim. DFS:n soveltaminen verkon yhtenäisyyden tarkistamiseen). Verkkoteoriaa; Joukot ja verkot; Kruskalin algoritmi; Topologinen lajittelu; lisää sovelluksia Algoritmi-analyysi Algoritmianalyysin matemaattinen perusta (mm. ylä- ja alarajan käsitteet, eksponentti- ja logaritmifunktiot, funktioiden kasvunopeuksien vertailu, jne.), algoritmien lukutaito ja iso O -notaatio Iteratiivisen ja rekursiivisen algoritmin matemaattinen analyysi, iso O -notaation syventäminen (mm. theta ja omega), yksinkertaisten rekursioyhtälöiden ratkaisu, tietorakenteiden ja algoritmien käsitteellinen luokittelu Analyyttisten taitojen syventäminen (esim. pikku o, rekursioyhtälöiden erilaiset ratkaisumenetelmät, kompleksisuusteoria ja kokeellinen algoritmianalyysi)
Työmäärä toteutustavoittain
Voimassa 01.08.2020-31.07.2022:
Luento-opetus 14 h, itsenäinen työskentely ja pienryhmäopetus 76 h, ryhmätyöskentely 40 h ja tentti 3 h.
Koskee tätä kurssikertaa:
Kurssin oppiaines on monin paikoin kumulatiivista (esim. kurssin loppupään verkkoalgoritmit nojaavat kurssin alussa esitettyihin abstraktioihin, kuten pinoon ja jonoon, ja tasapainotettujen hakupuiden toiminnan ymmärtämiseksi tulee ymmärtää yksinkertaisempi binäärinen hakupuu). Kumulatiivisuus näkyy myös kurssirakenteessa (kurssit perustuvat aikaisemmilla kursseilla opittuihin asioihin). Siksi oma tavoitetaso kannattaa heti alussa asettaa sellaiseksi, ettei myöhemmin ajaudu ongelmiin. Toisin sanoen, varaa kurssin suorittamiseen riittävästi aikaa koko syksyn ajalle. Tasaisen ajankäytön perusteella, jos 5 op = 132 tuntia jaetaan 13 viikolle, niin kurssiin tulisi käyttää reilut 10 tuntia viikossa. Todellisuudessa viikkotuntimäärä saattaa vaihdella mm. siksi, että välissä on tenttiviikko, jolloin ei ole määräaikoja ja saatat käyttää aikaa enemmän muihin kursseihin. Suositus on, että varaat kalenterista aikaa kurssille useampana päivänä viikossa.
PERUSTIETOJA
Oppimateriaali
Voimassa 01.08.2020-31.07.2022:
Ilmoitetaan kurssin MyCourses-sivulla.
Koskee tätä kurssikertaa:
Kurssin oppikirja on Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser: Data Structures and Algorithms in Python, Wiley, 2013. Se on perinteinen paperille painettu kirja, jonka esimerkeissä käytetään pääsääntöisesti Pythonia, kuten tämän kurssin harjoituksissakin. Kirja on saatavilla Aallon opiskelijoille verkossa. Linkki kirjan tietueeseen Aalto-Finnassa on: https://aalto.finna.fi/Record/alli.931781.
Toisaalta kurssi pyrkii olemaan ns. ”ohjelmointikieliriippumaton” ja opettamaan asioita yleisesti eikä tiettyyn ohjelmointikieleen sitoutuen. Siksi kurssimateriaalissa on esimerkkejä myös muilla ohjelmointikielillä ja esimerkiksi Pythonia muistuttavalla pseudo-kielellä, jonka ideana on tiivistää algoritmin idea ja karsia pois yksityskohdat, jotka tarvitaan ohjelmointikielen kääntäjää tai tulkkia varten.
Kursilla on käytössä myös OpenDSA-projektissa syntynyt sähköinen oppikirjana, joka on julkaistu vapaasti jaettavaksi MIT:n lisenssillä. Kirja sisältää tekstin ja kuvien lisäksi myös vuorovaikutteisia animaatioita, joita hyödynnetään kurssilla myös tehtävissä. Kirjan koodiesimerkit ovat Javalla ja C++:lla.
Muitakin oppikirjoja voi käyttää. Hyvä ostos on esimerkiksi rinnakkaiskurssilla (CS-A1140) käytössä oleva Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein: Introduction to Algorithms, joka on luettavissa verkossa Aalto-tunnuksilla. Sen esimerkit ovat pseudo-koodia.
Suomenkielisiäkin kirjoja on olemassa, ks. esim. Antti Laaksosen vapaasti saatavilla oleva Tietorakenteet ja algoritmit -kirja, jossa esimerkit ovat Javalla.
Mikäli kaipaat esimerkkejä nimen omaan Pythonilla, hanki ensi mainittu paperinen kirja. Sen hankkiminen ei kuitenkaan ole välttämätöntä, jos tulet toimeen jollain muulla vastaavalla oppikirjalla.
Esitiedot
Voimassa 01.08.2020-31.07.2022:
CS-A1111 Ohjelmoinnin peruskurssi Y1
SDG: Kestävän kehityksen tavoitteet
4 Hyvä koulutus
9 Kestävää teollisuutta, innovaatioita ja infrastruktuureja
13 Ilmastotekoja
LISÄTIETOJA
Lisätietoja
Voimassa 01.08.2020-31.07.2022:
CS-A1143 on sama kurssi englanniksi, molempia ei voi saada tutkintoon.
Koskee tätä kurssikertaa:
Kurssin esitietovaatimuksena on CS-A1111 Ohjelmoinnin peruskurssi Y1. Seuraavassa on lueteltu eräitä käsitteellisiä asioita, jotka ainakin on syytä hallita hyvin ennen kurssille tuloa. Voit käydä verestämässä muistiasi hyödyntämällä esitietokurssin luentomateriaalia ja harjoituksia. Mikäli aihepiiri ei ole tuttu, suositellaan se kerrattavaksi.
- Ohjelmointi, muuttujat, lausekkeet
- totuusarvot, listat, valinta
- koodin laatu, refaktorointi, vakiot, näkyvyys
- kääntäminen
- alkeistyypit, viittaustyypit
- silmukat, käyttöalue
- merkkijonot
- hakemistot
- ohjelman ajonaikainen toiminta
- taulukot
- rekursio
- syöte- ja tulostevirrat, tiedostot.
Kurssin aikataulu
Koskee tätä kurssikertaa:
Ks. kurssin kalenteri MyCoursesissa. Tarkempi aikataulu löytyy A+-järjestelmästä.