58131 Tietorakenteet ja algoritmit (luonnos 22.1.2015)

Pääteemat Esitiedot Lähestyy oppimistavoitetta Saavuttaa oppimistavoitteita Syventää oppimistavoitteita
Algoritmien laatiminen,
oikeellisuus ja vaativuus
  • joukko-opin ja logiikan alkeet; todistamisen perustekniikat (Johdatus yliopistomatematiikkaan)
  • logaritmi- ja eksponenttifunktion perusominaisuudet; aritmeettisten ja geometristen sarjojen summa (koulumatematiikka)
  • ohjelmoi yksinkertaisia algoritmeja muualla matriisissa esitettyjen tietorakenteiden ja ratkaisumallien mukaan
  • määrittää yksinkertaisen algoritmin asymptoottisen aika- ja tilavaativuuden
  • tuntee O-notaation (funktioiden suuruusluokat)
  • tunnistaa esimerkkejä hieman vaativammista eri suunnittelumetodeja edustavista algoritmeista
  • perustelee yksinkertaisen algoritmin toiminnan invarianttien avulla
  • käyttää invariantteja normaalina osana ohjelmointia
  • analysoi algoritmin resurssivaatimuksia palautuskaavoilla (Algoritmien suunnittelu ja analyysi)
Perustietorakenteet ja
ohjelmointitaidon syventäminen
  • käyttää taulukkoa osana normaalia ohjelmointia (Ohjelmoinnin perusteet)
  • sujuva ohjelmointitaito (Ohjelmoinnin jatkokurssi)
  • ohjelmoi linkitetyn listan ja sen yksinkertaisia muunnelmia Javalla
  • kirjoittaa Javalla yksinkertaisia rekursiivisia ohjelmia
  • toteuttaa prioriteettijonon kekorakenteena
  • käyttää pinoa, jonoa, listaa ja puurakenteita osana normaalia ohjelmointia
  • käyttää ohjelmoinnissa rekursiota tarpeen mukaan
  • tuntee Javan tarjoamia työkaluja ja ratkaisuja kurssilla esiintyvien tietorakenteiden ja algoritmien toteuttamiseen
  • tekee Javalla epätriviaaleja tietorakenteita sisältävän ohjelman (Tietorakenteiden harjoitustyö)
  • soveltaa tietorakenteita tehokkaasti nykyaikaisissa ohjelmointiympäristöissä mm. rinnakkaistamalla
Hakemistorakenteet
  •  tuntee taulukosta etsimisen idean ja osaa ohjelmoida binäärihaun (Ohjelmoinnin perusteet)
  • ohjelmoi (tasapainottoman) binäärihakupuun perus-operaatiot
  • ymmärtää hajautuksen käsitteen ja toteuttaa jonkin perusversion hajautustaulusta
  • ymmärtää hakupuun tasapainoisuuden käsitteen ja seuraukset ja tuntee tasapainotustapoja
  • käyttää hakemistorakenteiden aikavaativuustuloksia sopivan rakenteen valitsemiseen
  • soveltaa hajautusta ja muita hakemistorakenteita yksinkertaisten algoritmisten ongelmien ratkaisemiseen
  • tuntee levymuistiin soveltuvia hakemistorakenteita
  • analysoi hakemistorakenteiden tasoitettua aikavaativuutta (Algoritmien suunnittelu ja analyysi)
Järjestäminen
  • vertailuihin perustuvan järjestämisen aikavaativuusalaraja Ω(n log n) (Johdatus yliopistomatematiikkaan)
  • toteuttaa Javalla jonkin neliöllisen järjestämisalgoritmin (Ohjelmoinnin jatkokurssi)
  • tuntee muutaman järjestämisalgoritmin ja ohjelmoi ainakin yhden järjestämisalgoritmin, jonka aikavaativuus on O(n log n)
  • tuntee keskeisten järjestämisalgoritmien aikavaativuudet ja rajoitukset
  • analysoi järjestämisalgoritmien aikavaativuutta myös keski-määräisessä tapauksessa (Algoritmien suunnittelu ja analyysi)
Verkot
  • tuntee verkkojen perusmääritelmät (Johdatus yliopistomatematiikkaan)
  • ohjelmoi verkon leveyssuuntaisen ja syvyyssuuntaisen läpikäynnin
  • selittää (kuvin, sanoin, esimerkein) lyhimpien polkujen ja pienimpien virittävien puiden perusalgoritmien toiminnan
  • soveltaa verkon läpikäyntejä, polunetsintää ja virittäviä puita erilaisten verkko-ongelmien ratkaisemiseksi
  • perustelee lyhimpien polkujen ja pienimpien virittävien puiden perusalgoritmien oikeellisuuden ja aikavaativuuden
  • ratkaisee optimointiongelmia verkkovuoalgoritmeja soveltaen (Diskreetti optimointi)
  • tunnistaa useita NP-täydellisiä verkko-ongelmia ja osaa selittää NP-täydellisyyden merkityksen (Algoritmien suunnittelu ja analyysi)

 

22.01.2015 - 18:23 Patrik Floréen
01.03.2011 - 13:22 Patrik Floréen