FreeMind MarkTree

Ohj2, luennot 1-2, 11.2.-12.2.2005
- Byrokratiaa
  - Korppi - [ https://korppi.jyu.fi/ ]
    - Ilmoittautuminen - [ https://korppi.jyu.fi/kotka/course/student/generalCourseInfo.jsp?course=17333&language=2 ]
    - Tunnusten hankinta - [ https://korppi.jyu.fi/kotka/portal/showAddUser.jsp ]
    - Miksi?
      - Demopisteiden laskenta
      - Harjoitustöiden seuranta
      - Kalenteri
  - Luennot
    - Materiaali - [ http://people.cc.jyu.fi/~minurmin/ohj2/index.php#materiaali ]
    - Luentojen aiheet - [ https://korppi.jyu.fi/kotka/course/student/generalCourseInfo.jsp?course=17333 ]
      - Kurssin rakenne
        Yleistä algoritmikehitystä
        Java-kielen alkeita (kertausta Ohj 1:stä)
        Olio-ohjelmointia
        Kehittyneempiä ominaisuuksia käyttäen pääosin Kerho-ohjelmaa mallina
      - Vrt. Ohj1-kurssi!
        Päällekkäisyyksiä jonkin verran erityisesti kurssin alkupuolella
        Tarkista demotehtävistä, ettei ole kohtuuttomasti samoja tehtäviä...
      - Uusia aiheita voidaan käsitellä ja rakennetta muokata opiskelijoiden toiveet huomioiden...
        Esim. suunnittelumallit?
        Onko jotain, minkä voisi jättää pois?
  - Demot - [ http://people.cc.jyu.fi/~minurmin/ohj2/demo.php ]
    - Palautetaan sähköisesti! - [ http://people.cc.jyu.fi/~minurmin/ohj2/demopalautus.php ]
    - Demot käydään läpi jokaisen luentoviikon ensimmäisillä tunneilla
    - Korppiin täytettävä DemoWWW-kenttä
    - Demoista saa hyvityksiä max 6p. Äärimmäisen ahkerat demojen tekijät (> 105%) saavat 9p tenttiin.
      - Huom. vanhoja demotehtäviä ja vastauksia löytyy verkosta...
      - Oppimisen kannalta tehtävät on kuitenkin mietittävä itse (mahd. ryhmätyönä). Vanhojen vastausten suora kopiointi on verrattavissa lunttaamiseen!
  - Pääteohjaukset - [ http://people.cc.jyu.fi/~minurmin/ohj2/ohjaus.php ]
  - Harjoitustyö
    - Pakollinen!
    - Ks. harjoitustyöohje - [ http://people.cc.jyu.fi/~minurmin/ohj2/htohje.php ]
    - Mieluiten ryhmätyö (max. 3 henkilöä / ryhmä)
    - Pääosin kurssin harjoitustyö toteutetaan "pohjalta" alkaen, erityisesti tietorakenteiden osalta.
    - Viikon viimeisten pääteohjausten jälkeen varattu ylimääräinen tunti pelkästään harjoitustöiden ohjausta varten
    - Harjoitustyö tehdään vaiheittain, jokainen vaihe esiteltävä henkilökohtaisesti.
  - Tentti
    - 24.5.
    - "lunttilappu" saa olla mukana ja kehitysvälineiden dokumentaatiota saa käyttää, ei Internetiä.
    - Harjoitustyö oltava hyväksyttynä ennen tenttiin menoa! (huom. miinukset)
- Sisällöstä
  - Ks. käsitekartta! - [ http://localhost/ohj2/materiaali/kasitekartta.png ]
  - Ohjelman suunnittelu
    - Älä anna ohjelmointikielen syntaksin hämätä. SUUNNITTELU on ohjelmoinnin vaikein osa-alue.
    - Uuden kielen syntaksi ja laajakin luokkakirjasto on opeteltavissa kohtuullisella työllä
    - Parhaatkaan frameworkit, suunnittelumallit tai "keittokirjat" eivät kuitenkaan poista raakaa ajattelutyötä, jota tehtävän hahmottaminen, sovellusalueen käsitteiden suhteiden ymmärtäminen ja soveltaminen käytäntöön vaativat (niistä on toki apua)!
    - Huom. tämä ei tarkoita suunnittelua toteutus 'unohtaen' (lukuunottamatta analyysivaihetta)
      - Riskejä: käytetään valtavasti aikaa suunnitelman hiomiseen, joka osoittautuu toteutuskelvottomaksi
      - Miten ylläpitää laajoja suunnitelmia, kun vaatimukset kuitenkin muuttuvat jatkuvasti?
  - Tietorakenteet ja algoritmit
    - Yleisiä periaatteita, mm. "hajota ja hallitse", iteraatio, rekursio
    - Taulukko- ja listarakenteiden toteutuksesta (huom. kehittyneemmät rakenteet jätetään pääosin asiaan liittyvälle kurssille, muuten hyödynnetään Javan valmiita kirjastoja)
  - Pöytätestaus
    - Aliarvostettu tapa algoritmin testaamiseen ennen sen toteutusta
  - Java-perusteet
    - Painopiste yleisissä ohjelmointirakenteissa, ei kielen tai kirjaston yksityiskohdissa
    - Kuitenkin kurssin edetessä käsitellään myös Java 5:n (oikeastaan 1.5) uusia ominaisuuksia
    - Käytössä kurssin omia apualiohjelmia (mm. IO:n ja merkkijonojen käsittelyyn), muitakin (esim. Kyppö-Vesterholm-aliohjelmat) saa käyttää rajoitetusti
    - Suosituimmat ohjelmointikielet ja kirjastot muuttuvat muutaman vuoden välein, mutta ohjelmoinnin perusosaaminen ei ole 40 vuoden aikana muuttunut oleellisesti
      - Pyrkimyksenä abstraktiotason nostaminen (vrt. assembler -> c -> java)
      - Toisaalta monet abstraktiotasoa nostavat ominaisuudet (!tarkista artikkeli!) ovat olleet funktiokielissä (esim. LISP, haskell) lähes alusta alkaen - integroituvat suositumpiin kieliin vähitellen (esim. C++:n templatet, Javan roskienkeruu)
      - ks. esim. Paul Graham: what made lisp different - [ http://www.paulgraham.com/diff.html ]
  - Luokkien suunnittelu ja testaus
    - Tulevat tutuksi harkkatyötä tehdessä...
    - Junit!
  - Ohjelman kasaaminen
    - Ks. edellinen kohta
- Ohjelman suunnittelu
  - Materiaali: moniste, luvut 1-3
  - Prosessimalleja
    - code & fix
    - Vesiputousmalli (klassinen)
      - vaatimusmäärittely, analyysi, suunnittelu, toteutus, testaus...
    - Iteratiivinen
      - toistetaan (iteroidaan) vesiputousmallin vaiheita
    - Inkrementaalinen
      - kehitetään pala (inkrementti) kerrallaan
    - XP (extreme programming -metodologia)
      - käsittää mm. pariohjelmoinnin, ennen koodausta kirjoitettavat yksikkötestit ja voimakkaan refaktoroinnin
    - Lisää 'ohjelmistotuotanto'-kurssilla...
  - VL:n ohjelmointimalli, ks. kalvot
    - Tehtävän saaminen
    - Tehtävän tarkentaminen, toimintojen hahmottaminen
    - Luokkien, toimintojen ja tietorakenteiden suunnittelu
    - Yksityiskohtainen algoritmien suunnittelu
    - OHJELMOINTITYÖKALUN VALINTA
    - Luokkien ja algoritmien tarkentaminen valitulle työkalulle
    - Ohjelmakoodin kirjoittaminen
    - Ohjelman testaus
    - Ohjelman käyttöönotto
    - Ohjelman ylläpito
  - Suunnittelusta
    - Ohjelmointi != työkalun (kielen ja kehitysympäristön) hienouksien opettelu!
    - Kehityksen alkuvaiheessa on syytä keskittyä ongelman analysointiin ja ohjelman suunnitteluun
    - Käyttäjän ja vaatimusmäärittelyn kannalta protoilu ja joka käyttöohjeen kirjoittaminen etukäteen kannattaa.
  - Työkalun valinnasta
    - Työkalu tarpeen mukaan: C, Java, Python, Fortran ym ym on suunniteltu erilaisten ongelmien ratkaisuun eikä niiden "paremmuuden" vertailu ole täysin mielekästä
    - Joskus myös valmis tietokanta- taulukkolaskenta- tai jopa tekstinkäsittelyohjelma makroilla riittää
    - Ohjelmat vs. skriptit
    - Komentorivi vs. graafinen käyttöliittymä
    - Hajautus: yhdistetään erillisiä sovelluksia ja komponentteja (esim. ActiveX-kontrollit. löyhimmillään web-sovelluspalvelut)
    - Uudelleenkäytön mahdollisuudet (esim. Javalle saatavilla erittäin runsaasti valmiita komponentteja - toimivuus pitää tietysti testata)
  - Koodauksesta
    - TOP-DOWN- ja BOTTOM-UP-periaatteet
    - Käytännössä jokaisen ohjelman kehitys vaatii kummankin periaatteen soveltamista, mahdollisesti samanaikaisesti
    - Hajota ja hallitse - ratkaisu ohjelmistojen monimutkaisuuden ymmärtämiseen
      - "Insinööriparadigma": hajota ongelma pienempiin osiin niin kauan, että yksittäiset osat ovat hallittavissa
      - ongelmia: kuinka hajottaa ja kuinka varmistaa viestintä eri komponenttien välillä
      - komponenttien riippuvuudet?
  - Testauksesta
    - Suunnitteluvaiheessa algoritmin pöytätestaus ja ajonaikaisten testitapausten suunnittelu
    - Koodausvaiheessa jokainen metodi ja luokka pitäisi yksikkötestata (esim. JUnit)
    - Debuggerit ovat korvaamattomia, kunhan niitä osaa käyttää oikein
  - ks. vl-kalvot (stroustrup-kommentteja ym)
- Esimerkkiohjelmat: Kerhon jäsenrekisteri ja tulkkiohjelma
  - Materiaali: luentomoniste, luku 2
  - Tiedostoformaateista
    - CSV
      - Siirrettävä esim. Exceliin tai tietokantoihin
    - XML
      - Kerhoformaatti XML:nä - [ http://appro.mit.jyu.fi/cgi-bin/printfile.cgi?file=http://appro.mit.jyu.fi/kurki/kelmit.xml ]
      - Viinirekisteri. :-)
    - Sovelletut tekstiformaatit
    - Binääriformaatit
  - Käyttöliittymästä
    - Ks. kerho-ohjelma, lukemine_71
    - Tekstipohjaisen käyttöliittymän etuna on sen helppo kuvattavuus suunnitelmassa
    - Lisäksi tekstipohjaista järjestelmää voidaa periaatteessa testata automaattisesti syöttövirran avulla (java Naytto < syotto.txt)
    - Toisaalta ohjelman toiminta voidaan tallentaa tulostusvirran avulla (java Naytto > tulos.txt) (kannattaa yhdistää syöttövirtaan)
    - Jo käyttöliittymän ohjetta voidaan "testata" loppukäyttjällä
      - Koodaajan ja loppukäyttäjän mielipiteet helppoudesta eivät aina kohtaa...
      - Toisaalta käyttäjä ei aina tiedä mitä haluaa
  - Ohjelmien yleisestä rakenteesta:
    - "MVC" (Model-View-Controller) -kerrosarkkitehtuuri
    - = käyttöliittymä, sovelluslogiikka ja "tietokanta" pyritään erottamaan toisistaan
    - Etuja: tiedon esitystapa (esim. tekstitiedosto, tietokantapalvelin) voidaan vaihtaa, käyttöliittymä (teksti, web, desktop) voidaan vaihtaa.
      - ks. winkerho
    - Haittapuolena on, että ohjelmaan joudutaan määrittelemään samoja asioita moneen kertaan. Lisäksi kerrosten pitäminen erillään ei ole aina yksinkertaista.
- Algoritmit
  - Materiaali: moniste, luku 4
  - Ks. myös Johdatus ohjelmointiin -luentomoniste, luku 1 - [ http://appro.mit.jyu.fi/2002/johdatusohjelmointiin/ ]
  - Mikä on algoritmi?
    - Algoritmi == yksikäsitteinen kuvaus tehtävän ratkaisuun tarvittavista toimenpiteistä
      - Tarkemmin: mahdollisimman pitkälle tarkennettu toimenpidesarja, jossa askel askeleelta esitetään yksikäsitteisessä muodossa toimenpiteet asetetun ongelman ratkaisuun
        Lisäksi algoritmin suorituksen on jossain vaiheessa päätyttävä
      - Tehtävän suoritus koostuu erillisistä osatehtävistä (alialgoritmit)
      - Algoritmin kirjoittaminen on hierarkkinen prosessi, jossa tehtävät jaetaan osatehtäviin, joita edelleen tarkennetaan, kunnes kukin osatehtävä on niin yksikäsitteinen, ettei sen suorittamisessa ole moniselitteisyyksiä
        "hajota ja hallitse"-periaate toiminnoille
        jos osatehtävä "kutsuu itseään", algoritmi on rekursiivinen
      - Kun algoritmi on kuvattu riittävän tarkasti, sen toteuttaminen ohjelmointikielellä on helppoa
      - Määrittelyn jälkeen algoritmeja kannattaa yleistää muidenkin kuin alkuperäisen ongelman ratkaisuun
        "käsitteellinen aliohjelmakirjasto"
        toimintojen abstrahointia
        esim. lajittelualgoritmissa ei ole merkitystä sillä, mitä lajitellaan, kunhan lajiteltavia alkioita voidaan verrata
      - Tietty ongelma voidaan ratkaista monellakin algoritmilla. Kun ongelma on hyvin määritelty, ratkaisut ovat vaihdettavissa
        vrt. ohjelmointikielten rajapinnat tai funktioiden parametrivälitys
        koskee myös alialgoritmeja..
      - Huom. kaikki ongelmat eivät ole algoritmisesti ratkaistavissa (esim. pysähtymisongelma). Lisäksi monille ongelmille ei ole olemassa (tai tiedossa) laskennallisesti tehokkaita algoritmeja (esim. NP-täydelliset ongelmat).
        Pysähtymisongelma: tee algoritmi, joka tarkastaa, pysähtyykö sille syötteenä annettu ongelma äärellisessä ajassa
        NP (nondeterministic polynomial) -täydelliset ongelmat liittyvät usein graafin ominaisuuksien selvittämiseen.
        Esim. kauppamatkustajan ongelma: etsi lyhin silmukka, joka kiertää kaikki painotetun täydellisen verkon solmut
        Ongelma voidaan ratkaista eksponentiaalisella algoritmilla, mutta polynomista algoritmia ei tunneta (mutta ei ole pystytty todistamaan, ettei sellaista olisi olemassa)
    - Ohjelmointi == toimintaohjeiden (algoritmien) antamista ennalta määrätyn toimenpiteen suorittamista varten
      - Klassinen ohjelmointiparadigma: proseduraalinen ohjelmointi:
        valitse ohjelmalle tietorakenteet. käsittele tietorakenteita parhailla tiedossa olevilla algoritmeilla
        ks. kalvo
      - olio-ohjelmoinnissa lähestymistapa on erilainen: samassa yhteydessä esiintyvät tiedot ja toiminnot on koottu yhteen ja ohjelma hahmotetaan vuorovaikutuksessa keskenään olevien olioiden joukkona
        tästä huolimatta myös olioiden toiminta perustuu viime kädessä algoritmeihin
      - muitakin paradigmoja on: funktio-ohjelmointi (ohjelma on funktio) ja logiikkaohjelmointi (ohjelma on looginen päättelyketju) - sivuutetaan täällä, lisätietoa esim. Ohjelmointikielten periaatteet -kurssilla.
    - Esim. reseptit, ajo-ohjeet, videoiden ajastus, matemaattiset operaatiot ja tietokoneohjelmat.
    - Tietokoneohjelmia varten suunnitellut algoritmit kuvataan usein kieliriippumattomana pseudokoodina
      - Yksinkertaisissa tapauksissa tai algoritmin osien kuvailussa voidaan käyttää myös vuokaavioita
      - Matemaattista symboliikkaa (esim. joukko-operaatiot, loogiset lausekkeet) käytetään myös pseudokoodin ohessa
      - Algoritmeja ei pitäisi kuvata pelkästään ohjelmointikielellä, koska tällöin ollaan liiaksi kiinni toteutustekniikassa (sinänsä ohjelmakoodi on algoritmin tarkka kuvaus). Lisäksi pseudokoodi on ohjelmakoodia helpommin luettava.
      - Laudatur-tason algoritmikuvauksia: formaalit menetelmät...
  - Matematiikan puolella löydettävissä runsaasti algoritmeja:
    - Esim. matriisin determinantin laskeminen, matriisien kertolasku, matriisin kääntö, Fourier-muunnoksen laskeminen, "allekkain" yhteen- ja kertolasku, fibonaccin lukujen laskeminen, eukleideen algoritmi, piin arvon laskeminen, yhtälöiden (numeerinen) ratkaiseminen, kaikki konstruktiiviset todistukset...
    - Huomaa avainsana: "laskeminen".
    - Algoritmin suoritus on "mekaanista" laskentaa! Tietojenkäsittelyteoria on laskennan teoriaa.
    - Seuraus: matematiikan osaamisesta on apua myös ohjelmoinnissa. Toisaalta ohjelmointia voi oppia, vaikka ei matemaatikko olisikaan.
  - Esimerkki: ajo-ohjeet
  - Esimerkki: sanojen vertailu
    - versioita:
      - 1. sanallinen kuvaus
      - 2. "lausekielinen" kuvaus
      - 3. pseudokoodi
        huomioitavaa: miten verrata tyhjiä sanoja muihin, miten sanat kuvataan täsmällisesti
      - 4. ohjelmakoodi
        huomioitavaa: String-luokan käyttö, isot vs. pienet kirjaimet, skandit ja muut kansalliset merkistöt, java-kielen tapauksessa null-viitteet jne, reagointi erikoismerkkeihin ym. virheellisiin syötteisiin...
    - demotehtävissä lausekielinen kuvaus (mahdollisesti sanallisella kuvauksella täydennettynä) on sopiva abstraktiotaso
    - ks. vaihtoehdot sanojen pituuksista - erikoistapauksia
  - Esimerkki: lajittelu
    - Ks. "järjestä"-ohjelma (GKO-esimerkki), sovelma-animaatiot
    - Useita mahdollisia algoritmeja
      - lisäyslajittelu
      - valintalajittelu ("etsi pienin")
      - kuplalajittelu
      - muita algoritmeja: lomituslajittelu (merge sort), pikalajittelu (quick sort)
        Tietorakenteet & algoritmit -kurssi...
      - lisäksi esim: luokamiehen lajittelu (bogosort, heitellään aineistoa ilmaan, kunnes se laskeutuu järjestyksessä maahan) ja kvanttilajittelu (odotetaan, että kvanttimekaaniset muutokset ovat aiheuttaneet sen, että aineisto on järjestyksessä) :-)
    - Tarkennuksia: pienimmän etsiminen ja paikalleen sijoittaminen
  - Esimerkki: haku järjestetystä joukosta
    - peräkkäishaku
      - soveltuu myös järjestämättömälle joukolle
    - puolitushaku
      - kuva: puolitushaun eteneminen
      - algoritmin kompleksisuus on verrannollinen binääripuun syvyyteen (2:n logaritmeja)
    - matematiikassa puolitushakua voidaan käyttää esim. funktion 0-kohtien approksimointiin...
  - Algoritmin kompleksisuus
    - Ks. Jori Mäntysalo: Tietokoneohjelmien nopeus ja kompleksisuuden käsite - [ http://www.uta.fi/~jm58660/jutut/ohjelmointi/kompleksisuus.html ]
    - Kompleksisuus tarkoittaa miten nopeasti resurssien kulutus kasvaa, kun tietoalkioiden määrää lisätään
      - Resurssi voi tässä olla esim. suoritusaika (aikavaativuus) tai muistin kulutus (tilavaativuus)
    - Kompleksisuus ilmoitetaan usein O(n)-notaatiolla, missä O tarkoittaa pahimman tapauksen kompleksisuutta ja n on funktio
      - Vakiot ja termikertoimet jätetään yleensä pois
      - Esim O(k) - vakio, O(log n) - logaritminen, O(n) - lineaarinen, O(n^2) - neliöllinen, O(n^k) - polynominen, O(k^n) - eksponentiaalinen (k jokin vakio)
        Esim. taulukon n:n alkion haku on vakioaikainen, puolitushaku on logaritminen, peräkkäishaku on lineaarinen, kupla- lisäys- ja valintalajittelut ovat neliöllisi operaatioita
        Kompleksisuudeltaan eksponentiaalisia ongelmia ei yleensä voida ratkaista täsmällsesti suurilla joukoilla
        Ks. Excel-taulukko
      - Vakiokertoimien vaikutuksesta johtuen kompleksisuudeltaan suuri algoritmi voi olla kompleksisuudeltaan pienempää algoritmia tehokkaampi pienillä tietojoukoilla
        Kun joukon koko kasvaa, kompleksisuudeltaan pienempi algoritmi suoriutuu kuitenkin tehtävästä tehokkaammin
        Toteutusvaiheessa teoreettisen vaativuuden lisäksi myös kiintolevyn ja muistin käytöllä on suuri merkitys (todellisen maailman tietokoneissa ei ole äärettömästi muistia...)
    - Ohjelmaa kehitettäessä pitäisi olla jonkinlainen "tuntuma" siitä, mitä kertaluokkaa ohjelman vaativuus on
      - Esim. kaksi sisäkkäistä silmukkaa sisältävä algoritmi on yleensä neliöllinen. Toisaalta monet "hajota ja hallitse"-tyyppiset algoritmit ovat logaritmisia.
      - Jos ratkaistava ongelma tunnistetaan NP-täydelliseksi tai vieläkin vaativammaksi, sille ei todennäköisesti ole olemassa polynomista ratkaisua.
  - Vinkkejä algoritmin kehittämiseen
    - Kun kehität algoritmia, unohda muut ohjelman osat. Keskity vain ratkaistavaan osaongelmaan!
    - Pyri konkretisoimaan ongelmaa (vrt numerot - pelikortit)
      - Samaa periaatetta voidaan soveltaa myös ohjelmistotuotantoon yleensä: esim. XP-metodologiassa yritetään löytää koko järjestelmää kuvaava konkreettinen metafora, jonka pohjalta toiminnallisuus suunnitellaan
    - Jos mahdollista, jaa ongelma edelleen osiin.
    - Kaikkea ei tarvitse ratkaista kerralla - aluksi yleinen vaatimus toimintalistassa riittää.
      - vrt. ohjelmiston arkkitehtuurin suunnittelu: tällöin ongelma ei ole enää yksittäisen toiminnon toteutustapa, vaan rajapinnan kuvaaminen palveluun, joka toiminnon toteuttaa.
    - Kun algoritmi on kerran kehitetty, siihen ei tarvitse jälkikäteen palata (ellei esim. haluta optimoida koodia)
    - Muista yleistäminen.
    - Luonnostele, piirrä kuvia ja kaavioita.
      - Ainakin allekirjoittaneelle lyijykynä ja ruutupaperi ovat ylivoimaiset suunnitteluvälineet
    - Ohjelma vrt. organisaation johtaminen: ohjelmoija jakaa tehtäviä algoritmeille, jotka edelleen jakavat tehtäviä alialgoritmeille jne...
      - Jokainen vastaa omasta osuudestaan ja kutsujan on luotettava siihen, että työ tulee tehtyä
      - Laajaa ohjelmaa ei ole mahdollista hahmottaa täydellisenä kokonaisuutena, mutta yksittäisiin ohjelman osiin voidaan keskittyä
    - Itsestäänselvyyksiä ei ole!
      - Kone tekee sen, mitä sen käsketään tekevän...
      - ...ei sitä, mitä käyttäjä haluaisi sen tekevän.