Flere forskjellige algoritmer kan utvikles for å løse det samme problemet. Derfor oppstår oppgaven med å velge de mest effektive algoritmene. Merk at nøyaktig vurdering av effektiviteten til algoritmer er en svært vanskelig oppgave og krever spesiell forskning i hvert enkelt tilfelle.

Den delen av teorien om algoritmer som omhandler å estimere egenskapene til algoritmer kalles metrisk. Den kan deles inn i beskrivende (kvalitativ) og metrisk (kvantitativ). Den første undersøker algoritmer fra synspunktet om samsvaret de etablerer mellom inputdata og resultater. Den andre undersøker algoritmer fra synspunktet om kompleksiteten til både algoritmene selv og "beregningene" de spesifiserer, det vil si prosessene med sekvensiell transformasjon av strukturelle objekter. Det er viktig å understreke at kompleksiteten til algoritmer og beregninger kan bestemmes på ulike måter, og det kan vise seg at med én metode algoritmen EN det blir vanskeligere I, og med den andre metoden er det omvendt.

Oftest blir algoritmer evaluert av nødvendig minne, antall utførte operasjoner, løsningstid eller beregningsfeil. Disse egenskapene avhenger ofte av parametrene (dimensjonene) til problemet og er ikke-lineære. Derfor, i teorien om algoritmer, er det en retning for å vurdere effektiviteten til algoritmer ved asymptotiske estimater av funksjoner: nødvendig minne, beregningstid, etc. I dette tilfellet bestemmes den viktigste parameteren til funksjonen, og funksjonen til funksjonen studeres når parameterverdiene øker. I løpet av studien prøver de å bestemme arten av avhengigheten av verdiene til egenskapene til algoritmen som vurderes på parameteren. Den kan være lineær (dvs. proporsjonal med parameteren n), logaritmisk (dvs. proporsjonal med log n), kvadratisk (dvs. proporsjonal med n 2), etc. Ved å sammenligne de asymptotiske estimatene av algoritmer som løser det samme problemet, kan du velge en mer effektiv algoritme. De sier at verdien av en eller annen parameter T(n) er av størrelsesorden n x hvis det er positive konstanter k og n o slik at for alle n³n o gjelder ulikheten T(n) ≤ k n x.

Anta at n er mengden numeriske data mottatt ved inngangen til flere forskjellige algoritmer (A 1, A 2, A 3, A 4, A 5), som utfører beregninger med samme hastighet - 1000 operasjoner per sekund, men har forskjellige asymptotiske estimater. Tabell 1.8 viser verdiene av n som disse algoritmene kan behandle på 1 sekund, 1 minutt og 1 time (verdiene er rundet ned til nærmeste hele tall). Dataene i tabell 1.3 viser tydelig at ytelsen til algoritmen (dvs. antall data behandlet per tidsenhet) avhenger signifikant av arten av den asymptotiske evalueringsfunksjonen.

Testing av de utviklede algoritmene utføres vanligvis ved små verdier av parameteren n. Slik testing lar deg få tillit til ytelsen til algoritmen, men garanterer ikke i det hele tatt fullføring av oppgaven for store verdier på n. Vi har kanskje rett og slett ikke nok dataminne eller tid til å løse et reelt problem. Asymptotiske estimater er viktige i den forstand at de gjør det mulig å estimere tilstrekkeligheten av dataressurser for praktiske beregninger med kjente endringsgrenser i parameteren n.

Algoritme effektivitet er en egenskap til en algoritme som er assosiert med beregningsressursene som brukes av algoritmen. Algoritmen må analyseres for å bestemme ressursene som kreves av algoritmen. Algoritmeeffektivitet kan betraktes som analogt med produksjonsproduktiviteten til repeterende eller kontinuerlige prosesser.

For å oppnå maksimal effektivitet ønsker vi å redusere ressursbruken. Ulike ressurser (som tid og minne) kan imidlertid ikke sammenlignes direkte, så hvilken av to algoritmer som anses som mer effektiv avhenger ofte av hvilken faktor som er viktigst, for eksempel kravet til høy hastighet, minimalt minnebruk eller et annet mål på effektivitet.

Bakgrunn

Viktigheten av effektivitet med vekt på utførelsestid ble understreket av Ada Lovelace i 1843 angående Charles Babbages mekaniske analytiske motor:

"I nesten all databehandling er det et stort utvalg av konfigurasjoner som er mulig for å fullføre prosessen, og ulike konvensjoner bør påvirke valget for å utføre beregningen. Det vesentlige er å velge en konfigurasjon som vil resultere i å minimere tiden som kreves for å utføre beregningen."

Tidlige elektroniske datamaskiner var svært begrenset i både hastighet og minne. I noen tilfeller har man innsett at det er en avveining mellom tid og minne, der en oppgave enten må bruke en stor mengde minne for å oppnå høy hastighet, eller bruke en langsommere algoritme som bruker en liten mengde arbeidsminne. I dette tilfellet ble den raskeste algoritmen brukt som det tilgjengelige minnet var tilstrekkelig til.

Moderne datamaskiner er mye raskere enn de tidlige datamaskinene og har mye mer minne (gigabyte i stedet for kilobyte). Donald Knuth understreker imidlertid at effektivitet fortsatt er en viktig faktor:

"I etablerte ingeniørdisipliner er 12 % forbedring lett oppnåelig og har aldri blitt ansett som uoverkommelig, og jeg tror det samme bør gjelde i programmering."

Gjennomgå

En algoritme anses som effektiv hvis ressursforbruket (eller ressurskostnaden) er på eller under et akseptabelt nivå. Grovt sett betyr "akseptabel" her "algoritmen vil kjøre i rimelig tid på en tilgjengelig datamaskin." Fordi det har vært en betydelig økning i prosessorkraft og tilgjengelig minne til datamaskiner siden 1950-tallet, var det nåværende "akseptable nivået" ikke akseptabelt selv for 10 år siden.

Dataprodusenter slipper med jevne mellomrom nye modeller, ofte kraftigere. Pris programvare kan være ganske store, så i noen tilfeller er det enklere og billigere å få bedre ytelse ved å kjøpe en raskere datamaskin som er kompatibel med din eksisterende datamaskin.

Det er mange måter å måle ressursene som brukes av en algoritme. De to mest brukte målingene er hastighet og minne som brukes. Andre målinger kan inkludere overføringshastighet, midlertidig diskbruk, langsiktig diskbruk, strømforbruk, totale eierkostnader, responstid på eksterne signaler og så videre. Mange av disse målingene avhenger av størrelsen på algoritmens inngangsdata (det vil si mengdene som krever databehandling). Målinger kan også avhenge av måten dataene presenteres på (for eksempel fungerer noen sorteringsalgoritmer dårlig på allerede sorterte data eller når dataene er sortert i omvendt rekkefølge).

I praksis er det andre faktorer som påvirker effektiviteten til algoritmen, for eksempel nødvendig nøyaktighet og/eller pålitelighet. Som forklart nedenfor kan måten en algoritme implementeres på også ha en betydelig effekt på faktisk ytelse, selv om mange aspekter ved implementeringen er optimaliseringsproblemer.

Teoretisk analyse

I teoretisk analyse I algoritmer er det vanlig praksis å estimere kompleksiteten til en algoritme i dens asymptotiske oppførsel, det vil si å reflektere kompleksiteten til algoritmen som en funksjon av størrelsen på inngangen n Stor O-notasjon brukes. Dette anslaget er generelt ganske nøyaktig for store n, men kan føre til uriktige konklusjoner ved små verdier n(Derfor kan boblesortering, som anses som sakte, være raskere enn rask sortering hvis du bare trenger å sortere noen få elementer).

Verifikasjonstester: Måling av ytelse

For nye versjoner av programvare eller for å gi sammenligning med rivaliserende systemer, brukes noen ganger benchmarks for å sammenligne den relative ytelsen til algoritmer. Hvis for eksempel en ny sorteringsalgoritme slippes, kan den sammenlignes med forgjengerne for å sikre at algoritmen er minst like effektiv på kjente data som de andre. Ytelsestester kan brukes av brukere til å sammenligne produkter fra ulike produsenter for å vurdere hvilket produkt som best vil passe deres krav når det gjelder funksjonalitet og ytelse.

Noen benchmark-tester gir komparativ analyse av forskjellige kompilerings- og tolkespråk, for eksempel Roy Longbottoms PC Benchmark Collection, og Computer Language Benchmarks-spillet sammenligner ytelsen til implementeringer av typiske oppgaver i noen programmeringsspråk.

Implementeringsspørsmål

Implementeringsproblemer kan også påvirke faktisk ytelse. Dette inkluderer valg av programmeringsspråk og måten algoritmen faktisk er kodet på, valg av oversetter for det valgte språket eller kompilatoralternativene som brukes, og til og med typen operativsystem. I noen tilfeller kan et språk implementert som tolk være betydelig tregere enn et språk implementert som en kompilator.

Det er andre faktorer som kan påvirke timing eller minnebruk som er utenfor programmererens kontroll. Dette inkluderer datajustering, detaljering, søppelinnsamling , parallellitet på instruksjonsnivå og subrutineanrop .

Noen prosessorer har muligheten til å utføre vektoroperasjoner, noe som gjør at en operasjon kan behandle flere operander. Det kan være enkelt å bruke slike funksjoner på programmerings- eller kompileringsnivå. Algoritmer designet for sekvensiell databehandling kan kreve fullstendig redesign for å imøtekomme parallell databehandling.

Et annet problem kan oppstå med prosessorkompatibilitet, der instruksjoner kan implementeres annerledes, slik at instruksjoner på noen modeller kan være relativt tregere på andre modeller. Dette kan være et problem for optimaliseringskompilatoren.

Måling av ressursbruk

Målinger uttrykkes vanligvis som en funksjon av inngangsstørrelse n.

De to viktigste dimensjonene er:

• Tid: Hvor lang tid tar algoritmen på CPU.
• Hukommelse: Hvor mye arbeidsminne (vanligvis RAM) er nødvendig for algoritmen. Det er to aspekter ved dette: mengden minne for koden og mengden minne for dataene som koden opererer på.

For batteridrevne datamaskiner (som bærbare datamaskiner) eller for svært lange/store beregninger (som superdatamaskiner), er en annen type måling av interesse:

• Direkte energiforbruk: Energi som kreves for å kjøre en datamaskin.
• Indirekte energiforbruk: Energi som kreves for kjøling, belysning osv.

I noen tilfeller er det nødvendig med andre, mindre vanlige målinger:

• Girstørrelse: Båndbredde kan være den begrensende faktoren. Komprimering kan brukes til å redusere mengden data som overføres. Å vise et bilde eller et bilde (som Google-logoen) kan føre til at titusenvis av byte overføres (48K i dette tilfellet). Sammenlign dette med å overføre de seks bytene i ordet "Google".
• Eksternt minne: Minne kreves på en disk eller annen ekstern lagringsenhet. Dette minnet kan brukes til midlertidig lagring eller til fremtidig bruk.
• Responstid: Denne innstillingen er spesielt viktig for sanntidsapplikasjoner der datamaskinen må reagere raskt på eksterne hendelser.
• Totale eierkostnader: Parameteren er viktig når den er ment å utføre en enkelt algoritme.

Tid

Teori

Denne typen tester avhenger også vesentlig av valg av programmeringsspråk, kompilator og dets alternativer, slik at de sammenlignede algoritmene må implementeres under de samme betingelsene.

Hukommelse

Denne delen tar for seg bruken av hovedminne (ofte RAM) som trengs av algoritmen. Som med timinganalyse ovenfor, bruker analyse av en algoritme vanligvis romlig kompleksitet av algoritmenå estimere nødvendig kjøretidsminne som en funksjon av inngangsstørrelsen. Resultatet uttrykkes vanligvis i form av "O" stor.

Det er fire aspekter ved minnebruk:

• Mengden minne som kreves for å lagre algoritmekoden.
• Mengden minne som kreves for inndataene.
• Mengden minne som kreves for enhver utgang (noen algoritmer, for eksempel sorteringer, omorganiserer ofte inngangen og krever ikke ekstra minne for utgangen).
• Mengden minne som kreves av beregningsprosessen under beregning (dette inkluderer navngitte variabler og eventuell stabelplass som kreves for subrutineanrop, noe som kan være betydelig ved bruk av rekursjon).

Tidlige elektroniske datamaskiner og hjemmedatamaskiner hadde relativt liten arbeidsminnekapasitet. Således hadde EDSAC i 1949 et maksimalt arbeidsminne på 1024 17-bits ord, og i 1980 ble Sinclair ZX80 utgitt med 1024 byte arbeidsminne.

Moderne datamaskiner kan ha relativt store mengder minne (kanskje gigabyte), så å komprimere minnet som brukes av en algoritme til en gitt mengde minne er mindre nødvendig enn før. Imidlertid er eksistensen av tre forskjellige kategorier av hukommelse betydelig:

• Cache (ofte statisk RAM) - kjører med hastigheter som kan sammenlignes med CPU
• Fysisk hovedminne (ofte dynamisk RAM) - går litt tregere enn CPU
• Virtuelt minne (ofte på disk) - gir en illusjon av enormt minne, men fungerer tusenvis av ganger tregere enn RAM.

En algoritme hvis nødvendige minne passer inn i datamaskinens hurtigbuffer er mye raskere enn en algoritme som passer inn i hovedminnet, som igjen vil være mye raskere enn en algoritme som bruker virtuelt rom. Det som kompliserer saken er at noen systemer har opptil tre nivåer med cache. Ulike systemer har forskjellige mengder av disse typer minne, så minneeffekten på en algoritme kan variere betydelig fra ett system til et annet.

I de tidlige dagene av elektronisk databehandling, hvis en algoritme og dens data ikke passet inn i hovedminnet, kunne den ikke brukes. I disse dager gir bruk av virtuelt minne massivt minne, men på bekostning av ytelse. Hvis algoritmen og dens data passer inn i hurtigbufferen, kan svært høy hastighet oppnås, så minimering av minnet som kreves bidrar til å minimere tiden. En algoritme som ikke passer helt inn i cachen, men gir lokaliteten av lenker, kan fungere relativt raskt.

Eksempler på effektive algoritmer

Kritikk av nåværende tilstand av programmering

Programmer blir tregere raskere enn datamaskiner blir raskere.

I utbredte systemer kan halvering av instruksjonsutførelse doble batterilevetiden, og big data gir mulighet for bedre algoritmer: Å redusere antall operasjoner fra N x N til N x log(N) har en sterk effekt for store N... For N =30 milliarder, disse endringene ligner på 50 år med teknologiske forbedringer.

Konkurranse om den beste algoritmen

Følgende konkurranser inviterer til deltakelse i utviklingen av de beste algoritmene, hvis kvalitetskriterier bestemmes av dommerne:

Se også

• Aritmetisk koding er en type entropikoding med variabel kodelengde for effektiv datakomprimering
• En assosiativ matrise er en datastruktur som kan gjøres mer effektiv når den brukes trær PATRICIA eller Judy-arrayer
• Ytelsestest - en metode for å måle komparativ utførelsestid i visse tilfeller
• Beste, verste og gjennomsnittlige tilfelle- konvensjoner for å estimere utførelsestid for tre scenarier
• Binært søk er en enkel og effektiv teknikk for å søke i en sortert liste
• Grenbord

Det er enkelt å sende inn det gode arbeidet ditt til kunnskapsbasen. Bruk skjemaet nedenfor

Studenter, hovedfagsstudenter, unge forskere som bruker kunnskapsbasen i studiene og arbeidet vil være deg veldig takknemlig.

Det er ingen HTML-versjon av verket ennå.
Du kan laste ned arkivet til arbeidet ved å klikke på lenken nedenfor.

Lignende dokumenter

Beskrivelse av den formelle modellen av algoritmen basert på rekursive funksjoner. Utvikling av en analytisk og programmodell av en algoritme for en Turing-gjenkjenningsmaskin. Utvikling av en analytisk modell av algoritmen ved bruk av normale Markov-algoritmer.

kursarbeid, lagt til 07.07.2013


Konseptet med en algoritme og analyse av teoretiske estimater av tidskompleksiteten til. Komparativ analyse av å estimere tidskompleksiteten til noen klasser av algoritmer ved bruk av konvensjonell programmering og programmering ved bruk av Open MP-teknologi.

avhandling, lagt til 08.12.2017


Generelt konsept algoritme og mål på kompleksiteten. Tid og kapasitet kompleksitet av algoritmer. Grunnleggende metoder og teknikker for kompleksitetsanalyse. Optimalisering knyttet til valg av metode for å konstruere en algoritme og med valg av metoder for å presentere data i programmet.

sammendrag, lagt til 27.11.2012


Problemet med å forbedre kvaliteten på fingeravtrykk for å øke effektiviteten til biometriske autentiseringsalgoritmer. Gjennomgang av bildebehandlingsalgoritmer for fingeravtrykk. Analyse av en algoritme basert på bruk av Gabor-transformasjonen.

avhandling, lagt til 16.07.2014


Metoder for å organisere databehandlingsprosessen i systemer med flere prosessorer. Utvikling av et program basert på algoritmer for multiprosessorsystemer for batchbehandling av oppgaver. Beregning av nøkkelytelsesindikatorer for hver algoritme.

kursarbeid, lagt til 21.06.2013


Estimering av den beregningsmessige kompleksiteten til programmet. Implementering av Huffman informasjonskodingsalgoritmen. Koding av testen i binære og Huffman-trær. Binær tegnkode. Symbolet og hyppigheten av dets opptreden i teksten. Beregning av kompleksiteten til algoritmen.

test, lagt til 16.12.2012


Overgangen fra en verbal uformell formulering til en matematisk formulering av dette problemet. Vurder ulike alternativer for å velge de mest effektive datastrukturene og behandlingsalgoritmene. Implementering av algoritmer i et av programmeringsspråkene.

kursarbeid, lagt til 25.06.2013

Hovedprinsipper for å lage effektive algoritmer

Alle som utvikler algoritmer må mestre noen grunnleggende teknikker og konsepter. Alle som noen gang har stått overfor en vanskelig oppgave, ble møtt med spørsmålet: "Hvor skal man begynne?" En mulig måte er å se gjennom lageret av vanlige algoritmiske metoder for å se om en av dem kan brukes til å formulere en løsning på et nytt problem. Vel, hvis det ikke er en slik reserve, hvordan kan du da fortsatt utvikle en god algoritme? Hvor skal jeg begynne? Vi har alle hatt den frustrerende opplevelsen av å se på en oppgave og ikke vite hva vi skal gjøre. La oss se på tre generelle problemløsningsteknikker som er nyttige for å utvikle algoritmer.

Første metode forbundet med å redusere en vanskelig oppgave til en sekvens av enklere oppgaver. Håpet er selvfølgelig at enklere problemer er lettere å behandle enn det opprinnelige problemet, og også at en løsning på det opprinnelige problemet kan utledes fra løsninger på disse enklere problemene. Denne prosedyren kalles metode for private mål. Denne metoden ser veldig fornuftig ut. Men som de fleste generelle metoder for å løse problemer eller designe algoritmer, er det ikke alltid lett å overføre til et spesifikt problem. Å ta intelligente valg om lettere problemer er mer en kunst eller intuisjon enn en vitenskap. Det er ikke noe generelt sett med regler for å definere klassen av problemer som kan løses ved hjelp av denne tilnærmingen. Å tenke på et spesifikt problem begynner med å stille spørsmål. Spesifikke mål kan settes når følgende spørsmål er besvart:

• 1. Er det mulig å løse deler av problemet? Er det mulig å løse resten av problemet ved å ignorere noen forhold?
• 2. Er det mulig å løse problemet for spesielle tilfeller? Er det mulig å utvikle en algoritme som produserer en løsning som tilfredsstiller alle betingelsene for problemet, men hvis inngangsdata er begrenset til en delmengde av alle inngangsdata?
• 3. Er det noe knyttet til problemet som ikke er godt forstått? Hvis vi prøver å gå dypere inn i noen av funksjonene ved problemet, vil vi da kunne lære noe som vil hjelpe oss å nærme oss en løsning?
• 4. Finnes det en kjent løsning på et lignende problem? Er det mulig å endre løsningen for å løse problemet under vurdering? Er det mulig at dette problemet tilsvarer et kjent uløst problem?

Andre metode Algoritmeutvikling er kjent som løftemetode. Løftealgoritmen begynner med å gjøre en innledende gjetning eller beregne en innledende løsning på problemet. Da starter den raskeste bevegelsen oppover fra den første løsningen mot bedre løsninger. Når algoritmen når et punkt der det ikke lenger er mulig å bevege seg oppover, stopper algoritmen. Dessverre er det ikke alltid mulig å garantere at den endelige løsningen oppnådd av løftealgoritmen er optimal. Denne situasjonen begrenser ofte bruken av løftemetoden.

Generelt er løftemetoder klassifisert som "grove". De husker et eller annet mål og prøver å gjøre alt de kan, der de kan, for å komme nærmere målet. Dette gjør dem noe "kortsynte." Løftemetodens nærsynthet er godt illustrert av følgende eksempel. Anta at vi må finne maksimum av en funksjon på =/(X), presentert av grafen (fig. 2.15). Hvis den opprinnelige verdien av argumentet x = a, da vil oppstigningsmetoden gi aspirasjon til nærmeste mål, dvs. til verdien av funksjonen ved punktet x = b, mens det sanne maksimum for denne funksjonen er i = c. I dette tilfellet

Ris. 2.15. En illustrasjon av løftemetoden Løftemetoden finner et lokalt maksimum, men ikke et globalt. Dette er "ruheten" til løftemetoden.

Tredje metode kjent som jobber tilbake, de. Arbeidet med denne algoritmen begynner med et mål eller en løsning på et problem og beveger seg deretter mot den innledende formuleringen av problemet. Så, hvis disse handlingene er reversible, gjøres en bevegelse tilbake fra problemformuleringen til løsningen.

La oss se på alle tre metodene jeep problem. Anta at du må krysse en 1000 kilometer lang ørken i en jeep, med et minimum av drivstoff. Volumet på jeepens drivstofftank er 500 liter, drivstoff forbrukes jevnt, 1 liter per 1 km. Samtidig er det på startpunktet en ubegrenset tank med drivstoff. Siden det ikke er drivstoffdepoter i ørkenen, må du installere dine egne lagerfasiliteter og fylle dem med drivstoff fra bilens tank. Så ideen om problemet er klar: du må kjøre fra startpunktet med en full tank et stykke, sette opp det første lageret der, la en viss mengde drivstoff fra tanken være der, men nok til å komme tilbake. Ved startstedet gjennomføres det igjen full tanking og det andre lageret forsøkes flyttet lenger inn i ørkenen. Men hvor skal disse lagrene settes opp og hvor mye drivstoff skal lagres i hvert av dem?

La oss nærme oss dette problemet ved å arbeide bakover. På hvilken avstand fra enden kan du krysse ørkenen med nøyaktig samme mengde drivstoff? Til tanker? La oss vurdere dette spørsmålet for Til= 1,2, 3,... til vi finner et slikt heltall p, Hva n fulle tanker lar deg krysse hele den 1000 kilometer lange ørkenen. Til Til= 1 svar er 500 km = 500 l (punkt I), som vist i fig. 2.16.

Ris. 2.16.

Du kan fylle bensin på bilen din på punktet I og kryss de resterende 500 km med ørken. Et spesielt mål ble satt fordi det opprinnelige problemet ikke kan løses umiddelbart.

La oss anta det Til= 2, dvs. det er to fulle tanker (1000 l). Denne situasjonen er illustrert i fig. 2.16. Hva er den maksimale verdien av jCj slik at det, fra og med 1000 liter drivstoff fra punkt (500 - Xj), er mulig å frakte nok drivstoff til punktet for å fullføre turen, som i Til= 1. En måte å bestemme en akseptabel verdi på X ( er som følger. Vi fyller drivstoff på punktet (500 - Xj), vi går X ( kilometer til punkt I og hell alt drivstoffet i lageret, bortsett fra den delen som kreves for å gå tilbake til punktet (500 - Xj). På dette tidspunktet blir tanken tom. Nå fyller vi den andre tanken, kjører Xj kilometer til I, hentes kl I drivstoff igjen der, og fra I Vi skal til C med full tank. Den totale tilbakelagte distansen består av tre segmenter langs X ( kilometer og ett segment Sol 500 km lang. Derfor, fra ligningen 3x t + 500 = 1000 finner vi løsningen Xj = 500/3. Dermed lar to tanker (1000 l) deg reise Z> 2 = 500 +x ( = 500 (1 + 1/3) km.

La oss vurdere k = 3. Fra hvilket tidspunkt kan du gå ut med 1500 liter drivstoff slik at jeepen kan levere 1000 liter til punktet (500 - x))? La oss finne den største verdien av x 2 slik at vi, med 1500 liter drivstoff fra punktet (500 - Xj - x 2), kan levere 1000 liter til punktet (500 - Xj). Vi forlater punktet (500 - Xj - x 2), kjører til (500 - x), overfører alt drivstoff unntatt x 2 liter, og går tilbake til punktet (500 - Xj - x 2) med tom tank. Ved å gjenta denne prosedyren vil vi bruke 4x 2 liter på reise og la (1000 - 4x 2) liter stå på punktet (500 - x L). Nå ved punktet (500 - Xj - x 2) er det nøyaktig 500 liter igjen. Vi fyller på med de siste 500 liter og går til poenget (500 - Xj), etter å ha brukt x 2 liter på dette.

Når vi er på punktet (500 - Xj), bruker vi 5x 2 liter drivstoff på reise. Totalt (1500 - 5x 2) liter er igjen her. Denne mengden skal være lik 1000 l, dvs. x 2 = 500/5. Av dette konkluderer vi med at 1500 liter lar deg kjøre

Fortsetter prosessen med å jobbe bakover induktivt, det får vi n drivstofftanker lar oss passere Dn kilometer, hvor Dn = 500(1 +1/3 + 1/5 + ... + 1/(2n - 1)).

Vi må finne den minste verdien p, ved hvilken Dn> 1000. Enkle beregninger viser at for n = 7 vi har D?= 997,5 km, dvs. syv tanker, eller 3500 liter, med drivstoff lar deg reise

• 977,5 km. En full åttende tank - dette ville være mer enn nødvendig for å frakte 3500 liter fra punktet EN til et punkt som ligger ved
• 22,5 km (1000 - 977,5) fra A Leseren gis mulighet til uavhengig å verifisere at 337,5 liter er tilstrekkelig til å levere 3500 liter drivstoff til 22,5 km-merket. For å krysse ørkenen med bil fra I til C trenger du altså 3837,5 liter drivstoff.

Nå kan drivstofftransportalgoritmen presenteres som følger. Vi starter fra EN, med 3837,5 liter. Her er det akkurat nok drivstoff til å gradvis frakte 3500 liter til merket

22,5 km, hvor jeepen til slutt vil ende opp med tom tank og nok drivstoff til 7 fulle påfyllinger. Dette drivstoffet er nok til å transportere 3000 liter til et punkt 22,5 + 500/13 km fra EN, hvor bilens tank vil være tom igjen. Etterfølgende transport vil bringe jeepen til et punkt som ligger 22,5 + 500/13 + 500/11 km fra EN, med tom tank på bilen og 2500 l på lageret.

Fortsetter vi på denne måten, går vi fremover takket være analysen utført ved å jobbe bakover. Snart er jeepen ved 500(1 - 1/3) km-merket med 1000 liter drivstoff. Da skal vi frakte 500 liter drivstoff til punktum I, La oss helle dem i tanken på bilen og kjøre til poenget uten å stoppe MED(Fig. 2.17).

Ris. 2.17.

For de som er kjent med uendelige serier, merk det D Det er det n-th delsummen av en oddetall harmonisk serie. Siden denne serien divergerer, gjør algoritmen det mulig å krysse hvilken som helst ørken. Prøv å modifisere denne algoritmen for å legge igjen nok drivstoff på forskjellige punkter i ørkenen til å gå tilbake til punktet EN.

Spørsmålet oppstår om det er mulig å kjøre 1000 km med mindre enn 3837,5 liter drivstoff. Det viser seg at du ikke kan. Beviset for denne uttalelsen er ganske kompleks. Imidlertid kan følgende, ganske plausible, argument fremsettes. Det er klart vi handler på best mulig måte Til Til= 1. Når Til= 2 plan brukt til Til= 1 og deretter aktiveres den andre tanken med drivstoff for å være så langt unna punktet som mulig I. Utgangspunktet for Til tanks er at vi vet hvordan vi skal opptre best i tilfelle (Til - 1) tanker, og flytte tilbake så langt som mulig med hjelp WHO tank

Så, i det aktuelle problemet, er metoden for å jobbe bakover at problemet løses som fra slutten; metoden for delmål er at de ikke løser hele problemet på en gang, men så å si i deler; og til slutt manifesteres metoden for oppstigning i det faktum at løsningen ikke blir funnet umiddelbart, men sekvensielt, som om man nærmer seg den.

TEST SPØRSMÅL

• 1. Definer et objekt, klasse, system, modell.
• 2. Nevn hovedtyper av modeller.
• 3. Hva er simuleringsmodellering?
• 4. Hvilke klassifikasjoner av modeller finnes?
• 5. Angi hovedstadiene i modelleringen.
• 6. Hva er en algoritme?
• 7. List opp egenskapene til algoritmen.
• 8. Hvilke stadier utføres i den komplette konstruksjonen av algoritmen?
• 9. Hva er et algoritmeflytskjema?
• 10. Definer en funksjonsblokk.
• 11. Hvilken algoritme kalles strukturell?
• 12. Nevn hovedprinsippene som ligger til grunn for å lage effektive algoritmer.