Mai mulți algoritmi diferiți pot fi dezvoltați pentru a rezolva aceeași problemă. Prin urmare, apare sarcina de a alege cei mai eficienți algoritmi. Rețineți că evaluarea cu precizie a eficacității algoritmilor este o sarcină foarte dificilă și în fiecare caz specific necesită cercetări speciale.

Acea parte a teoriei algoritmilor care se ocupă cu estimarea caracteristicilor algoritmilor se numește metrică. Poate fi împărțit în descriptiv (calitativ) și metric (cantitativ). Primul examinează algoritmii din punctul de vedere al corespondenței pe care o stabilesc între datele de intrare și rezultate. Cel de-al doilea examinează algoritmii din punctul de vedere al complexității atât a algoritmilor înșiși, cât și a „calculelor” pe care le specifică, adică procesele de transformare secvențială a obiectelor structurale. Este important de subliniat faptul că complexitatea algoritmilor și calculelor poate fi determinată în diferite moduri și se poate dovedi că, cu o singură metodă, algoritmul A va fi mai greu ÎN, iar cu cealaltă metodă este invers.

Cel mai adesea, algoritmii sunt evaluați în funcție de memoria necesară, numărul de operații efectuate, timpul de rezolvare sau eroarea de calcul. Aceste caracteristici depind adesea de parametrii (dimensiunile) problemei și sunt neliniare. Prin urmare, în teoria algoritmilor, există o direcție de evaluare a eficacității algoritmilor prin estimări asimptotice ale funcțiilor: memoria necesară, timpul de calcul etc. În acest caz, se determină cel mai semnificativ parametru al funcției și se studiază comportamentul funcției pe măsură ce valorile parametrilor cresc. În cursul studiului, ei încearcă să determine natura dependenței valorilor caracteristicilor algoritmului luat în considerare de parametru. Poate fi liniară (adică proporțională cu parametrul n), logaritmică (adică proporțională cu log n), pătratică (adică proporțională cu n 2), etc. Comparând estimările asimptotice ale algoritmilor care rezolvă aceeași problemă, puteți alege un algoritm mai eficient. Ei spun că valoarea unui parametru T(n) este de ordinul n x dacă există constante pozitive k și n o astfel încât pentru toate n³n o inegalitatea T(n) ≤ k n x să fie valabilă.

Să presupunem că n este cantitatea de date numerice primite la intrarea mai multor algoritmi diferiți (A 1, A 2, A 3, A 4, A 5), care efectuează calcule cu aceeași viteză - 1000 de operații pe secundă, dar au diferiți estimări asimptotice. Tabelul 1.8 prezintă valorile lui n pe care acești algoritmi le pot procesa în 1 secundă, 1 minut și 1 oră (valorile sunt rotunjite în jos la cel mai apropiat număr întreg). Datele din Tabelul 1.3 arată clar că performanța algoritmului (adică, numărul de date procesate pe unitatea de timp) depinde în mod semnificativ de natura funcției de evaluare asimptotică.

Testarea algoritmilor dezvoltați se efectuează de obicei la valori mici ale parametrului n. O astfel de testare vă permite să câștigați încredere în performanța algoritmului, dar nu garantează deloc finalizarea sarcinii pentru valori mari ale lui n. Este posibil să nu avem suficientă memorie sau timp pentru computer pentru a rezolva o problemă reală. Estimările asimptotice sunt importante în sensul că fac posibilă estimarea suficienței resurselor informatice pentru calcule practice cu limite cunoscute de modificare a parametrului n.

Eficiența algoritmului este o proprietate a unui algoritm care este asociată cu resursele de calcul utilizate de algoritm. Algoritmul trebuie analizat pentru a determina resursele cerute de algoritm. Eficiența algoritmului poate fi considerată analogă cu productivitatea de fabricație a proceselor repetitive sau continue.

Pentru a obține o eficiență maximă, dorim să reducem utilizarea resurselor. Cu toate acestea, resurse diferite (cum ar fi timpul și memoria) nu pot fi comparate direct, astfel încât care dintre cei doi algoritmi este considerat mai eficient depinde adesea de ce factor este mai important, cum ar fi cerința pentru viteză mare, utilizarea minimă a memoriei sau o altă măsură a eficienţă.

fundal

Importanța eficienței cu accent pe timpul de execuție a fost subliniată de Ada Lovelace în 1843 cu privire la motorul analitic mecanic al lui Charles Babbage:

„În aproape toate calculatoarele, există o gamă largă de configurații posibile pentru a finaliza cu succes procesul și diferite convenții ar trebui să influențeze alegerea în scopul efectuării calculului. Esențial este să alegeți o configurație care va avea ca rezultat reducerea la minimum a timpului necesar pentru efectuarea calculului.”

Calculatoarele electronice timpurii erau foarte limitate atât ca viteză, cât și ca memorie. În unele cazuri, s-a realizat că există un compromis timp-memorie, în care o sarcină trebuie fie să folosească o cantitate mare de memorie pentru a atinge viteză mare, fie să folosească un algoritm mai lent care utilizează o cantitate mică de memorie de lucru. În acest caz, a fost folosit cel mai rapid algoritm pentru care memoria disponibilă a fost suficientă.

Calculatoarele moderne sunt mult mai rapide decât acele computere timpurii și au mult mai multă memorie (gigabytes în loc de kilobytes). Cu toate acestea, Donald Knuth subliniază că eficiența rămâne un factor important:

„În disciplinele de inginerie consacrate, o îmbunătățire de 12% este ușor de realizat și nu a fost niciodată considerată prohibitivă și cred că același lucru ar trebui să fie valabil și în programare.”

Revizuire

Un algoritm este considerat eficient dacă consumul său de resurse (sau costul resurselor) este la sau sub un nivel acceptabil. Aproximativ vorbind, „acceptabil” aici înseamnă „algoritmul va rula pentru o perioadă rezonabilă de timp pe un computer disponibil”. Deoarece a existat o creștere semnificativă a puterii de procesare și a memoriei disponibile a computerelor începând cu anii 1950, „nivelul acceptabil” actual nu era acceptabil nici măcar acum 10 ani.

Producătorii de computere lansează periodic noi modele, adesea mai puternice. Preț software poate fi destul de mare, așa că în unele cazuri este mai ușor și mai ieftin să obțineți performanțe mai bune prin achiziționarea unui computer mai rapid, compatibil cu computerul dvs. existent.

Există multe moduri de a măsura resursele utilizate de un algoritm. Cele mai utilizate două măsurători sunt viteza și memoria utilizată. Alte măsurători pot include viteza de transfer, utilizarea temporară a discului, utilizarea pe termen lung a discului, consumul de energie, costul total de proprietate, timpul de răspuns la semnalele externe și așa mai departe. Multe dintre aceste măsurători depind de dimensiunea datelor de intrare ale algoritmului (adică, cantitățile care necesită procesare a datelor). Măsurătorile pot depinde și de modul în care sunt prezentate datele (de exemplu, unii algoritmi de sortare funcționează slab pe datele deja sortate sau când datele sunt sortate în ordine inversă).

În practică, există și alți factori care influențează eficacitatea algoritmului, cum ar fi acuratețea și/sau fiabilitatea necesară. După cum se explică mai jos, modul în care este implementat un algoritm poate avea, de asemenea, un efect semnificativ asupra performanței reale, deși multe aspecte ale implementării sunt probleme de optimizare.

Analiza teoretică

ÎN analiza teoreticăÎn algoritmi, este o practică obișnuită să se estimeze complexitatea unui algoritm în comportamentul său asimptotic, adică să se reflecte complexitatea algoritmului în funcție de mărimea intrării. n Se folosește notația O mare. Această estimare este, în general, destul de precisă pentru mari n, dar poate duce la concluzii incorecte la valori mici n(Astfel, sortarea cu bule, care este considerată lentă, poate fi mai rapidă decât sortarea rapidă dacă trebuie doar să sortați câteva elemente).

Teste de verificare: Măsurarea performanței

Pentru versiuni noi de software sau pentru a oferi comparații cu sisteme rivale, benchmark-urile sunt uneori folosite pentru a compara performanța relativă a algoritmilor. Dacă, de exemplu, este lansat un nou algoritm de sortare, acesta poate fi comparat cu predecesorii pentru a se asigura că algoritmul este cel puțin la fel de eficient pe datele cunoscute ca și alții. Testele de performanță pot fi folosite de utilizatori pentru a compara produse de la diferiți producători pentru a evalua ce produs se va potrivi cel mai bine cerințelor lor în ceea ce privește funcționalitatea și performanța.

Unele teste de referință oferă o analiză comparativă a diferitelor limbaje de compilare și interpretare, cum ar fi colecția de benchmark pentru PC de la Roy Longbottom și Jocul de referință în limbajul computerului compară performanța implementărilor de sarcini tipice în unele limbaje de programare.

Probleme de implementare

Problemele de implementare pot afecta, de asemenea, performanța reală. Aceasta include alegerea limbajului de programare și modul în care algoritmul este de fapt codificat, alegerea traducătorului pentru limbajul ales sau opțiunile de compilare utilizate și chiar tipul de sistem de operare. În unele cazuri, un limbaj implementat ca interpret poate fi semnificativ mai lent decât un limbaj implementat ca compilator.

Există și alți factori care pot afecta sincronizarea sau utilizarea memoriei, care sunt dincolo de controlul programatorului. Aceasta include alinierea datelor, detalierea, colectarea gunoiului , paralelism la nivel de instrucţiuni şi apelare subrutine .

Unele procesoare au capacitatea de a efectua operații vectoriale, ceea ce permite unei singure operații să proceseze mai mulți operanzi. Poate fi sau nu ușor să utilizați astfel de caracteristici la nivel de programare sau compilare. Algoritmii proiectați pentru calculul secvenţial pot necesita o reproiectare completă pentru a se adapta calculului paralel.

O altă problemă poate apărea cu compatibilitatea procesorului, în care instrucțiunile pot fi implementate diferit, astfel încât instrucțiunile pe unele modele pot fi relativ mai lente pe alte modele. Aceasta poate fi o problemă pentru compilatorul de optimizare.

Măsurarea utilizării resurselor

Măsurătorile sunt de obicei exprimate în funcție de dimensiunea intrării n.

Cele mai importante două dimensiuni sunt:

• Timp: Cât durează algoritmul pe CPU.
• Memorie: Câtă memorie de lucru (de obicei RAM) este necesară pentru algoritm. Există două aspecte în acest sens: cantitatea de memorie pentru cod și cantitatea de memorie pentru datele pe care operează codul.

Pentru calculatoarele alimentate cu baterie (cum ar fi laptopurile) sau pentru calcule foarte lungi/mari (cum ar fi supercalculatoarele), un alt tip de măsurare este de interes:

• Consum direct de energie: Energia necesară pentru a rula un computer.
• Consum indirect de energie: Energie necesară pentru răcire, iluminare etc.

În unele cazuri, sunt necesare alte măsurători, mai puțin obișnuite:

• Dimensiunea angrenajului: Lățimea de bandă poate fi factorul limitator. Comprimarea poate fi utilizată pentru a reduce cantitatea de date transferate. Afișarea unei imagini sau a unei imagini (cum ar fi sigla Google) poate duce la transferul a zeci de mii de octeți (48K în acest caz). Comparați acest lucru cu transmiterea celor șase octeți din cuvântul „Google”.
• Memorie externa: Memorie necesară pe un disc sau alt dispozitiv de stocare extern. Această memorie poate fi folosită pentru stocare temporară sau pentru utilizare ulterioară.
• Timp de raspuns: Această setare este deosebit de importantă pentru aplicațiile în timp real în care computerul trebuie să răspundă rapid la evenimente externe.
• Costul total de proprietate: Parametrul este important atunci când se intenționează să execute un singur algoritm.

Timp

Teorie

Acest tip de test depinde semnificativ și de alegerea limbajului de programare, a compilatorului și a opțiunilor acestuia, astfel încât algoritmii comparați trebuie implementați în aceleași condiții.

Memorie

Această secțiune tratează utilizarea memoriei principale (adesea RAM) necesară algoritmului. Ca și în cazul analizei de timp de mai sus, se utilizează de obicei analiza unui algoritm complexitatea spațială a algoritmului pentru a estima memoria de rulare necesară în funcție de dimensiunea de intrare. Rezultatul este de obicei exprimat în termeni de „O” mare.

Există patru aspecte ale utilizării memoriei:

• Cantitatea de memorie necesară pentru stocarea codului algoritmului.
• Cantitatea de memorie necesară pentru datele de intrare.
• Cantitatea de memorie necesară pentru orice ieșire (unii algoritmi, cum ar fi sortările, rearanjează frecvent intrarea și nu necesită memorie suplimentară pentru ieșire).
• Cantitatea de memorie necesară procesului de calcul în timpul calculului (aceasta include variabilele numite și orice spațiu de stivă necesar pentru apelurile subrutinei, care poate fi semnificativ când se utilizează recursiunea).

Primele calculatoare electronice și computerele de acasă aveau capacități de memorie de lucru relativ mici. Astfel, în 1949 EDSAC avea o memorie de lucru maximă de 1024 de cuvinte pe 17 biți, iar în 1980 Sinclair ZX80 a fost lansat cu 1024 de octeți de memorie de lucru.

Calculatoarele moderne pot avea cantități relativ mari de memorie (poate gigaocteți), astfel încât comprimarea memoriei utilizate de un algoritm într-o anumită cantitate de memorie este mai puțin necesară decât înainte. Cu toate acestea, existența a trei categorii diferite de memorie este semnificativă:

• Cache (deseori RAM statică) - rulează la viteze comparabile cu procesorul
• Memoria fizică principală (de multe ori RAM dinamică) - rulează puțin mai lent decât CPU
• Memoria virtuală (adesea pe disc) - dă iluzia unei memorie uriașe, dar funcționează de mii de ori mai lent decât RAM.

Un algoritm a cărui memorie necesară se încadrează în memoria cache a computerului este mult mai rapid decât un algoritm care se încadrează în memoria principală, care, la rândul său, va fi mult mai rapid decât un algoritm care utilizează spațiu virtual. Complicarea problemelor este faptul că unele sisteme au până la trei niveluri de cache. Sistemele diferite au cantități diferite din aceste tipuri de memorie, astfel încât efectul de memorie asupra unui algoritm poate varia semnificativ de la un sistem la altul.

În primele zile ale calculului electronic, dacă un algoritm și datele sale nu se potriveau în memoria principală, nu putea fi folosit. În zilele noastre, utilizarea memoriei virtuale oferă memorie masivă, dar cu prețul performanței. Dacă algoritmul și datele sale se potrivesc în cache, se poate obține o viteză foarte mare, astfel încât reducerea la minimum a memoriei necesare ajută la minimizarea timpului. Un algoritm care nu se încadrează în întregime în cache, dar oferă localitatea legăturilor, poate funcționa relativ rapid.

Exemple de algoritmi eficienți

Critica privind starea actuală a programării

Programele devin mai lente mai rapid decât computerele devin mai rapide.

În sistemele răspândite, reducerea la jumătate a execuției instrucțiunilor poate dubla durata de viață a bateriei, iar datele mari oferă o oportunitate pentru algoritmi mai buni: Reducerea numărului de operații de la N x N la N x log(N) are un efect puternic pentru N mari... Pentru N = 30 de miliarde, aceste schimbări sunt similare cu 50 de ani de îmbunătățiri tehnologice.

Concurență pentru cel mai bun algoritm

Următoarele competiții invită participarea la dezvoltarea celor mai buni algoritmi, ale căror criterii de calitate sunt stabilite de arbitri:

Vezi si

• Codarea aritmetică este un tip de codificare entropică cu lungime variabilă a codului pentru compresia eficientă a datelor
• O matrice asociativă este o structură de date care poate fi făcută mai eficientă atunci când este utilizată copaci PATRICIA sau Matrice Judy
• Test de performanță - o metodă de măsurare a timpului de execuție comparativ în anumite cazuri
• Cel mai bun, cel mai rău și mediu caz- convenții pentru estimarea timpului de execuție pentru trei scenarii
• Căutarea binară este o tehnică simplă și eficientă pentru căutarea unei liste sortate
• Masa ramurilor

Trimiteți-vă munca bună în baza de cunoștințe este simplu. Utilizați formularul de mai jos

Studenții, studenții absolvenți, tinerii oameni de știință care folosesc baza de cunoștințe în studiile și munca lor vă vor fi foarte recunoscători.

Nu există încă o versiune HTML a lucrării.
Puteți descărca arhiva lucrării făcând clic pe linkul de mai jos.

Documente similare

Descrierea modelului formal al algoritmului bazat pe funcții recursive. Dezvoltarea unui model analitic și de program al unui algoritm pentru o mașină de recunoaștere Turing. Dezvoltarea unui model analitic al algoritmului folosind algoritmi normali Markov.

lucrare de curs, adăugată 07.07.2013


Conceptul de algoritm și analiza estimărilor teoretice ale complexității în timp a algoritmilor de multiplicare matriceală. Analiza comparativă a estimării complexității în timp a unor clase de algoritmi folosind programarea convențională și programarea folosind tehnologia Open MP.

teză, adăugată 08.12.2017


Concept general algoritm și măsuri ale complexității acestuia. Complexitatea de timp și capacitate a algoritmilor. Metode și tehnici de bază de analiză a complexității. Optimizare asociată cu alegerea metodei de construire a unui algoritm și cu alegerea metodelor de prezentare a datelor în program.

rezumat, adăugat 27.11.2012


Problema îmbunătățirii calității amprentelor digitale în vederea creșterii eficienței algoritmilor de autentificare biometrică. Revizuirea algoritmilor de procesare a imaginilor cu amprentă. Analiza unui algoritm bazat pe utilizarea transformării Gabor.

teză, adăugată 16.07.2014


Metode de organizare a procesului de calcul în sisteme cu procesoare multiple. Dezvoltarea unui program bazat pe algoritmi pentru sisteme multiprocesor pentru procesarea în lot a sarcinilor. Calculul indicatorilor cheie de performanță pentru fiecare algoritm.

lucrare curs, adaugat 21.06.2013


Estimarea complexității de calcul a programului. Implementarea algoritmului de codificare a informațiilor Huffman. Codificarea testului în arbori binari și Huffman. Cod de caractere binar. Simbolul și frecvența apariției sale în text. Calculul complexității algoritmului.

test, adaugat 16.12.2012


Trecerea de la o formulare verbală informală la o formulare matematică a acestei probleme. Evaluați diferite opțiuni pentru a selecta cele mai eficiente structuri de date și algoritmi de procesare. Implementarea algoritmilor intr-unul din limbajele de programare.

lucrare curs, adaugat 25.06.2013

Principii de bază pentru crearea algoritmilor eficienți

Oricine dezvoltă algoritmi trebuie să stăpânească câteva tehnici și concepte de bază. Oricine s-a confruntat vreodată cu o sarcină dificilă s-a confruntat cu întrebarea: „De unde să încep?” O modalitate posibilă este să vă uitați prin stocul dvs. de metode algoritmice comune pentru a vedea dacă una dintre ele poate fi folosită pentru a formula o soluție la o nouă problemă. Ei bine, dacă nu există o astfel de rezervă, atunci cum puteți dezvolta un algoritm bun? Unde sa încep? Cu toții am avut experiența frustrantă de a ne uita la o sarcină și de a nu ști ce să facem. Să ne uităm la trei tehnici generale de rezolvare a problemelor care sunt utile pentru dezvoltarea algoritmilor.

Prima metodă asociat cu reducerea unei sarcini dificile la o succesiune de sarcini mai simple. Desigur, speranța este că problemele mai simple sunt mai ușor de procesat decât problema inițială și, de asemenea, că o soluție la problema inițială poate fi derivată din soluțiile la aceste probleme mai simple. Această procedură se numește metoda scopurilor private. Această metodă pare foarte rezonabilă. Dar, la fel ca majoritatea metodelor generale de rezolvare a problemelor sau de proiectare a algoritmilor, nu este întotdeauna ușor de transferat la o anumită problemă. A face alegeri inteligente despre probleme mai ușoare este mai mult o artă sau intuiție decât o știință. Nu există un set general de reguli pentru a defini clasa de probleme care pot fi rezolvate folosind această abordare. Gândirea la orice problemă specifică începe cu a pune întrebări. Se pot stabili obiective specifice atunci când se răspunde la următoarele întrebări:

• 1. Este posibil să se rezolve o parte a problemei? Este posibil să rezolvi restul problemei ignorând unele condiții?
• 2. Este posibil să se rezolve problema pentru cazuri speciale? Este posibil să se dezvolte un algoritm care să producă o soluție care să satisfacă toate condițiile problemei, dar ale cărei date de intrare sunt limitate la un subset al tuturor datelor de intrare?
• 3. Există ceva legat de problemă care nu este bine înțeles? Dacă încercăm să aprofundăm unele dintre caracteristicile problemei, vom putea învăța ceva care ne va ajuta să abordăm o soluție?
• 4. Există o soluție cunoscută la o problemă similară? Este posibil să-i modifici soluția pentru a rezolva problema luată în considerare? Este posibil ca această problemă să fie echivalentă cu o problemă cunoscută nerezolvată?

A doua metodă dezvoltarea algoritmului este cunoscută ca metoda de ridicare. Algoritmul de ridicare începe prin a face o estimare inițială sau prin a calcula o soluție inițială a problemei. Apoi, cea mai rapidă mișcare ascendentă posibilă începe de la soluția inițială către soluții mai bune. Când algoritmul atinge un punct din care nu mai este posibil să se deplaseze în sus, algoritmul se oprește. Din păcate, nu este întotdeauna posibil să se garanteze că soluția finală obținută de algoritmul de ridicare este optimă. Această situație limitează adesea utilizarea metodei de ridicare.

În general, metodele de ridicare sunt clasificate drept „aspre”. Își amintesc de un scop și încearcă să facă tot ce pot, acolo unde pot, pentru a se apropia de obiectiv. Acest lucru îi face oarecum „miopi”. Miopia metodei de ridicare este bine ilustrată de următorul exemplu. Să presupunem că trebuie să găsim maximul unei funcții la =/(X), prezentate de grafic (Fig. 2.15). Dacă valoarea inițială a argumentului x = a, atunci metoda de ascensiune va da aspirație la cel mai apropiat obiectiv, adică. la valoarea funcţiei la punct x = b,întrucât adevăratul maxim al acestei funcții este în = c. În acest caz

Orez. 2.15. O ilustrare a metodei de ridicare Metoda de ridicare găsește un maxim local, dar nu unul global. Aceasta este „rugozitatea” metodei de ridicare.

A treia metodă cunoscut ca lucrând înapoi, acestea. Lucrarea acestui algoritm începe cu un scop sau o soluție la o problemă și apoi se îndreaptă către formularea inițială a problemei. Apoi, dacă aceste acțiuni sunt reversibile, se face o mișcare înapoi de la enunțul problemei la soluție.

Să ne uităm la toate cele trei metode în problema jeep-ului. Să presupunem că trebuie să traversezi un deșert de 1000 de kilometri cu un jeep, folosind un minim de combustibil. Volumul rezervorului de combustibil al jeep-ului este de 500 de litri, combustibilul este consumat uniform, 1 litru la 1 km. În același timp, la punctul de plecare există un rezervor nelimitat de combustibil. Deoarece nu există depozite de combustibil în deșert, trebuie să vă instalați propriile depozite și să le umpleți cu combustibil din rezervorul mașinii. Deci, ideea problemei este clară: trebuie să plecați de la punctul de plecare cu rezervorul plin pe o anumită distanță, să instalați primul depozit acolo, să lăsați o anumită cantitate de combustibil din rezervor acolo, dar suficient pentru Vino înapoi. La punctul de plecare, se efectuează din nou realimentarea completă și se încearcă mutarea celui de-al doilea depozit mai departe în deșert. Dar unde ar trebui înființate aceste depozite și cât combustibil ar trebui să fie depozitat în fiecare dintre ele?

Să abordăm această problemă folosind metoda de lucru invers. La ce distanță de la capăt poți traversa deșertul cu exact aceeași cantitate de combustibil? La tancuri? Să luăm în considerare această întrebare pentru La= 1,2, 3,... până când găsim un astfel de număr întreg P, Ce P tancurile pline vă permit să traversați întregul deșert de 1000 de kilometri. Pentru La= 1 răspuns este 500 km = 500 l (punct ÎN), după cum se arată în fig. 2.16.

Orez. 2.16.

Vă puteți alimenta mașina la punctul ÎNși traversează restul de 500 km de deșert. Un anumit scop a fost stabilit deoarece problema inițială nu poate fi rezolvată imediat.

Să ne prefacem că La= 2, adică sunt doua rezervoare pline (1000 l). Această situație este ilustrată în Fig. 2.16. Care este valoarea maximă a lui jCj astfel încât, începând cu 1000 L de combustibil din punctul (500 - Xj), să fie posibil să transportați suficient combustibil până la punctul pentru a finaliza călătoria, ca în La= 1. O modalitate de a determina o valoare acceptabilă X ( este după cum urmează. Facem plinul la punctul (500 - Xj), mergem X ( kilometri până la punct ÎNși turnați tot combustibilul în depozit, cu excepția piesei care trebuie să revină la punctul (500 - Xj). În acest moment rezervorul devine gol. Acum umplem al doilea rezervor, conducem Xj kilometri până ÎN, ridicați la ÎN combustibil rămas acolo, și din ÎN Mergem la C cu rezervorul plin. Distanța totală parcursă constă din trei segmente de-a lungul X ( kilometri și un segment Soare 500 km lungime. Prin urmare, din ecuația 3x t + 500 = 1000 găsim soluția ei Xj = 500/3. Astfel, două rezervoare (1000 l) vă permit să călătoriți Z> 2 = 500 +x ( = 500(1 + 1/3) km.

Sa luam in considerare k = 3. Din ce punct poti pleca cu 1500 de litri de combustibil pentru ca jeep-ul sa poata livra 1000 de litri pana la punctul (500 - x))? Să găsim cea mai mare valoare a lui x 2 astfel încât, plecând cu 1500 litri de combustibil din punct (500 - Xj - x 2), să putem livra 1000 litri până la punctul (500 - Xj). Părăsim punctul (500 - Xj - x 2), mergem la (500 - x), transferăm tot combustibilul, cu excepția x 2 litri, și revenim la punctul (500 - Xj - x 2) cu rezervorul gol. Repetând această procedură, vom cheltui 4x 2 litri în călătorie și vom lăsa (1000 - 4x 2) litri la punctul (500 - x L). Acum, în punctul (500 - Xj - x 2) au mai rămas exact 500 de litri. Umplem cu ultimii 500 de litri și mergem la punctul (500 - Xj), după ce am cheltuit x 2 litri pentru asta.

Fiind în punctul (500 - Xj), cheltuim 5x 2 litri de combustibil în călătorie. Un total de (1500 - 5x 2) litri au rămas aici. Această cantitate ar trebui să fie egală cu 1000 l, adică. x 2 = 500/5. De aici tragem concluzia că 1500 de litri vă permit să conduceți

Continuând procesul de lucru înapoi în mod inductiv, obținem asta P rezervoarele de combustibil ne permit să trecem Dn kilometri, unde Dn = 500(1 +1/3 + 1/5 + ... + 1/(2P - 1)).

Trebuie să găsim cea mai mică valoare P, la care Dn> 1000. Calculele simple arată că pt n = 7 avem D?= 997,5 km, adică șapte rezervoare, sau 3500 de litri, de combustibil vă vor permite să călătoriți

• 977,5 km. Un al optulea rezervor plin - ar fi mai mult decât necesar pentru a transporta 3500 de litri din punct A până la un punct situat la
• 22,5 km (1000 - 977,5) de la A Cititorului i se oferă posibilitatea de a verifica independent dacă 337,5 litri sunt suficienți pentru a livra 3500 de litri de combustibil până la marcajul de 22,5 km. Astfel, pentru a traversa deșertul cu mașina de la I la C ai nevoie de 3837,5 litri de combustibil.

Acum algoritmul de transport al combustibilului poate fi prezentat după cum urmează. Pornim de la A, având 3837,5 litri. Aici este suficient combustibil pentru a transporta treptat 3500 de litri până la marcaj

22,5 km, unde jeep-ul va ajunge în cele din urmă cu un rezervor gol și suficient combustibil pentru 7 rezerve complete. Acest combustibil este suficient pentru a transporta 3000 de litri la un punct la 22,5 + 500/13 km de A, unde rezervorul mașinii va fi din nou gol. Transportul ulterior va aduce jeep-ul într-un punct situat la 22,5 + 500/13 + 500/11 km de A, cu rezervorul gol al mașinii și 2500 l în depozit.

Continuând în acest fel, mergem înainte grație analizei efectuate lucrând înapoi. În curând, jeep-ul va ajunge la 500 (1 - 1/3) km cu 1000 de litri de combustibil. Apoi vom transporta 500 de litri de combustibil la obiect ÎN, Să le turnăm în rezervorul mașinii și să conducem până la punct fără a ne opri CU(Fig. 2.17).

Orez. 2.17.

Pentru cei familiarizați cu seria infinită, rețineți că D Există P-a-a sumă parțială a unei serii armonice impare. Deoarece această serie diverge, algoritmul face posibilă traversarea oricărui deșert. Încercați să modificați acest algoritm pentru a lăsa suficient combustibil în diferite puncte din deșert pentru a vă întoarce la punct A.

Se pune întrebarea dacă este posibil să parcurgeți 1000 km folosind mai puțin de 3837,5 litri de combustibil. Se dovedește că nu poți. Dovada acestei afirmații este destul de complicată. Cu toate acestea, se poate face următorul argument, destul de plauzibil. Evident, acţionăm cel mai bun mod Pentru La= 1. Când La= 2 plan folosit pentru La= 1 și apoi se activează al doilea rezervor de combustibil pentru a fi cât mai departe de punct ÎN. Premisa de pornire pentru La tancuri este că știm cum să acționăm cel mai bine în cazul (La - 1) tancuri și întoarceți-vă cât mai departe posibil cu ajutorul OMS rezervor.

Deci, în problema avută în vedere, metoda de lucru invers este ca problema să fie rezolvată ca de la capăt; metoda obiectivelor parțiale este aceea că nu rezolvă întreaga problemă deodată, ci, parcă, pe părți; si, in sfarsit, metoda de ascensiune se manifesta prin faptul ca solutia nu se gaseste imediat, ci secvential, parca s-ar apropia de ea.

ÎNTREBĂRI DE CONTROL

• 1. Dați o definiție a unui obiect, clasă, sistem, model.
• 2. Numiți principalele tipuri de modele.
• 3. Ce este modelarea prin simulare?
• 4. Ce clasificări ale modelelor există?
• 5. Indicați etapele principale ale modelării.
• 6. Ce este un algoritm?
• 7. Enumerați proprietățile algoritmului.
• 8. Ce etape se parcurg în construcția completă a algoritmului?
• 9. Ce este o diagramă de flux de algoritm?
• 10. Definiți un bloc funcțional.
• 11. Ce algoritm se numește structural?
• 12. Numiți principalele principii care stau la baza creării algoritmilor eficienți.