Wat zijn computeralgoritmen en hoe werken ze?
Tenzij je geïnteresseerd bent in wiskunde of programmeren, kan het woord 'algoritme' Grieks voor je zijn, 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. Wiskundige geeks, voel je vrij om te corrigeren of beter uit te leggen in de reacties, maar houd het alsjeblieft simpel voor wiskundig onzichtbare 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 (slechts een interessante vertelling). Een algoritme, voor de niet-programmeurs onder ons, is een verzameling instructies die een invoer nemen, A, en een uitvoer, B, verschaffen die de gegevens op een of andere manier verandert. Algoritmen hebben een grote verscheidenheid aan toepassingen. In wiskunde kunnen ze helpen bij het berekenen van functies uit punten in een gegevensverzameling, naast veel geavanceerdere dingen. Afgezien van hun gebruik in het programmeren zelf, spelen ze een belangrijke rol in zaken als bestandscompressie en gegevensversleuteling.
Een basis instructieset
Laten we zeggen dat je vriend je ontmoet in een supermarkt en je hem naar je toe begeleidt. Je zegt dingen als "kom binnen door de deuren aan de rechterkant", "passeer de vissectie aan de linkerkant" en "als je de zuivelfabriek ziet, passeer je me." Algoritmen werken zo. We kunnen een stroomdiagram gebruiken om instructies te illustreren op basis van criteria die we van tevoren kennen of om er tijdens het proces achter te komen.
(afbeelding getiteld "Icebreaking Routine" EDIT: met dank aan Trigger en Freewheel)
Vanaf START zou je het pad volgen en afhankelijk van wat er gebeurt, volg je de "stroom" naar een eindresultaat. Stroomdiagrammen zijn visuele hulpmiddelen die begrijpelijkerwijs een reeks instructies vertegenwoordigen die door computers worden gebruikt. Op dezelfde manier helpen algoritmen hetzelfde met meer op wiskunde gebaseerde modellen.
grafieken
Laten we een grafiek gebruiken om de verschillende manieren te illustreren waarop we een routebeschrijving kunnen geven.
We kunnen deze grafiek uitdrukken als een verbinding tussen al zijn punten. Om deze afbeelding te reproduceren, kunnen we een reeks instructies geven aan iemand anders.
Methode 1
We kunnen dit als een reeks punten voorstellen en de informatie zou de standaardvorm van grafiek = (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 na elkaar te plotten en ze te verbinden met het vorige punt. Stelt u zich echter een grafiek voor met duizend punten of meerdere segmenten die allemaal op elke manier gaan. Die lijst zou veel gegevens bevatten, toch? En dan een voor een een verbinding met elkaar maken, kan lastig zijn.
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 het volgende punt kan worden verwacht met behulp van de standaardvorm van grafiek = (startpunt, [m1, x1, h1 ], ..., [mn, xn, hn] Hier stelt de variabele 'm' de helling van de lijn voor, 'x' staat voor de richting waarin moet worden geteld (of x of y), en 'h' vertelt u hoe veel om in die richting te tellen. Je kunt ook onthouden 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 zult eindigen met dezelfde grafiek. Je kunt zien dat de laatste drie termen in deze uitdrukking hetzelfde zijn, dus we kunnen dat misschien inkorten door gewoon te zeggen "herhaal dat drie keer" op de een of andere manier. Laten we zeggen dat wanneer je de variabele 'R' ziet verschijnen, dit betekent dat je het laatste ding 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 dingen een beetje van waar ze eerder waren.
Methode 3
Laten we dit op een andere manier proberen te doen.
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, 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 kiest, hangt af van uw mogelijkheden. Misschien ben je goed met wiskunde en grafieken, dus je kiest voor de laatste optie. Misschien ben je goed in navigeren, dus kies je de tweede optie. Op het gebied van computers doe je echter veel verschillende soorten taken en de vaardigheid van de computer verandert niet echt. Daarom zijn algoritmen geoptimaliseerd voor de taken die ze uitvoeren.
Een ander belangrijk punt om op te merken is dat elke methode afhankelijk is van een sleutel. Elke set instructies is nutteloos, tenzij je weet wat je ermee moet doen. Als je niet weet dat je elk punt moet plotten en de punten moet verbinden, betekent de eerste reeks punten niets. Tenzij je weet wat elke variabele in de tweede methode betekent, weet je niet hoe je 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, extraheer 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 en alles op de achtergrond doen. Op mijn Windows 95-machine meer dan tien jaar geleden moest ik alles handmatig uitpakken voordat ik iets meer kon zien dan de bestandsnamen erin. Dat komt omdat wat op de schijf als .zip-bestand was opgeslagen, niet in een bruikbare vorm was. Denk aan een slaapbank. Als je het als een bed wilt gebruiken, moet je de kussens verwijderen en het uitklappen, wat meer ruimte in beslag neemt. Als je het niet nodig hebt, of als je het wilt transporteren, kun je het terug vouwen.
Compressiealgoritmen worden speciaal aangepast en geoptimaliseerd voor de typen bestanden waarop ze zijn getarget. 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 oorspronkelijke golfvorm. Bekijk voor meer informatie over dat verschil ons vorige artikel Wat zijn de verschillen tussen al die audio-indelingen? Lossless audioformaten en .zip-bestanden hebben één ding gemeen: ze geven beide de originele gegevens in de exacte vorm na het decompressieproces. Lossy audiocodecs gebruiken andere middelen om schijfruimte te besparen, zoals het trimmen van frequenties die niet door menselijke oren kunnen worden gehoord en het gladstrijken van de golfvorm in secties om van enig detail af te komen. Op het einde, hoewel we het verschil tussen een MP3- en een cd-nummer mogelijk niet echt kunnen horen, is er zeker een tekort aan informatie in de vorige.
Data encryptie
Algoritmen worden ook gebruikt bij het beveiligen van gegevens- of communicatielijnen. In plaats van gegevens op te slaan zodat het minder schijfruimte gebruikt, wordt het opgeslagen op een manier die niet door andere programma's kan worden gedetecteerd. Als iemand je harde schijf steelt en begint deze te scannen, kunnen ze gegevens ophalen, zelfs wanneer je bestanden verwijdert, omdat de gegevens zelf nog steeds aanwezig zijn, ook al is de doorstuurlocatie er niet meer. Wanneer gegevens worden gecodeerd, ziet wat er is opgeslagen er niet uit zoals het is. Het ziet er meestal willekeurig uit, alsof fragmentatie zich in de loop van de tijd heeft opgebouwd. U kunt ook gegevens opslaan en deze als een ander type bestand laten weergeven. Afbeeldingsbestanden en muziekbestanden zijn hier goed voor, omdat ze vrij groot kunnen zijn zonder bijvoorbeeld verdenkingen te trekken. Dit alles wordt gedaan door wiskundige algoritmen te gebruiken, die een soort input gebruiken en deze omzetten in een ander, zeer specifiek type output. Zie HTG Explains voor meer informatie over hoe encryptie werkt: wat is codering en hoe werkt het?
Algoritmen zijn wiskundige hulpmiddelen die een verscheidenheid aan toepassingen in de informatica bieden. Ze werken op een consistente manier om een pad tussen een startpunt en een eindpunt te bieden en geven de instructies om dit te volgen. Meer weten dan wat we hebben benadrukt? Deel uw uitleg in de opmerkingen!
