Kurssiaiheet 1 ja 2¶

Viikkoharkat¶

Ei viikkoharjoituksia ennen viikkoa 3.

Itseopiskelu (videot ja kalvot suomeksi)¶

Algoritmit ja pseudokoodi¶

Video algoritmi ja pseudokoodi

kalvot algoritmi ja pseudokoodi

Pseudokoodi¶

Video pseudokoodi

kalvot pseudokoodi

Pala kerrallaan¶

Video pala kerrallaan

kalvot pala kerrallaan

Lisäysjärjestäminen¶

Video lisäysjärjestäminen

kalvot lisäysjärjestäminen

Pseudokoodista toteutukseen¶

Video pseudokoodista toteutukseen

kalvot pseudokoodista toteutukseen

Viikko01 - Sanasto

Luentokysymykset¶

Kysymys 1

Algoritmi on

tietokoneohjelma, joka on kirjoitettu jollain ohjelmointikielellä, kuten C++ tai Java

laitteisto, jossa tietokoneohjelma toimii

kuvaus menetelmästä ongelman ratkaisemiseksi

kokoelma dataa tai materiaalia, jota tarvitaan jonkin ongelman ratkaisemiseen

Kysymys 2

Mitkä seuraavista ovat hyvin määritellyn algoritmin tärkeitä ominaisuuksia?

Algoritmin jokaisella vaiheella tai käskyllä tulisi olla vain yksi mahdollinen tulkinta.

Järjestyksen, jossa algoritmivaiheet suoritetaan, on oltava yksilöllinen.

Algoritmi on esitettävä jollakin ohjelmointikielellä, kuten C++, Java tai Python.

Algoritmin jokaisen vaiheen tai käskyn tulee vastata täsmälleen yhtä ohjelmointikoodin riviä.

Ainoat ihmiset, jotka voivat ymmärtää tai käyttää algoritmia, ovat sen keksijät.

Kysymys 1

Oletetaan, että henkilö X esittää algoritmin pseudokoodilla ja henkilö Y lukee sen. Mitä oletuksia X voi tehdä Y:stä?

X voi olettaa, että Y aikoo kirjoittaa pseudokoodista C++:n.

X voi olettaa, että Y ymmärtää tyypillisiä ohjelmointikielen ohjauslohkoja: for-silmukat, if-then-else lohkot jne.

X voi olettaa, että Y ymmärtää englantia.

X voi olettaa, että Y ymmärtää, mikä on muuttuja ja kuinka sitä käytetään koodia kirjoitettaessa.

X voi olettaa, että Y osaa kirjoittaa pseudokoodista ohjelmakoodia, kuten C++ tai Python

Kysymys 2

Oletetaan, että henkilö X on keksinyt uuden algoritmin tietyn ongelman ratkaisemiseksi. X kirjoittaa pseudokoodin uudelle algoritmille. Mikä seuraavista kuvaa parhaiten sitä, mikä X:n päätavoite pitäisi olla esitellessäsi uutta algoritmia pseudokoodina?

mahdollistaa se, että lukija voi tuottaa mahdollisimman nopeasti ja helposti toimivan C++-koodin algoritmille

varmistaa, että lukija tietää, mikä on paras laitteisto uuden algoritmin suorittamiseen

välittää jokaiselle lukijalle tarvittavat laskentavaiheet ja algoritmin olennaiset muuttujat ja parametrit

osoittaa lukijalle, että X:n uusi algoritmi on paras algoritmi tietyn ongelman ratkaisemiseen

Kysymys 1

Tyypillisesti algoritmin pseudokoodi ei sisällä virheiden tai syötetietojen oikeellisuuden testausta, kun taas tosielämän sovellusten koodin tulisi sisältää tällainen testaus. Mikä seuraavista on paras selitys tälle pseudokoodin testauksen puutteelle?

Koska pseudokoodia ei voida kääntää ja ajaa tietokoneessa, on mahdotonta sisällyttää pseudokoodiin testausta.

Pseudokoodin kirjoittajilla ei ole aavistustakaan siitä, millaista testausta tarvittaisiin.

Koska kukaan ohjelmoija ei kirjoita pseudokoodiin perustuvaa tosielämän sovelluskoodia, tällaisen testauksen sisällyttäminen pseudokoodiin on turhaa.

Testauksen sisällyttäminen pseudokoodiin pidentäisi sitä ja tekisi siitä vähemmän luettavan. Heikko luettavuus vaikeuttaisi algoritmin toiminnan ymmärtämistä.

Kysymys 2

Oletetaan, että algoritmille on annettu pseudokoodi. Toteutettaessa algoritmia jollain ohjelmointikielellä, kuten C++, mikä seuraavista tulee ottaa huomioon?

Meidän pitäisi kopioida kaikki pseudokoodin kommentit suoraan C++-koodiin.

Meidän tulee varmistaa, että C++-koodin rivien määrä on täsmälleen sama kuin pseudokoodin rivien määrä.

Meidän tulee varmistaa, että C++:n syntaksivaatimukset täyttyvät.

Meidän pitäisi miettiä, mitä C++:n ominaisuuksia voimme käyttää algoritmin toiminnan nopeuttamiseksi.

Kysymys 1

Mikä seuraavista kuvaa parhaiten pala kerrallaan -strategiaa?

Alkuperäinen ongelma on jaettu pienempiin osaongelmiin, jotka kaikki ratkaistaan yhdessä.

Alkuperäisestä ongelmasta otetaan vain pieni osa ja tämä pieni osa on ratkaistu. Tätä toistetaan, kunnes alkuperäinen ongelma on ratkaistu.

Voitamme ongelman olettaen, että meidän on ratkaistava ongelma joissakin erityisissä tapauksissa. Muut tapaukset voimme jättää kokonaan huomiotta.

Oraakkeliksi kutsuttua erityistä ohjelmistoa käytetään etsimään ongelman yksittäinen osa, josta ratkaisu löytyy.

Kysymys 2

Lisäyslajittelu toimii

löytämällä oikea paikka kullekin elementille jo lajiteltuja elementtejä vuorotellen siirtämällä

vertaamalla satunnaisia elementtejä ja vaihtamalla niitä tarvittaessa

vertaamalla kutakin viereistä elementtiä ja vaihtamalla niitä tarvittaessa

Kysymys 3

Kun lisäyslajitteluun syötettävän tiedon koko kasvaa, lisäyslajittelun suoritettavien laskelmien määrä..

pysyy samana

lisääntyy

vähenee

voi joko kasvaa tai laskea

Kysymys 4

Mikä seuraavista osoittaa, että lisäyslajittelu käyttää pala kerrallaan -strategiaa?

Laskuria, jota käytetään osoittamaan, mitä elementtiä käsitellään seuraavaksi, pienennetään jokaisessa iteraatiossa.

Lopullisessa lajitetussa taulukossa elementit lajitellaan suurimmasta pienimpään.

Jokaisella iteraatiolla vielä lajiteltavana olevien elementtien määrä pienenee.

Lajiteltavan taulukon koko ei koskaan kasva.

Kysymys 1

Muotoile kurssin kannalta keskeinen kysymys, johon tämän viikon videot antavat vastauksen.

Kysymys 2

Minkä videon aiheesta pitäisi erityisesti keskustella keskustelutilaisuudessa?

algoritmi

pseudokoodi

hajota ja hallitse

lisäyslajittelu

pseudokoodista toteutukseen

Kysymys 3

Oliko videoiden sisällössä jotain erityisen vaikeaa? Entä mielenkiintoista? Jotain josta haluaisit oppia lisää?

Linkkejä viikon aiheisiin:

Wikipedian pseudokoodiesimerkit

Viikkotehtävien palautus¶

Ei vielä mitään palautettavaa

Kurssiaihe 2¶

Itseopiskelu (videot ja kalvot suomeksi)¶

Tehokkuuden mittaaminen ja sen rajat¶

video tehokkuuden mittaaminen

kalvot tehokkuuden mittaaminen

Asymptoottisen tehokkuuden idea¶

video asymptoottisen tehokkuuden idea

kalvot tehokkuuden idea

Datan jakaminen¶

video datan jakaminen

kalvot datan jakaminen

Rekursio¶

video rekursio

kalvot rekursio

Viikko02 - Sanasto

Luentokysymykset¶

Kysymys 1

Mitä oikeastaan mitataan, kun mitataan algoritmin tehokkuutta?

Suoritettujen toimintojen määrää

Millisekunteja

Algoritmissa käytettyjen muuttujien määrää

Koodirivien määrää algoritmin pseudokoodissa

Kysymys 2

Miksi algoritmin asymptoottinen suorituskyky on kiinnostava?

Sen avulla voidaan arvioida toteutuksen koodirivien lukumäärä

Sen avulla tiedämme, miten algoritmin tehokkuus muuttuu syötetietojen koon kasvaessa.

Se mahdollistaa toteutetun algoritmin todellisen suoritusajan tarkan mittauksen

Kysymys 3

Valitse oikeat väittämät

Algoritmin asymptoottinen suorituskyky antaa aina tarkat arvot algoritmin suorituskyvylle.

Asymptoottisen suorituskyvyn avulla voimme verrata kahta vaihtoehtoista algoritmia saman tehtävän suorittamiseen.

Asymptoottinen suorituskyky ilmaisee nopeuden, jolla algoritmi hidastuu tiedon määrän kasvaessa.

Tehokas algoritmi hidastuu aina hyvin nopeasti tiedon määrän kasvaessa.

Kysymys 4

Miksi algoritmin ratkaisun laskemiseen kuluvan ajan mittaaminen ei ole toteuttamiskelpoinen tapa mitata algoritmin tehokkuutta?

Koskaan ei voi tietää, milloin algoritmi on lopettanut laskennan.

Ei ole olemassa kelloa, joka olisi tarpeeksi tarkka mittaamaan minkä tahansa algoritmin laskenta-aikaa millään tietokoneella.

Aika riippuu liian monesta tekijästä.

Jos on olemassa parempi algoritmi, niin heikomman algoritmin laskenta-ajan mittaaminen on turhaa.

Kysymys 5

Oletetaan, että meillä on pseudokoodi jollekin algoritmille A ja meille annetaan tehokkuusanalyysi tälle pseudokoodille. Mitä voimme tehdä tällä tehokkuusanalyysillä?

Voimme laskea tarkalleen algoritmin A laskenta-ajan jollekin tietylle syötteelle tietyllä tietokoneella.

Voimme tarkalleen määrittää sellaiset tilanteet, joissa algoritmi A laskee oikein ja tilanteet, joissa se epäonnistuu.

Jos algoritmi B on olemassa saman ongelman ratkaisemiseksi kuin algoritmi A ja meillä on myös algoritmin B tehokkuusanalyysi, niin voimme verrata A:n ja B:n tehokkuuksia.

Voimme kertoa kuinka monta muuttujaa algoritmi A tarkalleen käyttää.

Kysymys 1

Missä ohjelmoinnin osa-alueissa järkevä tiedon jakaminen tehostaa algoritmia?

tietojen ylläpidossa

koodin luettavuudessa ja ymmärrettävyydessä

turhan tiedon varastoinnin vähentämisessä

koodin suoritusajassa

koodin kirjoittamisessa

Kysymys 2

Oletetaan, että tietokonekieli X käyttää arvosemantiikkaa ja tietokonekieli Y viitesemantiikkaa. Oletetaan, että on olemassa suuri objekti A ja meillä on seuraava koodirivi: B=A. Mikä seuraavista on väärin?

Y:ssä sekä A että B viittaavat samaan kohteeseen.

Kun koodirivi B = A on suoritettu, sekä X että Y käyttävät saman määrän muistia.

X:ssä A ja B varaavat erilliset muistialueet.

Kysymys 3

Oletetaan, että C++:ssa jokainen taulukon A elementti sisältää suuren objektin. Useita tekniikoita voidaan käyttää A:n elementtien jakamiseen: osoittimet, älykkäät osoittimet, indeksit ja niin edelleen. Mitkä seuraavista ovat totta?

Kaikilla erilaisilla jakamistavoilla on automaattinen roskien kerääminen, jos jokin A:n elementti tuhoutuu.

Jokainen tekniikka edellyttää jonkin aputietorakenteen (tai tietorakenteiden) muodostamista A:n elementteihin viittaamista varten.

Jos käytämme jotakin tekniikoista, emme voi enää tehdä kopiota A:sta.

Käyttämällä jotakin aputietorakennetta voimme tehokkaasti käsitellä A:n elementtejä tietyssä järjestyksessä ilman, että A:ta tarvitsee muuttaa ollenkaan.

Yhdessä C++-funktiossa ei voi käyttää useampaa kuin yhtä jakotekniikkaa.

Kysymys 1

Rekursio on hyödyllinen, koska

rekursiivisella funktiolla on aina parempi suorituskyky kuin vastaavalla iteratiivisella funktiolla

rekursiossa ei koskaan tarvitse käyttää for-silmukoita, while-silmukoita tai if-lauseita

suuret ongelmat voidaan jakaa pienempiin versioihin samasta ongelmasta

rekursiivinen funktio sisältää vain triviaaleja (perus)tapauksia

Kysymys 2

Mitkä seuraavista kutsupinoa koskevista väittämistä ovat tosia rekursiolle?

Proseduurin parametrit (tai argumentit) ovat erilaisia pinon eri tasoilla.

Ohjelmoijan on nimenomaisesti sisällytettävä koodi sellaiseen prosessiin, joka pitää kirjaa kutsupinon koosta.

Kutsupinoa voidaan pitää sellaisten kutsujen järjestettynä pinona, joita ei ole vielä suoritettu kokonaan.

Kun kutsu on kerran lisätty kutsupinoon, sitä ei voi koskaan poistaa.

Kutsupino tyhjennetään aina kun rekursiivinen proseduuri suorittaa triviaalin (tai perus/pohjatapauksen).

Kysymys 3

Oletetaan, että taulukko A sisältää lukuja, jotka on järjestetty pienimmästä suurimpaan ja käytämme rekursiivista binäärihakua elementin etsimiseen. Mitkä seuraavista väitteistä ovat totta?

Suoritamme triviaalisen (tai perus)tapauksen vain silloin, kun A:n pienin elementti on suurempi kuin se elementti, jota etsimme.

Joka kerta kun binäärihakualgoritmia kutsutaan, sekä vasen että oikea sijainti muuttuvat.

Jos jollakin rekursiotasolla etsitään alitaulukosta, jonka koko on m ja m >= 2, niin seuraavalla rekursiotasolla etsitään alitaulukosta, jonka koko on enintään (m+1)/2.

Rekursiivisessa (tai ei-triviaalissa) tapauksessa lasketaan sijainti, joka on vasemman ja oikean sijainnin puolivälissä.

Kysymys 4

Oletetaan, että X on rekursiivinen funktio. Mikä seuraavista väitteistä on totta?

Perustapauksessa (tai triviaalissa) X kutsuu itseään kerran ja rekursiivisessa tapauksessa X kutsuu itseään vähintään kahdesti.

Sekä perus- (tai triviaali-) että rekursiivisessa tapauksessa X voi kutsua itseään.

Perustapauksessa (tai triviaalissa) X voi kutsua vain itseään, mutta ei mitään muuta proseduuria, ja rekursiivisessa tapauksessa X voi kutsua mitä tahansa muuta proseduuria paitsi itseään.

Perustapauksessa (tai triviaalissa) X ei kutsu itseään ja rekursiivisessa tapauksessa X kutsuu itseään ainakin kerran.

Kysymys 1

Muotoile kurssin kannalta keskeinen kysymys, johon tämän viikon videot antavat vastauksen.

Kysymys 2

Minkä videon aiheesta pitäisi erityisesti keskustella keskustelutilaisuudessa?

algoritmin tehokkuus

tietojen jakaminen

rekursio

Kysymys 3

Oliko videoiden sisällössä jotain erityisen vaikeaa? Entä mielenkiintoista? Jotain josta haluaisit oppia lisää?

Palauta viikkotehtävät¶

Kysymyksiä tämän viikon aiheista