Deel dit artikel

nu iedereen computers gebruikt, zijn de termen ‘hardware’ en ‘software’ ingeburgerd. computerapparatuur – de hardware – is beschikbaar in vele vormen: van de desktopcomputer op onze bureau tot een tablet of een smartphone. velen associëren ict, informatica en computerwetenschappen met het schrijven van programma’s, dus met het ontwikkelen van software. de kern van de computerwetenschappen zijn echter de algoritmen die in de software geïmplementeerd zijn.

Hardware, software, algoritmen

Dirk Roose

Een algoritme is een precieze beschrijving van de stappen die een computerprogramma doorloopt of de regels die het gebruikt om een probleem op te lossen. Vele algoritmen zijn een formele beschrijving van wat we doen om een bepaalde taak uit te voeren. Een eenvoudig voorbeeld is het zoeken naar een naam in een gesorteerde lijst. Je kijkt naar een bepaalde plaats in de lijst en je gaat na of de gezochte naam voor of na de bekeken naam voorkomt, vervolgens kies je een nieuwe plaats in het ‘goede deel’ van de lijst en kijk je weer of de naam voor of na de gekozen plaats voorkomt, en zo verder. Dit zoeken kunnen we gemakkelijk formaliseren tot een ‘binair zoekalgoritme’ door in elke stap het middelste element te nemen van de gesorteerde (deel)lijst waarin de naam voorkomt, en te berekenen of de naam voor of na dit element komt, en alleen het goede deel van de lijst te weerhouden voor de volgende stap. Op die manier kan een element in een lijst van n elementen worden gevonden in slechts log2(n) stappen, wat voor grote n veel efficiënter is dan de lijst van boven naar onder te doorlopen (bijvoorbeeld twintig stappen voor een lijst van 1 000 000 namen). Een goed algoritme werkt correct voor alle mogelijke gevallen en is bovendien efficiënt voor wat betreft rekentijd en geheugengebruik.

We gebruiken dagelijks computerprogramma’s die gebaseerd zijn op zeer originele en ingenieuze algoritmen, die een revolutie hebben teweeggebracht in de computerwereld. Het boek Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today’s Computers door John MacCormick geeft op een heel leesbare manier inzicht in een aantal baanbrekende algoritmen die we elke dag gebruiken zonder er stil bij te staan. Hier willen we drie van deze algoritmen toelichten.

Bestanden die je ‘downloadt’ van een website en waarbij de bestandsnaam eindigt op .zip zijn gecomprimeerd, zodat ze sneller doorgestuurd kunnen worden over het netwerk. Eens ontvangen worden die bestanden gedecomprimeerd om ze weer leesbaar en bruikbaar te maken. Foto’s bewaar je gecomprimeerd in je computer in bestanden waarvan de naam eindigt op .jpg. We hebben dus dagelijks te maken met compressiealgoritmen. Bestanden die een tekst of computerprogramma bevatten moeten verliesvrij worden gecomprimeerd en gedecomprimeerd, met andere woorden er mag geen informatie verloren gaan. De algoritmische principes achter verliesvrije compressie zijn vrij eenvoudig. Het ingenieuze van compressiealgoritmen ligt in de gepaste combinatie van een aantal basisalgoritmen. Stel dat de informatie die gecomprimeerd moet worden, bestaat uit een keten van letters. De keten ‘aaaaabcbcbcaaaadefdef’ kan compacter worden voorgesteld als ‘5a3bc4a2def’ door herhalingen van deelketens te detecteren en te coderen. Decompressie tot de oorspronkelijke keten is eenvoudig, want de cijfers die de herhaling weergeven, maken geen deel uit van het oorspronkelijke alfabet. Deze aanpak wordt ‘run-length encoding’ genoemd.

Het ingenieuze van compressiealgoritmen ligt in de gepaste combinatie van een aantal basisalgoritmen.

Voor tekstbestanden zal deze eenvoudige aanpak niet goed werken. Hier gebruikt men beter een variant ervan, waarbij herhalingen van deelketens die niet opeenvolgend zijn, gedetecteerd en compact voorgesteld worden. De keten ‘compressie en decompressie’ kan worden voorgesteld als ‘compressie en deT16K10’ waarbij T16K10 staat voor ‘ga 16 tekens terug, kopieer 10 tekens’. (In praktijk worden niet de hoofdletters ‘T’ en ‘K’ gebruikt, maar speciale symbolen die verwijzen naar de bewerking die uitgevoerd moet worden.) Hoeveel je hiermee wint, hangt natuurlijk af van de lengte van de gedetecteerde deelketen. Het detecteren van (lange) niet-opeenvolgende deelketens is natuurlijk complexer dan het detecteren van opeenvolgende deelketens en vergt ook meer rekentijd.

Een tweede basisalgoritme berekent een efficiënte voorstelling van letters en leestekens in het geheugen van een computer. In een gewoon tekstbestand wordt elke letter of elk leesteken gecodeerd als een ‘bit-string’, een keten van 0- en 1-en, van vaste lengte, namelijk 8 bits (= 1 byte). Een compactere codering wordt bekomen door na te gaan welke letters het vaakst voorkomen in de keten en die voor te stellen door een korte ‘bit-string’, terwijl weinig voorkomende letters voorgesteld worden door een langere ‘bit-string’. (Je kunt dit vergelijken met hoe het Morsealfabet werkt). De ‘bit-string’-voorstelling van de letters is dan afhankelijk van de keten (de tekst) zelf, en de conversietabel moet dus worden meegegeven met de gecomprimeerde voorstelling. Het zipcompressiealgoritme bestaat essentieel uit de hierboven beschreven stappen. Voor grote bestanden zal het gecomprimeerde zipbestand heel wat kleiner zijn dan het oorspronkelijke bestand, maar de reductiefactor is bestandsafhankelijk. Hoe meer repetitieve elementen een bestand bevat, hoe groter de reductiefactor zal zijn.

Het comprimeren van audio-, foto- en videobestanden gebeurt op basis van andere compressiealgoritmen, waarbij verlies van informatie is toegelaten (‘lossy compression’) om een hogere compressiefactor te halen. We kunnen als voorbeeld een zwart-witfoto van 1000 bij 1000 beeldpunten of pixels nemen. In iedere pixel wordt de lichtintensiteit voorgesteld door bijvoorbeeld een getal tussen 0 (zwart) en 255 (wit). De intensiteit van naburige pixels zal meestal maar weinig verschillen. Een zeer eenvoudige compressietechniek vervangt de intensiteit in elk blokje van 2 bij 2 pixels door de intensiteit van één van de pixels, of beter nog door de gemiddelde intensiteit van deze 4 pixels. Men kan zo een compressie met een factor 4 bekomen, en door dit een aantal keren te herhalen kan men compressiefactoren 16, 64 enzovoort bekomen, maar we verliezen natuurlijk ook telkens informatie. Bij hoge compressiefactoren zullen vrij grote blokken pixels dezelfde intensiteit hebben, en de intensiteit van naburige blokken kan vrij sterk verschillen. We krijgen dan een duidelijk ‘blokeffect’.

Er bestaan intelligente compressiealgoritmen die het verlies van informatie bij compressie beperken door gebruik te maken van wiskundige transformaties

Er bestaan echter intelligente compressiealgoritmen die het verlies van informatie bij compressie beperken door gebruik te maken van wiskundige transformaties. Voor een blokje van 8 bij 8 pixels wordt de intensiteit voorgesteld door een rij van 64 getallen, die elk de intensiteit voorstellen van één pixel. Door een wiskundige transformatie, de discrete cosinustransformatie, wordt deze informatie voorgesteld door een lineaire combinatie van tweedimensionale ‘golffuncties’ met verschillende frequenties. Voor elk blokje moeten we opnieuw 64 getallen (de coëfficiënten van de lineaire transformatie) bewaren. De eerste coëfficiënt komt overeen met het gemiddelde van de 64 intensiteiten, en de volgende coëfficiënten bevatten informatie over afwijkingen van het gemiddelde, de detailinformatie dus, waarbij de laatste coëfficiënten de fijnste details beschrijven. We kunnen nu de data comprimeren door slechts een deel van de coëfficiënten te behouden en de laatste coëfficiënten weg te gooien. De cosinustransformatie zorgt ervoor dat we bij foto’s heel wat minder informatie verliezen bij een bepaalde compressiefactor dan met de eerder beschreven eenvoudige compressiemethode. Het welbekende JPEG-formaat is een dataformaat waarin foto’s en andere beelden gecomprimeerd worden opgeslagen, steunend op de cosinustransformatie toegepast op blokjes van 8 bij 8 pixels, samen met de hogervermelde ‘run-length encoding’. Voor relatief kleine beelden (1000 bij 1000 pixels) is JPEG voldoende. Maar de foto’s en beelden waarmee we werken bevatten steeds meer pixels en er is dus nood aan betere compressiealgoritmen. De nieuwe JPEG2000 compressiestandaard is gebaseerd op een andere wiskundige transformatie, de discrete wavelettransformatie, waarvoor trouwens heel wat fundamenteel werk werd verricht door twee Vlaamse onderzoekers, Ingrid Daubechies en Wim Sweldens.

Compressiealgoritmen sluiten nog vrij dicht aan bij de manier waarop wij mensen de taak zouden aanpakken. Voor andere taken zoals patroonherkenning (bijvoorbeeld het herkennen van gezichten of nummerplaten of het lezen van een handschrift) is het heel wat moeilijker om precies te beschrijven hoe het probleem moet worden opgelost. Een belangrijke moeilijkheid hier is de variabiliteit in de gegevens: in een met de hand geschreven tekst heeft een bepaalde letter nooit precies dezelfde vorm. Patroonherkenningalgoritmen steunen vaak op het feit dat patroonherkenning kan worden gezien als een classificatieprobleem. Hierbij moet elke invoer (bijvoorbeeld een te herkennen foto) worden toegewezen aan een bepaalde ‘klasse’ (bijvoorbeeld een persoon). In een eerste fase (de leerfase) worden een aantal invoerpatronen met de bijbehorende klasse getoond. Een algoritme zal dan uit de invoerpatronen de karakteristieken van elke klasse extraheren. In een tweede fase (de classificatiefase) zal een ander algoritme nieuwe, onbekende invoerpatronen toewijzen aan de meest waarschijnlijke klasse. Het is hierbij van belang om de ‘afstand’ tussen de mogelijke klassen en het nieuwe invoerpatroon goed te definiëren. In de meest eenvoudige aanpak wordt elk nieuwe invoerpatroon toegewezen aan de klasse die er het dichtst bij ligt (ten opzichte van de gebruikte afstandsfunctie).

Patroonherkenning- of classificatieproblemen worden ook vaak opgelost door in de leerfase een beslissingsboom op te stellen. Hierbij genereert het algoritme van de leerfase een boomstructuur van ‘vragen’ over kenmerken van het invoerpatroon, waarbij het antwoord op die vragen leidt tot de juiste klasse voor het invoerpatroon. Deze leerfase is complex, maar daarna kan een invoerpatroon zeer gemakkelijk en snel worden geclassificeerd of herkend. Ook vele andere algoritmen worden gebruikt voor patroonherkenning, bijvoorbeeld gebaseerd op neurale netwerken. Waar vijftig jaar geleden patroonherkenning werd gezien als een probleem waarvoor computers helemaal niet geschikt zijn, beschikken we nu over een arsenaal aan krachtige en efficiënte algoritmen. Dit opent mogelijkheden voor nieuwe toepassingen, van snelheidstrajectcontrole waarbij nummerplaten worden herkend, tot datamining waarbij meer abstracte patronen in medische gegevens worden herkend.

Zoals in andere domeinen is het onderzoek naar algoritmen een mix van verbeteringen en verfijningen van wat al bestaat met sporadisch een fundamentele doorbraak

Bestaande algoritmen voldoen vaak na een tijd niet meer omdat ze bijvoorbeeld niet geschikt zijn om zeer grote hoeveelheden data te verwerken of omdat de toepassingen complexer worden. Zoals in andere domeinen is het onderzoek naar algoritmen een mix van verbeteringen en verfijningen van wat al bestaat met sporadisch een fundamentele doorbraak. Een voorbeeld van dit laatste is het Pagerank-algoritme waarop het succes van Google gebaseerd is. In 1998 bestonden er al verscheidene, al dan niet commerciële, zoekmachines die op het internet websites zoeken waarin een bepaald (sleutel)woord voorkomt. De basisingrediënten van een zoekmachine zijn algoritmen voor het vinden van de juiste webpagina’s (‘matching’) en voor het rangschikken van de gevonden pagina’s naar belangrijkheid (‘ranking’). Twee doctorandi van Stanford University hadden een nieuw ‘ranking’-algoritme ontwikkeld, gepubliceerd en geïmplementeerd in een zoekmachine. Omwille van de snel stijgende populariteit van hun zoekmachine richtten ze in 1998 een bedrijfje op. Drie maand na de start van Google werd hun website door PC Magazine uitgeroepen als één van de top 100 websites wereldwijd omwille van ‘its uncanny knack for returning extremely relevant results’, dus omwille van de kracht van het onderliggende Pagerank-algoritme. Dit algoritme is gebaseerd op een wiskundige abstractie van het netwerk van webpagina’s, een innovatieve definitie van belangrijkheid, en een statistische analyse die leidt tot een efficiënt numeriek algoritme. Natuurlijk was er veel meer nodig om Google te maken tot wat het nu is, maar het begon met het Pagerank-algoritme.

De impact van een nieuw algoritme kan dus zeer groot zijn en heel wat onderzoek in de computerwetenschappen is dan ook een zoektocht naar nieuwe en betere algoritmen. Ook in bedrijven zijn heel wat baanbrekende algoritmen ontwikkeld. Zo ontwikkelden twee onderzoekers van IBM en Bell Labs (nu Lucent Technologies) één van de belangrijkste numerieke algoritmen, het FFT-algoritme voor de efficiënte berekening van een Fouriertransformatie, een basisbewerking in signaalverwerking en in vele andere toepassingsgebieden. Bedrijven en ook universiteiten trachten soms algoritmen te patenteren, maar onlangs heeft een rechtbank in de Verenigde Staten gesteld dat wiskundige algoritmen niet patenteerbaar zijn. Dit zal de zoektocht naar nieuwe algoritmen echter niet hinderen, gezien de enorme impact van betere algoritmen in allerhande toepassingen. Er zijn trouwens nog andere ‘incentives’ naast patenten: als computerwetenschapper kun je onsterfelijk worden als het algoritme dat je ontwikkeld hebt naar jou wordt genoemd, zoals het Dijkstra-algoritme om het kortste pad tussen twee knopen van een grafe te berekenen.

John MacCormick, Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today’s Computers. (Princeton: Princeton University Press, 2012).

Deel dit artikel
Gerelateerde artikelen