Kurssiaiheet 3 ja 4

Itseopiskelu (videot ja kalvot suomeksi)

hajota ja hallitse

video hajota ja hallitse

kalvot hajota ja hallitse

Pikajärjestäminen (Quicksort)

video pikajärjestäminen

kalvot pikajärjestäminen

Pikajärjestäminen: ositus (Partition)

video pikajärjestäminen: ositus

kalvot pikajärjestäminen: ositus

Lomitusjärjestäminen (Mergesort)

video lomitusjärjestäminen

kalvot lomitusjärjestäminen

Lomitusjärjestäminen: Lomitus (Merge)

video lomitusjärjestäminen: lomitus

kalvot lomitusjärjestäminen: lomitus

Viikko03 - Sanasto

Luentokysymykset

Kysymys 1

hajota ja hallitse -suunnittelustrategiassa ..

alkuperäisen ongelma jaetaan pienempiin osaongelmiin, sitten yksi osaongelma ratkaistaan ja lopetetaan

alkuperäisen ongelma hajoitetaan osaongelmiin, jotka ovat pienempiä versioita alkuperäisestä ongelmasta

jaamme aina alkuperäisen ongelman tasan kahteen osaongelmaan

jaamme alkuperäisen ongelman joukoksi osaongelmia, joiden ratkaisut ovat kaikki helppoja laskea, ja sitten lopetamme

Kysymys 2

Mikä seuraavista kuvaa parhaiten hajota ja hallitse -strategian ja rekursiivisten algoritmien välistä suhdetta?

Koska hajota ja hallitse -strategiassa muodostetut osaongelmat ovat kaikki erilaisia, rekursiivisen algoritmin käyttö on lähes mahdotonta.

Rekursiivinen algoritmi on aina hajota ja hallitse -strategian toteutus.

Jaa ja hallitse (divide-and-conquer) -strategiat toteutetaan usein käyttämällä rekursiivisia algoritmeja, koska osaongelmat ovat pienempiä versioita alkuperäisestä ongelmasta.

hajota ja hallitse -strategiaa ei voida koskaan toteuttaa käyttämällä rekursiivista algoritmia.

Kysymys 3

Mikä seuraavista kuvaa parhaiten tietorakennetta, jossa hajota ja hallitse -strategiat voisivat olla tehokkaita?

Tietorakenne, jota ei voi jakaa osiin.

Tietorakenne, joka voidaan hajottaa osiin ja jokaisella osalla on samat ominaisuudet/ominaisuudet kuin alkuperäisellä tietorakenteella.

Tietorakenne, joka voidaan hajottaa osiin ja jokaisessa osassa on jokin uusi ominaisuus tai ominaisuus, jota alkuperäisessä ei ollut.

Kysymys 1

Sanotaan, että pikalajittelu käyttää hajota ja hallitse -strategiaa käsitellessään taulukkoa \(A\). Mikä pikalajittelun osa vastaa “hajoittamista”?

\(A\):n elementit jaetaan toistuvasti jollain vakiolla, kunnes kaikkien elementtien absoluuttinen arvo on pienempi kuin 1.

Osiointia käytetään \(A\):n jakamiseen kahdeksi aliryhmäksi, ja näitä kahta aliryhmää käytetään sitten itse syötteinä Quicksortille.

Binäärihakua käytetään \(A\):n elementtien jakamiseen alkioihin, jotka ovat pienempiä tai yhtäsuuria kuin pivot, ja niihin, jotka ovat pivotia suurempia.

Kysymys 2

Pikalajittelu-algoritmin tarkoitus on

löytää taulukon suurin elementti

tuottaa taulukko, jossa elementit ovat järjestyksessä

jakaa taulukon elementit suuriin ja pieniin elementteihin

Kysymys 3

Pikalajittelussa käytetään osiointimenettelyä. Olkoon osioinnin syöte array \(A\) ja \(A\):sta meidän tulee osioida vähintään kolme elementtiä. Mikä seuraavista on totta?

On mahdollista, että osioinnin for-silmukka ei tarvitse suorittaa.

On mahdollista, että pivot-elementin sijainti ei muutu osioinnin aikana.

On mahdollista, että toinen kahdesta osioinnin aikana muodostuneesta aliryhmästä on tyhjä.

Olettaen, että \(A[1]\) on ensimmäinen elementti, on mahdollista, että osioinnin palauttama pivot on pienempi kuin 1.

Kysymys 4

Pikalajittelussa osiointia käytetään

jakamaan taulukko kahdeksi aliryhmäksi, joista toisessa on elementit vähintään yhtä suuria kuin pivot ja toisessa enintään yhtä suuret elementit kuin pivot

jakamaan taulukko kahdeksi aliryhmäksi, joista toisessa on elementit, jotka ovat yhtä suuret kuin pivot ja toisessa elementit, jotka eivät ole yhtä suuret kuin pivot

jakamaan taulukon elementit kahdeksi aliryhmäksi sen perusteella, onko pivot parillinen vai pariton luku

Kysymys 5

Mikä seuraavista väittämistä pitää paikkansa pikalajittelun suhteen?

Osiointi (partition) osittaa taulukon aina kahteen samankokoiseen alitaulukkoon.

Pikalajittelu lakkaa kutsumasta itseään rekursiivisesti, kun sen syöte sisältää enintään yhden elementin.

Pikalajittelu ei koskaan tarvitse enempää kuin kolme rekursiotasoa.

Joka kerta kun osiointia kutsutaan, pivotin vasemmalla puolella olevat elementit lajitellaan pienimmästä suurimpaan suorituksen lopuksi.

Kysymys 1

Sanotaan, että lomituslajittelu käyttää jaa ja hallitse -strategiaa käsitellessään taulukkoa \(A\). Mikä lomituslajittelun osa vastaa “jakamista”?

Lomituslajittelun aikana taulukko \(A\) jaetaan kahteen alitaulukkoon, joiden koot ovat mahdollisimman lähellä toisiaan.

Kun yhdistetään kaksi aliryhmää, yksi vaihtoehto on jakaa toinen aliryhmistä kahteen osaan. Näistä kahdesta osasta vain toista käytetään yhdistämisessä.

Lomituslajittelun aikana tietyt taulukon \(A\) elementit jaetaan kahdella niiden pienentämiseksi.

Lomituslajittelun aikana aloitetaan \(A\) vasemmasta päästä ja etsitään ensimmäinen indeksi \(i\), jolle \(A[i] > A[i+1]\). Taulukko A jaetaan aliryhmiin tämän indeksin kohdalta.

Kysymys 2

Kun kaksi lajiteltua taulukkoa yhdistetään,

saamme yhden taulukon, jossa suurin elementti sijaitsee keskellä

saamme yhden taulukon, joka on lajiteltu

saamme yhden taulukon, jonka kokoa ei voi tietää etukäteen

saamme kaksi taulukkoa, joista toinen on lajiteltu nousevaan ja toinen laskevaan järjestykseen

Kysymys 3

Kun kaksi aliryhmää yhdistetään Mergesortissa,

yhden alitaulukon kaikkien elementtien on oltava suurempia kuin toisen alitaulukon suurin elementti

viimeinen taulukko ei koskaan sisällä kahta peräkkäistä elementtiä samasta aliryhmästä

lopullisessa yhdistetyssä taulukossa voivat kaikki elementit yhdestä alitaulukosta esiintyä peräkkäin

molemmissa aliryhmissä on oltava täsmälleen sama määrä elementtejä

Kysymys 4

Olkoon taulukon (tai alitaulukon) koko sen sisältämien elementtien lukumäärä. Lomituslajittelu..

lisää syöttötaulukon kokoa yhdellä

ei kutsu itseään rekursiivisesti, kun syötetaulukon koko on pienempi kuin 8

ei toimi, kun syöttötaulukon koko on pariton

jakaa syöttötaulukon kahteen alitaulukkoon, joiden koot ovat mahdollisimman lähellä toisiaan

Kysymys 5

Mitkä seuraavista väittämistä pätevät lomituslajitteluun?

Kun kaksi aliryhmää yhdistetään, taulukko lajitellaan.

Lomituslajittelu ei koskaan kutsu itseään syötetaulukolla (tai alitaulukolla), joka sisältää täsmälleen yhden elementin.

Keskipiste (tai keski-indeksi) lasketaan vain, jos syöttötaulukko (tai alitaulukko) sisältää vähintään kaksi elementtiä.

Lomituslajittelu ei lajittele oikein syötetaulukkoa, jossa kahdella tai useammalla elementillä on sama arvo.

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?

hajota ja hallitse

pikalajittelu

osiointi

lomituslajittelu

lomittaminen

Kysymys 3

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

Linkkejä viikon aiheisiin:

• An Introduction to Recursion, Part 1
• Efficient recursion
• Wikipedia’s pages on quicksort
• Wikipedia’s pages on mergesort

Week03 - Glossary

Viikko03 - Sanasto

Palauta viikkotehtävät

Kysymykset tältä viikolta .. _courseweek04_fi:

Kurssiaihe 4

Itseopiskelu (videot ja kalvot suomeksi)

O-notaatio

Video O-notaatio

kalvot O-notaatio

Omega- ja Theta-notaatiot

Video Omega- ja Theta-notaatiot

kalvot Omega- ja Theta-notaatiot

Tehokkuuden analysointi pseudokoodista

Video tehokkuuden analysointi pseudokoodista

kalvot tehokkuuden analysointi pseudokoodista

Järjestysalgoritmien tehokkuuden vertailu

Video Järjestysalgoritmien tehokkuuden vertailu

kalvot järjestysalgoritmien tehokkuuden vertailu

O, Omega, Theta, paras, huonoin

Video O, Omega, Theta, paras, huonoin

kalvot O, Omega, Theta, paras, huonoin

Viikko04 - Sanasto

Kysymys 1

Mitä iso-O-merkintä ( \(O\) ) kuvaa?

algoritmin ajonaikaisen tehokkuuden ylärajaa, kun syötteen koko on riittävän suuri

algoritmin ajonaikaisen tehokkuuden alarajaa, kun syötteen koko on riittävän suuri

algoritmin toteuttamiseen tarvittavien pseudokoodirivien tarkkaa lukumäärää

sekä ylä- että alarajaa algoritmin ajonaikaiselle tehokkuudelle, kun syötteen koko on riittävän suuri

Kysymys 2

Oletetaan, että algoritmin ajoaikafunktio on \(f(n)\) ja tiedämme, että \(f(n)\) kuuluu ryhmään \(O(1)\). Mikä seuraavista väittämistä on totta?

Algoritmin suoritusaika on aina enintään 1 sekunti riippumatta syötetietojen koosta; tietokoneesta, jolla algoritmi ajetaan; tai algoritmin koodaamiseen käytetystä kielestä.

Riittävän suurelle \(n\), \(f(n)\) ei ole koskaan suurempi kuin jokin vakio.

Funktio \(f(n)\) ei riipu \(n\):stä.

Algoritmissa ei ole for- tai while-silmukoita.

Kysymys 3

Mitä iso-omega( \(\Omega\)) kuvaa?

algoritmin ajonaikaisen tehokkuuden ylärajaa, kun syötteen koko on riittävän suuri

algoritmin ajonaikaisen tehokkuuden alarajaa, kun syötteen koko on riittävän suuri

algoritmin toteuttamiseen tarvittavien pseudokoodirivien tarkka lukumäärää

sekä ylä- että alarajaa algoritmin ajonaikaiselle tehokkuudelle, kun syötteen koko on riittävän suuri

Kysymys 4

Oletetaan, että algoritmeja A ja B voidaan käyttää saman asian laskemiseen. Mikä seuraavista väittämistä on totta?

Jos A suoritetaan lineaarisessa ajassa ja B logaritmisessa ajassa, A on nopeampi, kun syötetyn datan koko on riittävän suuri.

Jos A suoritetaan linearitmisessa ajassa ja B logaritmisessa ajassa, A on nopeampi, kun syötetyn datan koko on riittävän suuri.

Jos A suoritetaan neliöllisessä ja B lineaarisessa ajassa, B on nopeampi, kun syötetyn datan koko on riittävän suuri.

Jos A suoritetaan logaritmisessa ajassa ja B vakioajassa, A on nopeampi, kun syötetyn datan koko on riittävän suuri.

Jos A suoritetaan lineaarisessa ajassa ja B linearitmisessa ajassa, A on nopeampi, kun syötetyn datan koko on riittävän suuri.

Kysymys 5

Oletetaan, että algoritmin funktio on \(f(n)\) ja tiedämme, että \(f(n)\) kuuluu ryhmään \(O(n)\). Mikä seuraavista väittämistä on totta? (Moni kuin yksi voi olla totta.)

\(f(n)\) kuuluu ryhmään \(O(1)\)

\(f(n)\) kuuluu \(O(n \log n)\)

\(f(n)\) kuuluu \(O(\log n)\)

\(f(n)\) kuuluu ryhmään \(O(n^2)\)

Kysymys 6

Oletetaan, että algoritmin funktio on \(f(n)\) ja tiedämme, että \(f(n)\) kuuluu ryhmään \(O(g(n))\) ja myös :math:` Omega(h(n))`. Mikä seuraavista väittämistä on aina totta?

on olemassa vakiot \(c_1\) ja \(c_2\) siten että asymptoottisesti \(f(n)\) kasvaa vähintään yhtä nopeasti kuin \(c_1 g(n)\) ja korkeintaan yhtä nopeasti kuin \(c_2 h(n)\)

math:“g(n) = h(n)”.

on olemassa vakiot \(c_1\) ja \(c_2\) niin että asymptoottisesti \(f(n)\) kasvaa korkeintaan yhtä nopeasti kuin \(c_1 g(n)\) ja vähintään yhtä nopeasti kuin \(c_2 h(n)\)

on olemassa vakio \(c_1\) tai vakio \(c_2\) siten, että asymptoottisesti joko \(f(n) = c_1 g(n)\) tai \(f(n) = c_2 h(n)\).

Kysymys 1

Mikä väite pätee lisäyslajitteluun?

se toimii log(n) tehokkuudella parhaan tapauksen syötteellä

se toimii lineaarisessa ajassa huonoimman tapauksen syötteellä

se toimii neliöllisellä tehokkuudella pahimman tapauksen syötteellä

Kysymys 2

Oletetaan, että taulukko \(A\) annetaan syötteenä lisäyslajittelulle ja oletetaan, että lisäyslajittelu tuottaa taulukon \(A\), jonka elementit on lajiteltu pienimmästä suurimpaan. Mikä on pahimman tapauksen syöte \(A\)?

kaikki syötetaulukot \(A\) ovat pahimpia tapauksia

taulukko \(A\), jonka elementit on lajiteltu suurimmasta pienimpään

taulukko \(A\) jonka ensimmäinen elementti on pienin ja muut elementit voivat olla missä tahansa järjestyksessä

Kysymys 3

Oletetaan, että meillä on taulukko \(A\), jossa on numeroita. \(A_{best}\) ja \(A_{worst}\) vastaavat lisäyslajittelun parasta ja huonointa syötettä. Mikä seuraavista on totta?

Sekä \(A_{best}\) että \(A_{worst}\) suoritusaikaiset tehot kuuluvat samaan \(\Theta\) -joukkoon.

Kohteen \(A_{best}\) suoritusaikainen tehokkuus ei kuulu mihinkään \(\Theta\) joukkoon. Samaa voidaan sanoa \(A_{pahin}\) suoritusajan tehokkuudesta.

\(A\):lle on olemassa koko, jonka suoritusaikainen tehokkuus pahimmalle tapaukselle \(A_{worst}\) voi olla miljoona kertaa suurempi kuin parhaalle tapaukselle \(A_{best}\).

Kysymys 1

Lomituslajittelua kutsutaan syötetaulukolla \(A\), jossa on \(n\) elementtiä. Mikä seuraavista on paras yläraja lomituslajittelun käyttämien rekursiotasojen lukumäärälle?

\(n\)

\(n/2\)

\(\lceil \log_2 n \rceil\)

\(n \lceil \log_2 n \rceil\)

Kysymys 2

Oletetaan, että pikalajittelun asymptoottinen ajonaikainen tehokkuus analysoidaan, kun aloitustaulukossa \(A\) on :math:n elementtiä. Mitkä seuraavista ovat totta?

Parhaan tapauksessa ajonaikainen tehokkuus saavutetaan, kun kaikilla rekursiotasoilla pivot on mahdollisimman lähellä taulukon keskikohtaa.

Tehokkuus parhaassa ja pahimmassa tapauksessa on sama.

Parhaassa tapauksessa osiointia(partioning) ei tarvitse tehdä, joten paras ajonaikainen tehokkuus kuuluu \(\Omega( n )\):ään.

Parhaan tapauksen ajonaikainen tehokkuus kuuluu kategoriaan \(\Omega( n \log_2 n )\).

Kysymys 3

Verrataan lomituslajittelua, pikalajittelua ja lisäyslajittelua, mitkä seuraavista ovat totta?

Sekä lomituslajittelun että pikalajittelun parhaat tehokkuudet ovat parempia kuin \(O( n^2 )\).

Sekä pika- että lisäyslajittelu vaativat tilapäistä tallennustilaa, kun taas lomituslajittelu ei.

Sekä lomitus- että pikalajittelun parhaat tehokkuudet ovat huonompia kuin lisäyslajitteluin parhaan tapauksen tehokkuus.

Sekä pika- että lomituslajittelu voidaan esittää rekursiona, kun taas lisäyslajittelu ei voi.

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?

asymptoottinen analyysi yleensä

iso-O, iso-omega, iso-theta-notaatio

parhaan ja huonoimman tapauksen syötteet

Kysymys 3

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

Extra links on the topic:

• Khan Academy material on asymptotic notation

Week04 - Glossary

Viikko04 - Sanasto

Palauta viikkotehtävät

Kysymyksiä tälle viikolle

Palautusta lähetetään...