1.6 DRILL — LMC-sporing, fyll-inn og reverse tracing
Full drill på sjanger C: spor programmer mekanisk, fyll inn riktig instruksjon, dekod maskinkode og løs reverse tracing.
Nivå 1 — dette må sitte. Kapitlet inneholder ingen ny teori. Det er treningsbanken: fjorten programmer som roterer alle variantene sjangeren kommer i.
De fem variantene:
1. Ren sporing — «hva skriver programmet ut?»
2. Fyll inn — «hvilken instruksjon må stå i celle N for at programmet skal gjøre X?»
3. Maskinkode — «hva gjør dette programmet, gitt som rene tall?»
4. Selvmodifiserende kode — programmet endrer sine egne instruksjoner underveis.
5. Baklengs sporing — «hvilke inndata gir denne utskriften?», ofte med flere svar.
Tidsbruk: 80 minutter. Kapitlet tåler å deles over to kvelder — oppgave 1–7 den ene, 8–14 den andre. Er du kort i tid, gjør oppgave 4, 7, 9, 11 og 13: de fem dekker alle variantene.
Én regel for hele drillen: før sporetabell. Hver eneste gang.
Forkunnskaper — sist du var her
Kapitlet bygger på kap. 1.4 og kap. 1.5. Her er alt du trenger, ferdig oppfrisket:
1. Instruksjonssettet.
| Mnemonic | Kode | Virkning |
|---|---|---|
INP / OUT / OTC | 901 / 902 / 922 | Les inn · skriv ut som tall · skriv ut som tegn |
LDA xx / STA xx | 5xx / 3xx | Last fra celle · lagre til celle |
ADD xx / SUB xx | 1xx / 2xx | Legg til · trekk fra celleinnholdet |
BRA xx / BRZ xx / BRP xx | 6xx / 7xx / 8xx | Hopp alltid · hopp hvis 0 · hopp hvis 0 eller større |
HLT / DAT n | 000 / — | Stopp · datacelle med startverdi |
2. De tre kontraktspørsmålene. Hva ble akkumulatoren? Hvilken celle endret seg? Hvor peker programtelleren?
3. Sporetabellen. Én rad per utført instruksjon, med egen kolonne for hver navngitt celle — og for hver kodecelle som blir modifisert.
4. ASCII-utdraget:
A = 65, H = 72, I = 73, K = 75, O = 79, ! = 33, mellomrom = 32.1. Sett opp tabellen: PC, instruksjon, akkumulator, hver navngitt celle, ut-kurv.
2. Start med PC = 00, akkumulator = 0 og datacellene på sine DAT-verdier.
3. Én rad per utført instruksjon. Skriv av verdier også når de er uendret.
4. Ved betinget hopp: noter hva betingelsen var («akk = 2, ikke 0, hopper ikke»).
5. Fortsett til HLT.
Variant 2 — fyll inn instruksjon.
1. Les hva programmet skal gjøre, i ord.
2. Spor programmet fram til den tomme cellen, og skriv ned hva akkumulatoren og cellene inneholder der.
3. Spør: hvilken instruksjon tar oss fra denne tilstanden til det ønskede resultatet?
4. Test svaret ved å spore ferdig med instruksjonen på plass — og test det med minst to ulike inndata.
Variant 3 — maskinkode.
1. Dekod celle for celle: første siffer i opkodetabellen, de to siste er adressen.
2. Skriv programmet om til assemblerkode før du sporer.
3. Kontroller ved å kode tilbake.
Variant 4 — selvmodifiserende kode.
1. Se etter STA med adresse i kodeområdet. Der er modifikasjonen.
2. Gi den cellen egen kolonne i tabellen.
3. Dekod den nye verdien som instruksjon før du sporer videre.
4. Sjekk at cellen rekker å bli skrevet før programtelleren når den.
Variant 5 — baklengs sporing.
1. Beskriv i ord hva programmet gjør, gren for gren.
2. Spør hvilke inndata som gir den oppgitte utskriften, for hver gren.
3. Sjekk grenseverdien eksplisitt — BRP hopper også på null.
4. Oppgi alle løsningene.
Programmet skal gange to tall ved å legge det første til seg selv så mange ganger som det andre tallet sier. Med inndataene 3 og 4 skal det skrive ut 12.
Hvilken instruksjon må stå i celle 10?
00 INP
01 STA 60
02 INP
03 STA 61
04 LDA 62
05 ADD 60
06 STA 62
07 LDA 61
08 SUB 63
09 STA 61
10 ?
11 BRA 04
12 LDA 62
13 OUT
14 HLT
60 DAT
61 DAT
62 DAT 0
63 DAT 1Linje 00–03 leser de to tallene inn i celle 60 og 61. Linje 04–06 legger celle 60 til en sum som ligger i celle 62. Linje 07–09 teller celle 61 ned med 1.
Linje 11 er BRA 04, altså tilbake til toppen av løkka. Da må linje 10 være det som avslutter løkka når telleren er brukt opp.
Steg 2 — spor fram til den tomme cellen.
Med inndataene 3 og 4: celle 60 er 3, celle 61 er 4, celle 62 er 0.
| PC | Instruksjon | Akk | Celle 61 | Celle 62 |
|---|---|---|---|---|
| 04 | LDA 62 | 0 | 4 | 0 |
| 05 | ADD 60 | 3 | 4 | 0 |
| 06 | STA 62 | 3 | 4 | 3 |
| 07 | LDA 61 | 4 | 4 | 3 |
| 08 | SUB 63 | 3 | 4 | 3 |
| 09 | STA 61 | 3 | 3 | 3 |
| 10 | ? | 3 | 3 | 3 |
Akkumulatoren inneholder telleren, nettopp redusert med 1.
Steg 3 — hvilken instruksjon trengs?
Løkka skal kjøre til telleren er brukt opp, altså til akkumulatoren er 0. Da skal programmet ut av løkka og videre til linje 12, som henter summen.
Instruksjonen må altså hoppe til 12 når akkumulatoren er nøyaktig 0:
BRZ 12.Steg 4 — test svaret.
Med
BRZ 12 på plass: telleren går 4 → 3 → 2 → 1 → 0, altså fire runder. Summen blir 3 + 3 + 3 + 3 = 12. Riktig.Test med 5 og 2: to runder gir
5 + 5 = 10. Riktig. Test med 7 og 1: én runde gir 7. Riktig.— naturlig pausepunkt —
Margnotat: hvorfor ikke BRP 12?
BRP hopper på 0 og alt over. Da ville løkka avsluttet allerede første gang telleren var 3, altså etter én runde, og svaret blitt 3 i stedet for 12.
Dette er den vanligste bommen i fyll-inn-oppgaver: å velge BRP når BRZ er riktig, eller motsatt. Testen er alltid å spore med begge og se hvilken som gir riktig antall runder.
Margnotat: hvorfor ikke BRA 12?
Da ville løkka kjørt nøyaktig én runde uansett, siden BRA hopper hver gang. Utskriften ville alltid vært det første tallet.
Drillen — fjorten oppgaver
Oppgave 1–4 er ren sporing, 5–7 er maskinkode og tekstutskrift, 8–10 er fyll inn, 11–12 er selvmodifiserende kode, og 13–14 er baklengs sporing.
Alle har full sporetabell i løsningen. Sammenlign din egen tabell rad for rad — det er der du finner ut hvor du sklir.
Hva skriver programmet ut med inndataene 2, 3 og 4?
00 INP
01 STA 90
02 INP
03 ADD 90
04 STA 90
05 INP
06 ADD 90
07 OUT
08 HLT
90 DATHva skriver programmet ut med inndataene 4 og 9?
00 INP
01 STA 70
02 INP
03 STA 71
04 LDA 71
05 OUT
06 LDA 70
07 OUT
08 HLT
70 DAT
71 DATHva skriver programmet ut med inndata 4?
00 INP
01 STA 50
02 LDA 51
03 ADD 50
04 STA 51
05 LDA 50
06 SUB 52
07 STA 50
08 BRP 02
09 LDA 51
10 OUT
11 HLT
50 DAT
51 DAT 0
52 DAT 1Hvor mange ganger kjøres løkka, og hva skrives ut, med inndata 6? Og med inndata 7?
00 INP
01 STA 20
02 LDA 21
03 ADD 22
04 STA 21
05 LDA 20
06 SUB 23
07 STA 20
08 BRP 02
09 LDA 21
10 OUT
11 HLT
20 DAT
21 DAT 0
22 DAT 1
23 DAT 2Cellene 00 til 08 inneholder tallene under. Dekod programmet, og si hva det skriver ut med inndataene 8 og 3.
celle: 00 01 02 03 04 05 06 07 08 tall: 901 380 901 381 580 281 902 000 000Hva skriver programmet ut? Bruk ASCII-utdraget i forkunnskapene.
00 LDA 30
01 OTC
02 LDA 31
03 OTC
04 LDA 32
05 OTC
06 HLT
30 DAT 79
31 DAT 75
32 DAT 33Kryss av alle påstandene som stemmer om programmet under, kjørt med inndata 4.
00 INP
01 STA 40
02 SUB 41
03 BRP 07
04 LDA 40
05 ADD 40
06 BRA 08
07 LDA 40
08 OUT
09 HLT
40 DAT
41 DAT 5a) Programmet skriver ut 8.
b) Instruksjonen i celle 07 blir ikke utført.
c) Programmet dobler alle inndata under 5.
d) Med inndata 5 skriver programmet ut 10.
Programmet skal skrive ut inndataen og deretter hver verdi to lavere, ned til og med 0. Med inndata 8 skal utskriften være 8 6 4 2 0. Hvilken instruksjon må stå i celle 06?
00 INP
01 STA 20
02 LDA 20
03 OUT
04 SUB 21
05 STA 20
06 ?
07 HLT
20 DAT
21 DAT 2Alternativene er BRZ 02, BRP 02, BRA 02 og BRZ 07.
Programmet skal gange to tall. Med inndataene 3 og 4 skal det skrive ut 12. Hvilken instruksjon må stå i celle 10?
00 INP
01 STA 60
02 INP
03 STA 61
04 LDA 62
05 ADD 60
06 STA 62
07 LDA 61
08 SUB 63
09 STA 61
10 ?
11 BRA 04
12 LDA 62
13 OUT
14 HLT
60 DAT
61 DAT
62 DAT 0
63 DAT 1I programmet fra oppgave 9: hva skjer hvis celle 62 hadde hatt startverdien DAT 5 i stedet for DAT 0? Vis med inndataene 3 og 4.
Kryss av alle påstandene som stemmer om programmet under.
00 INP
01 ADD 40
02 STA 05
03 LDA 41
04 OUT
05 DAT 0
06 LDA 30
07 OUT
08 HLT
30 DAT 0
31 DAT 0
40 DAT 330
41 DAT 99a) Celle 05 utføres før den blir modifisert.
b) Med inndata 0 skriver programmet ut 99 to ganger.
c) Med inndata 1 skriver programmet ut 99 og deretter 0.
d) Celle 40 inneholder malen for en STA-instruksjon.
Hva blir instruksjonen i celle 05 i programmet fra oppgave 11 med inndata 2, og hvor havner verdien 99?
Programmet under skriver ut ett tall. Kryss av alle inndataene som gir utskriften 8.
00 INP
01 STA 40
02 SUB 41
03 BRP 07
04 LDA 40
05 ADD 40
06 BRA 08
07 LDA 40
08 OUT
09 HLT
40 DAT
41 DAT 5a) 4
b) 8
c) 3
d) 5
Programmet under skriver ut ett tall. Kryss av alle inndataene som gir utskriften 10.
00 INP
01 STA 80
02 BRP 06
03 LDA 81
04 SUB 80
05 BRA 07
06 LDA 80
07 ADD 82
08 OUT
09 HLT
80 DAT
81 DAT 0
82 DAT 3a) 7
b) −7
c) 10
d) 13
1. Å slurve med sporetabellen. Én rad per utført instruksjon, ikke per programlinje. Og skriv av verdier også når de er uendret — en tom celle blir til tvil to minutter senere.
2. Å velge feil hoppinstruksjon i fyll-inn. BRZ treffer bare på nøyaktig null; BRP treffer null og alt over. Forskjellen er typisk én runde, og i oppgave 8 var den forskjellen på 8 og 8 6 4 2 0. Test alltid alle alternativene ved å spore.
3. Å glemme selvmodifisering (felle #7). Se etter STA med adresse i kodeområdet. Overser du den, ser sporet ditt helt fornuftig ut — og er feil fra det punktet av.
4. Å oppgi bare én inndata i baklengs sporing. I oppgave 13 og 14 hadde begge oppgavene to riktige svar, fra hver sin gren. Spør alltid: kan denne utskriften nås fra begge grenene?
5. Å overse grenseverdien. Inndataen som ligger nøyaktig på terskelen, er alltid med som alternativ. Regn den ut eksplisitt — BRP hopper også på null.
6. Å ignorere startverdiene i DAT-cellene. En sum som starter på 5 i stedet for 0, forskyver hele svaret med 5. Se oppgave 10.
Begrepsbank til eksamen
Begrepsbanken er flashcard- og repetisjonsstoff — den gjentar det du nettopp har lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet gjelder kjernestoffet.
Standardformen for å bygge opp en sum i LMC: LDA summecellen, ADD det nye leddet, STA tilbake til summecellen.
04 LDA 62 ; hent summen så langt
05 ADD 60 ; legg til neste ledd
06 STA 62 ; lagre den nye summenSummecellen må starte på 0. Starter den på noe annet, forskyves hele svaret med den verdien — se oppgave 10.
Standardformen for en teller: LDA telleren, SUB steget, STA tilbake, og deretter et betinget hopp.
Antall runder avhenger av tre ting: startverdien, steget og hvilken hoppinstruksjon som brukes. Med BRP og steg 1 kjører løkka én gang mer enn startverdien tilsier, fordi null også hopper.
Oppgavetypen der én instruksjon er fjernet, og du skal velge den som får programmet til å gjøre det oppgaven beskriver.
Framgangsmåten: spor fram til den tomme cellen, skriv ned tilstanden der, og spør hvilken instruksjon som tar deg videre til målet.
Test alltid alle alternativene ved å spore ferdig — og med minst to ulike inndata. En instruksjon som gir riktig svar for én inndata, kan bomme for en annen.
Å avgjøre hvor mange ganger en løkke kjøres. Dette er det som oftest testes i sporeoppgaver, fordi det er der intuisjonen bommer.
Metoden: skriv opp verdien telleren har ved hver test, og marker hvor betingelsen slår om. Antall runder er antall verdier der betingelsen fortsatt holdt.
Husk at BRP inkluderer null — det gir én runde mer enn BRZ ville gitt.
Inndataen som gir nøyaktig 0 i testen, og som derfor havner i den «positive» grenen når hoppet er BRP.
Tester programmet med SUB 41 der celle 41 er 5, ligger grensen på inndata 5.
Eksamensoppgavene har nesten alltid ett alternativ nøyaktig på grensen. Regn den ut eksplisitt før du krysser av — det er den enkeltdistraktoren som tar flest.
Cellen der to grener møtes igjen, typisk en OUT som begge veier ender opp i.
Alt som står i den felles fortsettelsen, gjelder for begge grenene. I oppgave 14 var ADD 82 felles, så pluss 3 gjaldt uansett hvilken vei programmet gikk.
Den faste feilen er å tro at instruksjonene etter et grenmønster bare gjelder den ene grenen.
En minnecelle som ikke er nevnt i programmet, men som likevel finnes med startverdien 0.
Alle 100 celler eksisterer alltid. Et selvmodifiserende program kan derfor skrive til celle 32 selv om ingen DAT 32 står i listingen — uten at noe varsles.
Dette er en del av grunnen til at selvmodifiserende kode er vanskelig å feilsøke: det finnes ingen «ugyldig adresse» i LMC.
Vanen med å kontrollere et svar mot minst to, helst tre, ulike inndataverdier før du er fornøyd.
En instruksjon eller en DAT-verdi kan gi riktig svar for det ene tallet oppgaven nevner, og feil for alle andre.
Velg inndataene bevisst: én under grensen, én på grensen, én over. De tre avslører nesten enhver feil i et LMC-program.
De to arbeidsmåtene sjangeren krever.
Framover brukes når inndataen er gitt: før tabell, mekanisk, rad for rad. Ingen tolkning nødvendig.
Bakover brukes når utskriften er gitt: beskriv først hva programmet gjør som helhet, og løs deretter hvilke inndata som gir det resultatet. Å reversere instruksjon for instruksjon virker sjelden.
Vanen med å oppsummere hva et helt program gjør i én setning: «det regner ut absoluttverdien pluss 3», «det ganger de to inndataene», «det teller hvor mange ganger 2 går opp i tallet».
Denne setningen er ofte hele svaret på en flervalgsoppgave, og den er alltid første steg i baklengs sporing.
Skriv den ned før du begynner å teste alternativer — den sparer deg for å spore hvert alternativ for seg.
Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.
Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.