Domein B: Grondslagen

Een gesorteerde lijst bevat 1000 elementen. Bepaal het maximale aantal vergelijkingen dat binair zoeken nodig heeft en vergelijk dat met lineair zoeken.

1. 01Wat doet één stap?

   Binair zoeken vergelijkt de gezochte waarde met het middelste element en gooit daarna de helft van de kandidaten weg. Elke vergelijking halveert dus het zoekgebied.

2. 02Tel de halveringen

   Van 1000 blijven achtereenvolgens over: 500, 250, 125, 63, 32, 16, 8, 4, 2, 1. Na tien halveringen is er nog één element over.

   $$1000 \to 500 \to 250 \to \dots \to 1$$
3. 03Reken met de logaritme

   Het aantal halveringen is naar boven afgerond de tweelog van 1000.

   $$\lceil \log_2 1000 \rceil = \lceil 9{,}97 \rceil = 10$$
4. 04Vergelijk met lineair zoeken

   Lineair zoeken doet in het slechtste geval 1000 vergelijkingen ($O(n)$); binair zoeken maar 10 ($O(\log n)$) — honderd keer minder werk, mits de lijst gesorteerd is.

Resultaat: Binair zoeken heeft maximaal 10 vergelijkingen nodig, tegen 1000 voor lineair zoeken.

Speel bubble sort volledig na op de rij [5, 1, 4, 2, 8] en tel het totale aantal wissels.

1. 01Pass 1

   Vergelijk steeds twee buren: (5,1) wissel → [1,5,4,2,8]; (5,4) wissel → [1,4,5,2,8]; (5,2) wissel → [1,4,2,5,8]; (5,8) geen wissel. Drie wissels; de 8 stond al achteraan.

   $$[5,\,1,\,4,\,2,\,8] \to [1,\,4,\,2,\,5,\,8]$$
2. 02Pass 2

   (1,4) geen wissel; (4,2) wissel → [1,2,4,5,8]; (4,5) geen wissel. Eén wissel deze ronde.

   $$[1,\,4,\,2,\,5,\,8] \to [1,\,2,\,4,\,5,\,8]$$
3. 03Pass 3

   (1,2) en (2,4) geven geen wissel. Nul wissels: dat is het teken dat de rij gesorteerd is, dus we stoppen.

4. 04Tel de wissels

   Tel de wissels van alle passes op. Dat komt overeen met het aantal 'inversies' (paren die verkeerd om staan) in de beginrij.

   $$3 + 1 + 0 = 4$$

Resultaat: De gesorteerde rij is [1, 2, 4, 5, 8], bereikt met 4 wissels.

Voeg de getallen 8, 3, 10, 1, 6, 14, 4, 7, 13 in die volgorde in een lege binaire zoekboom in en beschrijf de ontstane structuur.

1. 01Wortel

   De eerste 8 wordt de wortel. Voor elk volgend getal geldt: kleiner → naar links, groter → naar rechts, net zo lang tot je een lege plek vindt.

2. 023 en 10

   3 < 8 → linkerkind van 8. 10 > 8 → rechterkind van 8.

3. 031 en 6

   1 < 8 (links), 1 < 3 (links) → linkerkind van 3. 6 < 8 (links), 6 > 3 (rechts) → rechterkind van 3.

4. 0414, 4 en 7

   14 > 8, 14 > 10 → rechterkind van 10. 4 < 8, 4 > 3, 4 < 6 → linkerkind van 6. 7 < 8, 7 > 3, 7 > 6 → rechterkind van 6.

5. 0513

   13 > 8, 13 > 10, 13 < 14 → linkerkind van 14.

Resultaat: Je krijgt de boom van Afbeelding 4: wortel 8, met bladeren 1, 4, 7 en 13. Zoeken naar 7 volgt kort de weg 8 → 3 → 6 → 7.

Bepaal met de DFA uit Afbeelding 6 of de string '1101' wordt geaccepteerd. Schrijf alle doorlopen toestanden op.

1. 01Start

   Je begint in de begintoestand q0. De string is 1-1-0-1.

2. 02Lees de eerste 1

   In q0 gaat een 1 via de zelf-lus terug naar q0.

3. 03Lees de tweede 1

   Opnieuw houdt de 1 je in q0.

4. 04Lees de 0

   Nu brengt de 0 je van q0 naar q1: je hebt net een 0 gezien, mogelijk het begin van '01'.

5. 05Lees de laatste 1

   In q1 brengt de 1 je naar q2, de accepterende toestand — je zag '01' aan het eind.

   $$q_0 \to q_0 \to q_0 \to q_1 \to q_2$$
6. 06Controleer de eindtoestand

   De string is op en je bent in q2, dat in F zit. Dus geaccepteerd.

Resultaat: De doorlopen weg is q0 → q0 → q0 → q1 → q2; je eindigt in de accepterende toestand q2, dus '1101' wordt geaccepteerd.

Leid met de regels $E \rightarrow E + T \mid T$, $T \rightarrow T * F \mid F$ en $F \rightarrow$ cijfer de string '3 + 4 * 5' af, en leg uit welke rekenvolgorde de parseboom vastlegt.

1. 01Begin bij het startsymbool

   We starten met E en passen steeds één regel toe tot er alleen cijfers en tekens overblijven. De linker-nonterminal werken we telkens eerst uit.

   $$E \Rightarrow E + T$$
2. 02Werk de linker E uit tot 3

   Kies E → T, dan T → F, dan F → 3.

   $$E + T \Rightarrow T + T \Rightarrow F + T \Rightarrow 3 + T$$
3. 03Werk de rechter term uit tot 4 * 5

   De term T rechts van de + wordt 4 5: kies T → T F en werk beide factoren uit tot cijfers.

   $$T \Rightarrow T * F \Rightarrow F * F \Rightarrow 4 * F \Rightarrow 4 * 5$$
4. 04Lees de betekenis af

   Omdat 4 en 5 samen onder één term T vallen, groepeert de parseboom ze: eerst 4 * 5 = 20, dan 3 + 20 = 23. De grammatica geeft de vermenigvuldiging dus voorrang.

Resultaat: De afleiding vanuit E slaagt en levert 3 + 4 * 5 op, dus de string is geldig; de parseboom (Afb. 7) legt vast dat de uitkomst 23 is, niet 35.

Reken $1101_2$ om naar decimaal en hexadecimaal, en vul de waarheidstabel van $A \land (\overline{B} \lor C)$ in.

1. 01Binair naar decimaal

   Schrijf de plaatswaarden 8, 4, 2, 1 onder de bits en tel de posities met een 1 op.

   $$1101_2 = 8 + 4 + 0 + 1 = 13_{10}$$
2. 02Decimaal naar hexadecimaal

   13 past in één hexcijfer: de waarde 13 heet in hex D. Dus 1101 binair is 0xD.

   $$13_{10} = \text{D}_{16}$$
3. 03Zet de tabel op

   Drie variabelen geven 2³ = 8 rijen. Maak eerst tussenkolommen voor ¬B en ¬B ∨ C, en reken dan de AND met A uit.

4. 04Reken de rijen uit

   De expressie is alleen waar als A = 1 én (¬B ∨ C) waar is. Dat gebeurt in de rijen (A,B,C) = (1,0,0), (1,0,1) en (1,1,1); in alle andere rijen is de uitkomst 0.

   $$A \land (\overline{B} \lor C)$$

Resultaat: Er geldt $1101_2 = 13_{10} = \text{0xD}$; de expressie $A \land (\overline{B} \lor C)$ is waar in 3 van de 8 rijen (zie Afb. 9).