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 de 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 på forhånd, eller finne ut i løpet av prosessen.
Fra START vil du hodet nedover banen, og avhengig av hva som skjer, følger du "strømmen" til et sluttresultat. Flytdiagrammer er visuelle verktøy som mer forståelig kan representere et sett med instruksjoner som brukes av datamaskiner. På samme måte bidrar algoritmer til å gjøre det samme med flere matematikkbaserte modeller.
grafer
La oss bruke en graf for å illustrere de ulike måtene vi kan gi retninger.
Vi kan uttrykke denne grafen som en sammenheng mellom alle punkter. 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)}.
graph = {(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 punkter eller flere segmenter, alle går på hvilken måte. Den listen ville ha mye data, ikke sant? Og da må du koble hverandre, 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.
graph = {(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 uttrykkene 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:
graph = {(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 tre siste seksjonene slik:
graph = {(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≤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
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≤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
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 datamaskins 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 med 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 inni 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 var 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 til å 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? Lossless lydformater og.zip-filer har en ting til felles: de gir begge opprinnelige dataene i eksakt 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 utjevner bølgeformen i seksjoner for å kvitte seg med 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 er matematiske verktøy som gir en rekke bruksområder i datavitenskap. De jobber for å gi en bane mellom et startpunkt og et sluttpunkt på en konsekvent måte, og gir instruksjonene for å følge den. Vet mer enn det vi fremhevet? Del forklaringene i kommentarene!