Hemsida » hur » Vad är datoralgoritmer, och hur fungerar de?

    Vad är datoralgoritmer, och hur fungerar de?

    Om du inte är i matte 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.

    Ansvarsbegränsning: Jag är ingen matematik eller datavetenskapslärare, så inte alla termer jag använder är tekniska. Det beror på att jag försöker förklara allt på vanlig engelska eftersom människor inte är ganska bekväma med matte. Det sägs att det finns en del matematik, och det är oundvikligt. Math geeks, gärna rätta eller bättre förklara i kommentarerna, men snälla, håll det enkelt för den matematiskt obehagliga bland oss.

    Bild av Ian Ruotsala

    Vad är en algoritm?

    Ordet "algoritm" har en etymologi som liknar "algebra", förutom att det här hänvisar till den arabiska matematikern själv, al-Khwarizmi (bara en intressant tidbit). En algoritm, för de icke-programmerare bland oss, är en uppsättning instruktioner som tar en inmatning, A, och tillhandahåller en utgång, B, som ändrar de uppgifter som är inblandade på något sätt. Algoritmer har ett brett utbud av applikationer. I matematik kan de hjälpa till att beräkna funktioner från punkter i en dataset, 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 mataffär och du leder honom mot dig. Du säger saker som "komma in genom högra dörrarna", "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 baserade på kriterier vi vet tidigare eller upptäcka under processen.

    (bild med titeln "Icebreaking Routine" EDIT: Med tillstånd av Trigger och Freewheel)

    Från START skulle du gå ner på vägen, och beroende på vad som händer följer du flödet till ett slutresultat. Flödesdiagram är visuella verktyg som mer begripligt kan representera en uppsättning instruktioner som används av datorer. På samma sätt hjälper algoritmer att göra detsamma med fler matematikbaserade modeller.

    grafer

    Låt oss använda ett diagram för att illustrera de olika sätten vi kan ge vägbeskrivningar.

    Vi kan uttrycka denna graf som en koppling mellan alla dess punkter. För att reproducera 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 grafen = (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 lätt att plotta varje punkt, en efter en och koppla dem till föregående punkt. Föreställ dig dock en graf med tusen punkter eller flera segment som alla går på vilket sätt. Den listan skulle ha mycket data, eller hur? Och då måste man ansluta var och en, en i taget, vara en smärta.

    Metod 2

    En annan sak vi kan göra är att ge en startpunkt, lutningen av linjen mellan den och nästa punkt och ange var du kan förvänta dig nästa punkt med hjälp av standardformen för graf = (utgångspunkt, [m1, x1, h1 ], ..., [mn, xn, hn]. Här representerar variabeln 'm' linjens lutning, 'x' representerar riktningen att räkna in (om x eller y) och 'h' berättar hur många att räkna i den riktningen. 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 kommer att sluta med samma graf. Du kan se att de tre sista termerna i det här uttrycket är desamma, så vi kanske kan trimma det med att bara säga "upprepa det tre gånger" på något sätt. Låt oss säga att när som helst ser du 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 poängen inte spelar någon roll, och bara grafen själv gör det? Vi kan konsolidera de sista tre sektionerna som så:

    graf = (0,0), [0, x, 3], [0, y, 3], [1, x, 2], [2,5, x, 2], [-3, x, 3]

    Det förkortar saker upp lite från var de var före.

    Metod 3

    Låt oss försöka göra det på ett annat sätt.

    y = 0, 0 x = 0, 0 y = x, 3 y = 2,5x-7,5, 5 y = -3x + 29, 7 y = -3x + 29, 8 y = -3x + 29, 9

    Här har vi det i rena algebraiska termer. Återigen, om punkterna själva inte spelar någon roll och bara grafen gör det, kan vi konsolidera de tre sista objekten.

    y = 0, 0 x = 0, 0 y = x, 3 y = 2,5x-7,5, 5 y = -3x + 29, 7

    Nu, vilken metod du väljer beror på dina förmågor. Kanske är du bra med matte och grafer, så du väljer det sista alternativet. Kanske är du bra på att navigera, så du väljer det andra alternativet. I datorns rike gör du dock många olika typer av uppgifter och datorns förmåga förändras inte riktigt. Därför optimeras algoritmer för de uppgifter de utför.

    En annan viktig sak att notera är att varje metod bygger på en nyckel. Varje uppsättning instruktioner är värdelös om du inte vet vad du ska göra med dem. Om du inte vet att du ska plotta varje punkt och ansluta prickarna, betyder den första uppsättningen punkter ingenting. Om du inte vet vad varje variabel betyder i den andra metoden, vet du inte hur man applicerar dem, precis som nyckeln till en chiffer. Den här 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 hämtar en .zip-fil tar du ut innehållet så att du kan använda vad som helst inom den. Numera kan de flesta operativsystem dyka in i .zip-filer som de var normala mappar, gör allt i bakgrunden. På min Windows 95-maskin för över tio år sedan var jag tvungen att extrahera allt manuellt innan jag kunde se något mer än filnamnen inuti. Det beror på att det som lagrats på skivan 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 öppna den, vilket tar upp mer utrymme. När du inte behöver det, eller om du vill transportera det, kan du lägga det tillbaka.

    Komprimeringsalgoritmer anpassas och optimeras specifikt för de typer av filer de riktar sig till. Ljudformat, till exempel, använder sig av olika sätt för att lagra data som, när de avkodas av ljudkoden, kommer att ge 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? Lossless ljudformat och .zip-filer har en sak gemensamt: de båda ger de ursprungliga uppgifterna i exakt form efter processen med dekompression. Lossy audio codecs använder andra metoder för att spara diskutrymme, såsom trimmfrekvenser som inte kan höras av mänskliga öron och utjämnar vågformen i sektioner för att bli av med detaljer. I slutändan, medan vi kanske inte kan höra skillnaden mellan en MP3 och ett CD-spår, finns det definitivt ett underskott av information i det tidigare.

    Datakryptering

    Algoritmer används också vid säkring av data- eller kommunikationslinjer. Istället för att lagra data så att det använder mindre diskutrymme lagras det 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 dataen är kvar där, även om vidarebefordringsplatsen till den är borta. När data krypteras, så är det som lagras inte som det är. Det ser oftast slumpmässigt ut som om fragmenteringen hade byggt upp över tiden. Du kan också lagra data och få den att visas som en annan typ av fil. Bildfiler och musikfiler är bra för detta, eftersom de kan vara ganska stora utan att exempelvis dra misstankar. Allt detta görs genom att använda matematiska algoritmer, som tar någon form av inmatning och konverterar den till en annan, mycket specifik typ av utdata. 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 användningsområden inom datavetenskap. De arbetar för att ge en väg mellan en startpunkt och en slutpunkt på ett konsekvent sätt och ge instruktionerna för att följa det. Vet mer än vad vi lyfte fram? Dela dina förklaringar i kommentarerna!