Ten einde alle omtrekslijnen op elkaar aan te sluiten, ko
men we tot de volgende formulering van een sorteeralgo-
ritme. We starten met de eerste omtrekslijn in de lijst van
omtrekslijnen, dat wil zeggen met de kop. Met deze kop
zoeken we in de staart van de lijst naar de omtrekslijn die
op de kop aansluit. Dit betekent dat we één voor één alle
elementen van de staart moeten nalopen: de recursie-
techniek zal weer moeten worden toegepast.
Hebben we de aansluitende omtrekslijn gevonden, dan
plaatsen we deze omtrekslijn achter de kop, maken een
nieuwe lijst van alle overige omtrekslijnen en zoeken naar
de volgende aansluitende omtrekslijn, plaatsen deze om
trekslijn achter kop én aansluitende omtrekslijn, vormen
weer een nieuwe lijst van alle overgebleven omtrekslij
nen, enz. Dit herhaalt zich net zolang tot de nieuwe lijst
van overgebleven omtrekslijnen nog slechts één element
bevat (stopconditie voor een recursiel). Dit sorteeralgorit-
me veronderstelt, dat we lijsten kunnen opdelen in su-
blijsten en ook weer sublijsten kunnen samenvoegen tot
nieuwe lijsten. Dit opdelen en samenvoegen kan in PRO
LOG met behulp van één en dezelfde relatie gebeuren.
Deze relatie geven we de predikaatnaam concat (van
„concateneren"), bijvoorbeeld:
concat L1L2, L3
beschouwt L1 en L2 als sublijsten van L3.
In PROLOG: |?- concat [1,2,3], [4,5], L
Antwoord: L 1,2,3,4,5]
Maar ook: ?- concat L, [5], [1,2,3,4,5]
Antwoord: L [1,2,3,4] I
Voor deze eigenschap van PROLOG verwijs ik naar het
tekstblok „functionele programmeertalen".
De concatrelatie wordt wederom recursief als volgt gede
finieerd.
Allereerst creëren we een stopconditie: een lege lijst
samengevoegd met een lijst L heeft L als resultaat.
In PROLOG: concat L, L
Als de eerste lijst niet leeg is, zal de staart van deze lijst
(SL1), samengevoegd met een tweede lijst (L2), de staart
vormen van de samengevoegde lijst van de eerste en
tweede lijst (L3):
We hebben nu alle gereedschappen voor ons sorteer-
algoritme. Deze krijgt de predikaatnaam order met als in
voer een lijst van rechtsom georiënteerde omtrekslijnen
en als uitvoer een lijst van dezelfde omtrekslijnen, nu ech
ter geordend.
In PROLOG:
Verklaring: de eerste twee premissen veronderstellen
Staart zodanig in twee sublijsten opgedeeld, dat de kop
van de tweede sublijst (Y) op Kop volgt (het zoekmecha-
nisme hier is backtracking); de derde premisse veron
derstelt een lijst NieuweStaart samengevoegd uit Y en
de overige sublijsten, de vierde premisse een recursieve
aanroep van het sorteeralgoritme voor deze lijst Nieu
weStaart en de vijfde premisse veronderstelt de lijst
Kop samengevoegd met de lijst GeordendeStaart tot de
lijst Geordend. Als diagram ziet dit er als volgt uit:
-4Staart
Kop
L1
Y
L2
NieuweStaart
Kop
Y
L1
L2
GeordendeStaart
Kop
Y
Geordend
Kop
Wat nog ontbreekt, is een stopconditie:
order [LaatsteElement] [LaatsteElement]
Vraag: sorteer alle omtrekslijnen van vlak v4 tot een aan
eengesloten lijst.
In PROLOG: |?- alleOmtrekslijnen v4, Lijst
richtvlak v4, Lijst
order Lijst, Geordend
Antwoord: Lijst N09, li 10, N02, Ii06
Geordend Ii09, Ii10, Ii06, Ii02
Nog een voorbeeld: sorteer alle omtrekslijnen van vlak v3
tot een aaneengesloten lijst:
In PROLOG: |?- alleOmtrekslijnen v3, Lijst
richtvlak v3, Lijst
order Lijst, Geordend
order Kop Staart Geordend :-
concat L1 Y L2 Staart 1*/
volgtop Kop, Y 1*2*1
concat Y L1 L2, NieuweStaart 1*3*1
order NieuweStaart, GeordendeStaart 1*4*1
concat Kop GeordendeStaart, Geordend)./*5*/
362
Logisch paradigma
Met de introductie van kennissystemen heeft ook de introductie
van het logisch paradigma in de informatica plaatsgevonden.
Het logisch paradigma beschouwt de afwikkeling van een
(PROLOG-) programma als een proces van incremented toe
name van een hoeveelheid kennis. Deze kennis wordt door de
gebruiker gespecificeerd in termen van ware of onware bewe
ringen (premissen) en logische relaties hiertussen, waarop de
waarheid van andere beweringen kan worden getoetst. Bij het
logisch paradigma wordt gebruik gemaakt van predikaten, re
gels en logische operatoren.
Predikaten zijn premissen die waar of onwaar zijn. Regels zijn
formele beschrijvingen van criteria op basis waarvan dit waar
of onwaar zijn van predikaten kan worden bepaald. Operatoren
zijn de basisprimitieven waarvan gebruik wordt gemaakt bij het
samenstellen van regels. Deze wijze van het beschrijven van
kennis wordt aangeduid met declaratieve kennisrepresentatie.
Bron: De formulering van een ontwerpparadigma voor bouw
kundige ontwerpers [6].
NGT GEODESIA 89 - 7/8
concat K SL1 L2, K L3] :-
concat SL1, L2, L3
