|
XL, 1992.-1993. õppeaasta Lõppvooru ülesanded ja lahendused ÜLESANNE Teadmiste testimise programmides on tarvis ära tunda ka sisuliselt õigeid sõnalisi vastuseid (võõrkeelseid sõnu, nimesid jms.), mis on sisestatud õigekirja- või trükivigadega. Olgu tegemist küsimustega, mille vastus on tähtedest a..z ja A..Z ning tühikutest koosnev string pikkusega kuni 20. Nimetame elementaarvigadeks järgmisi muudatusi stringis: 1. sümboli lisamine või ärajätmine suvalisel kohal, 2. sümboli asendamine teisega, 3. kahe järjestikuse sümboli vahetamine. Kui etalonvastuse saab õpetaja poolt lubatud arvu elementaarvigadega teisendada õpilase vastuseks, siis loeme vastuse sisuliselt õigeks. Koostada vastuste analüüsi programm, mis sisestab maksimaalse lubatud elementaarvigade arvu ja kordab siis järgmisi samme, kuni sisestatakse tühi etalonvastus: 1. Sisestab (tavalise lugemiskäsu abil) etalonvastuse ja õpilase poolt antud vastuse. 2. Väljastab kellaaja. 3. Kontrollib sisendi vastavust ülesande tingimustele. 4. Kontrollib, kas vastus on täpne. 5. Kui vastus pole täpne, siis kontrollib, kas vastus on vigane, aga sisuliselt õige (väljastades sel juhul minimaalse tehtud elementaarvigade arvu ja ühe võimaliku teisendustee) või vale. 6. Väljastab kellaaja. Programm peab töötama küllalt kiiresti, sest õpilase vastuse analüüsiks 0-3 lubatud vea korral ei tohiks kuluda üle 15-20 sekundi. Aega programmi koostamiseks oli 5 tundi, kasutada sai keeli Turbo Pascal 5.5, Turbo C 2.0, GW-Basic ja Quick Basic. Nagu olümpiaadide praktilistes voorudes kombeks, läksid arvesse ainult töötavad programmid, mida siis hindamiseks testiti. Püüame käesolevas artiklis anda lugejale ettekujutuse kasutatud testimistehnoloogiast ja toome ära lahenduse keeles Pascal. Aja kokkuhoidmiseks ja ühtlaste nõuete tagamiseks (testimine toimus paralleelselt mitmel arvutil) oli varem koostatud testimisprotokoll, kus kirjas põhiosa testidest. Protokolli ülaosa (veidi vertikaalselt kokkusurutuna) oli järgmine: TESTIMISPROTOKOLL TESTIMISPROTOKOLL
Autor....................... Testija.................
Kool........................
Progr.keel..................
*** ÜLDPILT
Organisatsioon (kuni ... taset, rekursioon, magasin, tsykkel,
tasemed fyysil. kujul)
Sõltumine symbolitest: mõne symboli valekäsitlus,
proovib kõiki lubatud symboleid
Teisenduste vaatlemise järjekord
Kuidas vaadeldavad teisendused sõltuvad tehtust ja olukorrast
Puu läbimine(n=1, siis n=2 jne. / lubatud sügavusega& minimis)
Dialoogi vastavuse vead
Test Oodatud reakts. Tegelik
--------------------------------------------------------------
n=0
1. | aa], aa] | ebasobiv ETALON |
2. | ZZ, XX1 | ebasobiv VASTUS |
3. |qwertyuiopqwertyuiop | |
|qwertyuiopqwertyuiopl (21)| ebasobiv VASTUS |
4. |ab, ab | Vastus täpne |
5. |ab, a | Vastus vale |
n=1
6. | asdf, asDF | Vastus vale |
7. | q wer, qwer | n=1 |
8. | ZXCV, ZXBCV | n=1 |
9. | ASDF, ASDf | n=1 |
10.| as d, a sd | n=1 |
11.| 20(10),lõpus viimane teis| n=1 | aeg=
qwertyuio*,qwertyuio*
n=2
12.| q wer, qwer | n=1 |
13.| ZXCV, ZXBCV | n=1 |
14.| ASDF, ASDf | n=1 |
15.| as d, a sd | n=1 |
16.| qwert, qsety | Vastus vale | aeg=
17.| asd, a | n=2 |
18.| q, pqo | n=2 |
19.| zxc,axd | n=2 |
20.| bnm,mnb | n=2 |
21.| zxc,acx | n=2 |
22.| asdf, sdfg | n=2 |
23.| qwert, qwzerz | n=2 | aeg=
? kahtlusel muud järjek.
?
24.| 10(6),lopus 2 halba teis | n=2 | aeg=
25.| 15(8),lopus 2 halba teis | n=2 | aeg=
26.| 20(10) -"- | n=2 | aeg=
27.| pikk, lopus 3 halba teis | Vastus vale | aeg=
n=4
28.| qwer,asdf | n=4 | aeg=
29.| zwert,waecty | n=4 | aeg=
Need testid püüti lahendada iga programmiga. Muidugi oli ka selliseid juhte, kus selgus, et programm käsitleb juba ühe teisenduse tegemist nii vigaselt, et mitme järjestikuse uurimine enam mõtet ei oma. Mõtekate testide hulka võis kärpida ka olukord, kus polnud jõutud programmeerida mitme vea uurimise mehhanismi või mõnda veatüüpidest. Protokolli ülaosas olevatele küsimustele vastuste saamiseks olid välja trükitud ka programmide tekstid. Tabelis toodud testide juures selgunud vigade tegeliku olemuse selgitamiseks tuli mõnikord kasutada ka teisi algandmeid või teksti vaatlemist. Protokolli alaosas olid veel testid programmi töökiiruse kohta, mida aga rahuldavalt töötavate programmide vähesuse tõttu praktiliselt ei saanud kasutada (kõigil juhtudel enamvähem korralikult töötavaid programme esitati kaks) ja kokkuvõte punktide kohta: Dialoog (10) Sisendi kontr. (5) Täpse kontr. (5) 1 vea kontr. (30) 2 vea kontr. (20) n vea korrektsus (15) 3 vea kiirus (15) ---------------------- Summa LAHENDUSKui proovida etalonsõnast õpilase vastust saada kõiki võimalikke muudatusi kõigis võimalikes järjekordades katsetades, töötab programm liiga aeglaselt. Olgu sõna pikkus l. Siis erinevate võimaluste arv järgmise muutuse tegemiseks on: lisamisi: l+1 kohale * 65 sümbolit = 65(l+1), eemaldamisi: l, asendamisi: l kohale * 64 sümbolit = 64 l, vahetamisi: l-1, s.t. kokku umbes 130l. Ja näiteks kolme lubatud elementaarvea puhul tuleb see arv võtta ligikaudu kuupi. Järelikult tuleb leida võimalusi, et üksteist mitte mõjutavate teisenduste jadad teha läbi ainult ühes järjekorras. Allpool toodud PASCAL-programmi põhiosaks on rekursiivne protseduur UURI, mida rakendatakse igale eelmise teisendusega saadud sõnale PROOV[TASE]. Uuritavate teisendusjadade arvu vähendamiseks on kasutatud järgmisi ideid (nende korrektsuse tõestamise jätame lugejale, vt. eriti paremalt vasakule kulgevate vahetuste mittevajalikkust): I1. Iga tulemuse võib saada elementaarvigade arvu suurendamata ka nii, et teisendusi tehakse sellises järjestuses (vt.parameeter ALGOPER): 1. kõik eemaldamised, 2. kõik vahetamised, 3. kõik lisamised, 4. kõik asendamised. I2. Samaliigilised teisendused tehakse sõnas vasakult paremale liikudes (vt. parameeter KOHT). Muuhulgas vabanetakse nii ka lisamiste ja asendamiste arvudes kordajatest 65 ja 64, sest need teisendused tehakse nüüd "õigel kohal" ja sinna proovitakse nüüd ainult sama sümbolit, mis sõnas VASTUS. I3. Ei vaadelda teisendusi, mille järel pole enam võimalik järgnevate sammudega jõuda õige pikkusega sõnani. Põhiprogrammi tsükkel parameetriga MAKSTASE proovib sõna algul saada 1 elementaarveaga, siis 2-ga jne. Et lahendusaeg kasvab otsimise sügavuse kasvades väga järsult, ei mõjuta väiksema sügavuse juures tehtud töö kordamine kiirust kuigi palju. Programmi tekst Turbo Pascal programmeerimiskeeles. |