Tenzij je van wiskunde of programmeren houdt, is het woord ‘algoritme’ misschien Grieks voor jou, maar het is een van de bouwstenen van alles wat je gebruikt om dit artikel te lezen. Hier volgt een korte uitleg van wat ze zijn en hoe ze werken.
Disclaimer: ik ben geen leraar wiskunde of informatica, dus niet alle termen die ik gebruik zijn technisch. Dat komt omdat ik alles in gewoon Engels probeer uit te leggen, want mensen zijn niet helemaal op hun gemak met wiskunde. Dat gezegd hebbende, er is wat wiskunde bij betrokken, en dat is onvermijdelijk. Wiskunde-geeks, voel je vrij om te corrigeren of beter uit te leggen in de commentaren, maar houd het alsjeblieft simpel voor de wiskundig onwillige onder ons.
Afbeelding door Ian Ruotsala
Wat is een algoritme?
Het woord ‘algoritme’ heeft een etymologie die lijkt op ‘algebra’, behalve dat dit verwijst naar de Arabische wiskundige zelf, al-Khwarizmi (gewoon een interessante versnapering). Een algoritme, voor de niet-programmeurs onder ons, is een set instructies die een invoer A aannemen en een uitvoer B leveren die de betrokken gegevens op de een of andere manier verandert. Algoritmen hebben een breed scala aan toepassingen. Bij wiskunde kunnen ze helpen bij het berekenen van functies op basis van punten in een gegevensset, naast veel geavanceerdere dingen. Afgezien van hun gebruik bij het programmeren zelf, spelen ze een belangrijke rol in zaken als bestandscompressie en gegevenscodering.
Een basisset met instructies
Stel dat je vriend je in een supermarkt ontmoet en je hem naar je toe leidt. Je zegt dingen als “kom binnen door de deuren aan de rechterkant”, “passeer het visgedeelte aan de linkerkant” en “als je de zuivelfabriek ziet, passeer je mij.” Algoritmen werken zo. We kunnen een stroomschema gebruiken om instructies te illustreren op basis van criteria die we van tevoren kennen of die we tijdens het proces ontdekken.
(afbeelding getiteld “Icebreaking Routine” EDIT: met dank aan Trigger en Freewheel)
Vanaf START ga je het pad af, en afhankelijk van wat er gebeurt, volg je de “stroom” naar een eindresultaat. Stroomdiagrammen zijn visuele hulpmiddelen die begrijpelijker een reeks instructies kunnen weergeven die door computers worden gebruikt. Op dezelfde manier helpen algoritmen hetzelfde te doen met meer op wiskunde gebaseerde modellen.
Grafieken
Laten we een grafiek gebruiken om de verschillende manieren te illustreren waarop we aanwijzingen kunnen geven.
We kunnen deze grafiek uitdrukken als een verbinding tussen al zijn punten. Om deze afbeelding te reproduceren, kunnen we een reeks instructies aan iemand anders geven.
Methode 1
We kunnen dit weergeven als een reeks punten, en de informatie zou de standaardvorm van graaf = {(x1, y1), (x2, y2),…, (xn, yn)} volgen.
grafiek = {(0,0), (3,0), (3,3), (5,5), (7,10), (8,7), (9,4), (10,1) }
Het is vrij eenvoudig om elk punt achter elkaar uit te zetten en ze met het vorige punt te verbinden. Stel je echter een grafiek voor met duizend punten of meerdere segmenten die alle kanten op gaan. Die lijst zou veel gegevens bevatten, toch? En dan kan het lastig zijn om ze allemaal een voor een te verbinden.
Methode 2
Een ander ding dat we kunnen doen is een startpunt geven, de helling van de lijn tussen het en het volgende punt, en aangeven waar we het volgende punt kunnen verwachten met behulp van de standaardvorm van graph = {(startpunt}, [m1, x1, h1], …, [mn, xn, hn]}. Hier staat de variabele ‘m’ voor de helling van de lijn, ‘x’ staat voor de richting waarin moet worden geteld (of het nu x of y is) en ‘h’ geeft aan hoeveel je in die richting moet tellen. U kunt er ook aan denken om na elke beweging een punt uit te zetten.
grafiek = {(0,0), [0,x,3], [0,y,3], [1,x,2], [2.5,x,2], [-3,x,1], [-3,x,1], [-3,x,1]}
Je krijgt dezelfde grafiek. Je kunt zien dat de laatste drie termen in deze uitdrukking hetzelfde zijn, dus we kunnen dat misschien verkleinen door op de een of andere manier gewoon “herhaal dat drie keer” te zeggen. Laten we zeggen dat elke keer dat u de variabele ‘R’ ziet verschijnen, dit betekent dat u het laatste moet herhalen. We kunnen dit:
grafiek = {(0,0), [0,x,3], [0,y,3], [1,x,2], [2.5,x,2], [-3,x,1], [R=2]}
Wat als de individuele punten er niet echt toe doen, en alleen de grafiek zelf? We kunnen die laatste drie secties als volgt consolideren:
grafiek = {(0,0), [0,x,3], [0,y,3], [1,x,2], [2.5,x,2], [-3,x,3]}
Het verkort de zaken een beetje ten opzichte van waar ze voorheen waren.
Methode 3
Laten we dit op een andere manier proberen.
y = 0, 0≤x≤3
x = 0, 0≤y≤3
y = x, 3≤x≤5
y = 2,5x-7,5, 5≤x≤7
y = -3x + 29, 7≤x≤8
y = -3x + 29, 8≤x≤9
y = -3x + 29, 9≤x≤10
Hier hebben we het in pure algebraïsche termen. Nogmaals, als de punten zelf er niet toe doen en alleen de grafiek doet dat, kunnen we de laatste drie items consolideren.
y = 0, 0≤x≤3
x = 0, 0≤y≤3
y = x, 3≤x≤5
y = 2,5x-7,5, 5≤x≤7
y = -3x + 29, 7≤x≤10
Welke methode u nu kiest, hangt af van uw mogelijkheden. Misschien ben je goed in rekenen en grafieken, dus kies je voor de laatste optie. Misschien ben je goed in navigeren, dus kies je voor de tweede optie. Op het gebied van computers voer je echter veel verschillende soorten taken uit en het vermogen van de computer verandert niet echt. Daarom zijn algoritmen geoptimaliseerd voor de taken die ze voltooien.
Een ander belangrijk punt om op te merken is dat elke methode afhankelijk is van een sleutel. Elke set instructies is nutteloos, tenzij u weet wat u ermee moet doen. Als je niet weet dat je elk punt moet plotten en de punten met elkaar moet verbinden, betekent de eerste reeks punten niets. Tenzij u weet wat elke variabele in de tweede methode betekent, weet u niet hoe u ze moet toepassen, net zoals de sleutel tot een cijfer. Die sleutel is ook een integraal onderdeel van het gebruik van algoritmen, en vaak wordt die sleutel gevonden in de gemeenschap of via een ‘standaard’.
Bestandscompressie
Wanneer u een .zip-bestand downloadt, extraheert u de inhoud zodat u alles kunt gebruiken wat erin zit. Tegenwoordig kunnen de meeste besturingssystemen in .zip-bestanden duiken alsof het normale mappen zijn, waarbij ze alles op de achtergrond doen. Op mijn Windows 95-machine, meer dan een decennium geleden, moest ik alles handmatig extraheren voordat ik meer kon zien dan de bestandsnamen erin. Dat komt omdat wat op de schijf was opgeslagen als een .zip-bestand niet in een bruikbare vorm was. Denk aan een uittrekbare bank. Wanneer je hem als bed wilt gebruiken, moet je de kussens verwijderen en uitklappen, wat meer ruimte in beslag neemt. Als je hem niet nodig hebt, of je wilt hem vervoeren, dan kun je hem weer opklappen.
Compressie-algoritmen worden specifiek aangepast en geoptimaliseerd voor de soorten bestanden waarop ze zijn gericht. Audioformaten gebruiken bijvoorbeeld elk een andere manier om gegevens op te slaan die, wanneer ze worden gedecodeerd door de audiocodec, een geluidsbestand opleveren dat lijkt op de originele golfvorm. Lees voor meer informatie over die verschillen ons vorige artikel, Wat zijn de verschillen tussen al die audioformaten? Lossless audioformaten en .zip-bestanden hebben één ding gemeen: ze leveren allebei de originele gegevens in hun exacte vorm op na het decompressieproces. Lossy-audiocodecs gebruiken andere middelen om schijfruimte te besparen, zoals het bijsnijden van frequenties die niet door het menselijk gehoor kunnen worden gehoord en het afvlakken van de golfvorm in secties om wat details te verwijderen. Hoewel we het verschil tussen een mp3- en een cd-track misschien niet echt kunnen horen, is er zeker een tekort aan informatie in de eerste.
Data encryptie
Algoritmen worden ook gebruikt bij het beveiligen van data- of communicatielijnen. In plaats van gegevens op te slaan zodat ze minder schijfruimte gebruiken, worden ze opgeslagen op een manier die niet detecteerbaar is voor andere programma’s. Als iemand uw harde schijf steelt en deze begint te scannen, kunnen ze gegevens ophalen, zelfs als u bestanden verwijdert, omdat de gegevens zelf nog steeds aanwezig zijn, ook al is de doorstuurlocatie erheen verdwenen. Wanneer gegevens zijn gecodeerd, ziet alles wat wordt opgeslagen er niet uit zoals het is. Het ziet er meestal willekeurig uit, alsof fragmentatie in de loop van de tijd is ontstaan. U kunt ook gegevens opslaan en deze als een ander type bestand laten verschijnen. Afbeeldingsbestanden en muziekbestanden zijn hier goed voor, omdat ze vrij groot kunnen zijn zonder bijvoorbeeld argwaan te wekken. Dit alles wordt gedaan door wiskundige algoritmen te gebruiken, die een soort invoer nemen en deze omzetten in een ander, heel specifiek type uitvoer. Voor meer informatie over hoe versleuteling werkt, ga naar HTG Explains: Wat is versleuteling en hoe werkt het?
Algoritmen zijn wiskundige hulpmiddelen die op verschillende manieren in de informatica kunnen worden gebruikt. Ze werken om op een consistente manier een pad te bieden tussen een beginpunt en een eindpunt, en geven de instructies om dit te volgen. Meer weten dan wat we hebben benadrukt? Deel uw uitleg in de comments!
