Samenvattingen · InformaticaNL · VWO

Keuze G: Algoritmiek, berekenbaarheid en logica

Dit keuzethema verdiept de grondslagen tot hun theoretische kern: hoe meet je de efficiëntie van een algoritme (complexiteit en O-notatie, P versus NP), wat kan een computer principieel wél en niet berekenen (de turingmachine en het onbeslisbare haltingsprobleem), en hoe redeneer je exact met propositie- en predicatenlogica (waarheidstabellen, geldige argumenten). Het is verdieping binnen het schoolexamen, geen ‘buiten-het-examen’-stof.

4 Onderdelen~14 min leestijd4 VaardighedenNiveau Standaard 2 · Verdieping 2

T·0777 / 18

Examenprofiel

G · De tijd- en ruimtecomplexiteit van een algoritme bepalen en met O-notatie beschrijven; P versus NPG · Berekenbaarheid: de turingmachine en de onbeslisbaarheid van het haltingsprobleemG · Propositielogica: waarheidstabellen, logische equivalenties en geldige argumentenG · Predicatenlogica: kwantoren en redeneren

Operatoren:bepaaltoon aanberedeneervul invergelijk

basisniveau

O-notatie en waarheidstabellen zijn de kern van dit thema en sluiten aan op domein B (algoritmen).

verhoogd niveau

P versus NP en de onbeslisbaarheid van het haltingsprobleem raken de diepste grenzen van wat berekenbaar is.

Diepte

Tekst

Inhoud · 4 onderdelen

Keuze G: Algoritmiek, berekenbaarheid en logica

Complexiteit en O-notatie#

Standaardexamenblad-informatica-G

Complexiteit meet hoeveel werk een algoritme kost als functie van de invoergrootte

n

: de tijdcomplexiteit (aantal stappen) en de ruimtecomplexiteit (geheugengebruik). Omdat de exacte stapaantallen van machine en implementatie afhangen, kijk je naar de groeiorde: hoe schaalt het werk als

n

groot wordt? Afb. 1 toont de belangrijkste groeikrommen. Een algoritme dat bij verdubbeling van

n

ongeveer verdubbelt in werk gedraagt zich heel anders dan één dat verviervoudigt — en dat verschil, niet de constante voorfactor, bepaalt of het bij grote invoer bruikbaar blijft.

Groeikrommen van complexiteitsklassen

Afb. 1Afb. 1 — Dezelfde invoergroei, sterk verschillende werkgroei: de klasse bepaalt de bruikbaarheid bij grote n.

De O-notatie (grote-O) vat die groeiorde samen door constanten en lagere-orde-termen weg te laten:

3n^2 + 5n + 7

is gewoon

O(n^2)

, want bij grote

n

domineert de

n^2

-term. Je leest

O(f(n))

als ‘groeit hooguit zo snel als

f(n)

’. De vertrouwde klassen, van gunstig naar ongunstig:

O(1)

(constant — even snel ongeacht

n

O(\log n)

(logaritmisch — binair zoeken),

O(n)

(lineair — één keer doorlopen),

O(n\log n)

(goede sorteeralgoritmen),

O(n^2)

(kwadratisch — geneste lussen, eenvoudige sorteringen) en

O(2^n)

(exponentieel — alle deelverzamelingen aflopen).

Je bepaalt de complexiteit door de dominante bewerking te tellen. Eén lus over

n

elementen is

O(n)

; twee geneste lussen die elk tot

n

lopen geven

n \times n = O(n^2)

; halveren van de zoekruimte per stap geeft

O(\log n)

. Het onderscheid tussen

O(n)

O(n^2)

is enorm: bij een miljoen elementen is dat het verschil tussen een miljoen en duizend miljard bewerkingen — seconden tegenover jaren. Vaak analyseer je het slechtste geval (de ongunstigste invoer), omdat dat een garantie geeft; soms ook het gemiddelde geval.

Het exponentiële

O(2^n)

markeert de grens van het praktisch haalbare: bij

n = 60

2^n

al groter dan het aantal seconden sinds de oerknal. Sommige problemen (zoals het optimaal inplannen of het handelsreizigersprobleem) kennen we alleen met zulke trage algoritmen. Dat leidt tot de beroemde open vraag P versus NP: is elk probleem waarvan je een gevonden oplossing snel kunt controleren (NP), ook snel op te lossen (P)? Vrijwel iedereen vermoedt van niet (

P \neq NP

), maar bewezen is het niet — het is een van de grootste onopgeloste vragen in de wiskunde en informatica.

O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n)

Complexiteitsklassen van gunstig naar ongunstig

Elke klasse groeit sneller dan de vorige naarmate n toeneemt.

Uitgewerkt voorbeeld

Complexiteit van geneste lussen

Bepaal de tijdcomplexiteit van een algoritme dat met twee geneste lussen elk paar elementen uit een array van lengte n één keer vergelijkt.

Buitenlus
De buitenlus draait n keer (voor elk element).
Binnenlus
Voor elke ronde van de buitenlus draait de binnenlus in de orde van n keer.
Vermenigvuldigen
Totaal aantal vergelijkingen is in de orde van n × n = n².
$n \times n = n^2 \;\Rightarrow\; O(n^2)$

Resultaat: Het algoritme is O(n²): bij tien keer zoveel elementen honderd keer zoveel werk.

Veelgemaakte fouten

Constanten en lagere-orde-termen meenemen in de O-notatie; $3n^2 + 100n$ is gewoon $O(n^2)$ , niet $O(3n^2 + 100n)$ .
Twee geneste lussen als $O(2n)$ tellen; ze geven $n \times n = O(n^2)$ , want de binnenlus draait volledig voor elke ronde van de buitenlus.

Actieve herhaling

Bepaal de tijdcomplexiteit in O-notatie van: (a) een lus die elk element van een array van lengte n één keer optelt; (b) twee geneste lussen die elk element met elk ander element vergelijken; (c) binair zoeken in een gesorteerde array van n elementen.

Actief ophalen

Haal de kernpunten op — onthul ze daarna.

Bronnen: Examenprogramma informatica vwo — keuze G (complexiteit) (CvTE / Examenblad)

Berekenbaarheid: turingmachine en haltingsprobleem#

Verdiepingexamenblad-informatica-G

De turingmachine

Afb. 2Afb. 1 — De turingmachine: een oneindige band, een lees-/schrijfkop en een besturing met eindig veel toestanden.

Complexiteit vraagt hoe snel; berekenbaarheid vraagt de diepere vraag of het überhaupt kan. Om die precies te stellen, bedacht Alan Turing een uiterst eenvoudig maar universeel model: de turingmachine. Afb. 1 toont haar onderdelen: een oneindig lange band verdeeld in vakjes (het geheugen), een lees-/schrijfkop die één vakje tegelijk leest en beschrijft en naar links of rechts schuift, en een besturing met een eindig aantal toestanden die per gelezen symbool bepaalt wat te schrijven, welke kant op te bewegen en naar welke toestand te gaan. Meer heeft een computer in de kern niet nodig.

Hoe primitief ook, de turingmachine is maximaal krachtig: alles wat een moderne computer kan uitrekenen, kan een turingmachine ook (de these van Church-Turing). Ze is daarmee de wiskundige definitie van ‘berekenbaar’ geworden: een probleem heet berekenbaar (of beslisbaar, bij ja/nee-vragen) als er een turingmachine bestaat die het voor elke invoer oplost en altijd stopt. Een universele turingmachine kan bovendien een beschrijving van een andere turingmachine als invoer lezen en die nabootsen — precies het stored-program-principe uit domein E, en het theoretische fundament onder de programmeerbare computer.

Turings verrassende ontdekking is dat sommige goedgedefinieerde problemen onberekenbaar zijn — geen enkel algoritme kan ze oplossen, hoe krachtig de computer ook. Het beroemdste is het haltingsprobleem: bestaat er een algoritme dat voor élk programma met élke invoer beslist of het ooit stopt of eeuwig doorloopt? Turing bewees van niet. De redenering is een diagonaalargument: stel dat zo’n haltbeslisser H bestaat, bouw dan een programma dat H op zichzelf toepast en juist het tegenovergestelde doet — dat leidt tot een tegenspraak, dus H kan niet bestaan.

Onberekenbaarheid is geen theoretische curiositeit. Veel praktische vragen — ‘bevat dit programma een virus?’, ‘is deze code equivalent aan die?’, ‘stopt deze berekening ooit?’ — zijn in het algemeen onbeslisbaar, wat verklaart waarom antivirus- en analysehulpmiddelen altijd met benaderingen en heuristieken werken en nooit perfect kunnen zijn. Berekenbaarheid trekt zo een principiële grens: naast wat traag is (exponentiële complexiteit) is er ook wat onmogelijk is, hoeveel tijd en geheugen je ook hebt. Dat besef hoort tot de kern van de informatica als wetenschap.

Uitgewerkt voorbeeld

Waarom de haltbeslisser niet kan bestaan

Toon met een tegenspraak aan dat er geen programma H bestaat dat voor elk programma P en invoer x beslist of P(x) stopt.

Aanname
Stel H bestaat en zegt correct ‘stopt’ of ‘stopt niet’ voor elke P en x.
Bouw een tegenprogramma
Maak een programma T dat op invoer P vraagt aan H of P(P) stopt; als H ‘stopt’ zegt, gaat T juist eeuwig door, zegt H ‘stopt niet’, dan stopt T meteen.
Pas T op zichzelf toe
Beschouw T(T): stopt T(T), dan doet T juist het tegenovergestelde en stopt niet — en omgekeerd. Beide gevallen leiden tot een tegenspraak.

Resultaat: De aanname dat H bestaat leidt tot een tegenspraak; dus geen enkel algoritme kan het haltingsprobleem in het algemeen oplossen.

Veelgemaakte fouten

‘Onberekenbaar’ verwarren met ‘te traag om te berekenen’; het haltingsprobleem is niet langzaam op te lossen maar principieel onoplosbaar door welk algoritme dan ook.
Denken dat een krachtigere of snellere computer het haltingsprobleem wél zou kunnen oplossen; de onbeslisbaarheid is onafhankelijk van rekenkracht.

Actieve herhaling

Leg in eigen woorden uit waarom er geen algoritme kan bestaan dat voor elk programma beslist of het stopt. Schets de kern van het diagonaalargument (een programma dat de veronderstelde haltbeslisser op zichzelf toepast).

Actief ophalen

Haal de kernpunten op — onthul ze daarna.

Bronnen: Examenprogramma informatica vwo — keuze G (berekenbaarheid) (CvTE / Examenblad)

Propositielogica en waarheidstabellen#

Standaardexamenblad-informatica-G

Waarheidstabel voor twee proposities

Afb. 3Afb. 1 — De waarheidstabel (1 = waar, 0 = onwaar) definieert elke operator ondubbelzinnig; let op de implicatie in de laatste kolom.

Propositielogica rekent met beweringen die waar of onwaar zijn (proposities), verbonden door logische operatoren. De basis: en (

\land

, alleen waar als beide waar zijn), of (

\lor

, waar als minstens één waar is), niet (

\lnot

, keert de waarde om) en de implicatie (

\to

, ‘als … dan …’). Deze logica is het skelet onder elke selectie in code (domein D) en onder elke digitale schakeling (keuze K): een `als`-voorwaarde ís een propositie, en een logische poort ís een operator in silicium.

De betekenis van een samengestelde uitdrukking leg je uit in een waarheidstabel: je somt alle mogelijke combinaties van waar (1) en onwaar (0) voor de proposities op en berekent per rij de uitkomst. Afb. 1 toont de tabel voor twee proposities

p

q

. Met

k

proposities heeft de tabel

2^k

rijen — dezelfde

2^n

-explosie als bij de bits in domein C. De waarheidstabel is de definitieve, ondubbelzinnige definitie van een operator: hij laat voor elke situatie precies zien wat de uitkomst is.

Let bijzonder op de implicatie

p \to q

, de grootste struikelblok. Ze is alleen onwaar als

p

waar is maar

q

onwaar; in alle andere gevallen waar — óók als

p

onwaar is (‘als de maan van kaas is, dan …’ is altijd waar, ongeacht het vervolg). Dit heet de ‘lege waarheid’. Verder is

p \to q

níet hetzelfde als

q \to p

: uit ‘als het regent, is de straat nat’ volgt niet ‘als de straat nat is, regent het’ (hij kan ook gesproeid zijn). Deze fout — de omkering voor gelijkwaardig houden — is een klassieke redeneerfout.

Twee uitdrukkingen zijn logisch equivalent als hun waarheidstabellen exact gelijk zijn. Nuttige equivalenties zijn de wetten van De Morgan:

\lnot(p \land q)

is gelijk aan

\lnot p \lor \lnot q

, en

\lnot(p \lor q)

aan

\lnot p \land \lnot q

— een ontkenning verdeelt over de operanden en klapt

\land

\lor

om. Ze zijn in de praktijk onmisbaar: bij het vereenvoudigen van ingewikkelde `als`-voorwaarden in code, bij het optimaliseren van digitale schakelingen, en bij het correct ontkennen van een bewering. Wie logica beheerst, schrijft heldere voorwaarden en vermijdt subtiele redeneerfouten.

\lnot(p \land q) \;\equiv\; \lnot p \lor \lnot q \qquad \lnot(p \lor q) \;\equiv\; \lnot p \land \lnot q

Wetten van De Morgan

De ontkenning verdeelt over de operanden en wisselt en/of om.

Uitgewerkt voorbeeld

Een equivalentie bewijzen met een waarheidstabel

Toon met een waarheidstabel aan dat $\lnot p \lor q$ equivalent is met $p \to q$ .

p en q beide waar
¬p = 0, dus ¬p ∨ q = 0 ∨ 1 = 1. En p → q = 1. Gelijk.
p waar, q onwaar
¬p ∨ q = 0 ∨ 0 = 0. En p → q = 0. Gelijk.
p onwaar (beide rijen)
¬p = 1, dus ¬p ∨ q = 1 in beide gevallen. En p → q = 1 als p onwaar. Gelijk.

Resultaat: In alle vier de rijen komen de uitkomsten overeen; dus $\lnot p \lor q \equiv p \to q$ — een implicatie is een verkapte of-uitdrukking.

Veelgemaakte fouten

De implicatie $p \to q$ gelijkstellen aan haar omkering $q \to p$ ; ‘als het regent is de straat nat’ betekent niet ‘als de straat nat is, regent het’.
Bij het ontkennen van $p \land q$ vergeten de operator om te klappen; $\lnot(p \land q)$ is $\lnot p \lor \lnot q$ (De Morgan), niet $\lnot p \land \lnot q$ .

Actieve herhaling

Stel de volledige waarheidstabel op van de uitdrukking $\lnot p \lor q$ en toon aan dat die logisch equivalent is met de implicatie $p \to q$ .

Actief ophalen

Haal de kernpunten op — onthul ze daarna.

Bronnen: Examenprogramma informatica vwo — keuze G (logica) (CvTE / Examenblad)

Predicatenlogica en redeneren#

Verdiepingexamenblad-informatica-G

Modus ponens

Afb. 4Afb. 1 — Modus ponens: uit ‘als p dan q’ en ‘p’ volgt met zekerheid de conclusie ‘q’.

Propositielogica behandelt hele beweringen als één blok, maar kan niet over ‘alle’ of ‘sommige’ dingen praten. Daarvoor is predicatenlogica. Een predicaat is een eigenschap of relatie met een variabele, bijvoorbeeld

P(x)

= ‘

x

is priem’; ingevuld wordt het waar of onwaar. Met kwantoren zeg je over hoeveel het gaat: de aluitspraak

\forall x\, P(x)

(‘voor alle

x

geldt

P

’) en de bestaanuitspraak

\exists x\, P(x)

(‘er is een

x

waarvoor

P

geldt’). Zo druk je precies uit wat in gewone taal vaag blijft — onmisbaar om de specificatie van een programma exact vast te leggen.

Kwantoren ontkennen vraagt zorg. De ontkenning van ‘alle zwanen zijn wit’ (

\forall x\,W(x)

) is níet ‘geen enkele zwaan is wit’, maar ‘er bestaat een zwaan die niet wit is’ (

\exists x\,\lnot W(x)

) — één tegenvoorbeeld volstaat. Omgekeerd is de ontkenning van

\exists x\,P(x)

juist

\forall x\,\lnot P(x)

. Deze regel — bij ontkennen wisselt

\forall

met

\exists

en gaat de ontkenning naar binnen — is de predicaten-versie van De Morgan en cruciaal bij het opstellen en weerleggen van beweringen over gegevens.

Logica dient het geldig redeneren: uit ware premissen sluitende conclusies trekken. Een argument is geldig als de conclusie noodzakelijk uit de premissen volgt, ongeacht of de premissen feitelijk waar zijn. Afb. 1 toont modus ponens, de meest gebruikte geldige vorm: uit ‘als

p

dan

q

’ en ‘

p

’ volgt met zekerheid ‘

q

’. Een geldige tegenhanger is modus tollens: uit ‘als

p

dan

q

’ en ‘niet

q

’ volgt ‘niet

p

’. Deze vormen zijn de bouwstenen van elk sluitend bewijs en van elke correcte reeks `als`-beslissingen.

Even belangrijk is het herkennen van ongeldige redeneringen (drogredenen). Twee klassiekers: het bevestigen van de consequent — uit ‘als

p

dan

q

’ en ‘

q

’ concluderen ‘

p

’ (fout: de straat kan nat zijn zonder regen) — en het ontkennen van de antecedent — uit ‘als

p

dan

q

’ en ‘niet

p

’ concluderen ‘niet

q

’ (fout om dezelfde reden). Ze lijken op modus ponens en tollens maar zijn ongeldig. Dit onderscheid is geen woordenspel: een programma dat een ongeldige gevolgtrekking maakt, trekt verkeerde conclusies uit correcte gegevens. Exacte logica is daarmee net zo goed een informatica- als een filosofievaardigheid.

Uitgewerkt voorbeeld

Geldig of drogreden?

Uit ‘als het regent, is de straat nat’ en ‘de straat is nat’ concludeert iemand ‘dus het regent’. Beoordeel deze redenering.

Herken de vorm
Premissen: p → q (regen → nat) en q (nat). Conclusie: p (regen).
Vergelijk met modus ponens
Modus ponens gebruikt p → q én p om q te concluderen; hier wordt juist uit q naar p geredeneerd.
Weerleg met tegenvoorbeeld
De straat kan nat zijn door een sproeier; dan geldt q wel maar p niet.

Resultaat: De redenering bevestigt de consequent en is ongeldig: uit ‘nat’ volgt niet ‘regen’.

Veelgemaakte fouten

De ontkenning van ‘alle A zijn B’ opvatten als ‘geen A is B’, terwijl het ‘er bestaat een A die geen B is’ is (één tegenvoorbeeld volstaat).
De consequent bevestigen: uit ‘als p dan q’ en ‘q’ concluderen dat p geldt — dat lijkt op modus ponens maar is ongeldig.

Actieve herhaling

Gegeven: ‘Als een getal deelbaar is door 4, dan is het even’ en ‘het getal 10 is niet deelbaar door 4’. Welke conclusie mag je hieruit wél en welke níet trekken? Benoem de geldige of ongeldige redeneervorm.

Actief ophalen

Haal de kernpunten op — onthul ze daarna.

Bronnen: Examenprogramma informatica vwo — keuze G (predicatenlogica en redeneren) (CvTE / Examenblad)

Referenties en bronnen

Bronnen

CvTE / Examenblad

Examenprogramma informatica vwo — keuze G (complexiteit)

Keuze G: Algoritmiek, berekenbaarheid en logica

Kernpunten

Complexiteit van geneste lussen

Kernpunten

Waarom de haltbeslisser niet kan bestaan

Kernpunten

Een equivalentie bewijzen met een waarheidstabel

Kernpunten

Geldig of drogreden?

Bronnen

Keuze G: Algoritmiek, berekenbaarheid en logica

Kernpunten

Complexiteit van geneste lussen

Kernpunten

Waarom de haltbeslisser niet kan bestaan

Kernpunten

Een equivalentie bewijzen met een waarheidstabel

Kernpunten

Geldig of drogreden?

Bronnen