Hvad er computeralgoritmer, og hvordan virker de?

Medmindre du er i matematik eller programmering, kan ordet "algoritme" være græsk til dig, men det er en af byggestenene i alt, hvad du bruger til at læse denne artikel. Her er en hurtig forklaring på, hvad de er, og hvordan de virker.

Ansvarsfraskrivelse: Jeg er ikke en matematik eller computervidenskabslærer, så ikke alle de vilkår jeg bruger er tekniske. Det er fordi jeg forsøger at forklare alt i ren engelsk, fordi folk ikke er helt fortrolige med matematik. Når det er sagt, er der noget matematik involveret, og det er uundgåeligt. Math geeks, er du velkommen til at korrigere eller bedre forklare i kommentarerne, men vær venlig at holde det enkelt for det matematisk uhensigtsmæssige blandt os.

Billede af Ian Ruotsala

Hvad er en algoritme?

Ordet 'algoritme' har en etymologi svarende til 'algebra', bortset fra at dette henviser til den arabiske matematiker selv, al-Khwarizmi (bare en interessant tidbit). En algoritme for de ikke-programmører blandt os er et sæt instruktioner, der tager et input, A, og giver en output, B, der ændrer de involverede data på en eller anden måde. Algoritmer har en bred vifte af applikationer. I matematik kan de hjælpe med at beregne funktioner fra punkter i et datasæt blandt langt mere avancerede ting. Bortset fra deres brug i programmeringen selv spiller de store roller i ting som filkomprimering og datakryptering.

Et grundlæggende sæt af instruktioner

Lad os sige, at din ven møder dig i en købmand, og du leder ham til dig. Du siger ting som "komme ind gennem højre sidedøre", "send fiskesektionen til venstre", og "hvis du ser mejeriet, passerede du mig." Algoritmer fungerer sådan. Vi kan bruge et rutediagram til at illustrere instruktioner baseret på kriterier, vi kender i forvejen, eller finde ud af under processen.

(billede med titlen "Icebreaking Routine" EDIT: høflighed af Trigger og Freewheel)

Fra START vil du gå ned ad stien, og afhængigt af hvad der sker, følger du "flow" til et slutresultat. Flowcharts er visuelle værktøjer, der mere forståeligt kan repræsentere et sæt instruktioner, der bruges af computere. På samme måde hjælper algoritmer med at gøre det samme med flere matematiske modeller.

Grafer

Lad os bruge en graf til at illustrere de forskellige måder, vi kan give retninger.

Vi kan udtrykke denne graf som en forbindelse mellem alle dens punkter. For at reproducere dette billede kan vi give et sæt instruktioner til en anden.

Metode 1

Vi kan repræsentere dette som en række punkter, og oplysningerne følger standardformen for 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 er ret nemt at plotte hvert punkt, den ene efter den anden, og forbinde dem med det forrige punkt. Men forestil dig en graf med tusind punkter eller flere segmenter, der alle går hver eneste vej. Denne liste ville have mange data, ikke? Og derefter at skulle forbinde hver enkelt, en ad gangen, kan være en smerte.

Metode 2

En anden ting, vi kan gøre, er at give et udgangspunkt, hældningen af linjen mellem det og det næste punkt og angive, hvor du kan forvente det næste punkt ved hjælp af standardformularen for graf = (startpunkt, [m1, x1, h1 ], ..., [mn, xn, hn]. Her repræsenterer variablen 'm' hældningen af linjen, 'x' repræsenterer retningen til at tælle ind (hvad enten x eller y), og 'h' fortæller dig hvordan mange til at tælle i retningen. Du kan også huske at plotte et punkt efter hver bevægelse.

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 ender med den samme graf. Du kan se, at de sidste tre udtryk i dette udtryk er ens, så vi kan muligvis trimme det ned ved blot at sige "gentage det tre gange" på en eller anden måde. Lad os sige, at når som helst du ser variablen 'R' vises, betyder det at gentage det sidste. Vi kan gøre det:

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

Hvad hvis de enkelte punkter ikke rigtig betyder noget, og kun grafen selv gør det? Vi kan konsolidere de sidste tre sektioner som sådan:

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

Det forkorter ting lidt fra, hvor de var før.

Metode 3

Lad os prøve at gøre det på en anden måde.

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

Her har vi det i rene algebraiske termer. Endnu en gang, hvis punkterne selv ikke betyder noget, og kun grafen gør det, kan vi konsolidere de sidste tre elementer.

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

Nu, hvilken metode du vælger afhænger af dine evner. Måske har du det godt med matematik og grafik, så du vælger den sidste mulighed. Måske er du god til at navigere, så du vælger den anden mulighed. I computerernes rige laver du mange forskellige opgaver, og computerens evne ændrer sig ikke rigtig. Derfor er algoritmer optimeret til de opgaver, de gennemfører.

Et andet vigtigt punkt at bemærke er, at hver metode er afhængig af en nøgle. Hvert sæt instruktioner er ubrugeligt, medmindre du ved hvad de skal gøre med dem. Hvis du ikke ved, at du skal plotte hvert punkt og forbinde prikkene, betyder det første sæt punkter ikke noget. Medmindre du ved, hvad hver variabel betyder i den anden metode, ved du ikke hvordan man skal anvende dem, ligesom nøglen til en chiffer. Denne nøgle er også en integreret del af brugen af algoritmer, og ofte findes den nøgle i samfundet eller via en "standard".

Filkomprimering

Når du downloader en .zip-fil, udtrækker du indholdet, så du kan bruge hvad der er indeni. I dag kan de fleste operativsystemer dykke ind i .zip-filer som de var normale mapper, gør alt i baggrunden. På min Windows 95-maskine for over et årti siden måtte jeg udtrække alt manuelt, før jeg kunne se noget mere end filnavnet indeni. Det skyldes, at hvad der blev gemt på disken som en .zip-fil, ikke var i en brugbar form. Tænk på en udtrækssofa. Når du vil bruge det som en seng, skal du fjerne puderne og udfolde det, hvilket tager mere plads. Når du ikke har brug for det, eller du vil transportere det, kan du folde det igen.

Komprimeringsalgoritmer tilpasses og optimeres specifikt til de typer filer, de er målrettet mod. Lydformater, for eksempel, bruger hver en anden måde til at gemme data, der, når de afkodes af lydkoden, vil give en lydfil, der ligner den oprindelige bølgeform. For mere information om denne forskel, se vores tidligere artikel, Hvad er forskellene mellem alle disse lydformater? Uslettede lydformater og .zip-filer har én ting til fælles: de giver begge de originale data i sin nøjagtige form efter dekomprimeringsprocessen. Lossy audio codecs bruger andre midler til at spare diskplads, såsom trimning af frekvenser, der ikke kan høres af menneskelige ører og udjævning af bølgeformen i sektioner for at slippe af med nogle detaljer. I sidste ende, selv om vi måske ikke kan høre forskellen mellem en MP3 og et cd-spor, er der helt sikkert et underskud på information i det tidligere.

Datakryptering

Algoritmer bruges også til sikring af data- eller kommunikationslinjer. I stedet for at lagre data, så den bruger mindre diskplads, gemmes den på en måde, der ikke kan opdages af andre programmer. Hvis nogen stjæler din harddisk og begynder at scanne det, kan de hente data, selv når du sletter filer, fordi dataene selv er der stadig, selvom viderestillingsstedet er væk. Når data krypteres, bliver alt, hvad der er lagret, ikke som det er. Det ser som regel tilfældigt ud, som om fragmentering havde bygget op over tid. Du kan også gemme data og gøre det til en anden type fil. Billedfiler og musikfiler er gode til dette, da de kan være ret store uden at tegne mistanker, for eksempel. Alt dette gøres ved hjælp af matematiske algoritmer, som tager en slags input og konverterer det til en anden, meget specifik type output. For mere information om, hvordan kryptering fungerer, skal du tjekke HTG Forklarer: Hvad er kryptering og hvordan virker det?

Algoritmer er matematiske værktøjer, der giver en bred vifte af anvendelser inden for datalogi. De arbejder for at give en vej mellem et startpunkt og et slutpunkt på en ensartet måde, og giver vejledningen til at følge den. Vide mere end hvad vi fremhævede? Del dine forklaringer i kommentarerne!