Hva er Computer Algoritmer, og hvordan fungerer de?
Med mindre du er i matte eller programmering, kan ordet "algoritme" være gresk til deg, men det er en av byggesteinene til alt du bruker for å lese denne artikkelen. Her er en rask forklaring på hva de er, og hvordan de fungerer.
Ansvarsfraskrivelse: Jeg er ikke en matematikk- eller informatikklærer, så ikke alle vilkårene jeg bruker er tekniske. Det er fordi jeg prøver å forklare alt på vanlig engelsk fordi folk ikke er ganske komfortabel med matte. Når det er sagt, er det noen matte involvert, og det er uunngåelig. Math geeks, vær så snill å korrigere eller bedre forklare i kommentarene, men vær så snill, hold det enkelt for den matematisk disinclined blant oss.
Bilde av Ian Ruotsala
Hva er en algoritme?
Ordet 'algoritme' har en etymologi som ligner på 'algebra', bortsett fra at dette refererer til den arabiske matematikeren selv, al-Khwarizmi (bare en interessant tidbit). En algoritme, for de ikke-programmører blant oss, er et sett med instruksjoner som tar en inngang, A, og gir en utgang, B, som endrer dataene som er involvert på en eller annen måte. Algoritmer har et bredt spekter av applikasjoner. I matte kan de bidra til å beregne funksjoner fra punkter i et datasett, blant mye mer avanserte ting. Bortsett fra deres bruk i selve programmeringen, spiller de store roller i ting som filkomprimering og datakryptering.
Et grunnleggende sett med instruksjoner
La oss si at vennen din møter deg i en matbutikk, og du veileder ham mot deg. Du sier ting som "kom inn gjennom høyre dører", "pass fiskeseksjonen til venstre", og "hvis du ser meieriet, passerte du meg." Algoritmer fungerer slik. Vi kan bruke et flytskjema for å illustrere instruksjoner basert på kriteriene vi kjenner til i forveien eller finne ut i løpet av prosessen.
(bildet heter "Icebreaking Routine" EDIT: høflighet av Trigger og Freewheel)
Fra START vil du gå nedover banen, og avhengig av hva som skjer, følger du "flyt" til et sluttresultat. Flytdiagrammer er visuelle verktøy som mer forståelig kan representere et sett med instruksjoner som brukes av datamaskiner. Tilsvarende hjelper algoritmer til å gjøre det samme med flere matematikkbaserte modeller.
grafer
La oss bruke en graf for å illustrere de forskjellige måtene vi kan gi retninger.
Vi kan uttrykke denne grafen som en forbindelse mellom alle punktene. For å reprodusere dette bildet kan vi gi et sett med instruksjoner til noen andre.
Metode 1
Vi kan representere dette som en serie punkter, og informasjonen vil følge 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 ganske enkelt å plotte hvert punkt, den ene etter den andre, og koble dem til det forrige punktet. Imidlertid forestille du en graf med tusen poeng eller flere segmenter, alle går på hvilken måte. Den listen ville ha mye data, ikke sant? Og da må du koble hver og en, en om gangen, være en smerte.
Metode 2
En annen ting vi kan gjøre er å gi utgangspunkt, helling av linjen mellom det og neste punkt, og angi hvor du kan forvente neste punkt ved å bruke standardformen for graf = (startpunkt), [m1, x1, h1 ], ..., [mn, xn, hn]. Her representerer variabelen 'm' helling av linjen, 'x' representerer retningen som skal telle inn (enten x eller y), og 'h' forteller deg hvordan mange til å telle i retningen. Du kan også huske å plotte et poeng etter hver bevegelse.
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 vil ende opp med den samme grafen. Du kan se at de tre siste begrepene i dette uttrykket er de samme, så vi kan kanskje trimme det ned ved å bare si "gjenta det tre ganger" på en eller annen måte. La oss si at når som helst ser du variabelen 'R', betyr det å gjenta det siste. Vi kan gjøre dette:
graf = (0,0), [0, x, 3], [0, y, 3], [1, x, 2], [2,5, x, 2], [-3, x, 1] [R = 2]
Hva om de enkelte punktene egentlig ikke betyr noe, og bare grafen selv gjør det? Vi kan konsolidere de siste tre seksjonene slik:
graf = (0,0), [0, x, 3], [0, y, 3], [1, x, 2], [2,5, x, 2], [-3, x, 3]
Det forkorter ting litt fra hvor de var før.
Metode 3
La oss prøve å gjøre dette på en annen måte.
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. Igjen, hvis poengene selv ikke har betydning og bare grafen gjør, kan vi konsolidere de tre siste elementene.
y = 0, 0
x = 0, 0 y = x, 3 y = 2,5x-7,5, 5 y = -3x + 29, 7
Nå, hvilken metode du velger, avhenger av dine evner. Kanskje du er flott med matte og grafer, så du velger det siste alternativet. Kanskje du er god til å navigere, så du velger det andre alternativet. I datamaskers rike gjør du imidlertid mange forskjellige typer oppgaver, og datamaskinens evne endres ikke egentlig. Derfor er algoritmer optimalisert for oppgavene de fullfører.
Et annet viktig poeng å merke seg er at hver metode er avhengig av en nøkkel. Hvert sett med instruksjoner er ubrukelig med mindre du vet hva du skal gjøre med dem. Hvis du ikke vet at du skal plotte hvert punkt og koble prikkene, betyr det første settet av punkter ingenting. Med mindre du vet hva hver variabel betyr i den andre metoden, vet du ikke hvordan du skal bruke dem, akkurat som nøkkelen til en kryptering. Denne nøkkelen er også en integrert del av bruk av algoritmer, og ofte er nøkkelen funnet i fellesskapet eller via en "standard".
Filkomprimering
Når du laster ned en .zip-fil, trekker du ut innholdet slik at du kan bruke det som er inne i det. I dag kan de fleste operativsystemer dykke inn i .zip-filer som de var normale mapper, gjør alt i bakgrunnen. På min Windows 95-maskin over et tiår siden måtte jeg pakke ut alt manuelt før jeg kunne se noe mer enn filnavnene inni. Det er fordi det som ble lagret på disken som en .zip-fil, ikke var i brukbar form. Tenk på en uttrekkbar sofa. Når du vil bruke den som en seng, må du fjerne puttene og utfolde den, noe som tar opp mer plass. Når du ikke trenger det, eller du vil transportere det, kan du kaste det opp igjen.
Komprimeringsalgoritmer justeres og optimaliseres spesielt for hvilke typer filer de er målrettet mot. Lydformater, for eksempel, bruker hver en annen måte å lagre data som, når de dekodes av lydkoden, vil gi en lydfil som ligner på den opprinnelige bølgeformen. For mer informasjon om forskjellen, sjekk ut vår forrige artikkel, Hva er forskjellene mellom alle lydformatene? Uslettede lydformater og .zip-filer har en ting til felles: de gir begge opprinnelige dataene i nøyaktig form etter prosessen med dekomprimering. Lossy audio codecs bruker andre metoder for å spare diskplass, for eksempel trimming av frekvenser som ikke kan høres av menneskelige ører og utjevne bølgeformen i seksjoner for å kvitte seg med noen detaljer. Til slutt, mens vi kanskje ikke kan høre forskjellen mellom en MP3 og et CD-spor, er det definitivt et underskudd av informasjon i det tidligere.
Datakryptering
Algoritmer brukes også når data eller kommunikasjonslinjer sikres. I stedet for å lagre data slik at den bruker mindre diskplass, lagres den på en måte som ikke kan oppdages av andre programmer. Hvis noen stjeler harddisken din og begynner å skanne den, kan de hente data selv når du sletter filer fordi dataene selv er der, selv om videresendingsstedet til det er borte. Når data er kryptert, blir det som lagres, ikke som det er. Det ser vanligvis ut som tilfeldig, som om fragmentering hadde bygd opp over tid. Du kan også lagre data og få den til å vises som en annen type fil. Bildefiler og musikkfiler er gode for dette, da de kan være ganske store uten å tegne mistanke, for eksempel. Alt dette gjøres ved å bruke matematiske algoritmer, som tar noen form for inngang og konverterer den til en annen, veldig spesifikk type utgang. For mer informasjon om hvordan kryptering fungerer, sjekk ut HTG Forklarer: Hva er kryptering og hvordan fungerer det?
Algoritmer er matematiske verktøy som gir en rekke bruksområder innen datavitenskap. De arbeider for å gi en bane mellom et startpunkt og et sluttpunkt på en konsekvent måte, og gi instruksjonene for å følge den. Vet mer enn det vi fremhevet? Del forklaringene i kommentarene!
