Digitaalsüsteemid   IAY0150 IAS0150

kirjalik   KODUTÖÖ
    2018

ARVUTUSALGORITM ja selle PROGRAMNE MODELLEERIMINE

  tagasi
1.  Koostada algoritmi graafskeemina (AGS) järgnevas tabelis määratud algoritm ja esitada ka sellega kokkusobiv operatsioonseadme struktuurskeem (algoritmis vajalikud kõik registrid ja summaatorid.., nendevahelised ühendused, juhtsignaalid (juhtkäsud)   y  , mida juhtsignaalid mõjutavad/kuhu rakenduvad...)
AGSi iga juhtkäsu ja tingimuskontrolli kohta esitada ka 1...2-lauseline selgitav kommentaar.
Vormistusele erinõudeid pole, kuid see peab olema arusaadav ja korrektne, ilma rohkete käsitsiparandusteta/sodimisteta.

  Matr. nr.  
käsitletav   algoritm
x x x x 00
x x x x 33
x x x x 13
x x x x 26
x x x x 39
x x x x 52
x x x x 65
x x x x 78
x x x x 91
Korrutamine kahe kohaga üheaegselt (s.o. ühes korrutustsüklis analüüsitakse korrutaja kahte naaberjärku).
Operandid on positiivsed 2ndtäisarvud, mille pikkus on antud   tehteoperandide tabelis.
Resultaat on sama pikkusega nagu operandid.
Algoritm peab korrektselt töötama suvaliste operandide korral (mis mahuvad etteantud formaati), mitte ainult (punktis 3) modelleerimiseks/simuleerimiseks kasutatud konkr. operandide korral.
Algoritm peab tuvastama ka tehtetulemuse võimaliku ületäitumise.
x x x x 01
x x x x 19
x x x x 46
x x x x 06
x x x x 14
x x x x 27
x x x x 40
x x x x 53
x x x x 66
x x x x 79
Suvalise märgiga arvude vahetu korrutamine (s.o. operande ei teisendata korrutamistsükli ajaks positiivseteks).
Operandid on märgiga 2ndtäisarvud, mille pikkus ja neg. operandi kodeering (täiendkood/pöördkood) on antud   tehteoperandide tabelis.
Resultaat on sama pikkusega nagu operandid.
Algoritm peab korrektselt töötama suvaliste operandide korral (mis mahuvad etteantud formaati), mitte ainult (punktis 3) modelleerimiseks/simuleerimiseks kasutatud konkr. operandide korral.
Algoritm peab tuvastama ka tehtetulemuse võimaliku ületäitumise.
x x x x 02
x x x x 32
x x x x 15
x x x x 28
x x x x 41
x x x x 54
x x x x 67
x x x x 80
x x x x 93
Korrutamine Booth'i algoritmiga.
Operandid on märgiga 2ndtäisarvud, mille pikkus on antud   tehteoperandide tabelis.
Negatiivsed operandid on täiendkoodis.
Resultaat on sama pikkusega nagu operandid.
Algoritm peab korrektselt töötama suvaliste operandide korral (mis mahuvad etteantud formaati), mitte ainult (punktis 3) modelleerimiseks/simuleerimiseks kasutatud konkr. operandide korral.
Algoritm peab tuvastama ka tehtetulemuse võimaliku ületäitumise.
x x x x 03
x x x x 16
x x x x 59
x x x x 29
x x x x 42
x x x x 55
x x x x 68
x x x x 81
x x x x 94
Suvalise märgiga arvude vahetu jagamine (s.o. operande ei teisendata jagamistsükli ajaks positiivseteks).
Operandid on märgiga 2ndtäisarvud, mille pikkus ja neg. operandi kodeering (täiendkood/pöördkood) on antud   tehteoperandide tabelis.
Resultaadiks olevad jagatis ja jääk on mõlemad sama pikkusega täisarvud nagu on ka operandide pikkus.
Algoritm peab korrektselt töötama suvaliste operandide korral (mis mahuvad etteantud formaati), mitte ainult (punktis 3) modelleerimiseks/simuleerimiseks kasutatud konkr. operandide korral.
(algoritmi modelleerimisel operandidega:   A1  jagada operandiga B1  ja  A2   jagada operandiga B2  )
x x x x 04
x x x x 45
x x x x 17
x x x x 30
x x x x 43
x x x x 56
x x x x 69
x x x x 82
x x x x 95
Jagamine jäägi taastamisega.
Operandid on märgiga 2ndtäisarvud, mille pikkus ja neg. operandi kodeering (täiendkood/pöördkood) on antud   tehteoperandide tabelis.
Resultaadiks olevad jagatis ja jääk on mõlemad sama pikkusega täisarvud nagu on ka operandide pikkus.
Algoritm peab korrektselt töötama suvaliste operandide korral (mis mahuvad etteantud formaati), mitte ainult (punktis 3) modelleerimiseks/simuleerimiseks kasutatud konkr. operandide korral.
(algoritmi modelleerimisel operandidega:   A1  jagada operandiga B1  ja  A2   jagada operandiga B2  )
x x x x 05
x x x x 58
x x x x 18
x x x x 31
x x x x 44
x x x x 57
x x x x 70
x x x x 83
x x x x 96
Jagamine jäägi taastamiseta.
Operandid on märgiga 2ndtäisarvud, mille pikkus ja neg. operandi kodeering (täiendkood/pöördkood) on antud   tehteoperandide tabelis.
Resultaadiks olevad jagatis ja jääk on mõlemad sama pikkusega täisarvud nagu on ka operandide pikkus.
Algoritm peab korrektselt töötama suvaliste operandide korral (mis mahuvad etteantud formaati), mitte ainult (punktis 3) modelleerimiseks/simuleerimiseks kasutatud konkr. operandide korral.
(algoritmi modelleerimisel operandidega:   A1  jagada operandiga B1  ja  A2   jagada operandiga B2  )
x x x x 08
x x x x 71
x x x x 21
x x x x 34
x x x x 47
x x x x 60
x x x x 73
x x x x 86
x x x x 99
Ujupunktarvude korrutamine (suvaline korrutusalgoritm).
Operandid ja resultaat on samasuguse ujupunktformaadiga, mis on antud   tehteoperandide tabelis.
Negatiivsed   mantissi  ja  astendaja  väärtused on   täiendkoodis  või  pöördkoodis ,   nagu on määratud samas tehteoperandide tabelis.
x x x x 09
x x x x 72
x x x x 84
x x x x 22
x x x x 35
x x x x 48
x x x x 61
x x x x 74
x x x x 87
Ujupunktarvude jagamine jäägi taastamisega.
Operandid ja resultaat on samasuguse ujupunktformaadiga, mis on antud   tehteoperandide tabelis.
Negatiivsed   mantissi  ja  astendaja  väärtused on   täiendkoodis  või  pöördkoodis ,   nagu on määratud samas tehteoperandide tabelis.
(algoritmi modelleerimisel operandidega:   A1  jagada operandiga B1  ja  A2   jagada operandiga B2  )
x x x x 10
x x x x 85
x x x x 23
x x x x 36
x x x x 49
x x x x 62
x x x x 75
x x x x 88
x x x x 97
Ujupunktarvude jagamine jäägi taastamiseta.
Operandid ja resultaat on samasuguse ujupunktformaadiga, mis on antud   tehteoperandide tabelis.
Negatiivsed   mantissi  ja  astendaja  väärtused on   täiendkoodis  või  pöördkoodis ,   nagu on määratud samas tehteoperandide tabelis.
(algoritmi modelleerimisel operandidega:   A1  jagada operandiga B1  ja  A2   jagada operandiga B2  )
x x x x 11
x x x x 07
x x x x 24
x x x x 37
x x x x 50
x x x x 63
x x x x 76
x x x x 98
x x x x 89
Ujupunktarvude liitmine.
Operandid ja resultaat on samasuguse ujupunktformaadiga, mis on antud   tehteoperandide tabelis.
Negatiivsed   mantissi  ja  astendaja  väärtused on   täiendkoodis  või  pöördkoodis ,   nagu on määratud samas tehteoperandide tabelis.
x x x x 12
x x x x 20
x x x x 25
x x x x 38
x x x x 51
x x x x 64
x x x x 77
x x x x 90
x x x x 92
Ujupunktarvude lahutamine.
Operandid ja resultaat on samasuguse ujupunktformaadiga, mis on antud   tehteoperandide tabelis.
Negatiivsed   mantissi  ja  astendaja  väärtused on   täiendkoodis  või  pöördkoodis ,   nagu on määratud samas tehteoperandide tabelis.

Vormistus

Kodutöö esituskuju paberil võib olla nii arvutiväljatrükk kui ka parandusteta (sodimisteta) käsikiri.

Kodutöö peab olema A4 lehtedel, kus esimesele lehele on prinditud printeriga pealkiri  
kirjalik   KODUTÖÖ
Esimese lehe paremale serva peab olema printeriga prinditud:
nimi
matriklinumber
rühm


Edasi tohivad lahendused olla ka käsitsi kirjutatud, kuid soovijad tohivad teha kogu töö sisu arvutiga.
Vormistus võib olla ka selline prinditud väljatrükk, kuhu on käsitsi juurde kirjutatud kõik need erimärgid/sümbolid/tähised, mida arvutiga on raske teha.
Kodutöö ülejäänud lehtedel peab olema paremal üleval nurgas samuti olemas   nimi.    Ülejäänud lehtedel (peale tiitellehe) võib nimi olla lehenurka kirjutatud käsitsi.

Köitmisvõimalused

A4 lehed peavad olema kokku köidetud klambrilööjaga (ühe klambriga lehtede vasakus ülaservas) VÕI lahtised (klambriga kinnitamata) A4 lehed tohib panna õiges järjekorras A4 läbipaistvasse kiletaskusse, tiitelleht kõige pealmisena nähtavaks.
Lahtisi paberilehti vastu ei võeta. Klambrilööjaga kinnitus, üheainsa klambriga lehe vasakus ülaservas või läbipaistev A4 kiletasku on vajalik.
"Tavalised" (äravõetavad) kirjaklambrid ei sobi:


Failina kodutööd esitada ei saa.   Seega ei saa kodutööd esitada ka e-mailiga.

Tähtaeg

KIRJALIKU KODUTÖÖ   tähtaeg on neljap. 17. mai.   Tähtaegselt esitatud arvestatud töö võib saada kuni 15 punkti (ilma simuleeriva programmita) või kuni 25 punkti   (koos simuleeriva programmiga).
Hilinenud töö saab vähem punkte.

1 päeva võrra hilinenult esitatud programmita töö võib saada kuni 14 punkti; 1 päeva võrra hilinenult esitatud programmiga töö võib saada kuni 24 punkti;
      19. ja 20. mai   on nädalavahetus ja ei lisa hilinemist
4 päeva võrra hilinenult esitatud töö võib saada kuni 13 / 23 punkti;
5 päeva võrra hilinenult esitatud töö võib saada kuni 12 / 22 punkti;
6 päeva võrra hilinenult esitatud töö võib saada kuni 11 / 21 punkti;
7 päeva võrra hilinenult esitatud töö võib saada kuni 10 / 20 punkti;
8 päeva võrra hilinenult esitatud töö võib saada kuni 9 / 19 punkti;
      26. ja 27. mai   on nädalavahetus ja ei lisa hilinemist
11 päeva võrra hilinenult esitatud töö võib saada kuni 8 / 18 punkti;
12 päeva võrra hilinenult esitatud töö võib saada kuni 7 / 17 punkti;
13 päeva võrra hilinenult esitatud töö võib saada kuni 6 / 16 punkti;
2 nädalat või enam hilinenud kodutöö võib saada kuni 5 / 15 punkti;
Üle 2 nädala hilinenud igasugune kodutöö kuulub kaitsmisele, kus töö kohta esitatakse küsimusi.

Enne ja pärast tähtaega on võimalik kodutööd esitada harjutustundides või loengutes, samuti   ARVUTITEHNIKA INSTITUUT postkasti   ICT-majas välisukse juures.
Kirjalikku kodutööd saab hilinenult esitada ka harjutustundide materjalide vastamisaegadel, mis teatatakse maikuus veebilehel   www.diskmat.ee


2.   Algoritmi modelleeriv arvutiprogramm

Kui töö autor programmeerib oma kirjaliku kodutöö koosseisus ka algoritmi simuleeriva (modelleeriva) arvutiprogrammi, siis koos arvutiprogrammiga töö võib saada kuni 25 punkti.
Oma algoritmi simulaatorprogrammi programmeerimine on vabatahtlik. Ilma simuleeriva programmita kirjalik kodutöö võib arvestatuna saada kuni 15 punkti.
Koos simuleeriva arvutiprogrammiga tehtud kodutöö saab arvestatuks alles pärast kaitsmise läbimist, mille käigus demonstreeritakse/kontrollitakse programmi töötamist ja esitatakse kodutöö kohta küsimusi.

Programmeerimisvahendid võib valida vabalt.
Sobivad teostuskujud on:
  • PC-arvutil töötav autonoomne .EXE-programm või interpretaatoris töötav programm (näit. Basic).
  • Veebibrowseris (näiteks Internet Explorer, Mozilla Firefox, Chrome .....) töötav WWW-põhine realisatsioon.
  • Riistvara kirjelduskeeles   VHDL   kirjeldatud seade, mis realiseerib kodutöö algoritmi. Simulatsiooni demonstreerimisel võib kasutada suvalist simulaatorit. Simulatsiooni (vahe)tulemused / registrite sisud   tuleb väljastada ekraanile vabaltvalitud, kuid arusaadaval kujul.
    ! VHDL-i ei õpita aines IAY0140. See võimalus on neile, kes on VHDL kursuse juba läbinud või samal semestril läbimas mõnes muus õppeaines.

    sisendandmed ja väljund

    Simuleeriva arvutiprogrammi töötulemused peavad väljatrükkidena töö koosseisus sisalduma enda kahe operandipaari jaoks siit tehteoperandide tabelist (vastavalt matriklinumbrile).

    Esitada (programmi töötulemusena) kaks täielikku modelleerimistsüklit erinevate tehteoperandidega:
    esmalt operandidega A1 ja B1 ja seejärel operandidega A2 ja B2 , näidates kõikide kasutuselolevate registrite sisu pärast nende igat muutumist algoritmi töö käigus.
    Selleks koostada "registriväärtuste veerg". (veeru igale reale üks registriväärtus, kuid VEERGE tohib leheküljel olla ka mitu)
    Kui algoritm muudab oma töösammul mingit registrit, siis lisandub jada lõppu selle registri uus väärtus.
    näide:
    RgA = 00.0110010
    RgB = 1100010
    RgC = 11.0011011
    . . . . .
    Registriväärtuste jadas näidata ära ka iteratiivsete tsüklite "piirid" (kus eelmine algoritmitsükkel lõppeb ja algab uus tsükkel).

    Sisendandmed peavad olema sisestatavad klaviatuurilt ja programm peab väljastama algoritmitsüklite vahetulemused (registrite 2ndkujulised sisud) ja algoritmi töö resultaadi ekraanile.
    Sisendandmeid (registrite algväärtused enne algoritmi töö algust) peab olema võimalik sisestada ka kahendkujul!
    Lisaks 2ndkujulisele sisestusvõimalusele võib kasutusmugavuseks (autori soovi korral) olemas olla ka 10ndkujuline lähteandmete sisestusvõimalus, misjuhul peab programm siiski näitama ka nende (kui algandmete) 2ndkujulist paigutumist registrites.
    Programm võiks sisendandmete sobivust kontrollida ehk olla valeandmete eest kaitstud. (Programmi töötamise kontrollimisel püüame siiski sisestada ainult sobivaid väärtusi) Programmi paberileprinditud lähtetekst (source) tuleb lisada kodutöö lõppu ja selle kohta esitatakse töö kaitsmisel küsimusi. (Programm peab olema enda programmeeritud - mitte sama algoritmi tegeva sõbra käest valmiskujul saadud)

    programmi töötamise demonstreerimine

    Teostusviisist olenemata tuleb programmi töötamine kodutöö kaitsmisel ette näidata.
    Programmi demonstreerima/kaitsma tuleb tulla selleks ettevalmistatud sülearvutiga.
    Modelleeriv programm peab edukalt töötama mitte ainult kodutöövariandis antud enda operandidega , vaid suvaliste (sobivas väärtusvahemikus) operandide korral.
    Programmi töötamist kontrollitakse mitmete juhuslike sobivate lähteandmetega.

    vabatahtlik lisapunktide võimalus aine IAY0150 läbinutele:
    Mealy' juhtautomaadi projekteerimine/süntees vaadeldud algoritmi realiseeriva operatsiooniautomaadi juhtimiseks

    Juhtautomaadi loomine on vabatahtlik — kodutöö on täielik ka ilma selleta.
    Juhtautomaati (oma algoritmi realiseeriva operatsiooniautomaadi jaoks) saavad teha ainut need õpilased, kellel on aine IAY0150 (Digitaalsüsteemid) juba läbitud.
    Juhtautomaadi loomine võimaldab saada kirjaliku kodutöö eest kuni 5 lisapunkti.
    Juhtautomaadiga kodutöö peab läbima kaitsmise (s.t. määratakse kaitsmisele) ja saab punkte alles pärast edukat kaitsmist.   Kaitsmisel esitatakse küsimusi kogu kodutöö kohta.

    Juhtautomaadi mäluelemendid (trigerite tüübid) on määratud olenevalt matriklinumbrist:
    paarituarvulise matr.numbriga õpilased võtavad mäluelementideks D-trigerid;
    paarisarvulise matr.numbriga õpilased võtavad mäluelementideks JK-trigerid;

    üldjuhised Mealy' juhtautomaadi loomiseks:
    käsitletud algoritmi graafskeemil (AGS ehk GSA) tähista algoritmi juhtkäsud / sammud   (ehk ristkülikukujulised kastid) AGS-is:
    y1
    y2
    y3
    . . .
    ja algoritmi hargnemisi määravad (rombikujulised) tingimussõlmed tähista:
    x1
    x2
    x3
    . . .

    Kui algoritmi mitu järjestikust käsku ei mõjuta üksteist (ehk tohivad seega toimuda samaaaegselt), siis neid esitavad juhtkäsud y tasub juhtautomaadi AGS-il kokku paigutada samasse "kasti" - näiteks:
    y1 y2
    Juhtautomaati esitaval AGS-il vali Mealy' automaadi vajalikud olekud. Vaja taotleda vähimat piisavat olekute arvu.
    Kodeerida automaadi olekud. Olekukoodid võib omistada meelevaldselt / juhuslikult või sihipäraselt, mingit optimeerimistunnust arvestades.
    Kui kodeering pole valitud "juhuslik", siis selgitada / põhjendada olekukoodide valikut.
    Minimeerida on vaja (suvalisel meelepärasel viisil) iga loogikafunktsioon (siirdefunktsioon või väljundfunktsioon), mille muutujate arv on 3 või 4 või 5.
    6 ja enama muutujaga loogikafunktsioone ei pea minimeerima: neid võib esitada/realiseerida/kasutada nende algsel, minimeerimata kujul.

    Kuni 5 muutujaga loogikafunktsioonid tuleb esitada VÕI-EI kujulise loogikaavaldisena (näidates ka leidmise vahetulemused/avaldised) ja nad tuleb realiseerida loogikaskeemina VÕI-EI loogikaelementidel. Loogikaelementide sisendite arv pole piiratud. Samas loogikaskeemis on lubatud ka erinevate sisendite arvuga VÕI-EI elemendid.
    6 või enama muutujaga loogikafunktsioonid tuleb esitada JA-EI kujulise loogikaavaldisena (näidates ka leidmise vahetulemused/avaldised). 6 või enama muutujaga loogikafunktsioonide jaoks nende loogikaskeemide väljajoonistamine on vabatahtlik: tohib - aga ei pea. ("Suurte funktsioonide" loogikaskeemid võivad osutuda väga mahukateks, mahtudes ära ainult suurele paberile)
    Olenevalt konkreetsest algoritmist on ka võimalik, et vastava juhtautomaadi kõik loogikafunktsioonid juhtuvad olema enam kui 5 muutujaga.

    Juhtautomaadi ülesjoonistatud kujule pole rangeid nõudeid. Piisab kui skeem on asjakohase sisuga ja arusaadav. Juhinduda võib aines IAY0150 olnud praktikatest. Puuduste korral tuleb nendest juttu töö kaitsmisel.
    Juhtautomaadi ülesjoonistatud kujus peavad olema näha trigerid (juhtautomaadi mäluelemendid), ergutussignaalide (juhtsignaalide) genereerumine/saabumine nendele ja trigeri väljundite kasutamine.
    Kui mingi loogikaskeem on joonisel tema liigsuuruse tõttu ärajäetud (nagu on eespool lubatud suurte JA-EI skeemide jaoks), siis peab joonisel olema teda tähistav "kast" milles on (näiteks) tekst:". . . JA-EI loogikaskeem . . ." ning näidatud peavad olema sellesse skeemi/kasti saabuvad sisendid ja skeemi väljundsignaali (ehk väljaarvutatud loogikafunktsiooni väärtuse) rakendumine: läheb skeemil ergutussignaalina trigerile; rakendub juhtsignaalina y mingile komponendile operatsiooniautomaadis (OA) . . . .

    punktid kirjaliku kodutöö eest

    Arvestatud kodutöö ilma simuleeriva arvutiprogrammita ja ilma juhtautomaadita võib saada kuni 15 punkti. Kui kodutöö määratakse kaitsmisele, siis saab ta arvestatuks (ja annab punkte) alles pärast edukat kaitsmist.
    Arvutiprogrammiga ja/või juhtautomaadiga kodutöö määratakse kindlasti kaitsmisele ja ta saab arvestatuks pärast edukat kaitsmist, lisades punktiarvestusse kuni (15 + 10 + 5) punkti olenevalt modelleeriva programmi töötamise õigsusest ja/või olenevalt loodud juhtautomaadist ja olenevalt kogu kodutöö "kaitsmise" edukusest.
    Kuigi arvutiprogrammi lähtetekst lisatakse vormistatud kodutööle, siis esitamise ja kaitsmise (programmi demonstreerimise) vahelisel ajal tohib programmis ikkagi teha muudatusi/parandusi.
    Kui programmi läbikukkunud kaitsmisel selgub, et esitaja pole seda programmi ilmselgelt ise programmeerinud, siis temapoolt väljateenitud eksamieelne hinne langeb ühe hinde võrra.


    3.   algoritmi modelleerimine "käsitsi"   ilma arvutiprogrammita kodutöös

    Simuleeriva arvutiprogrammiga kodutöödes ei ole vaja esitada algoritmi "käsitsi modelleerimise" tulemusi, kuna programmiga tööd sisaldavad arvutiprogrammiga saadud simuleerimistulemusi.
    (Samas pole võimatu, et autor soovis modelleerida ka seljuhul oma algoritmi töötamist ka "käsitsi", et kontrollida arvutiprogrammi töötulemuste õigsust)

    Ilma simuleeriva arvutiprogrammita kodutöödes tuleb modelleerida "käsitsi" oma algoritmi töötamist kahe operandipaariga samast tehteoperandide tabelist.
    Esitada kaks täielikku modelleerimistsüklit erinevate tehteoperandidega:
    esmalt operandidega A1 ja B1 ja seejärel operandidega A2 ja B2 , näidates kõikide kasutuselolevate registrite sisu pärast nende igat muutumist algoritmi töö käigus.
    Selleks koostada "registriväärtuste veerg". (veeru igale reale üks registriväärtus, kuid VEERGE tohib leheküljel olla ka mitu)
    Kui algoritm muudab oma töösammul mingit registrit, siis lisandub jada lõppu selle registri uus väärtus.
    näide:
    RgA = 00.0110010
    RgB = 1100010
    RgC = 11.0011011
    . . . . .
    Registriväärtuste jadas näidata ära ka iteratiivsete tsüklite "piirid" (kus eelmine algoritmitsükkel lõppeb ja algab uus tsükkel).
    Hinnata tulemuseks saadud 2ndkuju õigsust, teisendades ta 10ndkujule ja võrreldes oodatava 10ndväärtusega.

    JÕUDU TÖÖLE !

      tagasi

      hl@cc.ttu.ee