Za rješavanje istog problema može se razviti nekoliko različitih algoritama. Stoga se nameće zadatak odabira najučinkovitijih algoritama. Imajte na umu da je točna procjena učinkovitosti algoritama vrlo težak zadatak iu svakom konkretnom slučaju zahtijeva posebno istraživanje.

Onaj dio teorije algoritama koji se bavi procjenom karakteristika algoritama naziva se metrika. Može se podijeliti na deskriptivni (kvalitativni) i metrički (kvantitativni). Prvi ispituje algoritme sa stajališta korespondencije koju uspostavljaju između ulaznih podataka i rezultata. Drugi ispituje algoritme sa stajališta složenosti i samih algoritama i "izračunavanja" koje specificiraju, tj. procesa sekvencijalne transformacije strukturnih objekata. Važno je naglasiti da se složenost algoritama i izračuna može odrediti na različite načine, te se može pokazati da jednom metodom algoritam A bit će teže U, a kod druge metode je obrnuto.

Najčešće se algoritmi ocjenjuju prema potrebnoj memoriji, broju izvedenih operacija, vremenu rješavanja ili računskoj pogrešci. Ove karakteristike često ovise o parametrima (dimenzijama) problema i nelinearne su. Stoga u teoriji algoritama postoji smjer za procjenu učinkovitosti algoritama na temelju asimptotskih procjena funkcija: potrebne memorije, vremena računanja itd. U ovom slučaju se određuje najznačajniji parametar funkcije i proučava se ponašanje funkcije kako se vrijednosti parametra povećavaju. Tijekom studije pokušavaju utvrditi prirodu ovisnosti vrijednosti karakteristika algoritma koji se razmatra o parametru. Može biti linearan (tj. proporcionalan parametru n), logaritamski (tj. proporcionalan log n), kvadratni (tj. proporcionalan n 2), itd. Usporedbom asimptotskih procjena algoritama koji rješavaju isti problem, možete odabrati učinkovitiji algoritam. Kažu da je vrijednost nekog parametra T(n) reda n x ako postoje pozitivne konstante k i n o takve da za sve n³n o vrijedi nejednakost T(n) ≤ k n x.

Pretpostavimo da je n količina numeričkih podataka primljenih na ulazu nekoliko različitih algoritama (A 1, A 2, A 3, A 4, A 5), koji izvode izračune istom brzinom - 1000 operacija u sekundi, ali imaju različite asimptotske procjene. Tablica 1.8 prikazuje vrijednosti n koje ovi algoritmi mogu obraditi u 1 sekundi, 1 minuti i 1 satu (vrijednosti su zaokružene prema dolje na najbliži cijeli broj). Podaci u tablici 1.3 jasno pokazuju da izvedba algoritma (tj. broj podataka obrađenih po jedinici vremena) značajno ovisi o prirodi funkcije asimptotske procjene.

Testiranje razvijenih algoritama obično se provodi pri malim vrijednostima parametra n. Takvo testiranje omogućuje vam da steknete povjerenje u izvedbu algoritma, ali uopće ne jamči dovršenje zadatka za velike vrijednosti n. Možda jednostavno nemamo dovoljno računalne memorije ili vremena za rješavanje stvarnog problema. Asimptotske procjene važne su u smislu da omogućuju procjenu dostatnosti računalnih resursa za praktične proračune s poznatim granicama promjene parametra n.

Učinkovitost algoritma je svojstvo algoritma koje je povezano s računalnim resursima koje koristi algoritam. Algoritam se mora analizirati kako bi se odredili resursi potrebni za algoritam. Učinkovitost algoritma može se smatrati analognom produktivnosti proizvodnje ponavljajućih ili kontinuiranih procesa.

Kako bismo postigli maksimalnu učinkovitost, želimo smanjiti korištenje resursa. Međutim, različiti resursi (kao što su vrijeme i memorija) ne mogu se izravno usporediti, tako da koji se od dva algoritma smatra učinkovitijim često ovisi o tome koji je faktor važniji, kao što je zahtjev za velikom brzinom, minimalna upotreba memorije ili druga mjera učinkovitost.

Pozadina

Važnost učinkovitosti s naglaskom na vrijeme izvršenja naglasila je Ada Lovelace 1843. u vezi s mehaničkim analitičkim strojem Charlesa Babbagea:

„U gotovo svakom računalstvu postoji veliki izbor mogućih konfiguracija za uspješno dovršenje procesa, a različite konvencije trebale bi utjecati na izbor u svrhu izvođenja izračuna. Bitno je odabrati konfiguraciju koja će minimizirati vrijeme potrebno za izvođenje izračuna."

Rana elektronička računala bila su vrlo ograničena u brzini i memoriji. U nekim je slučajevima uočeno da postoji kompromis između vremena i memorije, u kojem zadatak mora ili koristiti veliku količinu memorije da bi postigao veliku brzinu, ili koristiti sporiji algoritam koji koristi malu količinu radne memorije. U ovom slučaju korišten je najbrži algoritam za koji je bilo dovoljno raspoložive memorije.

Moderna računala mnogo su brža od ranih računala i imaju mnogo više memorije (gigabajta umjesto kilobajta). Međutim, Donald Knuth naglašava da učinkovitost ostaje važan čimbenik:

"U etabliranim inženjerskim disciplinama, poboljšanje od 12% je lako ostvarivo i nikada se nije smatralo pretjeranim, a vjerujem da bi isto trebalo vrijediti i za programiranje."

Pregled

Algoritam se smatra učinkovitim ako je njegova potrošnja resursa (ili cijena resursa) na ili ispod neke prihvatljive razine. Grubo govoreći, "prihvatljivo" ovdje znači "algoritam će se izvoditi razumno vrijeme na dostupnom računalu." Budući da je došlo do značajnog povećanja računalne snage i raspoložive memorije računala od 1950-ih, sadašnja "prihvatljiva razina" nije bila prihvatljiva ni prije 10 godina.

Proizvođači računala povremeno izdaju nove modele, često snažnije. Cijena softver može biti prilično velik, pa je u nekim slučajevima lakše i jeftinije postići bolje performanse kupnjom bržeg računala koje je kompatibilno s vašim postojećim računalom.

Postoji mnogo načina za mjerenje resursa koje koristi algoritam. Dva najčešće korištena mjerenja su brzina i iskorištena memorija. Ostala mjerenja mogu uključivati ​​brzinu prijenosa, privremenu upotrebu diska, dugotrajnu upotrebu diska, potrošnju energije, ukupni trošak vlasništva, vrijeme odziva na vanjske signale i tako dalje. Mnoga od tih mjerenja ovise o veličini ulaznih podataka algoritma (to jest, veličinama koje zahtijevaju obradu podataka). Mjerenja također mogu ovisiti o načinu na koji su podaci predstavljeni (na primjer, neki algoritmi za sortiranje rade loše na već sortiranim podacima ili kada su podaci sortirani obrnutim redoslijedom).

U praksi postoje i drugi čimbenici koji utječu na učinkovitost algoritma, poput potrebne točnosti i/ili pouzdanosti. Kao što je objašnjeno u nastavku, način na koji je algoritam implementiran također može imati značajan učinak na stvarnu izvedbu, iako su mnogi aspekti implementacije problemi optimizacije.

Teorijska analiza

U teorijska analiza U algoritmima je uobičajena praksa procijeniti složenost algoritma u njegovom asimptotskom ponašanju, to jest, odražavati složenost algoritma kao funkciju veličine ulaza n Koristi se oznaka Veliko O. Ova je procjena općenito prilično točna za velike n, ali može dovesti do netočnih zaključaka pri malim vrijednostima n(Dakle, sortiranje u obliku mjehurića, koje se smatra sporim, može biti brže od brzog sortiranja ako trebate sortirati samo nekoliko elemenata).

Testovi provjere: Mjerenje performansi

Za nove verzije softvera ili za pružanje usporedbe sa konkurentskim sustavima, referentne vrijednosti se ponekad koriste za usporedbu relativne izvedbe algoritama. Ako se, na primjer, objavi novi algoritam za sortiranje, može se usporediti sa svojim prethodnicima kako bi se osiguralo da je algoritam barem jednako učinkovit na poznatim podacima kao i ostali. Korisnici mogu koristiti testove performansi za usporedbu proizvoda različitih proizvođača kako bi procijenili koji će proizvod najbolje odgovarati njihovim zahtjevima u smislu funkcionalnosti i performansi.

Neki referentni testovi daju komparativnu analizu različitih jezika za prevođenje i tumačenje, kao što je PC Benchmark Collection Roya Longbottoma i Igra kompjutorskih jezičnih mjerila uspoređuje izvedbu implementacija tipičnih zadataka u nekim programskim jezicima.

Problemi s provedbom

Problemi s implementacijom također mogu utjecati na stvarnu izvedbu. To uključuje izbor programskog jezika i način na koji je algoritam zapravo kodiran, izbor prevoditelja za odabrani jezik ili korištene opcije prevoditelja, pa čak i vrstu operativni sustav. U nekim slučajevima, jezik implementiran kao prevoditelj može biti znatno sporiji od jezika implementiranog kao kompajler.

Postoje i drugi čimbenici koji mogu utjecati na vrijeme ili korištenje memorije koji su izvan kontrole programera. To uključuje usklađivanje podataka, detaljiziranje, sakupljanje smeća , paralelizam na razini instrukcija i pozivanje potprograma .

Neki procesori imaju mogućnost izvođenja vektorskih operacija, što omogućuje da jedna operacija obradi više operanda. Može, ali i ne mora biti lako koristiti takve značajke na razini programiranja ili kompilacije. Algoritme dizajnirane za sekvencijalno računanje možda će trebati potpuno redizajnirati za korištenje paralelnog računanja.

Drugi problem može nastati s kompatibilnošću procesora, gdje se upute mogu implementirati drugačije, tako da upute na nekim modelima mogu biti relativno sporije na drugim modelima. Ovo može predstavljati problem za optimizirajući kompilator.

Mjerenje korištenja resursa

Mjerenja se obično izražavaju kao funkcija veličine ulaza n.

Dvije najvažnije dimenzije su:

• Vrijeme: Koliko dugo algoritam zauzima CPU.
• Memorija: Koliko radne memorije (obično RAM) je potrebno za algoritam. Postoje dva aspekta ovoga: količina memorije za kod i količina memorije za podatke na kojima kod radi.

Za računala s baterijskim napajanjem (kao što su prijenosna računala) ili za vrlo duge/velike izračune (kao što su superračunala), drugačija vrsta mjerenja je od interesa:

• Izravna potrošnja energije: Energija potrebna za rad računala.
• Neizravna potrošnja energije: Energija potrebna za hlađenje, rasvjetu itd.

U nekim slučajevima potrebna su druga, manje uobičajena mjerenja:

• Veličina zupčanika: Širina pojasa može biti ograničavajući faktor. Kompresija se može koristiti za smanjenje količine prenesenih podataka. Prikazivanje grafike ili slike (kao što je Google logo) može rezultirati prijenosom desetaka tisuća bajtova (48 K u ovom slučaju). Usporedite ovo s prijenosom šest bajtova u riječi "Google".
• Vanjska memorija: Potrebna memorija na disku ili drugom vanjskom uređaju za pohranu. Ova se memorija može koristiti za privremenu pohranu ili za buduću upotrebu.
• Vrijeme odziva: Ova postavka je posebno važna za aplikacije u stvarnom vremenu gdje računalo mora brzo reagirati na vanjske događaje.
• Ukupni trošak vlasništva: Parametar je važan kada je namijenjen za izvršavanje jednog algoritma.

Vrijeme

Teorija

Ova vrsta testa također značajno ovisi o izboru programskog jezika, prevoditelja i njegovih opcija, pa se uspoređeni algoritmi moraju implementirati pod istim uvjetima.

Memorija

Ovaj odjeljak bavi se korištenjem glavne memorije (često RAM-a) koja je potrebna algoritmu. Kao i kod gornje vremenske analize, analiza algoritma obično koristi prostorna složenost algoritma kako bi se procijenila potrebna radna memorija kao funkcija ulazne veličine. Rezultat se obično izražava velikim "O".

Postoje četiri aspekta korištenja memorije:

• Količina memorije potrebna za pohranjivanje koda algoritma.
• Količina memorije potrebna za ulazne podatke.
• Količina memorije potrebna za bilo koji izlaz (neki algoritmi, poput sortiranja, često preuređuju ulaz i ne zahtijevaju dodatnu memoriju za izlaz).
• Količina memorije koju zahtijeva računalni proces tijekom izračuna (ovo uključuje imenovane varijable i bilo koji prostor na stogu potreban za pozive potprograma, što može biti značajno kada se koristi rekurzija).

Rana elektronička računala i kućna računala imala su relativno male kapacitete radne memorije. Tako je 1949. godine EDSAC imao maksimalnu radnu memoriju od 1024 17-bitne riječi, a 1980. godine izdan je Sinclair ZX80 s 1024 bajta radne memorije.

Moderna računala mogu imati relativno velike količine memorije (možda gigabajta), tako da je komprimiranje memorije koju koristi algoritam u određenu količinu memorije manje potrebno nego prije. Međutim, značajno je postojanje tri različite kategorije pamćenja:

• Predmemorija (često statički RAM) - radi brzinom usporedivom s CPU-om
• Glavna fizička memorija (često dinamički RAM) - radi malo sporije od CPU-a
• Virtualna memorija (često na disku) - daje iluziju ogromne memorije, ali radi tisuće puta sporije od RAM-a.

Algoritam čija potrebna memorija stane u predmemoriju računala puno je brži od algoritma koji stane u glavnu memoriju, a koji će zauzvrat biti puno brži od algoritma koji koristi virtualni prostor. Stvari komplicira činjenica da neki sustavi imaju do tri razine predmemorije. Različiti sustavi imaju različite količine ove vrste memorije, tako da učinak memorije na algoritam može značajno varirati od jednog sustava do drugog.

U ranim danima elektroničkog računalstva, ako algoritam i njegovi podaci nisu stali u glavnu memoriju, nisu se mogli koristiti. Ovih dana korištenje virtualne memorije osigurava ogromnu memoriju, ali po cijenu performansi. Ako algoritam i njegovi podaci stanu u predmemoriju, može se postići vrlo velika brzina, tako da smanjivanje potrebne memorije pomaže smanjiti vrijeme. Algoritam koji ne stane u potpunosti u predmemoriju, ali pruža lokalitet poveznica, može raditi relativno brzo.

Primjeri učinkovitih algoritama

Kritika trenutnog stanja u programiranju

Programi postaju sporiji brže nego što računala postaju brža.

U široko rasprostranjenim sustavima, prepolovljeno izvršavanje instrukcija može udvostručiti trajanje baterije, a veliki podaci pružaju priliku za bolje algoritme: Smanjenje broja operacija s N x N na N x log(N) ima snažan učinak za velike N... Za N =30 milijardi, te su promjene slične 50 godina tehnološkog napretka.

Natjecanje za najbolji algoritam

Sljedeća natjecanja pozivaju na sudjelovanje u razvoju najboljih algoritama čije kriterije kvalitete određuju suci:

Vidi također

• Aritmetičko kodiranje je vrsta entropijskog kodiranja s promjenjivom duljinom koda za učinkovito sažimanje podataka
• Asocijativni niz je struktura podataka koja se može učiniti učinkovitijom kada se koristi stabla PATRICIJA ili Judy nizovi
• Test performansi - metoda mjerenja usporednog vremena izvršenja u određenim slučajevima
• Najbolji, najgori i prosječni slučaj- konvencije za procjenu vremena izvršenja za tri scenarija
• Binarno pretraživanje je jednostavna i učinkovita tehnika za pretraživanje sortiranog popisa
• Stol za grane

Slanje vašeg dobrog rada u bazu znanja jednostavno je. Koristite obrazac u nastavku

Studenti, diplomanti, mladi znanstvenici koji koriste bazu znanja u svom studiju i radu bit će vam vrlo zahvalni.

Još ne postoji HTML verzija djela.
Arhivu rada možete preuzeti klikom na link ispod.

Slični dokumenti

Opis formalnog modela algoritma temeljenog na rekurzivnim funkcijama. Izrada analitičkog i programskog modela algoritma za Turingov stroj za raspoznavanje. Razvoj analitičkog modela algoritma korištenjem normalnih Markovljevih algoritama.

kolegij, dodan 07.07.2013


Pojam algoritma i analiza teorijskih procjena vremenske složenosti algoritama množenja matrica. Usporedna analiza procjene vremenske složenosti nekih klasa algoritama primjenom konvencionalnog programiranja i programiranja primjenom Open MP tehnologije.

diplomski rad, dodan 12.08.2017


Opći koncept algoritam i mjere njegove složenosti. Vremenska i kapacitetna složenost algoritama. Osnovne metode i tehnike analize složenosti. Optimizacija povezana s izborom metoda za konstrukciju algoritma i s izborom metoda za prikaz podataka u programu.

sažetak, dodan 27.11.2012


Problem poboljšanja kvalitete otisaka prstiju kako bi se povećala učinkovitost biometrijskih algoritama autentifikacije. Prikaz algoritama za obradu slike otiska prsta. Analiza algoritma temeljenog na korištenju Gaborove transformacije.

diplomski rad, dodan 16.07.2014


Metode organizacije računalnog procesa u sustavima s više procesora. Razvoj programa temeljenog na algoritmima za višeprocesorske sustave za skupnu obradu zadataka. Izračun ključnih pokazatelja uspješnosti za svaki algoritam.

kolegij, dodan 21.06.2013


Procjena računske složenosti programa. Implementacija Huffmanovog algoritma za kodiranje informacija. Kodiranje testa u binarnim i Huffmanovim stablima. Kod binarnog znaka. Simbol i učestalost njegovog pojavljivanja u tekstu. Izračun složenosti algoritma.

test, dodan 16.12.2012


Prijelaz s verbalne neformalne formulacije na matematičku formulaciju ovog problema. Procijenite različite opcije za odabir najučinkovitijih struktura podataka i algoritama obrade. Implementacija algoritama u jednom od programskih jezika.

kolegij, dodan 25.06.2013

Glavna načela za stvaranje učinkovitih algoritama

Svatko tko razvija algoritme mora ovladati nekim osnovnim tehnikama i konceptima. Svatko tko se jednom suočio s teškim zadatkom suočio se s pitanjem: "Odakle početi?" Jedan od mogućih načina je pregledati svoju zalihu uobičajenih algoritamskih metoda kako biste vidjeli može li se jedna od njih koristiti za formuliranje rješenja za novi problem. Pa, ako nema takve rezerve, kako onda još uvijek možete razviti dobar algoritam? Gdje početi? Svi smo imali frustrirajuće iskustvo gledanja u zadatak i neznanja što učiniti. Pogledajmo tri opće tehnike rješavanja problema koje su korisne za razvoj algoritama.

Prva metoda povezan sa svođenjem teškog zadatka na niz jednostavnijih zadataka. Naravno, nadamo se da je jednostavnije probleme lakše obraditi nego izvorni problem, a također da se rješenje izvornog problema može izvesti iz rješenja ovih jednostavnijih problema. Ovaj postupak se zove metoda privatnih ciljeva. Ova metoda izgleda vrlo razumno. No, poput većine općih metoda za rješavanje problema ili dizajniranje algoritama, nije uvijek lako prenijeti na određeni problem. Donošenje inteligentnih odluka o lakšim problemima više je umjetnost ili intuicija nego znanost. Ne postoji opći skup pravila za definiranje klase problema koji se mogu riješiti ovim pristupom. Razmišljanje o bilo kojem konkretnom problemu počinje postavljanjem pitanja. Konkretni ciljevi mogu se utvrditi kada se odgovori na sljedeća pitanja:

• 1. Je li moguće riješiti dio problema? Je li moguće riješiti ostatak problema zanemarivanjem nekih uvjeta?
• 2. Je li moguće riješiti problem za posebne slučajeve? Je li moguće razviti algoritam koji proizvodi rješenje koje zadovoljava sve uvjete problema, ali čiji su ulazni podaci ograničeni na neki podskup svih ulaznih podataka?
• 3. Postoji li nešto u vezi s problemom što nije dobro shvaćeno? Ako pokušamo dublje proniknuti u neke značajke problema, hoćemo li moći naučiti nešto što će nam pomoći da pristupimo rješenju?
• 4. Postoji li poznato rješenje za sličan problem? Je li moguće modificirati njegovo rješenje kako bi se riješio problem koji se razmatra? Je li moguće da je ovaj problem ekvivalent poznatom neriješenom problemu?

Druga metoda razvoj algoritma je poznat kao način podizanja. Algoritam podizanja počinje početnim nagađanjem ili izračunavanjem početnog rješenja problema. Tada počinje najbrži mogući uzlazni pomak od početnog rješenja prema boljim rješenjima. Kada algoritam dođe do točke s koje više nije moguće krenuti prema gore, algoritam se zaustavlja. Nažalost, nije uvijek moguće jamčiti da je konačno rješenje dobiveno algoritmom podizanja optimalno. Ova situacija često ograničava korištenje metode podizanja.

Općenito, metode podizanja klasificirane su kao "grube". Pamte neki cilj i pokušavaju učiniti sve što mogu, gdje mogu, da se približe cilju. To ih čini pomalo "kratkovidnima". Kratkovidnost metode dizanja dobro ilustrira sljedeći primjer. Pretpostavimo da trebamo pronaći maksimum funkcije na =/(X), prikazano grafom (sl. 2.15). Ako je početna vrijednost argumenta x = a, tada će metoda uspona dati težnju najbližem cilju, tj. na vrijednost funkcije u točki x = b, dok je pravi maksimum ove funkcije in = c. U ovom slučaju

Riža. 2.15. Ilustracija metode podizanja Metoda podizanja pronalazi lokalni maksimum, ali ne i globalni. Ovo je "grubost" metode dizanja.

Treća metoda poznat kao raditi natrag, one. Rad ovog algoritma počinje s ciljem ili rješenjem problema, a zatim se kreće prema početnoj formulaciji problema. Zatim, ako su te radnje reverzibilne, vraća se od izjave problema do rješenja.

Pogledajmo sve tri metode u problem s džipom. Pretpostavimo da trebate prijeći pustinju od 1000 kilometara u džipu, uz minimalnu potrošnju goriva. Volumen spremnika goriva džipa je 500 litara, gorivo se troši ravnomjerno, 1 litra po 1 km. U isto vrijeme, na početnoj točki postoji neograničen spremnik goriva. Budući da u pustinji nema skladišta goriva, morate instalirati vlastita skladišta i puniti ih gorivom iz spremnika automobila. Dakle, ideja zadatka je jasna: treba se s polazišta odvesti s punim spremnikom na neku udaljenost, tamo postaviti prvo skladište, tamo ostaviti određenu količinu goriva iz spremnika, ali dovoljno da vratiti se. Na početnoj točki ponovno se vrši potpuno punjenje gorivom i pokušava se pomaknuti drugo skladište dalje u pustinju. Ali gdje bi ta skladišta trebala biti postavljena i koliko bi goriva trebalo skladištiti u svakom od njih?

Pristupimo ovom problemu metodom rada unatrag. Na kojoj udaljenosti od kraja možete prijeći pustinju s točno istom količinom goriva? Do tenkovi? Razmotrimo ovo pitanje za Do= 1,2, 3,... dok ne pronađemo takav cijeli broj p,Što n puni spremnici vam omogućuju prijeći cijelu pustinju od 1000 kilometara. Za Do= 1 odgovor je 500 km = 500 l (točka U), kao što je prikazano na sl. 2.16.

Riža. 2.16.

Na mjestu možete natočiti gorivo u automobil U i prijeći preostalih 500 km pustinje. Postavljen je poseban cilj jer se izvorni problem ne može odmah riješiti.

Pretpostavimo da Do= 2, tj. postoje dva puna rezervoara (1000 l). Ova situacija je ilustrirana na sl. 2.16. Koja je najveća vrijednost jCj tako da je, počevši s 1000 L goriva od točke (500 - Xj), moguće prenijeti dovoljno goriva do točke da se dovrši putovanje, kao u Do= 1. Jedan od načina za određivanje prihvatljive vrijednosti X ( je kako slijedi. Točimo gorivo na točki (500 - Xj), idemo X ( kilometara do točke U i ulijte sve gorivo u spremište, osim dijela koji je potreban za povratak u točku (500 - Xj). U ovom trenutku spremnik postaje prazan. Sada punimo drugi spremnik, vozimo Xj kilometara do U, preuzeti u U tamo ostalo gorivo, a od U Idemo u C s punim rezervoarom. Ukupna prijeđena udaljenost sastoji se od tri segmenta X ( kilometara i jedan segment Sunce Dugačak 500 km. Stoga iz jednadžbe 3x t + 500 = 1000 nalazimo njezino rješenje Xj = 500/3. Dakle, dva spremnika (1000 l) omogućuju vam putovanje Z> 2 = 500 +x ( = 500(1 + 1/3) km.

Razmotrimo k = 3. S koje točke možete krenuti s 1500 litara goriva tako da džip može dostaviti 1000 litara do točke (500 - x))? Nađimo najveću vrijednost x 2 tako da, polazeći s 1500 litara goriva od točke (500 - Xj - x 2), možemo isporučiti 1000 litara do točke (500 - Xj). Napuštamo točku (500 - Xj - x 2), vozimo do (500 - x), pretačemo svo gorivo osim x 2 litre i vraćamo se na točku (500 - Xj - x 2) s praznim spremnikom. Ponavljajući ovaj postupak, potrošit ćemo 4x 2 litre na putovanju i ostaviti (1000 - 4x 2) litara na točki (500 - x L). Sada je na točki (500 - Xj - x 2) ostalo točno 500 litara. Napunimo zadnjih 500 litara i idemo do točke (500 - Xj), potrošivši na to x 2 litre.

Budući da smo na točki (500 - Xj), trošimo 5x 2 litre goriva na putovanje. Ovdje je ostalo ukupno (1500 - 5x 2) litara. Ova količina treba biti jednaka 1000 l, tj. x 2 = 500/5. Iz ovoga zaključujemo da vam 1500 litara omogućuje vožnju

Nastavljajući proces rada unatrag induktivno, dobivamo to n spremnici goriva omogućuju nam prolaz Dn kilometara, gdje Dn = 500(1 +1/3 + 1/5 + ... + 1/(2n - 1)).

Moramo pronaći najmanju vrijednost p, kod kojih Dn> 1000. Jednostavni izračuni pokazuju da za n = 7 imamo D?= 997,5 km, tj. sedam spremnika, odnosno 3500 litara goriva omogućit će vam putovanje

• 977,5 km. Pun osmi spremnik - to bi bilo više nego potrebno za prijevoz 3500 litara od točke A do točke koja se nalazi na
• 22,5 km (1000 - 977,5) od A. Čitatelj ima priliku samostalno provjeriti je li 337,5 litara dovoljno za isporuku 3500 litara goriva do oznake od 22,5 km. Dakle, da biste automobilom prešli pustinju od I do C, potrebno vam je 3837,5 litara goriva.

Sada se algoritam transporta goriva može predstaviti na sljedeći način. Počinjemo od A, koji ima 3837,5 litara. Ovdje ima taman toliko goriva da se postupno preveze 3500 litara do oznake

22,5 km, gdje će džip na kraju završiti s praznim spremnikom i dovoljno goriva za 7 punjenja. Ovo gorivo je dovoljno za transport 3000 litara do točke 22,5 + 500/13 km od A, gdje će rezervoar automobila opet biti prazan. Naknadni prijevoz će dovesti džip do točke koja se nalazi 22,5 + 500/13 + 500/11 km od A, sa praznim rezervoarom automobila i 2500 l u skladištu.

Nastavljajući na taj način, idemo naprijed zahvaljujući analizi provedenoj radom unatrag. Uskoro će džip biti na 500(1 - 1/3) km sa 1000 litara goriva. Zatim ćemo do mjesta prevesti 500 litara goriva U, ulijmo ih u rezervoar auta i odvezimo se do mjesta bez zaustavljanja S(Slika 2.17).

Riža. 2.17.

Za one koji su upoznati s beskonačnim nizovima, obratite pažnju na to D Postoji n-ti parcijalni zbroj neparnog harmonijskog niza. Budući da se ovaj niz razlikuje, algoritam omogućuje prelazak bilo koje pustinje. Pokušajte modificirati ovaj algoritam da ostavite dovoljno goriva na raznim točkama u pustinji za povratak na točku A.

Postavlja se pitanje je li moguće prijeći 1000 km s manje od 3837,5 litara goriva. Ispostavilo se da ne možete. Dokaz ove tvrdnje prilično je složen. Međutim, može se iznijeti sljedeći, prilično uvjerljiv, argument. Očito glumimo na najbolji mogući način Za Do= 1. Kada Do= 2 plana koji se koristi za Do= 1 i tada se aktivira drugi spremnik goriva kako bi bio što dalje od točke U. Polazna pretpostavka za Do tenkova je da znamo kako najbolje postupiti u slučaju (Za - 1) tenkove, i pomaknite se što je više moguće uz pomoć WHO tenk.

Dakle, u razmatranom problemu, metoda rada unatrag je da se problem rješava kao od kraja; metoda parcijalnih ciljeva je da oni ne rješavaju cijeli problem odjednom, već, takoreći, u dijelovima; i, konačno, metoda uspona očituje se u činjenici da se rješenje ne nalazi odmah, već sekvencijalno, kao da mu se približava.

TEST PITANJA

• 1. Definirajte objekt, klasu, sustav, model.
• 2. Navedite glavne vrste modela.
• 3. Što je simulacijsko modeliranje?
• 4. Koje klasifikacije modela postoje?
• 5. Navedite glavne faze modeliranja.
• 6. Što je algoritam?
• 7. Navedite svojstva algoritma.
• 8. Koje se faze provode u kompletnoj konstrukciji algoritma?
• 9. Što je dijagram toka algoritma?
• 10. Definirajte funkcijski blok.
• 11. Koji se algoritam naziva strukturnim?
• 12. Navedite glavna načela na kojima se temelji stvaranje učinkovitih algoritama.