Såvida du inte gillar matematik eller programmering kan ordet "algoritm" vara grekiskt för dig, men det är en av byggstenarna i allt du använder för att läsa den här artikeln. Här är en snabb förklaring av vad de är och hur de fungerar.
Ansvarsfriskrivning: Jag är inte matte- eller datalogi-lärare, så inte alla termer jag använder är tekniska. Det beror på att jag försöker förklara allt på vanlig engelska för att människor inte är riktigt bekväma med matematik. Med detta sagt är det matematik involverat, och det är oundvikligt. Matematiska nördar, gärna korrigera eller förklara bättre i kommentarerna, men snälla, håll det enkelt för de matematiskt böjda bland oss.
Bild av Ian Ruotsala
Vad är en algoritm?
Ordet "algoritm" har en etymologi som liknar "algebra", förutom att detta hänvisar till den arabiska matematikern själv, al-Khwarizmi (bara en intressant godbit). En algoritm, för de icke-programmerare bland oss, är en uppsättning instruktioner som tar en ingång, A, och ger en utgång, B, som ändrar data involverad på något sätt. Algoritmer har ett stort antal applikationer. I matematik kan de hjälpa till att beräkna funktioner från punkter i en datamängd, bland mycket mer avancerade saker. Bortsett från deras användning i själva programmeringen spelar de stora roller i saker som filkomprimering och datakryptering.
En grundläggande uppsättning instruktioner
Låt oss säga att din vän träffar dig i en livsmedelsbutik och du guidar honom mot dig. Du säger saker som "kom in genom dörrarna till höger", "passera fiskavsnittet till vänster" och "om du ser mejeriet passerade du mig." Algoritmer fungerar så. Vi kan använda ett flödesschema för att illustrera instruktioner baserat på kriterier som vi känner till i förväg eller ta reda på under processen.
(bild med titeln “ Isbrytande rutin ”EDIT: med tillstånd av Trigger och frihjul )
Från START skulle du gå nerför vägen, och beroende på vad som händer följer du "flödet" till ett slutresultat. Flödesscheman är visuella verktyg som mer förståeligt kan representera en uppsättning instruktioner som används av datorer. På samma sätt hjälper algoritmer att göra detsamma med mer mattebaserade modeller.
Grafer
Låt oss använda ett diagram för att illustrera de olika sätten vi kan ge vägbeskrivning på.
Vi kan uttrycka denna graf som en koppling mellan alla dess punkter. För att återge den här bilden kan vi ge en uppsättning instruktioner till någon annan.
Metod 1
Vi kan representera detta som en serie punkter, och informationen skulle följa standardformen för graf = {(x1, y1), (x2, y2), …, (xn, yn)}.
graf = {(0,0), (3,0), (3,3), (5,5), (7,10), (8,7), (9,4), (10,1)}
Det är ganska enkelt att plotta varje punkt, en efter en, och ansluta dem till den föregående punkten. Föreställ dig dock en graf med tusen poäng eller flera segment som alla går åt vart som helst. Den listan skulle ha mycket data, eller hur? Och då kan det vara ont att behöva ansluta var och en, en i taget.
Metod 2
En annan sak vi kan göra är att ge en startpunkt, lutningen på linjen mellan den och nästa punkt, och ange var nästa punkt kan förväntas med hjälp av standardformen för graf = {(starting point}, [m1, x1, h1],…, [mn, xn, hn]}. Här representerar variabeln 'm' linjens lutning, 'x' representerar riktningen att räkna i (antingen x eller y) och 'h' berättar hur många som ska räknas i nämnda riktning. Du kan också komma ihåg att plotta en punkt efter varje rörelse.
graf = {(0,0), [0,x,3], [0,y,3], [1,x,2], [2.5,x,2], [-3,x,1], [-3,x,1], [-3,x,1]}
Du får samma diagram. Du kan se att de sista tre termerna i detta uttryck är desamma, så vi kan kanske klippa ner det genom att bara säga ”upprepa det tre gånger” på något sätt. Låt oss säga att när du ser variabeln 'R' visas betyder det att du upprepar det sista. Vi kan göra det här:
graf = {(0,0), [0,x,3], [0,y,3], [1,x,2], [2.5,x,2], [-3,x,1], [R=2]}
Vad händer om de enskilda punkterna inte spelar någon roll, och bara själva diagrammet gör det? Vi kan konsolidera de tre sista avsnitten så:
graf = {(0,0), [0,x,3], [0,y,3], [1,x,2], [2.5,x,2], [-3,x,3]}
Det förkortar saker lite från var de var tidigare.
Metod 3
Låt oss försöka göra det på ett annat sätt.
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
Här har vi det i rena algebraiska termer. Återigen, om själva punkterna inte spelar någon roll och bara grafen gör det, kan vi konsolidera de tre sista objekten.
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
Nu, vilken metod du väljer beror på dina förmågor. Du kanske är bra med matematik och diagram, så du väljer det sista alternativet. Du kanske är bra på att navigera, så du väljer det andra alternativet. På datorerna gör du dock många olika typer av uppgifter och datorns förmåga förändras inte riktigt. Därför är algoritmer optimerade för de uppgifter de slutför.
En annan viktig punkt att notera är att varje metod är beroende av en nyckel. Varje uppsättning instruktioner är värdelösa om du inte vet vad du ska göra med dem. Om du inte vet att du ska plotta varje punkt och ansluta punkterna betyder den första uppsättningen punkter ingenting. Om du inte vet vad varje variabel betyder i den andra metoden vet du inte hur du använder dem, ungefär som nyckeln till en kryptering. Den nyckeln är också en integrerad del av att använda algoritmer, och ofta finns den nyckeln i samhället eller via en "standard".
Filkomprimering
När du laddar ner en .zip-fil extraherar du innehållet så att du kan använda vad som helst i det. Numera kan de flesta operativsystem dyka in i .zip-filer som de var normala mappar och göra allt i bakgrunden. På min Windows 95-maskin för över ett decennium sedan var jag tvungen att extrahera allt manuellt innan jag kunde se något mer än filnamnen inuti. Det beror på att det som lagrades på disken som en .zip-fil inte var i användbar form. Tänk på en utdragbar soffa. När du vill använda den som en säng måste du ta bort kuddarna och fälla ut den, vilket tar mer plats. När du inte behöver det eller om du vill transportera det kan du fälla upp det igen.
Kompressionsalgoritmer justeras och optimeras specifikt för de typer av filer de är inriktade på. Ljudformat använder till exempel var och en för sig att lagra data som, när de avkodas av ljudkodeken, ger en ljudfil som liknar den ursprungliga vågformen. För mer information om skillnaden, kolla in vår tidigare artikel, Vad är skillnaderna mellan alla dessa ljudformat? Förlustfria ljudformat och .zip-filer har en sak gemensamt: de ger båda originaldata i sin exakta form efter dekomprimeringsprocessen. Förlust av ljudkodek använder andra metoder för att spara diskutrymme, som att trimma frekvenser som inte kan höras av mänskliga öron och jämna ut vågformen i sektioner för att bli av med några detaljer. I slutändan, även om vi kanske inte verkligen kan höra skillnaden mellan en MP3 och ett CD-spår, finns det definitivt ett underskott på information i det förra.
Datakryptering
Algoritmer används också för att säkra data eller kommunikationslinjer. Istället för att lagra data så att den använder mindre diskutrymme lagras den på ett sätt som inte kan upptäckas av andra program. Om någon stjäl din hårddisk och börjar skanna den, kan de hämta data även när du tar bort filer eftersom själva data fortfarande finns kvar, även om vidarebefordringsplatsen till den är borta. När data krypteras ser allt som lagras inte ut som det är. Det ser vanligtvis slumpmässigt ut som om fragmentering hade byggts upp över tiden. Du kan också lagra data och få dem att se ut som en annan filtyp. Bildfiler och musikfiler är bra för detta, eftersom de till exempel kan vara ganska stora utan att dra misstanke om det. Allt detta görs med hjälp av matematiska algoritmer, som tar någon form av input och konverterar den till en annan, mycket specifik typ av output. För mer information om hur kryptering fungerar, kolla in HTG förklarar: Vad är kryptering och hur fungerar det?
Algoritmer är matematiska verktyg som ger en mängd olika användningsområden inom datavetenskap. De arbetar för att skapa en väg mellan en startpunkt och en slutpunkt på ett konsekvent sätt och ger instruktioner för att följa den. Vet du mer än vad vi lyfte fram? Dela dina förklaringar i kommentarerna!
