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: 10.09.2019 - 20.12.2019

Vastuuopettaja (voimassa 01.08.2020-31.07.2022): Ari Korhonen

Vastuuopettaja (koskee tätä kurssikertaa): Ari Korhonen

Kurssin yhteystiedot (voimassa 06.08.2019-21.12.2112):

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.

    AihepiiriA: Aina välttämätön ainesB: Usein tarpeellinen ainesC: Joskus hyödyllinen aines
    Perustieto-rakenteet ja algoritmitAbstraktien 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-rakenteetLinkitetyn listan, binääripuun ja verkon määritelmät; puiden läpikäyntialgoritmien (esi-, sisä-, jälki- ja tasojärjestys) toiminnan ymmärtäminenPuiden 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 toteutuksetTehokkaan tietorakenteen valinta annettuun sovellukseen; erilaiset puiden läpikäyntialgoritmien toteutukset (binääripuu, yleinen puu, rekursiivinen ja ei-rekursiivinen) 
    Järjestämis-menetelmätJä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.
    HakurakenteetADT: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 vertailuSyvällisempi hakurakenteiden tuntemus ja kyky valita tehokas menetelmä annettuun sovellukseen.
    PrioriteettijonotADT:n prioriteettijono määrittely; binäärikeon operaatioiden analyyttisten ominaisuuksien tunteminenBinäärikeon toteutus (taulukko) ja sen vastaavan binääripuu-esitysmuodon tuntemus; lisäys- ja suurimman alkion poistoalgoritmien toteutus ja analyysiLineaarisessa ajassa toimiva BuildHeap algoritmi; kekojärjestäminen
    Verkko-algoritmitVerkon 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-analyysiAlgoritmianalyysin matemaattinen perusta (mm. ylä- ja alarajan käsitteet, eksponentti- ja logaritmifunktiot, funktioiden kasvunopeuksien vertailu, jne.), algoritmien lukutaito ja iso O -notaatioIteratiivisen ja rekursiivisen algoritmin matemaattinen analyysi, iso O -notaation syventäminen (mm. theta ja omega), yksinkertaisten rekursioyhtälöiden ratkaisu, tietorakenteiden ja algoritmien käsitteellinen luokitteluAnalyyttisten 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:

    Kurssilla on käytössä A+-järjestelmä kurssimateriaalien jakamiseen, josta löytyvät luentomateriaalien lisäksi myös harjoitustehtävät. Linkki A+-järjestelmään avataan ja julkaistaan ensimmäisellä luennolla. 

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ä. 

Description

Registration and further information