Programmeerimise algkursus (0)

Arvutitest ja programmeerimisest

• Riistvara :
  
  • loogikaelemendid, kahendsüsteem, 16-süsteem, 8-süsteem, teisendused , ...
    
  • protsessor (CPU) - juhtseade (CU), aritmeetikaseade (ALU), registrid , taimer, ...
    
  • põhimälu - muutmälu (RAM), püsimälu (ROM), ülekirjutatav püsimälu, ...
    
  • adresseerimine - bitt, bait , sõna, aadress, aadressruum, ...
    

k - kilo (10^3), M - mega (10^6), G - giga (10^9), T - tera (10^12), P - peta (10^15), E - eksa (10^18), Z - zeta (10^21), Y - jota (10^24)

• siinid - andmesiin, aadress-siin, juhtsiin, ...
  
• välisseadmed - välismälu, sisend /väljundseadmed, kontrollerid , ...
  

• Programmi täitmine arvutis:
  
  • masinkäsud - protsessori käsustik
    
  • operandid , aadresside moodustamine
    
  • andmete kujutamine madaltasemel: täisarvud, ujupunktarvud, sümbolid ja stringid (sõned), ...
    
  • käskude täitmistsükkel juhtseadmes: käsuregister, käsuloendaja (PC), aadressregister, olekuregister (flags), ...
    
  • katkestused
    

John von Neumann (1903 - 1957) - mällu salvestatud programmi idee. Annab võimaluse programme genereerida (programm on andmete eriliik). Neumanni arhitektuuri kriitika.
Need kaks pilti siin on kopeeritud meie põhiõpikust

• Arvutisüsteemi kihid :
  
  • riistvaralised komponendid, füüsiline võrk
    
  • tarkvaralised komponendid
    
    • riistvaralähedane kiht - operatsioonisüsteemi tuum, seadmete draiverid, ...
      
    • operatsioonisüsteem, selle poolt pakutavad teenused, ressursside haldamine : mälu, protsessid, s/v, ...
      
    • süsteemitarkvara - kompilaatorid, süsteemi haldamine, arendusvahendid, ...
      
    • rakendustarkvara   -  üldotstarbeline (näit. kontoripakett) või eriotstarbeline (näit. kassaaparaadi tarkvara)
      
  • organisatsioonilised jm. mittetehnilised asjad - kasutajad, koolitus, ... (need on rohkem infosüsteemi aspektid, praegu meid ei huvita)
    

Vajalikke lühendeid:
IDE - Integrated Development Environment. Arenduskeskkond programmide koostamiseks, silumiseks ja testimiseks (tavaliselt graafiline, näiteks eclipse - www.eclipse org).
API - Applications Programmer Interface . Programmeerijatele mõeldud kirjeldus mingi süsteemi funktsioonide kasutamiseks programmis , näiteks Java API kirjeldab keeles Java olemasolevaid funktsioone (konkreetselt Java puhul on need jagatud pakettidesse ja klassidesse, aga sellest hiljem...).
Programmeerimiskeeltest
Eesmärk: mitte töötada riistvara terminites, muuta programmeerimine universaalseks (sõltumatuks konkreetsest arvutitüübist).

• masinkood - konkreetse protsessori käsud kahendkujul, elektroonika tase
  
• assembler - madaltaseme programmeerimiskeel, käskude koodid on mnemoonilised (näit. ADD, DIV, MOV, ...), operandide ja aadresside jaoks saab kasutada nimesid, saab deklareerida andmeid, programmi võib varustada kommentaaridega, ...
  
• universaalsed programmeerimiskeeled (ei sõltu protsessori käsustikust) e. kõrgtaseme keeled, saab liigitada paradigma alusel
  
• keskkonnad tööks valmiskomponentidega, võimaldavad "liimida" valmiskomponendid tervikuks
  

Keele muudab arvutile arusaadavaks eriline süsteemitarkvara hulka kuuluv programm - keele translaator:

• Kompilaator - tõlgib kõrgtaseme keelest masinkoodi (või mingisse nn. vahekoodi, näit. Java baitkoodi).
  
• Interpretaator - täidab programmi ilma masinkoodi moodustamata; tavaliselt interpreteeritakse vahekoodi, mitte programmi teksti.
  
• JIT (Just In Time) kompilaator - teisendab vahekoodi masinkoodiks "vajadusel" (näit. optimiseerimise eesmärgil).
  

Näiteks keele Java korral
Programmi elutsükkel (IDE mõttes - small picture , mitte segi ajada elutsükliga tarkvaratootmises):

• programmi teksti sisestamine (näiteks notepad abil, programmi teksti toimetamiseks kontoripaketid hästi ei sobi!)
  
• programmi kompileerimine (Java keele korral: javac Programm.java)
  
• süntaksivigade parandamine (süntaksi silumine)
  
• käivitamiseks vajaliku keskkonna loomine ja muude programmide kaasamine (kui vaja)
  
• programmi käivitamine (Java keele korral: java Programm )
  
• sisuliste vigade parandamine (silumine, debugging)
  
• programmi testimine (testid peavad olema ENNE välja mõeldud; parem veel, kui testib keegi teine)
  
• programmi dokumenteerimine (Java keele korral genereeritakse html- vormingus dokumentatsioon javadoc abil)
  
• programmi viimine tegeliku kasutajani ja kõik see, mis on seotud tarkvaratehnika aspektidega - big picture
  

Programmeerimise paradigmad ,  imperatiivne vs. deklaratiivne lähenemine:

• imperatiivne
  
• funktsionaalne
  
• loogiline
  
• objekt-orienteeritud
  
• ...
  

Ajalooliselt esimesed kõrgtaseme keeled toetavad imperatiivset lähenemist.

• FORTRAN , kirjeldus 1954, realisatsioon 1956. J. Backus. FORmula TRANslator
  
• ALGOL , 1958, P. Naur. ALGOrithmic Language - Euroopa projekt
  
• COBOL, 1959 , COmmon Business Oriented Language - USA
  
• BASIC , 1965, Beginners All- purpose Symbolic Instruction Code - USA
  
• Pascal , 1971 , N. Wirth - Euroopa
  
• C, 1974, D. Ritchie
  
• Ada, 1979 - USA
  
• Funktsionaalsetest keeltest esimene on Lisp, 1962, J. McCarthy, LISt Processing - MIT
  
• Loogilistest keeltest esimene on Prolog, 1971, PROgramming in LOGic - Marseille Univ .
  
• OOP alused Simula, 1967
  
• Smalltalk - "puhas" OOP
  
• C++ , 1986, B. Stroustrup, OOP
  
• ML, Haskell , Scheme - funktsionaalsed
  
• Java, 1995, Sun - OOP
  

Programmeerimiskeelt iseloomustavad:

leksika - kuidas panna kirja elementaarseid "sõnu" antud keeles - nimed (identifikaatorid), konstandid (arvud, stringid, tõeväärtused jne.),  võtmesõnad (reserveeritud nimed), eraldajad jne.

süntaks - antud keele grammatikareeglid. Erinevalt loomulikest keeltest ei ole programmeerimiskeeltes mitte midagi peale hakata süntaktiliselt vigaste tekstidega.

semantika - keelekonstruktsioonide tähendus, s.t. kuidas interpreteeritakse süntaktiliselt korrektset programmi.

stiil ja programmide koostamise metoodika. On kokkulepped, millega vabatahtlikult kitsendatakse süntaktiliselt lubatud programmide hulka, et saavutada paremat loetavust inimese poolt (näit. "treppimine" programmi struktuuri väljatoomiseks, nimekokkulepped jne.).
Algoritmidest
ca 825 m.a.j. , Abu Ja'far Mohammed ibn Mûsâ al-Khowârizmî - reeglid aritmeetiliste operatsioonide sooritamiseks
Algoritm on täpne (üheselt mõistetav) juhis antud ülesande lahendamiseks. Algoritm koosneb lõplikust arvust sammudest, millest igaüks on täidetav lõpliku aja jooksul lõplikke ressursse kasutades. Algoritmi rakendatakse teatavale lähteandmete komplektile (sisend) ning ta annab teatava resultaadi (väljund).
Kui algoritm lõpetab töö (peatub) mistahes sisendi korral, siis nim. seda kõikjal määratud algoritmiks, vastasel juhul osaliseks algoritmiks.
Kui algoritmi mistahes sammu täitmise järel on üheselt määratud, milline on järgmine samm, siis nim. algoritmi determineeritud algoritmiks.
Teosti on vahend teatud tüüpi ülesannete lahendamiseks. Teosti põhiomaduseks on juhitavus - teda saab programmeerida etteantud käsusüsteemi piirides (käsusüsteemi kuuluvad tavaliselt nn. lihtkäsud, tingimuste kontrollimise käsud, juhtimiskäsud jm.). Programm on tegevusjuhend, mis on teostile üheselt mõistetav ning viib püstitatud eesmärgi saavutamisele . Programm on algoritmi realisatsioon konkreetse teosti jaoks. Tavaliselt peame teosti all silmas arvutit, aga miks mitte näiteks ka robotit või pesumasinat...
Algoritmi iseloomustamiseks kasutatakse järgmisi mõisteid:

• Korrektsus (algoritm lahendab "õiget" ülesannet, tulemus vastab spetsifikatsioonile).
  
• Määratletus (sammud on lõplikud ja üheselt määratud).
  
• Kirjelduse lõplikkus (algoritm on kirjeldatav lõpliku arvu sammudega).
  
• Peatuvus. Töö lõpetamine mistahes sisendi korral - kõikjal määratud algoritm. Osaline e. "poollahenduv" algoritm kas annab tulemuse või ei lõpeta tööd.
  
• Determinism ( samade algandmete korral vastus sama, lahenduskäik on korratav) vs. mittedeterminism (näit. "tõeline" juhuarvude generaator ).
  
• Universaalsus (lahendab probleemide klassi: sisend -> väljund ).
  
• Keerukus (efektiivsus, kas lõpetamise aeg ja/või mälumaht on praktilised).
  

Algoritmi formaalsed ( matemaatilised ) esitused (samaväärsed):

• Turingi masin, 1936-37
  
• lambda-arvutus (Church), 1941
  
• Posti süsteemid, 1943
  
• Markovi algoritmid, 1951
  
• Chomsky 0-tüüpi grammatikad , 1959
  
• programmeerimiskeeled, Sammet, 1969
  

Algoritmi peab saama väljendada nii, et see oleks mugav nii koostajale (algoritme koostavad inimesed) kui ka täitjale (teostile, arvutile).
Algoritmi esitusviisid:

•  inimesele orienteritud esitused
  
  • sõnaline kirjeldus (peab siiski mahtuma algoritmi def. alla!)
    
  • joonis - plokkskeem
    
  • algoritmikeel, näit. poolformaalne pseudokeel, millest saab kerge vaevaga tõlkida mistahes (imperatiivsesse) programmeerimiskeelde
    
  • joonis - Jacksoni skeem, E-skeem (näide1, näide2),  ...
    
  • ...
    
• arvutile orienteeritud esitused
  
  • programm kõrgtaseme programmeerimiskeeles
    
  • programm assembleris või masinkoodis
    
  • ...
    

Näide: Eukleidese algoritm kahe täisarvu suurima ühisteguri leidmiseks.

Kui teine arv on null, siis anda vastuseks esimene arv ja lõpetada.

Leida jääk, mis tekib esimese arvu jagamisel teisega .

Asendada esimene arv teisega ja teine leitud jäägiga.

Minna sammule 1.
 Joonised (plokkskeem, E-skeem)
   public static int syt (int a, int b)
      return a;
   } // syt
Algoritmi sammude järjekorra määramiseks on kasutusel kaks lähenemisviisi:

"goto"-stiilis juhtimine. Sammud on märgendatud. Algoritmis tohib "suunata" mistahes märgendile, s.t. on lubatud käsud stiilis "minna sammule 6". See on pärit masinkoodi aegadest (suunamiskäsud), kõrgkeeltest kannab seda ideed näiteks Basic. Raskesti jälgitav/ hallatav .

Struktuurne lähenemine. Algoritm pannakse kokku lihtkäskudest ja juhtimisstruktuuridest. Iga juhtimisstruktuuri tervikuna saab vaadelda kui lihtkäsku, samuti võib iga juhtimisstruktuuri koostisosa olla kas lihtkäsk või omakorda juhtimisstruktuur .
Tüüpilisteks juhtimisstruktuurideks on:

• järjend, plokk - mingi hulk samme võetakse kokku üheks sammuks
  
• valik - vastavalt mingi tingimuse täidetusele valitakse üks alternatiivsetest variantidest
  
• jadatsükkel - etteantud tegevust korratakse etteantud lõpliku jada kõigi elementide jaoks
  
• jätkamistingimusega tsükkel - etteantud tegevust korratakse niikaua , kui nn. jätkamistingimus on tõene
  
• katkestiga tsükkel - etteantud tegevust korratakse niikaua, kuni nn. väljumistingimus muutub tõeseks
  

Seni oleme vaadelnud korraga üht algoritmi/programmi - programming in small. Kui tekivad algoritmide/programmide kogud, mida on tarvis hallata, siis muutub meie ülesanne keerukamaks - programming in large.