Tietorakenteet ja algoritmit 22. - 23.9.2004 Harjoitus 1 1) Saat tehtäväksesi käsipelissä lajitella A4-arkkeja arkilla olevan nimen mukaan aakkosjärjestykseen. Millä taktiikalla/menetelmällä ryhtyisit toimeen kun lajiteltavia arkkeja on a) 10 b) 100 c) 1000 d) 10000 Arvioi kuinka paljon kunkin pinon lajitteluun kuluu aikaa (minuutteina, tai muuna sopivana aikayksikkönä). Yritä laskea aika perustellen käyttämästäsi menetelmästä. Ajan arviointi on helpointa kun arvioit kuhunkin yksinkertaiseen toimenpiteeseen (yhden paperin käsittely) kuluvan ajan ja lasket kuinka monta kutakin yksinkertaista operaatiota tarvitaan kussakin vaiheessa. 2) Laske, kuinka kauan menisi kunkin tehtävän 1 pinon lajitteluun valintalajittelulla. Valintalajittelun kussakin vaiheessa etsitään jäljellä olevan pinon aakkosjärjestyksessä ensimmäinen paperi ja asetetaan se alassuin valmiiden pinoon. Käytä paperien selauksen nopeutena 1 sek/arkki. Mitkä ovat tämän algoritmissa parhaita ja pahimpia tapauksia ja kuinka kauan niissä menee aikaa? 3) Käytössä jälleen tehtävän 1 neljä paperipinoa. Kuinka paljon aikaa arvelet kuluvan annetun henkilön lomakkeen etsimiseen kustakin pinoista kun a) pinot ovat sekaisin b) pinot ovat aakkosjärjestykseen lajiteltuna Perustele taas aika-arviosi. Jos pinot ovat aluksi sekaisin, niin yhtä hakua varten niitä ei kannata lajitella. Sensijaan tuhansia hakuja varten varmaankin kannattaa. Missä arvelet kunkin pinon tapauksessa menevän rajan, kuinka monta hakua joudutaan suorittamaan, ennenkuin olisi ollut järkevämpää aluksi lajitella pino? 4) Oletetaan jonkin tahon seuraavan suomalaisten tekstiviestiliikennettä (1,6 miljardia viestiä vuodessa (2003)) . Järjestelmä tallettaisi jokaisen lähetetyn tekstiviesti siten, että siitä olisi nopea hakea halutun lähettäjän (puhelinnumero) tai vastaanottajan kaikki tekstiviestit. Miten toteuttaisit järjestelmän? Minkälainen laitteisto tarvitaan? Minkälaista talletustietorakennetta käyttäisit? Miten nopea (sekunneissa) haku olisi? Voit olettaa kytkennän matkaviestinverkkoihin olevan valmiina. 5) Oletetaan edellisen tehtävän tekstiviestien tallennusjärjestelmään lisättäväksi myös reaaliaikainen sanaskannaus ja hälytys. Tällöin järjestemän käyttäjä saisi välittömästi tiedon viestistä joka sisältää jonkin aktiivisista avainsanoista. Miten edellisessä tehtävässä kuvaamaasi järjestelmää tulisi muuttaa? Entä jos haluttaisiin myös tehokas sanahaku kaikkiin arkistoistoituihin viesteihin? 6) Aseta seuraavat funktiot kasvunopeuden mukaiseen järjestykseen: (tämä tehtävä on paperilla paljon selkeämpi) a) sqrt(n) / log n f) 42 loglog n k) n^3 / log n p) n * (log n)^2 b) cbrt(n) g) n^3/sqrt(n) + n^3 l) 3^n q) n! c) n^2.5 h) n^3 m) n log n r) sqrt(n) + log n d) n^(log 7) i) 2004 n) n log(n^2) e) n j) (7/2)^n o) n^2 + n valmistaudu perustelemaan peräkkäisten funktioiden järjestys. (sqrt = neliöjuuri, cbrt = kuutiojuuri, log on 2-kantainen logaritmi)