Datatekniske metoder 8251903696 [PDF]

Zitiervorschau

Odd Pettersen

DAT ATEKNfSKE MET ODER

TAPIR 1980

©TAPIR

ISBN 82-519-0369-6

FORORD

Denne bok er skrevet med utgangspunkt i behov for lærebok på et middels nivå ved NTH’s Elektroteknisk avdeling. Stoffvalget er derfor sterkt påvirket av innholdet av faget Datatekniske metoder som følges av en overveiende del av 3årskurs elektrostudenter ved NTH. Som forkunnskaper skulle det være tilstrekkelig med et 2-semesters grunnkurs i databehandling av omfang ca. 2 forelesningstimer pr. uke

samt

øvingsoppgaver,

og

også

helst

litt

etterfølgende

erfaring

i

anvendelse av datamaskin. av norske lærebøker

I betraktning av at utvalget

på dette

nivå

er

meget begrenset, er det imidlertid forfatterens håp at boken vil ha interesse også utenfor NTH's Elektroavdeling. Det finnes en rekke helt elementære lærebøker, men få som går litt videre. Dessuten skiller denne boken seg fra de fleste andre på elementært og middels nivå

ved å behandle generelle prinsipper uten binding til noe bestemt programmeringsspråk. Eksempler må naturligvis uttrykkes i program­ meringsspråk, språk,

e^

språk.

Med

eksempler

forvirres.

dette

understreke uavhengigheten av ett bestemt vekselvis uttrykt i notasjon fra forskjellige

for

men

løper

å

man

naturligvis

Dette er imidlertid

den

risiko

at

leseren

ikke noen lærebok i FORTRAN,

kan

Pascal,

Algol eller noe annet spesifikt programmeringsspråk. Hvis leseren derfor forsøker å få tak i de prinsipper som eksemplene tar sikte på

å vise,

vil

han oppdage at alle

de

vanlige

programmeringsspråk har

visse felles trekk og uttrykker felles programstrukturer. Bare notasjonen er forskjellig. Når mange lærebøker legger sterk vekt på notasjon og språk-syntaks, vil dessverre de almengyldige prinsipper ha lett for å komme i bakgrunnen. Jeg oppfordrer derfor leseren til

å forsøke å ta lett på den umiddelbare forvirring som kan inntreffe

på grunn av at eksemplene er uttrykt i

forskjellige programmerings­

språk. Det er på

forsøkt

fremstiling

strukturert

lagt balansert av

effektive

programmering

både

vekt på strukturert programmering og programmer.

Selv

om

erkjennes

fullt

ut

betydningen

og

av

understrekes

sterkt i boken, har forfatteren en mistanke om at mange programmerere

-VI-

i dag legger så stor vekt på disse i og for seg både gode og nødvendige prinsipper, at de ofte neglisjerer hensynet til at programmer også

skal kjøre effektivt. Det er i dag ålment akseptert at nesten all programmering skal foregå i høynivåspråk. Det er imidlertid lettere å forstå prinsippene for effektive programmer hvis det eksisterer et visst kjennskap til den

underliggende maskinkoden. Med den sterke utbredelse som mikrodata­ maskiner nå holder på å få, er det også blitt mer nødvendig for flere programmerere å kunne skrive rutiner for inn- og utlesning og andre mer maskinrettede operasjoner. Forfatteren mener derfor at alle programmerere som skal gå litt videre bør ha en kort gjennomgåelse

av prinsippene for maskinkode og assemblykoding. Dette er helt nødvendig bakgrunn for å forstå prinsippene for sammenkopling mellom datamaskin og eksternt utstyr, og med en slik bakgrunn blir også en rekke prinsipper uttrykt i høynivåspråk lettere å forstå. Kapittel 2

den bevisste frigjøringen fra et bestemt programmeringsspråk og en bestemt søker

å

fylle

dette

behov.

Det

er

også

i

dette

kapittelet at

datamaskin adskiller seg mest fra det som er vanlig i lærebøker. Det har ofte syntes som om studentene har hatt et for svakt grunnlag i elementær algebra. Selv om betydningen av dette ikke er avgjørende for programmeringsundervisningen , har jeg tatt med en kort gjennom­ gåelse av dette, blant annet for å introdusere og definere en del begrep som brukes i resten av boken. Graf-teorien viktigste del av kapittel 1 ut fra dette hensyn.

er

kanskje

den

Lesere som kjenner min tidligere utgitte bok Sanntidsprogrammering ( [11 ]) vil kjenne igjen noe av kapittel 4. Dette er generelt stoff

som ikke har noen spesiell sammenheng med sanntidsprogrammering men som tidligere ble tatt med der for å styrke bakgrunnen for studenter som studerte Sanntidsprogrammering eller Sanntids datateknikk før undervisningen i datatekniske metoder var startet. Stoffet er nå

kommet "på plass" og vil kunne fjernes fra senere utgaver av [11]. Kapittel 5 om datastrukturer og data-administrering representerer etter forfatterens mening et minimum. Omfanget av dette skulle gjerne

vært langt større. Det later til at hensynet til datastruktur ofte har blitt neglisjert i forhold til programstruktur, mens det kanskje

er

det

viktigste.

Datastrukturens

betydning

øker

imidlertid

med

størrelsen av et datateknisk prosjekt, og siden denne boken tar sikte

på et forholdsvis moderat nivå, kan omfanget av behandlingen kanskje

aksepteres for ikke å gjøre for vanskelig.

boken

for

omfattende og

fremstillingen

-VII-

Det er en rekke tildels forskjellige felter som skulle dekkes i faget Datatekniske metoder og av denne boken. Faren er derfor i høy grad tilstede for at fremstillingen kan bli springende. Jeg håper dette ikke er for sjenerende og at leseren vil vise overbærenhet hvis dette

likevel skulle være mer fremtredende enn ønskelig. Jeg

vil

gjerne

gi

til

honnør

en

rekke

forfattere

som

forfatteren inspirerende lesning under arbeid med boken.

har

gitt

Alle kilder

som bevisst er brukt under arbeidet er referert bak i boken,

men i

som

under

tillegg

stadig

er

det

lesning

naturligvis bidrar

til

en en

mengde mer

litteratur,

annen

ubevisst

bakgrunn.

Blant

den

litteratur som danner en mer bevisst inspirasjon vil jeg gjerne trekke frem en bok skrevet av min venn og tidligere kollega Donald L. Dietmeyer ved University of Wisconsin ([4]). Jeg ble kjent med professor Dietmeyer og hans bok da jeg sommeren 1974 vikarierte for ham og underviste fra denne boken. Jeg takker Don for hans tillatelse til å legge opp behandlingen av aksiomer og teorembevis i kapittelet

om Boolsk algebra etter mønster fra hans bok. Videre vil jeg få takke mine mange medarbeidere ved NTH, Institutt for teknisk kybernetikk og SINTEF avd. Reguleringsteknikk som har

bidratt

på

flere

måter.

Blant

annet

har

Kjell

Hervig

bearbeidet

kapittel 2, Sigurd Lone har som vitenskapelig assistent for meg under det første året kurset har vært holdt bidratt på mange måter med blant annet å oppklare uklarheter. Lars Nesland har laget et program til

hjelp ved fremstilling av stikkordlisten. Det meste av tegnearbeidet er utført av ing. Gunnar Meland ved SINTEF. Nevnes må også de studentene

som

fulgte

faget

i

"introduksjonssemesteret"

våren

1979

og måtte tåle alle ulempene ved å være prøvekluter. For dette kullet

ble boken

først laget som kompendium.

Dette er senere omarbeidet en

del på grunnlag av erfaringer i det første året.

Til slutt skal nevnes at bok-satsen er fremstillet ved Datalaboratoriet ved Institutt for teknisk kybernetikk, ved hjelp av tekst-

behandlings-programmet DIATEXT.

NTH, Trondheim, februar 1980

Odd Pettersen

- VIII -

INNHOLD

side

FORORD

............................................................

Kapittel 1.

LITT MATEMATISK GRUNNLAG .............................

V

1

1.1

Innledning

1.2 1.3 1.4

Mengdelære .................................................. Boolsk algebra ............................................. Relasjon mellom mengdeoperatorer og boolske operatorer ..

18

1.5

Noen trekk fra graf-teorien

21

..................................................

1 1

1.5.1

Begrep og definisjoner

............................

21

1.5.2 1.5.3

Representasjonsformer for grafer ................ Spor-relasjonen ....................................

23 25

1.5.4

Tre-strukturer

Kapittel 2.

2.1

2.2

2.4

....................................

27

MASKTNKODING ..........................................

29

....................................................

29

Oversikt 2.1.1

Maskinkode og assembly-kode

2.1.2

Forskjell fra hoynivå-språk og hensikt

Instruksjonen

...................... ..........

29 29

..............................................

31

................................

31

2.2.2 Symboler og etiketter ............................. Adresseringsformer .........................................

33 34

2.3.1

Umiddelbar adressering

............................

35

2.3.2 2.3.3

Direkte adressering ............................... Indirekte adressering .............................

35 36

2.3.4

Relativ adressering

36

2.3.5 2.3.6

Adressering ved hjelp av Indeks-register ........ Indirekte og indeksert adressering ...............

37 38

2.3.7

Rekursivt indirekte og relativt

..................

40

2.3.8

Dynamisk relokering via register

.................

40

2.2.1 2.3

...............................

Instruksjonsformat

...............................

Hvordan instruksjoner settes sammen til

etprogram

.......

41

2.4.1

En-, to- og flerords instruksjoner

..............

41

2.4.2

Operander av forskjellig ordlengde

..............

42

2.4.3

Pseudo-operasjoner

................................

43

2.4.4

Streng-generering

.................................

44

-X-

2.5

2.6

2.7

2.8 2.9

Litt videregående bruk

.....................................

45

2.5.1 2.5.2

Stakk-lager ........................................ Definerte og udefinerte symboler .................

45 48

2.5.3 2.5.4

Symbolenes spillerom .............................. Redefinering av symboler ..........................

49 50

2.5.5 Registre adressert som hukommelses-elementer .... 51 Symbol-tabeller ............................................. 51 2.6.1 Hvordan assembleren opererer påsymbol-tabellene 51 2.6.2 Organisering av symbol-tabeller .................. 52 Assembly-prosessen ......................................... 2.7.1 Assembling i 2 eller 1 passasjer ................. Laderen ..................................................... 2.8.1 Lenking og lading .................................. Makro-assemblere

Kapittel 3-

3.1

...........................................

GRUNNLEGGENDE PROGRAMMERINGSMETODIKK

Strukturert programmeringog Topp-Ned-metoden

.............. .............

53 53 55 55 56

58

58

3-1.1

Problemspesifiseringog systemplanlegging

.........

59

3.1.2

Oppdeling i moduler. Subrutiner.....................

62

3-2

Valg av løsningsmetode og algoritmer

......................

64

3.3 3.4

Flytskjema .................................................. "Strukturerte" programstrukturer ..........................

65 70

3.5 3.6

Systematisk algoritmebevis ................................ Blokk-diagram ...............................................

76 79

Kapittel 4.

NOEN ALGORITMISKE METODER

..........................

82

4.1 4.2

Valgmekanismer og flaskehalser ............................ Beslutningstabeller ........................................

82 90

4.3

Sekvensstyring , introduksjon

..............................

94

Kombinatoriske og sekvensiellefunksjoner ........ Sekvensfunksjoner .................................

94 94

4.3.3 Huffman-tabell .................................... Tabellstyrt program ........................................

96 99

Søking og sortering ........................................ 4.5.1 Primitiv (lineær) søking ..........................

103 104

4.5.2 4.5.3

Binær søking ....................................... Delvis ordnet tabell ..........................

106 103

4.5.4 4.5.5

Sortering .......................................... Ekstern sortering .................................

103 113

4.3.1 4.3.2

4.4 4.5

4.6

Iterasjon og rekursjon

.....................................

114

-XI -

5.1 5.2

5.3

Oversikt over datarepresentasjon og -administrering Forskjellige elementære datatyper ........................ 5.2.1 Enkle heltall .....................................

5.5 5.6 5.7

123 124

125

5.2.2

Tekst

5.2.3

Dobbelord

..........................................

127

5.2.4 5.2.5

Flytende tall ..................................... Reelle tall påfastkomma-form .....................

128

5.2.6

Erklæringen avdataformer i høynivå-språk

129

5.2.7 Lineære 5.3.1 5.3.2

Pekere ............................................. datastrukturer ..................................... Enkle tabeller ................................... Lenkede lister ..................................... Kø og stakk ........................................ Pakkede tabeller ..................................

5.3.3 5.3.4 5.4

123

DATASTRUKTURER OG DATA-ADMINISTRASJON

Kapittel 5.

..............................................

........

12^

131 131 134

1110 1^2 142 J 144

Tre-strukturer ............................................. . . Fil-organisenng ............................................. Nøkkel-transformasjon ("hash-tabeller") ................. Databaser. Inverterte lister............................... 151

INN - OG UT - LESNING

Kapittel 6.

...............................

1

6.1 6.2 6.3

Oversikt .................................................... Sekvensiell og vilkårlig Inn/Ut-overføring .............. 155 Prosesseringshastighet og avhengighet avInn/Ut-utstyr .. 156

6

4

6.5

Inn/Ut-operasjoner på lavt nivå

6.6

Hvordan Inn/Ut-operasjoner tar seg ut sett fra et

brukerprogram ...........................

6.5.1

Programmert tegn for tegn

6.5.2

Direkte hukommelses-adgang (DMA)

.........................

158 ........... 160 160

..................

162

6.5.3 Avbrudd ............................................. Datatyper og formater ...................................... 6.6.1 Eksterne formater ..................................

1o5 1$7

6.6.2

Interne formater

6.6.3

Litt om standarder, for formater og annet .........

LITTERATURLISTE STIKKORDREGISTER

...................................

17$

171

....................................................

172

...................................................

175

Kapittel

1.1

1.

Litt

matematisk

grunnlag

Innledning

Boolsk algebra er det matematiske grunnlag til beskrivelse av elektroniske koplingselementer og byggeelementer innen datateknikken. De fleste av dere har allerede stiftet bekjentskap med den Boolske algebra, slik at dere vet hva den går ut på. Det kan imidlertid være

forbindelsen bakover til grunnleggende trekk fra algebraen, som også danner grunnlaget for den Boolske algebra, for å kunne forstå de forutsetninger og begrensninger som gjelder.

av interesse å knytte

I kapittel 1.5 vil bli gjennomgått enkelte trekk fra grafteorien. Dette danner grunnlag for noen viktige program- og datastrukturer

behandlet i etterfølgende kapitler.

1.2

Mengdelære (Eng.: The algebra of sets)

En samling av gjenstander, symboler osv. med visse spesifiserte felles særtrekk kan vi kalle en mengde. Disse særtrekkene er av en slik art og slik konsist spesifisert at vi er i stand til å avgjøre om en gjenstand er medlem av mengden eller ikke.

En slik spesifisering kan

for eksempel gå ut på en oppramsing av alle medlemmene av mengden, eller å definere matematisk en regel som angir kriteriet for medlemsskap i mengden.

Eksempler på slike defineringer kan være: "Mengden

A

består av personene

PER PAL ESPEN "

eller: "Mengden

SN

består av alle studenter ved NTH"

eller:

"Mengden

ALF

er samtlige bokstaver i det norske alfabet".

2

Kriteriet på at "definisjonene” foran er tilstrekkelige er at når vi

har et element eller en kandidat for oss, skal vi være i stand til å om vedkommende er medlem av mengden. Oftest er derfor eksempelvis "samtlige bokstaver i det norske alfabet" tilstrekkelig konsist, men om nødvendig kan dette spesifiseres ytterligere, ved listen: avgjøre

ALF = -^ABCDEFGHIJKLMNOPQRSTUVWXYZEOA.

abcdefghijklmnopqrstuvwxyzæøå}-(1.1)

Tilsvarende kan mengden studentfortegnelsen.

SN

Det faktum at en kandidat

x

angis mer eksplisitt ved henvisning til

er medlem av mengden

S

uttrykkes ved:

x E S

(1.2)

Vi sier også at x er et element av S. Hvis kandidaten

y

ikke er et element av

S, uttrykkes dette:

(1.3)

y £ S

Vi kan inkludere kriteriet for medlemsskap i definisjonslikningen:

S =

x |

(1.4)

kriteriumJ>

som leses: "S består av elementene

x

slik at

" .

Eksempel:

SN =

x |

x er en student ved NTHj

(1.5)

Den vertikale streken kan altså leses "slik at”. Likhetstegnet brukes på liknende måte som i aritmetikken, det vil si at P=Q betyr at mengdene P og Q har eksakt samme elementer. Tilsvarende betyr

dette

ikke er tilfelle.

±

at

Vi har ofte behov for å betrakte en mindre

gruppe elementer innen en mengde. En slik gruppe kaller vi en delmengde (eng.: "subset") av den mengden vi startet med. Formelt uttrykkes

dette slik:

B C S

eller

B C S

(1.6)

- 3 -

som forteller at B er en delmengde av S. Forskjellen mellom tegnene C og C ligger i at når C brukes, kan delmengden B også bety S selv, det vil si B=S. TegnetC uttrykker at det finnes elementer av S som ikke er elementer av B. I sistnevnte tilfelle er B en ekte delmengde

av S (eng.: "proper subset of S"). Med andre ord:

B C S

=>

B jf S

(1.7)

Mengden uten elementer kaller vi null-mengden. Denne er delmengde av alle

andre

ytterlighet:

betegnes

mengder

og

Mengden

som alle

med

Den

ø.

symbolet

motsatte

(blant de aktuelle som

andre mengder

betraktes) er delmengder av kalles universalmengden og betegnes

og

Nullmengden

universalmengden

skranker for en vilkårlig mengde

kan

betraktes

som

nedre

og

I. øvre

S , altså (1-8)

0 C SC I

Som et geometrisk bilde av en mengde forestiller man seg ofte elementene som punkter, gjenstander o. 1. plassert i en klynge innen

et avgrenset område på et plan. Dette del-området tegnes gjerne som for eksempel en sirkel, som avgrenser elementene fra de øvrige elementene i universalmengden. For øvrig er elementenes innbyrdes

såvel som formen på grenselinjen, av underordnet betydning. En slik figur kalles et "Venn-diagram" og er hensiktsmessig plassering,

til blant annet å vise

sammenhengen mellom

delmengder. Se eksempler i fig.

Fig.

forskjellige mengder

og

1-1.

1-1: Eksempler på Venn-diagram.

Elementene i en universal-mengde som ikke er komponenter i en mengde

A

tilhører

betegnes

Å

en

mengde

som

kalles

komplementet

til

mengde

A

og

A. Komplementet kan defineres slik:

X |

X

A}

(1-9)

Ethvert medlem av et univers er derfor enten medlem av en mengde eller av A. Komplementet kan også uttrykkes gjennom operatoren —। :

-| (A)

Å =

A

(1.10)

I en universalmengde kan det finnes komponenter som er medlemmer av to mengder A og B. Disse komponentene danner da en mengde C som vi

kaller snittet av A og B. Tilsvarende vil A og B til sammen danne en

mengde

D

som

betegnes

operasjoner som betegnes med nevnte mengdene er: C = A C) B

og

og ”union” er symbolene henholdsvis f og U . For de

unionen

av

A

og

B.

"Snitt”

(1.11)

D = A U B

Unionen av to mengder A og B består altså av de komponenter som er medlemmer av enten A eller B eller begge.

Spesielt er:

og

A H Å =

A U A = I

(1.12)

To mengder som ikke har felles komponenter er gjensidig utelukkende, eller "disjunkt".

Fig. 1-2 illustrerer snitt, union og komplement, diagram.

1-2: Eksempler på snitt, union og komplement.

Fig. Det For

fremstillet i Venn-

kan være verdt å illustrere disse operasjonene med et eksempel. å finne mengder som egner seg til å vise operasjonene bør vi

velge

mengder

som

ikke er delmengder

av

hverandre.

La oss velge

mengder som følger: A: personer som er født i Trondheim B: personer som har arbeidssted i Elektrobygget, NTH

E: personer som er ansatt ved NTH

3

- 5 -

Mengden C = A A B vil da være personer født i Trondheim og har arbeidssted Elektrobygget, mens unionen D = A U B vil omfatte personer som er født i Trondheim eller arbeider i Elektrobygget. Vi

ser straks analogien med "logisk produkt" og "logisk sum", operasjoner i Boolsk algebra og som vi skal behandle spesielt i kap. 1-3Med tilbakeblikk på likning (1.11), får vi dannet de samme mengdene C og D selv om operasjonene snitt og union foretas i omvendt rekkefølge,

siden det er intet i definisjonene av snitt og union som

Vi kan derfor like gjerne skrive:

avhenger av rekkefølgen. C = B A A

(1.13)

D = B U A

og

Dette betyr at disse operasjonene følger den kommutative loven:

A A B = BH A

og

(1.14)

A U B = B U A

Vi kan gå videre og definere to nye mengder:

(1.15)

F = CAEogG = DUE

ut fra mengdene C og D formet i likning (1.13), og en ny mengde E. I likning (1.15) kan vi uttrykke C og D ut fra de mengdene A og B de er dannet av, og får: F = (B A A) A E = B A A A E = B A (A A E)

(1.16)

G=(BUA)UE = BUAUE = BU(AUE)

(1.17)

og

I likningene (1.15) og (1.17) er uttrykkene videreført og komponentene oppført i vilkårlig rekkefølge. Fig. 1-3 illustrerer operasjonene.

Bu AuE

Fig.

1-3:

Snitt

og

union

rekkefølge.

mellom 3 mengder.

Likegyldig operasjons-

Dette viser at operasjonene også er assosiative . Anvendt på eksempelet

foran, er de nye mengdene F og G: F: personer født i Trondheim, ansatt ved NTH. G: personer som enten

er

arbeider

født

i

ved

Elektro

Trondheim,

og

arbeider

er ved

Elektro eller er ansatt ved NTH.

I stedet for å forme

BOA

kan vi finne snittene mellom

F1 = B Cl E,

og deretter danne F = (B Cl E)

Fig.

1-4.

først, og deretter finne snittet med E,

B

og

E

samt mellom

A

og

F2 = A Cl “

E

først: (1.18)

F = F1 0 F2:

Cl (A fl E)

(1.19)

Snitt mellom 3 mengder følger den distributive loven

Med referanse til eksempelet, vil:

F1: personer ved Elektro, ansatt ved NTH F2: personer født i Trondheim, ansatt ved NTH

Tilsvarende gjelder for operasjonen U :

Vi får samme resultat. Dette

indikerer at den distributive loven gjelder. Av likningene ovenfor kan også lett utledes: -i (AUB) = Å^B

(1.20)

= AUB

(1.21)

-! (AClB)

Disse to likningene refereres ofte som "De Morgans teorem".

La oss nå introdusere operasjonen relativ komplement: Komplementet til mengden A relativt til mengden B er:

X = Å n B = «f x |

xØAog xG b}

(1.22)

7

X består altså av de medlemmene av B som ikke er medlemmer av A.

Vi

skriver dette slik: (1.23)

X = B - A

Hvis B er universal-mengden , kan vi sette: (1.24)

X = I - A = A

altså det vanlige komplementet. Mengden X, dannet ved likning (1.23), kalles også differens-mengden. Hvis for eksempel A ={ 1, 2, 3, 5} og B = { 2, 3, 4, 6} , vil A - B = { 1, 5), mens B - A = { 4, 6} .

Antall elementer i en mengde kan være uendelig. Dette gjelder for eksempel '‘mengden av alle reelle tall". Dette kalles en "uendelig

mengde", og tilsvarende kalles en mengde hvor antall elementer ikke er uendelig en "endelig mengde". De mengdene vi så på som eksempler

foran var endelige mengder. Til en mengde er tilknyttet et "kardinal—tall", "størrelsen" av mengden. For en endelig mengde er

som uttrykker kardinaltallet

ganske enkelt antall elementer i mengden. Vi vil for øvrig ikke komme nærmere inn på den formelle definisjon for kardinaltall .

Enda en operasjon vil være nyttig: Cartesisk produkt mellom mengder. La oss anta vi har de to mengdene: A = £a1, a2, a3,

og B =

{ b1, b2, b3,

•••}

Det cartesiske produkt mellom A og B er

.

da definert som mengden som består av alle komponentparene

fra

A

og

to

(ai?

Bj)

B :

Y = A * B = ^(a,b) |

(1.25)

a € A, bG B J

Analogien med matriseoperasjoner er tydelig. Anta for eksempel at

(T2)2 = { (o, 0),

= -£o,

(0,

1}. Da vil ?2 * T2 bli:

1), (1,

0),

(T2)2 er mengden av alle binære par,

(1,

og

1)}

(T2)11

alle binære n-tupler.

Vi vil nå introdusere begrepet potensmengde:

vil være mengden av

- 8 -

Potensmengden av et univers er mengden av alle mulige delmengder som det er mulig å forme av universets komponenter. At dette fort blir et stort sett er åpenbart. Anta for eksempel at I = { 1,2,3,4}. Kardinaltallet er altså 4. Setter vi opp en liste over komponentene i potensmengden, får vi: 50 < 18

" ”

alle disse betingelser samtidig, dvs. de utelukker hverandre.

Det kan meget vel tenkes beslutningstabeller og data hvor ingen, eller flere enn én, regel tilfredsstilles. Hvis flere regler tilfreds­ stilles, men de forer alle til samme aksjon, har beslutningstabellen OVERFLODIGHET. Er aksjonene ikke like, er tabellen TVETYDIG (motstridende).

Tvetydigheten

kan

elimineres

å

ved

fastlegge

en

prioritet, dvs. reglene dominerer over hverandre i en gitt rekkefolge. At

ingen

regel

tilfredsstilles

verdi av datavektoren.

må

ikke

inntreffe

for

noen

tenkbar

Beslutningstabellen er da MANGELFULL. Maskinen

må selvsagt alltid "vite” hva den skal gjøre i et hvert foreliggende tilfelle. Slike situasjoner kan "oppfanges” av en ELLERS-regel som eksempelvis kan gi innholdet 0 i tilhørende kolonner i både maskematrise og betingelsesmatrise. Da vil enhver datavektor gl overensstemmelse. Samtidig må regelen gis laveste prioritet. Hensikts­ messig aksjon kan være en passende feilutskrift.

rikholdig litteratur som blant annet ganske utførlig behandler spørsmålet om gunstigste rekkefølge for test av datavektoren mot reglene. Se for eksempel [i 3j , kap. 5.10 - 5.11. Det

finnes

Med Beslutningstabeller kan blant annet oppnås følgende: 1. 2.

Logikken fremtrer presist og på kompakt form. Kompliserte tilfeller blir oversiktlig fremstilt.

3.

Tydelig relasjon mellom variable.

4.

Forenklet programmering.

5.

Enkel og oversiktlig dokumentasjon.

6.

Overflødighet, tvetydighet og mangelfull tabell avsløres lett.

Se også kapittel 4.3Beslutningstabeller er behandlet utførlig i litteraturen, blant annet i [13], [22], [23] og [24],

- 94 -

Sekvensstyring, introduksjon.

4.3

4.3.1

Kombinatoriske og sekvensielle funksjoner.

Logikkstyring opererer på logiske (boolske) variable. De variable er gjerne binære, dvs. de kan innta en av to mulige verdier.

(fri variable)

Logiske inn-variable

inngår i logiske funksjoner som

logiske ut-variable. Inn-størrelsene kan være innleste signaler fra prosess, operatørpult og liknende, eller de kan dannes i programmet fra operasjoner på kontinuerlige variable i systemet. genererer

Eksempel: b1: = x1 prosessvariable .

x2

-

>

2;

x2

og

x1

hvor

er

kontinuerlige

Tilsvarende, kan beregnede funksjonsverdier bli utlest til prosess eller operatørpult som binært pådrag, eller de kan benyttes internt

i programmet. Det kan være naturlig å skille mellom:

i) Kombinatoriske funksjoner og ii) Sekvensielle funksjoner.

Kombinatoriske funksjoner er boolske funksjoner hvor funksjonsverdien er entydig bestemt av de øyeblikkelige verdier av de boolske inngangsdata. Kombinatoriske funksjoner blir ikke behandlet videre her. Sekvensielle funksjoner avhenger av kombinasjoner av boolske inn­

data

og

forhistorie.

øyeblikkelige

Vi

tilstander.

at tidligere forhistorien

Forhistorien

diskrete forsøker

kan

og

imidlertid

å

kanskje formulere

inngår i karakteriseres bare

tilstander

av

karakteriseres

tilstand,

ikke

også

tidligere slik

systemmodellen

beskrivelsen.

av

funksjonens

av

systemets

hvor øyeblikkelige

Systemer

tilstand kalles Markovsystemer. Endring av tilstand forårsakes av en diskret hendelse (eng.: "discrete event"). En diskret hendelse skjer

momentant, diskrete verdier.

4.3.2

Av

ideelt

betraktet.

forandringer

av

Eksempler

signalverdier,

på

som

diskrete

hendelser

forandring

av

er

binære

Sekvensfunksjoner.

sekvensfunksjoner

har

vi

rene

prosessbetingede

sekvenser,

tids-

sekvenser og blandinger av disse. Ved rene prosessbetingede sekvenser er bare signaler fra prosessen bestemmende for overgang til en annen

- 95

tilstand.

Ved

tidspunkt,

ikke

tidssekvenser nødvendigvis

skjer

overgang

ved

Dette

ekvidistante.

forutbestemte

kan

illustreres

slik:

Tilstand nr. :

Fig. Ved

1

4.

2

3

1

3

Illustrasjon av tidssekvens.

4-5.

blandet

sekvens

4

2

og

sekvenstype

endre

kan

denne,

prosess-signaler

eller

forskjellige

bryte

inn

i

en

undersekvenser

tids­

kan

innkoples ved forskjellige tidspunkt. Generelle formuleringer for sekvensielle forløp er gitt av blant andre Mealy og Moore. Vi skal her se ganske kort pa Mealy’s formulering.

En sekvensiell prosess kan beskrives ved: 1.

Et endelig sett Q interne tilstander.

2. 3.

Et endelig sett P innganger. Et endelig sett W utganger (ut-signaler).

4.

Tilstandsforandring T fra qm til qn

5.

Utgangstransformasjon (x) fra qm

Fig.

4-6.

hvor q€ Q

til w hvor w €

Illustrasjon av tilstandsforandringer og tilhørende aksjoner.

Q

- 96 -

De nevnte "innganger” kan være kombinasjoner av logiske inn-signaler. Dette innebærer at prosessen vil gå over fra en tilstand til en annen

som folge av inn-signaler. Tilstandsovergangen ledsages av en aksjon, karakterisert ved dannelsen av utgangssignaler. Q og inngang pi £ p, vil transformasjonen

For en gitt tilstand q^ £ T

definere neste tilstand: 9S = T (qj,Pi) € Q

Transformasjonen

(4.2-1)

definerer utgangssignalene:

CO

w =(jL)(qj,Pi) £ W

(4.2-2)

Tilstander og transformasjonene T og CO kan illustreres med figur 4-6. Overgang mellom de aktuelle tilstander, med derav følgende utlesning

av utgangssignaler, kan oppstilles i forskjellige former for .LLLstands_tabel_ler. Tilstandstabeller er hensiktsmessige for system­ atisk og oversiktlig behandling under programmeringen, og programmet

kan hensiktsmessig arbeide direkte på disse tabeller. Vi skal nedenfor se på noen viktige former for tilstandstabeller.

4.3.3

Huffman-tabell.

En av de viktigste typer sekvenstabeller er Huffman-tabellen,

i alle

fall fra et teoretisk synspunkt. Huffman-tabellen uttrykker direkte teorien for tilstandstransformasjon, gitt foran.

meget

En Huffman-tabell fremstilles som en tre-dimensjonal matrise med n*m*2 elementer,

elementer

n=antall

hvor k

=

1

,

2

for

tilstander hver

og

verdi

m=antall i,

j

innganger.

(i

(Si, P)

then

B

if

Eksempel: P(n) = if

B

then

P)

n>0

then

(Si5 P(n-D)

eller: P(n) = (Si, jf

n>0

N. Wirth gir i

noen enkle eksempler på rekursive prosedyrekall.

05]

then

P(n-D)

For eksempel kan beregning av fakultet beskrives slik: p =_ jf

Kn

I:=0;

F:=1;

then (I:=I+1; F:=I*F; P) P

hvor prosedyren P kan uttrykkes som følger,

skrevet i Pascal.

procedure P begin if Kn then begin I:=1+1; F:=I*F; P

end

end eller, som en funksjon: function F(I:integer): integer; begin if I>0 then F:=I*F(I-1)

else

F:=1

end For

fakultet-beregning

adskillig enklere:

g.jør

en

enkel

iteras jon

samme

nytten,

og

116

I:=0;

F: = 1;

while

Kn

do

I:=I+1; F:=I*F;

begin

end

Følgelig kan den generelle rekursjons-algoritmen som ble presentert ovenfor: P =. if eller:

then

B

P = (Si, jf

B

(S^, P) P)

then

omskrives til iterasjon:

P = (X:=XQ;

while

B

do

S)

Konklusjonen på dette blir:

Unngå rekursjon hvis det finnes en naturlig måte å løse problemet på ved hjelp av iterasjon.

Det

kan vises

at

enhver

løsning basert

til iterasjon. Rent umiddelbart komplisert å forstå enn iterasjon. Hvorfor i det hele bry seg med

på

rekursjon

kan

omskrives

virker kanskje rekursjon mer Det er da nærliggende å spørre:

rekursjon,

når iterasjon alltid kan

brukes i stedet, og iterasjon også er enklere å forstå ? Svaret på dette er at det er en del problemtyper hvor løsning faller

mer naturlig ved hjelp av rekursjon enn iterasjon. En viktig kategori av disse løsninger kan fremstilles som vandring i en trestruktur. Det startes med roten og vandres utover,

etter et søkekriterium som

er slik at det ved et knutepunkt kan vise seg at vi har gått for langt og må søke et antall trinn tilbake for så å velge en annen gren.

Metoden kan kalles "tilbakesporing"

(eng.

"back-tracking" )

og

benyttes blant annet i noen sorteringsmetoder og i kompilatorer.

Det er intet i vegen for å løse et slikt problem med iterasjon, samt for eksempel en stakk til lagring av det sporet som er fulgt utover i trestrukturen. Stakken egner seg godt for dette, fordi vi alltid tar ut igjen det elementet som sist ble plassert, og dette avspeiler den måten vi må følge et spor tilbake i trestrukturen på. Imidlertid

er det enda enklere ved hjelp av rekursjon, som eksempelet nedenfor vil vise, årsaken til dette ligger i at vi utnytter en automatisk stakk-mekanisme i systemet når vi kaller subrutiner rekursivt.

117

Følgende problem er utførlig beskrevet i

[27] :

Anta at en viss behandling av knutepunktene i et binært tre skal foregå

i rekkefølgen

Venstre sønn - far - høyre sønn. En slik ordning kalles

”Inn-ordning". Numrene i denne rekkefølgen kalles innordnings-nummer,

slik at for det enkle basis-treet i fig. 1-13 er innordnings-numrene for knutepunktene venstre sønn - far - høyre sønn henholdsvis 1, 2

og 3. Tilsvarende er det i fig. 4-12 knutepunktene 8 - 4 - 9 som er tilordnet de første innordningsnumrene , altså 1, 2 og 3- Disse tre knutepunktene er et elementært "sub-tre" innen hele treet i fig. 412 og utgjør venstre sønn til knutepunkt 2. Etter regelen skal derfor "far", altså knutepunkt 2 tildeles neste innordningsnummer, altså 4.

Etter dette kommer høyre sønn av knutepunkt 2, og dette er sub-treet -|0 _ 5 _ 11.

Dette behandles først separat,

altså vil knutepunkt

10

tildeles neste innordningsnummer som er 5- Deretter kommer knutepunkt 10’s far som er nr. 5, og dette tildeles innordningsnummer 6 som er

det neste i rekken. Slik fortsettes, med å betrakte enhver sønn som ikke er blad som et subtre, i en hierarkisk oppdeling, eller en slags nivåer. Uten å gå nærmere inn på aktuelle operasjoner som skal

foregå etter

denne ordningen, kan vi her konsentrere oss om det isolerte problemet å finne innordningen for et gitt binært tre. Treet trenger ikke å være fullstendig. Et eksempel på et slikt tre kan være fig. 4-12:

Fig.

4-12. Eksempel på ikke-fullstendig binært tre.

For treet i fig. 4-12 er knutepunktene gitt tilfeldige nummer. Inn­ ordningen for dette treet vil være, referert til knutepunktenes nummer:

8-4-9-2-10-5

11

1

12-6-3-7

118 -

Blant

mange

mulige

representasjonsmåter

for

trestrukturer

i

et

datamaskinprogram er følgende meget brukt for binære trær: I

to

heltall-arrayer

VSON

og

HSON

er

indeksen

knyttet

til

knutepunktnumrene. Innholdet i hvert element er knutepunktnumrene for henholdsvis venstre og høyre sønn. Hvis vedkommende sønn mangler, inneholder elementet verdien 0. For treet i fig. 4-12 vil de to

arrayene ha følgende innhold: VSON(1):

2

HSONd):

3

VSON(2):

HS0N(2):

5 7

VSON(3):

4 6

VS0NC4) :

8

HS0N(3): HS0N(4):

VSON(5) :

10

HS0N(5) :

9 11

VSON(6) : VS0N(7) :

12 0

HS0N(6): HS0NC7):

0 0

VSON(8):

0

HS0N(8):

VSON(9) : VSONdO) : VSONd 1) : VSON(1 2) :

0 0 0 0

HSON(9): HSONdO): HSONd 1) :

0 0 0

HSONd 2):

0 0

Vi gir oss nå som oppgave å lage en algoritme som beregner innordningsnumrene for knutepunktene i et binært tre, definert ved hjelp av de to arrayene VSON og HSON. En program-modul som arbeider på grunnlag

av algoritmen skal levere innordningen i et tredje array, NUMMER, hvor elementenes nummer svarer til knutepunktnumrene, i likhet med

arrayene VSON og HSON. Arrayelement NUMMER(i) innordningsnummeret for knutepunkt nr. i. For eksempelet innholdet:

NUMMER(1):

8

NUMMER(2): NUMMER(3): NUMMER(4): NUMMER(5):

4 11 2 5

NUMMER(6):

10

NUMMER(7): NUMMER(B):

12 1

NUMMER(9):

3

NUMMER(10):

5

i

fig.

4-12

skal

algoritmen

skal

altså

resultere

inneholde

i

array-

119 -

NUMMER(H):

7

NUMMER(12):

9

Følgende ALGOL-prosedyre og program løser problemet ved hjelp av rekursjon. Det benyttes en global variabel COUNT, som puogrammet

initialiserer til

1:

procedure INORDER(KNUTE);

begin if VSON [KNUTE]

f 0 then INORDER(VSON [KNUTE] ) ;

:= COUNT;

NUMMER [KNUTE]

COUNT := COUNT+1; if HSON [KNUTE] 4 0 then INORDER(HSON [KNUTE] ) ; end;

og programmet kan skrives: begin COUNT: = 1 ; comment rot

INORDER(1); end;

Den store fordelen en rekursiv algoritme gir i dette tilfelle er at vi ikke trenger bekymre oss om representeringen av det sporet vi følger gjennom

treet.

generelle

Dette

blir

stakk-mekanisme

tatt

som

er

hånd

om

automatisk,

nødvendig

for

av

maskinens

realisering

av

de

rekursive prosedyrekallene. Hvis vi ikke skulle benytte oss av rekursive prosedyrekall, ville vi måtte administrere stakken selv i

vårt program, og en iterativ algoritme på dette grunnlag kunne for eksempel bli som programavsnittet øverst på neste side, hentet fra [27],

øvingsoppgave : Gå gjennom

de

to algoritmene,

med

det

gitte

treet representert

ved arrayene VSON og HSON. Førsøk om du kommer til samme innhold av arrayet NUMMER som vist ovenfor. Tenk til slutt gjennom hvilken av algoritmene du

synes er enklest å

syneg enklest å bevise ?

forstå.

Hvilken

algoritme

- 120 -

begin

COUNT := 1; KNUTE := 1; V:

comment rot;

STAKK := 0; comment tom; while VSON [KNUTE] f 0 do begin

PUSH(KNUTE); KNUTE := VSON [KNUTE] C:

end ; NUMMER [KNUTE]

:= COUNT;

COUNT := COUNT+1; if HSON [KNUTE] } 0 then begin KNUTE := HSON [KNUTE] ; go to V end; if STAKK } 0 then

begin

KNUTE := POP; go to C

end

end;

eksempel

Neste

sorteringsmetode,

er

også

hentet

"Haug-sortering"

[27] •

fra

(eng.:

Det

illustrerer

"heap-sorting”) ,

en

løst ved

hjelp av rekursjon.

En "haug" er i denne sammenheng et binært tre arrangert slik innholdet av hvert knutepunkt er større enn innholdet i de

at to

etterfølgerne. Haug-sortering baserer seg på at elementene som skal sorteres arrangeres i en slik "haug". Gjennom systematisk ombytting av elementer og løsrivelse fra treet fremkommer til slutt datamengden

sortert. Treet minker etter hvert og degenererer til slutt til 0 elementer, idet roten inneholder det siste elementet som forsvinner idet det minste elementet føyes til mengden av de sorterte elementene.

Vi lagrer datamengden i et lineært array A [i] med 1