Posts in category sorteren
Boekenplanken voor gevorderden
In dit vervolg op deze blogpost ga ik het hebben over het ordenen van boeken.
Bij de twitterdiscussie over of er verschil is, of niet, tussen boeken en getallen kwam ook de mogelijkheid getallen en boeken te ordenen ter sprake. Hierbij werd met `getal’ stilzwijgend `natuurlijk getal’ bedoeld. Nu komen natuurlijke getallen met een natuurlijke ordening, waarin elk getal een directe opvolger heeft en elk getal, behalve het eerste, een directe voorganger.
Hoe zit het met de boeken? Als je het met Marc eens bent dat een boek van vijf miljard pagina’s meer dan genoeg is zijn we gauw klaar.
Nee, ik denk dat het redelijk is om te zeggen dat een boek een bepaalde maximale omvang heeft: iets van vijf miljard pagina's is niet langer een boek, maar een serie boeken.
— Marc van Oostendorp (@fonolog) October 15, 2019
Als we het aantal bladzijden begrenzen en niet raar doen met onhandelbaar grote pagina’s en ook niet al te kleine letters gebruiken dan is, in een vaste alfabet, het aantal boeken eindig. Als we de letters, spaties, interpunctie etc van een vaste ordening voorzien kunnen we elk boek als een rij symbolen beschouwen en gewoon lexicografisch ordenen: als rij/boek A een echt beginstuk van rij/boek B is dan komt boek A voor boek B; anders kijken we naar de eerste plek waar A en B verschillen en gebruiken de ordening van de tekens om te beslissen welke van de twee eerst komt. Het resultaat is een rij boeken met een eerste en een laatste, waarin elk boek behalve het eerste een directe opvolger heeft, en elk boek behalve het laatste een directe voorganger.
En dit laat inderdaad een praktisch verschil zien tussen getallen en boeken: van de laatste zijn er maar eindig veel.
Oneindig veel boeken
Echter, …, de hele discussie begon met een artikel van Paul Postal, waarin het begrip boek wat ruimer werd opgevat: elke eindige rij symbolen is een potentieel boek.
Dan wordt het ordenen van de boeken een minder eenvoudige klus. Er was een heel specifieke vraag van Marc:
Maar boeken kun je toch ook ordenen? Bijvoorbeeld alfabetisch (op de hele tekst)? Dus na een boek dat eindigt op 'vrede op aardbei' komt een boek dat verder identiek is, maar eindigt op 'vrede op aarde'?
— Marc van Oostendorp (@fonolog) October 15, 2019
Het antwoord daarop is niet geheel flauw.
Lexicografisch
Je kunt je (potentiële) boeken nog steeds als hierboven lexicografisch ordenen. Dan is in ieder geval duidelijk dat het antwoord op de vraag van Marc bevestigend luidt: zijn twee boeken zijn geen beginstukken van elkaar en ze verschillen als eerste bij de positie van de b en de d, en de b komt voor de d. Er zitten natuurlijk nog zat boeken tussen die twee: aardbei komt voor aardbeienjam en dat komt voor aardappel hetwelk zelf weer voor aarde komt.
Het interessante, zeker voor wiskundigen, is dat tussen elk tweetal boeken oneindig veel (potentiële) boeken staan.
Tussen de nogal flauwe boeken (a) en (b) staan (ab), (aab), (aaab), (aaaab), … (een dalende rij boeken); tussen (ab) en (aab) kun je ook zoiets maken: (aba), (abab), (abaab), …
Dit is voor makers van boekeplanken nogal vervelend: de planken moeten overal oneindig lang zijn om al die oneindig veel tussenliggende boeken kwijt te kunnen.
Iets praktischer
Het kan praktischer (ook al door Marc opgemerkt in een commentaar op neerlandistiek.nl: sorteer de boeken eerst op lengte en orden ze bij vaste lengte weer gewoon lexicografisch. Dan heb je een eerste boek en elk ander boek heeft net als bij de natuurlijke getallen een directe voorganger en een directe opvolger. Dit is wel zo praktisch voor de timmerlieden: terwijl jij de planken vult kunnen zij gewoon vooruit werken.
Het verschil met hierboven is wel dat het aarde-boek van Marc vóóor het aardbei-boek komt: het eerste is één karakter korter dan het tweede.
Kleene-Brouwer
Tijdens de discussie noemde ik nog de Kleene-Brouwerorde; die lijkt op de lexicografische met dit verschil dat indien A een echt beginstuk van B is A juist achter B geplaatst wordt. Het tweede deel van de definitie blijft ongewijzigd. Dus (a) komt nog steeds voor (b), maar (aaa) komt voor (aa) en die weer voor (a).
Ook dit is een nachtmerrie voor boekenkastmakers: tussen elk tweetal boeken hebben we weer oneindig veel boeken. Het is zelfs een dubbele nachtmerrie: lexicografisch is er tenminste een eerste boek, bij Kleene-Brouwer hebben we dat niet eens; de timmerlieden moeten nu twee kanten op planken ophangen die overal oneindig veel boeken moeten kunnen hebben.
Voor mensen die werken in Beschrijvende Verzamelingenleer en in de Recursietheorie is de Kleene-Brouwerordening heel nuttig. Maar dat is weer een heel ander verhaal.
Boeken, getallen, stellingen
Vorige week ontspon zich een kleine discussie op Twitter over boeken en getallen; Marc van Oostendorp schreef Neerlandistiek.nl over een artikel van Paul Postal waarin de laatste over de aard, de ontologie, van boeken schrijft.
Boeken zijn als getallen. https://t.co/UPA1zENKqx
— Marc van Oostendorp (@fonolog) October 15, 2019
Ietwat kort door de bocht is de these van Postal dat een boek (hij gebruikte Pride and Prejudice als voorbeeld, Marc nam De Kleine Johannes als voorbeeld) als abstract object altijd al bestaan heeft, het is namelijk een rij symbolen (letters, spaties, interpunctie, …) en iemand heeft die rij een keer voor het eerst opgeschreven. Net als het getal gerepresenteerd door 7.987.923.892.274 (gezien de ene hit bij Google waarschijnlijk door Marc als eerste opgeschreven).
Voor het geval de ingebedde tweet hierboven niet goed werkt is hier een korte samenvatting van de discussie.
Mogelijke tegenwerping (Ionica Smeets): elk natuurlijk getal heeft een natuurlijke opvolger, hoe zit dat met boeken? Lijken boeken en stellingen niet meer op elkaar?
Antwoord (Marc): orden ze alfabetisch.
Ander argument (ik): dat werkt niet helemaal, als je alfabetisch wilt werken is Kleene-Brouwerorde beter, maar dan staan tussen elk tweetal boeken weer oneindig veel boeken (ik zag elke rij symbolen als een potentieel boek). Dit geldt overigens ook voor de normale Lexicografische orde van eindige rijen symbolen.
Antwoord (Marc): een boek van vijf miljard pagina’s is lang genoeg. Zou het verschil dan niet zijn dat er maar eindig veel boeken (kunnen) zijn?
Het laatste argument schuurt dan weer met de inhoud van het artikel van Postal (pagina 12): die laat willekeurig lange zinnen toe en concludeert dan dat er niet alleen oneindig veel boeken zijn maar zelfs overaftelbaar veel. Sterker nog: de boeken in een gegeven taal vormen niet eens een verzameling (volgens mij is dat laatste lariekoek maar daar hebben we het later nog wel eens over).
Is er wel verschil?
Je kunt op diverse niveau’s naar deze vraag kijken.
Representaties: rijen symbolen
Als het om opgeschreven verhalen en opgeschreven getallen gaat dan is er inderdaad geen echt verschil: beide bestaan uit rijen symbolen die hun betekenis prijsgeven als je volgens bepaalde regels (in dit geval op school aangeleerd) decodeert.
Bestonden die rijen symbolen ook al voor ze werden opgeschreven? En zo ja, hoe lang al?
Dat is een lastige vraag en waarschijnlijk voer voor lange filosofische discussies. Mijn mening: eigenlijk wel. In ieder geval sinds halverwege de negentiende eeuw (dat maakt het voor Pride and Prejudice wat onzeker): toen begon men namelijk functies als objecten te beschouwen en niet als `formules’ of `regels’. En Cantor nam, gegeven twee verzamelingen X en Y, de verzameling van alle functies van X naar Y ter hand om machtsverheffen van kardinaalgetallen te definiëren.
Als we dus voor een groot genoeg natuurlijk getal N alle functies nemen van {1,2,…,N} naar ons alfabet, aangevuld met spaties en interpunctiesymbolen, dan zit daar het verhaal van De Kleine Johannes (1884) dus ook in. In de tijd van Pride and Prejudice was de wiskunde nog niet zo ver en ik laat het aan de meer filosofisch ingestelden onder ons om te overdenken of dat boek er (ver) voor 1811 ook al was.
Het boek zelf; het getal zelf
Tot nu toe hebben we boek en getal vereenzelvigd met hun representaties. Bij een boek is dat bijna noodzakelijk. We kunnen het boek anders representeren, denk aan een lange rij nullen en enen in een e-reader, maar we hebben bij het lezen toch de oorspronkelijke rij symbolen nodig (tenzij iemand zich heeft aangeleerd de binaire code uit het hoofd te vertalen maar dat lijkt me vergezocht).
Bij een getal is dat niet zo. Neem het getal gegeven in decimale representatie als 1729 (decimale representatie) of als 6C1 (hexadecimaal) of als 11011000001 (binair). Deze representeren alledrie exact dezelfde hoeveelheid stippen, of hoop kogeltjes. En die hoop kogeltjes is de kleinste die op twee verschillende manieren in drie hoopjes verdeeld kan worden die dan elk als kubus gestapeld kunnen worden.
En Stellingen?
Ik was het in eerste instantie met Ionica eens maar nu twijfel ik. Ik vind achteraf dat stellingen dichter bij getallen liggen dan ik dacht. Een stelling heeft vele representaties maar de uiteindelijke betekenis is altijd dezelfde, net als elke representatie van een getal tot dezelfde hoeveelheid stippen, strepen, dropjes zal leiden.
Er is meer
In de tweets hadden we het ook over de mogelijkheid boeken en getallen te ordenen en het al dan niet bestaan van getallen.
Daar zal ik het in een latere post een keer over hebben.
Voegwoorden en rekenen
“Taal is geen Wiskunde” schreef @onzetaal als reactie op de vorige post. Inderdaad.
In 2002 stond in het tijdschrift Onze Taal een artikel Alle Aaanwezigen Behalve De Kinderen waarin de werking van voegwoorden gerelateerd werd aan, vooral, optellen en aftrekken.
En, helaas, na een bladzijde voorbeelden gaat het meteen mis:
De betekenis van en is gemakkelijk: het komt overeen met de optelling van twee aantallen. In de wiskundige verzamelingenleer worden aantallen als verzamelingen voorgesteld. De betekenis van `Jan is bakker en visser’ wordt in verzamelingstheoretische termen opgevat als `Jan behoort zowel tot de verzameling bakkers als tot de verzameling vissers.’
De betekenis van en is een stuk ingewikkelder dan optellen en dat laat het geciteerde voorbeeld meteen zien: door te zeggen `Jan is bakker en visser’ verwijst men inderdaad naar de doorsnede van twee verzamelingen: Jan∊Bakkers∩Vissers. Echter `Willen alle bakkers en vissers naar voren komen’ verwijst naar een vereniging: Bakkers∪Vissers. En beide mogelijkheden komen niet overeen met optellen: in het eerste geval laten we niet-vissers weg uit de verzameling bakkers en in het tweede geval is het totale aantal mensen niet noodzakelijk de som van de aantallen bakkers en vissers want onze Jan wordt dan dubbel geteld.
Later wordt aan of ook een rekenkundige kant toegedicht. Die lijkt ook verdacht veel op optellen `Jan is bakker of visser’ verwijst (weer) naar de vereniging van de verzamelingen bakkers en vissers. “Jan behoort tot de verzameling die het resultaat is van de samenvoeging van de bakkers en de vissers. Daar moet je nog de doorsnede van aftrekken, omdat Jan niet tegelijk bakker en visser zou kunnen zijn”. Dat is nou jammer, want de tweede helft van de zin is nogal ongelukkig.
Als het er om gaat de bakkers en vissers bijeen te nemen dan is weglaten van de doorsnede niet nodig: iemand mag best bakker en visser tegelijk zijn. Als het om het totale aantal mensen gaat moet je, als boven, het anatal mensen in de doorsnede aftrekken van de som van de twee aantallen om dubbeltellen te voorkomen.
De tweede helft is ongelukkig omdat hij niets uitlegt: door het `zou kunnen zijn’ laat hij in het midden of Jan twee beroepen uitoefent, of niet en maakt hij het `omdat’ niet waar.
Ik proefde daar een beetje het verschil tussen het exclusieve of en het inclusieve of maar het kwam niet geheel uit de verf. In de omgangstaal is of veelal exclusief: een koekje of een snoepje, maar niet allebei. In de wiskunde gebruiken we het inclusieve of, een beetje uit gemakzucht maar vooral omdat het in de Logica allemaal een stuk mooier werkt.
Met de tweedeling aan het eind kan ik het wel eens zijn: er zijn twee soorten voegwoorden, die in de ene groep gedragen zich als binaire operaties (denk aan +, ∪ ∩, …) en die in de andere als binaire relaties (≤, =, ≥, ⊆, …). En daar was het in het artikel om te doen: proberen een vinger te krijgen achter het verschijnsel dat je sommige voegwoorden `binnen/buiten de haakjes kunt halen’. De zinnen `Jan is bakker en Jan is visser’ en `Jan is bakker en visser’ betekenen hetzelfde en zijn syntactisch correct. Maar van `Ik ga naar buiten omdat ik wil hardlopen’ kun je niet `Ik ga naar buiten omdat wil hardlopen’ maken; `omdat’ is hier een binaire relatie en die kun je ook in de wiskunde niet buiten de haakjes halen: 5+a=5+b is niet hetzelfde als 5=a+b.
Ten slotte
Om het werken met voegwoorden met rekenen te vergelijken ligt voor de hand maar is niet de juiste keuze. Beter is het naar de Boolese Algebra te kijken (spreek uit: Boelse Algebra). Deze is voortgekomen uit het werk An Investigation into the Laws of Thought van de Ierse wiskundige George Boole. Daarin wordt gerekend met ∧ (en) en ∨ (of), volgens regels die een beetje op die van het gewone rekenen lijken maar ook niet meer dan een beetje.
Veel van wat in het artikel wordt besproken kan hiermee geanalyseerd worden. De ervaring leert dat de studenten met dat rekenen niet zoveel moeite hebben. Het kost ze (en niet alleen de studenten) veel meer moeite normale zinnen correct naar dit formalisme te vertalen.
Sorteren
In haar column van 1 juli beschreef Ionica Smeets hoe de logistiek van een menselijke keten van de Belgische kerncentrale Tihange naar de Duitse stad Aken haar aan van alles deed denken, behalve kernenergie.
Een van de problemen die bij haar opkwam was het op alfabet sorteren van de schakels in de mensenketen en hoe lang dat zou duren. De sorteermethode waar ze aan dacht bestaat uit het telkens vergelijken van de namen van twee naast elkaar staande personen en die, indien nodig, omwisselen.
Nu kun je zoiets op veel manieren uitvoeren en zo ongeveer het eerste sorteerprogramma dat ik zelf geschreven heb loopt telkens van begin tot eind door de lijst en wisselt verkeerd geordende buren om. Hier is een versie in de taal python (de n is de lengte van de lijst; in python wordt een lijst van lengte n genummerd van 0 tot en met n-1):
for k in range(1,n-1):
for l in range(1,n-k):
if x[l] < x[l-1]:
xx = x[l]
x[l] = x[l-1]
x[l-1] = xx
Het programma is iets versneld: als k=1 staat aan het eind van de binnenste loop het grootste element in x[n-1]; als k=2 staat aan het eind van de binnenste loop het op één na grootste element in x[n-2], enzovoort. Dit betekent dat er slechts n-1 binnenloops uitgevoerd hoeven worden die ook steeds korter worden: l loopt telkens maar tot n-k.
Hoe lang duurt het voor het programma klaar is? Neem aan dat we het alfabetisch van Aken naar Tihange willen sorteren. In het ergste geval, als de lijst al alfabetisch gesorteerd is maar net andersom, van Tihange naar Aken dus, moeten er 50000×49999/2 verwisselingen gedaan worden. Dat zijn er, afgerond, 1,25×109, (veel) meer dan een miljard dus.
Aangenomen dat een verwisseling een seconde kost dan zijn we met mijn programmaatje wat meer dan 39 jaar bezig.
Efficiënter?
Het bovenstaande programmaatje implementeert het zogeheten bubble-sort (de grotere elementen `borrelen’ omhoog door de lijst). Bedenk dat dit bij onze mensenketen neerkomt op het volgende: de hoofdorganisator holt iedere keer keer weer langs de keten mensen en laat telkens verkeerd geordende tweetallen omwisselen. Hierbij staat iedereen vrijwel de hele tijd te niksen.
We kunnen die mensen beter zelf wat laten doen door ze als parallelle processoren te gebruiken. Op elk moment laten we de mensen die dan op een evengenummerde plaats staan zich met een buur vergelijken en, zo nodig, van plaats verwisselen. Op de oneven momenten kijken die mensen richting Tihange en op de even momenten richting Aken.
Dus bij stap 1 laten we alle paren (0,1), (2,3), (4,5), … (49998,49999) vergelijken en, indien nodig, wisselen. Bij stap 2 laten we dat de paren (1,2), (3,4), (5,6), … (49997,49998) doen. Dit gebeurt om en om tot de rij gesorteerd is. Dit proces staat, om een voor de hand liggende reden, bekend als odd-even sort.
Omdat we nu telkens 25.000 verwisselingen tegelijk laten doen kost dit `maar’ 50.000 iteraties. En als iedereen goed meewerkt zijn we dus in 50.000 seconden klaar, dat is wat minder dan 14 uur.
Recent Comments