Algoritmeegenskaper, hva det er til, deler, eksempler

1895
David Holt
Algoritmeegenskaper, hva det er til, deler, eksempler

EN algoritme det er et sett med instruksjoner designet for å utføre en bestemt oppgave. Det vil si at det er en systematisk prosedyre som i et endelig antall trinn gir svaret på et spørsmål eller løsningen på et problem. Et eksempel på en algoritme er Googles søkemotor, der det når du setter inn et ord, gir flere resultater i form av websider.

Det kan være en kompleks prosess, som å spille av en musikkfil, eller en enkel operasjon, som å legge til to tall. I dataprogrammering opprettes algoritmer som funksjoner. Disse funksjonene er små programmer som kan refereres til av et større program.

Et bildevisningsapplikasjon kan inneholde et bibliotek med funksjoner, som hver bruker en bestemt algoritme for å representere forskjellige bildefilformater..

Et bilderedigeringsprogram kan inneholde algoritmer designet for å behandle bildedata. Noen eksempler er beskjæring, endring av størrelse, skjerping, uskarphet, redusering av røde øyne og forbedring av farger..

Artikkelindeks

  • 1 Egenskaper ved en algoritme
    • 1.1 Klarhet og presisjon
    • 1.2 Godt definerte innganger
    • 1.3 Godt definerte utganger
    • 1.4 Finhet
    • 1.5 Gjennomførbart
    • 1.6 Uavhengighet av språk
    • 1.7 Effektive programmer
  • 2 Hva er en algoritme for?
    • 2.1 Filkomprimering
    • 2.2 Datakryptering
  • 3 Hvordan fungerer en algoritme?
    • 3.1 Eksempel på tilfelle
  • 4 Deler av en algoritme
    • 4.1 Anskaffelse av inndata
    • 4.2 Beregning
    • 4.3 Valg
    • 4.4 Iterasjon
    • 4.5 Rapport om resultater eller utdata
  • 5 Typer algoritmer
    • 5.1 Rekursiv algoritme
    • 5.2 Del og erobre algoritme
    • 5.3 Dynamisk programmeringsalgoritme
    • 5.4 Brute force algoritme
    • 5.5 Backtracking-algoritme
  • 6 Eksempler på algoritmer
    • 6.1 Rekursiv algoritme
    • 6.2 Dynamisk programmeringsalgoritme
    • 6.3 Backtracking-algoritme
    • 6.4 Ulike eksempler
  • 7 Referanser

Kjennetegn ved en algoritme

Klarhet og presisjon

Algoritmen må være tydelig og entydig. Hvert av trinnene dine eller handlingene dine må være nøyaktig definert, strengt klare i alle henseender, og må utvetydig bare ha en betydning..

Godt definerte innganger

En algoritme har null eller flere innganger, hentet fra et bestemt sett med objekter. Hvis algoritmen indikerer at inngangsdata skal tas, bør disse inngangsdataene være godt definert.

Godt definerte utganger

Algoritmen har alltid en eller flere utganger, som har et forhold til inngangene. Algoritmen må tydelig definere hvilken utdata som skal produseres, og må også være godt definert.

Endelighet

Algoritmen må være endelig, det vil si at den alltid må slutte på et tidspunkt etter et endelig antall trinn, og ikke bli hekta på uendelige løkker eller lignende.

Gjennomførbart

Algoritmen må være smart og enkel, på en slik måte at den kan utføres uten problemer med de tilgjengelige ressursene. Derfor må den ikke inneholde noen fremtidig teknologi.

Språkuavhengighet

Den utformede algoritmen må være uavhengig av språket, det vil si at den bare må bestå av enkle instruksjoner som kan implementeres på hvilket som helst programmeringsspråk, og resultatet er imidlertid alltid det samme som forventet.

Effektive programmer

Det er alltid forskjellige måter å utføre en bestemt operasjon i et program. Derfor søker programmerere å skape mest mulig effektive algoritmer..

Ved bruk av svært effektive algoritmer kan det garanteres at programmene kjører i høyeste hastighet, med et minimum av systemressurser.

Imidlertid produseres ikke algoritmer alltid feilfritt første gang. Av denne grunn ønsker utviklere å forbedre dem for å inkludere dem i fremtidige programvareoppdateringer..

Derfor, når en ny versjon av et program med bedre ytelse er kjent, betyr det at denne versjonen inneholder mer effektive algoritmer.

Hva er en algoritme for?

Algoritmen er et ekstremt nyttig instrument som brukes til å utføre arbeid. I databehandling sikrer valg av den beste algoritmen at datamaskinen utfører den gitte oppgaven på best mulig måte.

Derfor tjener den til å optimalisere et dataprogram med tilgjengelige ressurser. Det vil si at når du bestemmer deg for å løse et problem gjennom de beste algoritmene, vil du ha den beste kombinasjonen av programhastighet og lavere minneforbruk.

De forskjellige algoritmene som kan studeres er like varierte som problemene de løser. Det er imidlertid veldig sannsynlig at problemet du prøver å løse ligner på et annet problem i noen henseender..

Ved å forstå et bredt spekter av algoritmer, kan du velge det som passer best for et problem og bruke det riktig.

Filkomprimering

Disse algoritmene er spesielt innstilt og optimalisert for filtypene de målretter mot. For eksempel bruker hvert lydformat en annen måte å lagre data på. Når den dekodes av lydkodeken, genererer den en lydfil som ligner på den opprinnelige bølgeformen.

Datakryptering

Algoritmer brukes også til å beskytte data eller kommunikasjonslinjer. I stedet for å lagre komprimerte data slik at de bruker mindre diskplass, lagres de på en måte som andre programmer ikke kan oppdage det. Når data blir kryptert, ser ikke det som er lagret ut som det som er.

Hvordan fungerer en algoritme?

For å få en datamaskin til å gjøre noe, må du skrive et dataprogram. For å skrive dette programmet må du fortelle datamaskinen trinn for trinn hva du vil at den skal gjøre.

Datamaskinen kjører deretter programmet og utfører hver instruksjon automatisk for å oppnå det endelige resultatet. I tillegg til å indikere hva du skal gjøre med datamaskinen, kan du også velge hvordan den skal gjøre det, gjennom algoritmen, som er den grunnleggende teknikken som brukes til å utføre arbeidet.

Eksempel tilfelle

La oss si at du har en venn som ankommer flyplassen og må reise fra flyplassen til huset vårt. Dette er fire forskjellige algoritmer som kan gis for å løse denne situasjonen:

Kall meg algoritme

- Ring flyet mitt når flyet kommer.

- Møt meg utenfor bagasjeoppfordringsområdet.

Drosjealgoritme

- Gå til taxiholdeplassen.

- Sett deg i taxi.

- Gi sjåføren min adresse.

Bussalgoritme

- Ta buss nummer 70 når du forlater flyplassen.

- Når du kommer til Main Street, ta buss 14.

- Gå av på Elmo Street.

- Gå to kvartaler nordover til huset mitt.

Algoritme leier et kjøretøy

- Ta en shuttle til stedet der de leier biler.

- Lei et kjøretøy.

- Følg GPS-instruksjonene for å komme til huset mitt.

Alle fire algoritmer oppnår nøyaktig samme mål, men hver gjør det annerledes. Hver algoritme har også forskjellig kostnad og reisetid. Derfor velges algoritmen etter omstendighetene.

Deler av en algoritme

Anskaffelse av inndata

Algoritmen må ha visse ressurser for å kunne lese verdiene fra en ekstern kilde. De fleste algoritmer krever noen dataverdier for å definere et bestemt problem. For eksempel koeffisientene til et polynom.

Beregning

Algoritmen må ha visse ressurser for å kunne utføre aritmetiske beregninger, sammenligninger, sjekke logiske forhold osv..

Utvalg

Algoritmen må ha visse midler for å kunne velge mellom to eller flere mulige handlingsmåter, basert på innledende data, brukerinngang og / eller beregnede resultater..

Iterasjon

Algoritmen må ha visse midler for å kunne utføre et sett med instruksjoner gjentatte ganger, enten for et fast antall ganger eller til noen logisk tilstand er oppfylt.

Rapport om resultater eller utdata

Algoritmen må ha visse ressurser for å kunne informere brukeren om resultatene den har beregnet, eller for å kunne be om ytterligere data fra brukeren.

Typer algoritmer

Rekursiv algoritme

Denne algoritmen er veldig interessant, fordi den kaller seg med en annen verdi som inndataparameter, som den fikk etter å ha løst den forrige inndataparameteren. Det vil si at den kaller seg gjentatte ganger til problemet er løst.

Problemer som Tower of Hanoi eller det dype søket i en graf kan enkelt løses ved hjelp av denne typen algoritmer..

Del og erobre algoritme

I disse algoritmene er den delt inn i to deler. I den første delen er det aktuelle problemet delt inn i mindre delproblemer av samme type. På samme måte løses delproblemene i andre del, og deretter kombineres begge deler for å produsere den endelige løsningen på problemet..

For eksempel, med disse algoritmene kan du utføre kombinasjonssortering og rask sortering.

Dynamisk programmeringsalgoritme

Disse algoritmene fungerer ved å huske resultatene fra forrige løp og bruke dem til å finne nye resultater. Det vil si at de løser komplekse problemer ved å dele dem opp i flere enkle underproblemer og deretter løse hver enkelt av dem og lagre dem senere for senere bruk..

Brute force algoritme

Denne algoritmen søker blindt etter alle mulige løsninger for å finne en eller flere løsninger som kan løse en funksjon. Du kan tenke på brute force som å bruke alle mulige kombinasjoner av tall for å åpne en safe..

Tilbakeslagsalgoritme

Denne algoritmen løser problemer rekursivt og prøver å løse et problem ved å løse hver del av den. Hvis løsningen mislykkes, fjernes den og spores tilbake for å finne en annen løsning.

Det vil si at denne algoritmen løser et underproblem, men hvis dette ikke løser det totale problemet, angrer det det siste trinnet og begynner på nytt for å finne løsningen på problemet..

Eksempler på algoritmer

Rekursiv algoritme

Denne pseudokoden finner faktoren til et ikke-negativt heltall "N" ved hjelp av en rekursjonsalgoritme:

Dynamisk programmeringsalgoritme

Fibonacci-sekvensen er et godt eksempel på en dynamisk programmeringsalgoritme. Du kan se det i denne pseudokoden:

- Hvis (N = 0 eller N = 1), er Fibonacci (N) = 0

- Hvis ikke, er Fibonacci (N) = Fibonacci (N-1) + Fibonacci (N-2)

Tilbakeslagsalgoritme

De 8 dronningene sjakkproblem er et godt eksempel. Dette problemet fastslår at det er 8 dronningstykker på et sjakkbrett, og de må plasseres på en slik måte at ingen av dronningene er i stand til å angripe noen andre etter at de er organisert..

Ulike eksempler

- Algoritme for HIV-diagnose.

Algoritme for diagnostisering av HIV. Kilde: Immunopedia / CC BY-SA (https://creativecommons.org/licenses/by-sa/4.0)

- Søkemotorer på Internett bruker proprietære algoritmer for å vise de mest relevante resultatene fra søkeindeksen for spesifikke spørsmål..

- Oppskrifter, som matematiske ligninger, er algoritmer.

- E-post vet hvor du skal sende takk til algoritmer.

- Innholdet sett på sosiale nettverk kommer gjennom algoritmer. Faktisk er alt som gjøres på nettet et produkt av algoritmer.

- Videospill er algoritmisk historiefortelling.

- Smartphone-apper er bare algoritmer.

- De fleste økonomiske transaksjoner utføres ved hjelp av algoritmer.

- Hver gang en kolonne blir sortert i et regneark, griper algoritmer inn.

Referanser

  1. Lee Rainie (2017). Kodeavhengig: Fordeler og ulemper med algoritmealderen. Pew Research Center. Hentet fra: pewresearch.org.
  2. Tekniske vilkår (2020). Algoritme. Hentet fra: techterms.com.
  3. Britannica (2020). Algoritme. Hentet fra: britannica.com.
  4. Educba (2020). Typer algoritmer. Hentet fra: educba.com.
  5. How to Geek (2016). Hva er datalgoritmer, og hvordan fungerer de? Hentet fra: howtogeek.com.
  6. How Stuff Works (2020). Hva er en datalgoritme? Hentet fra: computer.howstuffworks.com.

Ingen har kommentert denne artikkelen ennå.