Може да се развијат неколку различни алгоритми за да се реши истиот проблем. Затоа, се поставува задачата за избор на најефикасните алгоритми. Забележете дека прецизното оценување на ефективноста на алгоритмите е многу тешка задача и во секој конкретен случај бара посебно истражување.

Тој дел од теоријата на алгоритми кој се занимава со проценка на карактеристиките на алгоритмите се нарекува метрички. Може да се подели на описен (квалитативен) и метрички (квантитативен). Првиот ги испитува алгоритмите од гледна точка на кореспонденцијата што ја воспоставуваат помеѓу влезните податоци и резултатите. Вториот ги испитува алгоритмите од гледна точка на сложеноста и на самите алгоритми и на „пресметките“ што тие ги специфицираат, т.е., процесите на секвенцијална трансформација на структурните објекти. Важно е да се нагласи дека сложеноста на алгоритмите и пресметките може да се одреди на различни начини и може да испадне дека со еден метод алгоритмот Аќе биде потешко ВО, а со другиот метод е обратно.

Најчесто, алгоритмите се оценуваат според потребната меморија, бројот на извршени операции, времето на решавање или грешката во пресметката. Овие карактеристики често зависат од параметрите (димензиите) на проблемот и се нелинеарни. Затоа, во теоријата на алгоритми постои насока за проценка на ефективноста на алгоритмите со асимптотични проценки на функции: потребна меморија, време на пресметување итн. Во овој случај, се одредува најзначајниот параметар на функцијата и се проучува однесувањето на функцијата како што се зголемуваат вредностите на параметарот. Во текот на студијата, тие се обидуваат да ја утврдат природата на зависноста на вредностите на карактеристиките на алгоритмот што се разгледува од параметарот. Може да биде линеарен (т.е. пропорционален на параметарот n), логаритамски (т.е. пропорционален на log n), квадратен (т.е. пропорционален на n 2) итн. Со споредување на асимптотичните проценки на алгоритми кои го решаваат истиот проблем, можете да изберете поефикасен алгоритам. Тие велат дека вредноста на некој параметар T(n) е од ред n x ако има позитивни константи k и n o такви што за сите n³n o важи неравенката T(n) ≤ k n x.

Да претпоставиме дека n е количината на нумерички податоци добиени на влез на неколку различни алгоритми (A 1, A 2, A 3, A 4, A 5), кои вршат пресметки со иста брзина - 1000 операции во секунда, но имаат различни асимптотични проценки. Табелата 1.8 ги прикажува вредностите на n што овие алгоритми можат да ги обработат за 1 секунда, 1 минута и 1 час (вредностите се заокружуваат надолу до најблискиот цел број). Податоците во Табела 1.3 јасно покажуваат дека перформансите на алгоритмот (т.е. бројот на обработени податоци по единица време) значително зависи од природата на функцијата за асимптотичка евалуација.

Тестирањето на развиените алгоритми обично се врши со мали вредности на параметарот n. Ваквото тестирање ви овозможува да стекнете доверба во изведбата на алгоритмот, но воопшто не гарантира завршување на задачата за големи вредности на n. Можеби едноставно немаме доволно компјутерска меморија или време за да решиме вистински проблем. Асимптотичните проценки се важни во смисла дека овозможуваат да се процени доволноста на компјутерски ресурси за практични пресметки со познати граници на промена на параметарот n.

Ефикасност на алгоритаме својство на алгоритам што е поврзано со пресметковните ресурси што ги користи алгоритмот. Алгоритмот мора да се анализира за да се одредат ресурсите што ги бара алгоритмот. Ефикасноста на алгоритмот може да се смета како аналогна на производната продуктивност на повторувачки или континуирани процеси.

За да постигнеме максимална ефикасност, сакаме да ја намалиме употребата на ресурси. Меѓутоа, различни ресурси (како што се времето и меморијата) не можат директно да се споредат, така што кој од двата алгоритми се смета за поефикасен често зависи од тоа кој фактор е поважен, како што е барањето за голема брзина, минимална употреба на меморија или друга мерка за ефикасност.

Позадина

Важноста на ефикасноста со акцент на времето на извршување беше нагласена од Ада Лавлејс во 1843 година во врска со механичкиот аналитички мотор на Чарлс Бебиџ:

„Речиси во сите компјутери, постои голем избор на конфигурации можен за успешно завршување на процесот, а различните конвенции треба да влијаат на изборот за да се изврши пресметката. Суштинската работа е да се избере конфигурација која ќе го минимизира времето потребно за извршување на пресметката“.

Раните електронски компјутери беа многу ограничени и во брзина и во меморија. Во некои случаи, се сфати дека постои компромис за временска меморија, во која задачата мора или да користи голема количина на меморија за да постигне голема брзина, или да користи побавен алгоритам кој користи мала количина работна меморија. Во овој случај се користеше најбрзиот алгоритам за кој беше доволна достапната меморија.

Современите компјутери се многу побрзи од оние раните компјутери и имаат многу повеќе меморија (гигабајти наместо килобајти). Сепак, Доналд Кнут нагласува дека ефикасноста останува важен фактор:

„Во воспоставените инженерски дисциплини, подобрувањето од 12% е лесно достижно и никогаш не се сметало за премногу, а верувам дека истото треба да биде и во програмирањето“.

Преглед

Алгоритамот се смета за ефикасен ако неговата потрошувачка на ресурси (или трошоците за ресурси) е на или под некое прифатливо ниво. Грубо кажано, „прифатливо“ овде значи „алгоритмот ќе работи разумно време на достапен компјутер“. Бидејќи има значително зголемување на процесорската моќ и достапната меморија на компјутерите од 1950-тите, сегашното „прифатливо ниво“ не беше прифатливо ниту пред 10 години.

Производителите на компјутери периодично издаваат нови модели, често помоќни. Цена софтверможе да биде доста голем, така што во некои случаи е полесно и поевтино да се добијат подобри перформанси со купување на побрз компјутер кој е компатибилен со вашиот постоечки компјутер.

Постојат многу начини за мерење на ресурсите што ги користи алгоритам. Двете најкористени мерења се брзината и користената меморија. Други мерења може да вклучуваат брзина на пренос, привремено користење на дискот, долгорочно користење на дискот, потрошувачка на енергија, вкупни трошоци на сопственост, време на одговор на надворешни сигнали итн. Многу од овие мерења зависат од големината на влезните податоци на алгоритмот (односно, количините за кои е потребна обработка на податоците). Мерењата може да зависат и од начинот на кој се прикажуваат податоците (на пример, некои алгоритми за сортирање работат лошо на веќе подредените податоци или кога податоците се подредени во обратен редослед).

Во пракса, постојат и други фактори кои влијаат на ефективноста на алгоритмот, како што се потребната точност и/или доверливост. Како што е објаснето подолу, начинот на кој се имплементира алгоритам може исто така да има значаен ефект врз реалните перформанси, иако многу аспекти од имплементацијата се прашања за оптимизација.

Теоретска анализа

ВО теоретска анализаВо алгоритмите, вообичаена практика е да се процени сложеноста на алгоритам во неговото асимптотичко однесување, односно да се одрази сложеноста на алгоритмот како функција од големината на влезот. nСе користи ознака Big O. Оваа проценка е генерално доста точна за големи n, но може да доведе до неточни заклучоци при мали вредности n(Така, сортирањето со меурчиња, кое се смета за бавно, може да биде побрзо од брзото сортирање ако треба само да сортирате неколку елементи).

Тестови за верификација: Мерење на перформансите

За нови верзии на софтвер или за да се обезбеди споредба со ривалските системи, понекогаш се користат репери за да се споредат релативните перформанси на алгоритмите. Ако, на пример, се објави нов алгоритам за сортирање, тој може да се спореди со неговите претходници за да се осигура дека алгоритмот е барем исто толку ефикасен на познати податоци како и другите. Корисниците можат да ги користат тестовите за изведба за да ги споредат производите од различни производители за да проценат кој производ најдобро ќе одговара на нивните барања во однос на функционалноста и перформансите.

Некои бенчмарк тестови обезбедуваат компаративна анализа на различни јазици за составување и толкување, како што е колекцијата PC репер на Рој Лонгботом, и Играта со репери за компјутерски јазикги споредува перформансите на имплементации на типични задачи во некои програмски јазици.

Прашања за имплементација

Проблемите со имплементацијата може да влијаат и на реалните перформанси. Ова го вклучува изборот на програмскиот јазик и начинот на кој алгоритмот е всушност кодиран, изборот на преведувач за избраниот јазик или опциите на компајлерот што се користат, па дури и типот на операционен систем. Во некои случаи, јазикот имплементиран како преведувач може да биде значително побавен од јазикот имплементиран како компајлер.

Постојат и други фактори кои можат да влијаат на времето или користењето на меморијата кои се надвор од контрола на програмерот. Ова вклучува усогласување на податоците, детализирање, собирање ѓубре , паралелизам на ниво на инструкции и потпрограмско повикување .

Некои процесори имаат способност да вршат векторски операции, што овозможува една операција да обработува повеќе операнди. Може или не може да биде лесно да се користат такви карактеристики на ниво на програмирање или компилација. Алгоритмите дизајнирани за секвенцијално пресметување може да бараат целосен редизајн за да се приспособат на паралелно пресметување.

Друг проблем може да се појави со компатибилноста на процесорот, каде што инструкциите може да се имплементираат поинаку, така што инструкциите на некои модели може да бидат релативно побавни кај другите модели. Ова може да биде проблем за оптимизирачкиот компајлер.

Мерење на користење на ресурси

Мерењата обично се изразуваат како функција на големината на влезот n.

Двете најважни димензии се:

• Време: Колку време трае алгоритмот на процесорот.
• Меморија: Колку работна меморија (обично RAM) е потребна за алгоритмот. Постојат два аспекти за ова: количината на меморија за кодот и количината на меморија за податоците на кои работи кодот.

За компјутери на батерии (како што се лаптопи) или за многу долги/големи пресметки (како суперкомпјутери), различен вид на мерење е од интерес:

• Директна потрошувачка на енергија: Потребна енергија за да работи компјутер.
• Индиректна потрошувачка на енергија: Потребна енергија за ладење, осветлување итн.

Во некои случаи, потребни се други, поретки мерења:

• Големина на менувачот: Пропусниот опсег може да биде ограничувачки фактор. Компресијата може да се користи за да се намали количината на пренесени податоци. Прикажувањето слика или слика (како што е логото на Google) може да резултира со префрлување на десетици илјади бајти (48K во овој случај). Споредете го ова со пренос на шест бајти во зборот „Гугл“.
• Надворешна меморија: Потребна е меморија на диск или друг надворешен уред за складирање. Оваа меморија може да се користи за привремено складирање или за идна употреба.
• Време на одговор: Оваа поставка е особено важна за апликации во реално време каде што компјутерот мора брзо да реагира на надворешни настани.
• Вкупни трошоци на сопственост: Параметарот е важен кога е наменет да изврши еден алгоритам.

Време

Теорија

Овој тип на тест значително зависи и од изборот на програмскиот јазик, компајлерот и неговите опции, така што споредените алгоритми мора да се имплементираат под исти услови.

Меморија

Овој дел се занимава со употребата на главната меморија (често RAM) потребна за алгоритмот. Како и со анализата на времето погоре, обично се користи анализа на алгоритам просторна сложеност на алгоритмотза да се процени потребната меморија за траење како функција од влезната големина. Резултатот обично се изразува во однос на „О“ големо.

Постојат четири аспекти на користење на меморијата:

• Количината на меморија потребна за складирање на кодот на алгоритмот.
• Количината на меморија потребна за влезните податоци.
• Количината на меморија потребна за кој било излез (некои алгоритми, како што се сортирање, често го преуредуваат влезот и не бараат дополнителна меморија за излезот).
• Количината на меморија потребна за пресметковниот процес за време на пресметувањето (ова ги вклучува именуваните променливи и кој било простор на магацинот потребен за потпрограмски повици, што може да биде значајно кога се користи рекурзија).

Раните електронски компјутери и домашните компјутери имаа релативно мал капацитет на работна меморија. Така, во 1949 година EDSAC имаше максимална работна меморија од 1024 17-битни зборови, а во 1980 година Sinclair ZX80 беше издаден со 1024 бајти работна меморија.

Современите компјутери можат да имаат релативно големи количини на меморија (можеби гигабајти), така што компресирањето на меморијата што ја користи алгоритам во одредена количина меморија е помалку потребна од претходно. Сепак, постоењето на три различни категории на меморија е значајно:

• Кеш (често статична RAM меморија) - работи со брзини споредливи со процесорот
• Главна физичка меморија (често динамична RAM) - работи малку побавно од процесорот
• Виртуелна меморија (често на диск) - дава илузија на огромна меморија, но работи илјадници пати побавно од RAM меморијата.

Алгоритам чија потребна меморија се вклопува во кешот на компјутерот е многу побрз од алгоритам што се вклопува во главната меморија, што, пак, ќе биде многу побрз од алгоритам што користи виртуелен простор. Работата ја комплицира е фактот што некои системи имаат до три нивоа на кеш меморија. Различни системи имаат различни количини на овие типови меморија, така што меморискиот ефект врз алгоритам може значително да варира од еден систем до друг.

Во раните денови на електронското пресметување, ако алгоритам и неговите податоци не се вклопуваат во главната меморија, тој не може да се користи. Овие денови, користењето на виртуелната меморија обезбедува огромна меморија, но по цена на перформансите. Ако алгоритмот и неговите податоци се вклопат во кешот, може да се постигне многу голема брзина, па минимизирањето на потребната меморија помага да се минимизира времето. Алгоритам кој не се вклопува целосно во кешот, но обезбедува локалитет на врски, може да работи релативно брзо.

Примери на ефективни алгоритми

Критика за моменталната состојба на програмирањето

Програмите стануваат побавни побрзо отколку што компјутерите стануваат побрзи.

Во широко распространетите системи, преполовувањето на извршувањето на инструкциите може да го удвои траењето на батеријата, а големите податоци даваат можност за подобри алгоритми: Намалувањето на бројот на операции од N x N на N x log(N) има силен ефект за големи N... За N =30 милијарди, овие промени се слични на 50 години технолошки подобрувања.

Конкурс за најдобар алгоритам

Следниве натпревари покануваат учество во развојот на најдобрите алгоритми, чии критериуми за квалитет ги одредуваат судиите:

исто така види

• Аритметичкото кодирање е тип на ентропија кодирање со променлива должина на кодотза ефикасна компресија на податоците
• Асоцијативна низа е податочна структура која може да се направи поефикасна кога се користи дрвја PATRICIAили Џуди низи
• Тест на перформанси - метод за мерење на споредбено време на извршување во одредени случаи
• Најдобар, најлош и просечен случај- конвенции за проценка на времето на извршување за три сценарија
• Бинарното пребарување е едноставна и ефикасна техника за пребарување сортирана листа
• Табела за гранки

Испратете ја вашата добра работа во базата на знаење е едноставна. Користете ја формата подолу

Студентите, дипломираните студенти, младите научници кои ја користат базата на знаење во нивните студии и работа ќе ви бидат многу благодарни.

Сè уште нема HTML верзија на делото.
Можете да ја преземете архивата на делото со кликнување на врската подолу.

Слични документи

Опис на формалниот модел на алгоритам базиран на рекурзивни функции. Изработка на аналитички и програмски модел на алгоритам за Турингова машина за препознавање. Развој на аналитички модел на алгоритам со користење на нормални Марков алгоритми.

работа на курсот, додадена 07/07/2013


Концептот на алгоритам и анализа на теоретски проценки на временската сложеност на алгоритмите за множење на матрици. Компаративна анализа на проценка на временската сложеност на некои класи на алгоритми со користење на конвенционално програмирање и програмирање со помош на технологијата Open MP.

теза, додадена 08.12.2017


Општ концепталгоритам и мерки за неговата сложеност. Временска и капацитетна сложеност на алгоритмите. Основни методи и техники на анализа на сложеност. Оптимизација поврзана со изборот на метод за конструирање на алгоритам и со изборот на методи за прикажување податоци во програмата.

апстракт, додаден на 27.11.2012 година


Проблемот на подобрување на квалитетот на отпечатоците со цел да се зголеми ефикасноста на алгоритмите за биометриска автентикација. Преглед на алгоритми за обработка на слики со отпечатоци од прст. Анализа на алгоритам заснован на употреба на Габор трансформација.

теза, додадена 16.07.2014 година


Методи за организирање на пресметковниот процес во системи со повеќе процесори. Изработка на програма базирана на алгоритми за повеќепроцесорски системи за сериска обработка на задачи. Пресметка на клучни показатели за перформанси за секој алгоритам.

работа на курсот, додадена 21.06.2013


Проценка на пресметковната сложеност на програмата. Имплементација на алгоритам за кодирање на информации Хафман. Кодирање на тестот во бинарни и Хафманови дрвја. Бинарен код на знаци. Симболот и зачестеноста на неговото појавување во текстот. Пресметка на сложеноста на алгоритмот.

тест, додаден на 16.12.2012 година


Премин од вербална неформална формулација во математичка формулација на овој проблем. Оценете различни опции за да ги изберете најефикасните структури на податоци и алгоритми за обработка. Имплементација на алгоритми на еден од програмските јазици.

работа на курсот, додадена на 25.06.2013 година

Главни принципи за создавање ефективни алгоритми

Секој кој развива алгоритми мора да совлада некои основни техники и концепти. Секој кој некогаш бил соочен со тешка задача се соочил со прашањето: „Каде да почне? Еден можен начин е да ги разгледате вашите залихи на вообичаени алгоритамски методи за да видите дали еден од нив може да се користи за да се формулира решение за нов проблем. Па, ако не постои таква резерва, тогаш како може сè уште да развиете добар алгоритам? Каде да се започне? Сите сме имале фрустрирачко искуство да гледаме задача и да не знаеме што да правиме. Ајде да погледнеме три општи техники за решавање проблеми кои се корисни за развој на алгоритми.

Првиот методповрзани со намалување на тешка задача на низа поедноставни задачи. Се разбира, надежта е дека поедноставните проблеми се полесни за обработка од првобитниот проблем, а исто така и дека решението за првичниот проблем може да се изведе од решенијата за овие поедноставни проблеми. Оваа постапка се нарекува метод на приватни цели.Овој метод изгледа многу разумен. Но, како и повеќето општи методи за решавање проблеми или дизајнирање алгоритми, не е секогаш лесно да се префрли на одреден проблем. Правењето интелигентни избори за полесни проблеми е повеќе уметност или интуиција отколку наука. Не постои општ сет на правила за да се дефинира класата на проблеми што може да се решат со овој пристап. Размислувањето за кој било конкретен проблем започнува со поставување прашања. Специфичните цели може да се утврдат кога ќе се одговори на следниве прашања:

• 1. Дали е можно да се реши дел од проблемот? Дали е можно да се реши остатокот од проблемот со игнорирање на некои услови?
• 2. Дали е можно да се реши проблемот за посебни случаи? Дали е можно да се развие алгоритам кој произведува решение кое ги задоволува сите услови на проблемот, но чии влезни податоци се ограничени на некое подмножество од сите влезни податоци?
• 3. Дали има нешто поврзано со проблемот што не е добро разбрано? Ако се обидеме да навлеземе подлабоко во некои од карактеристиките на проблемот, дали ќе можеме да научиме нешто што ќе ни помогне да пристапиме кон решение?
• 4. Дали постои познато решение за сличен проблем? Дали е можно да се измени неговото решение за да се реши проблемот што се разгледува? Дали е можно овој проблем да е еквивалентен на познат нерешен проблем?

Втор методРазвојот на алгоритам е познат како метод на кревање.Алгоритмот за подигнување започнува со првично погодување или пресметување на почетно решение на проблемот. Тогаш најбрзото можно движење нагоре започнува од првичното решение кон подобри решенија. Кога алгоритмот ќе достигне точка од која повеќе не е можно да се движи нагоре, алгоритмот запира. За жал, не е секогаш можно да се гарантира дека конечното решение добиено со алгоритмот за подигнување е оптимално. Оваа ситуација често ја ограничува употребата на методот на кревање.

Општо земено, методите за кревање се класифицирани како „груби“. Се сеќаваат на некоја цел и се трудат да направат се што можат, каде што можат, за да се доближат до целта. Ова ги прави малку „кратковидни“. Кратковидоста на методот на кревање е добро илустрирана со следниот пример. Да претпоставиме дека треба да го најдеме максимумот на функцијата на =/(X),претставена со графикот (сл. 2.15). Ако почетната вредност на аргументот x = a,тогаш методот на искачување ќе даде аспирација до најблиската цел, т.е. до вредноста на функцијата во точката x = b,додека вистинскиот максимум на оваа функција е во = c. Во овој случај

Ориз. 2.15. Илустрација на методот на кревање Методот на подигање наоѓа локален максимум, но не и глобален. Ова е „грубоста“ на методот на кревање.

Трет методпознат како работејќи назад,тие. Работата на овој алгоритам започнува со цел или решение на проблем и потоа се движи кон првичната формулација на проблемот. Потоа, ако овие дејства се реверзибилни, се врши движење назад од изјавата за проблемот до решението.

Ајде да ги погледнеме сите три методи во проблем со џипот.Да претпоставиме дека треба да поминете пустина од 1000 километри со џип, користејќи минимум гориво. Волуменот на резервоарот за гориво на џипот е 500 литри, горивото се троши рамномерно, 1 литар на 1 км. Во исто време, на почетната точка има неограничен резервоар гориво. Бидејќи во пустината нема складишта за гориво, треба да инсталирате свои капацитети за складирање и да ги наполните со гориво од резервоарот на автомобилот. Значи, идејата за проблемот е јасна: треба да се вози од почетната точка со полн резервоар на одредено растојание, да го поставите првиот магацин таму, да оставите одредена количина гориво од резервоарот таму, но доволно за да врати се. На почетната точка повторно се врши целосно полнење гориво и се прави обид вториот магацин да се пресели понатаму во пустината. Но, каде треба да се постават овие магацини и колку гориво треба да се складира во секој од нив?

Ајде да му пристапиме на овој проблем користејќи го методот на работа наназад. На кое растојание од крајот можете да ја поминете пустината со точно иста количина на гориво? Дотенкови? Ајде да го разгледаме ова прашање за До= 1,2, 3,... додека не најдеме таков цел број П,Што Пполните резервоари ви овозможуваат да ја поминете целата пустина долга 1000 километри. За До= 1 одговор е 500 km = 500 l (точка ВО),како што е прикажано на сл. 2.16.

Ориз. 2.16.

Можете да го наполните автомобилот со гориво во точката ВОи да ги поминете преостанатите 500 километри пустина. Беше поставена посебна цел бидејќи првобитниот проблем не може веднаш да се реши.

Ајде да се преправаме дека До= 2, т.е. има два полни резервоари (1000 l). Оваа ситуација е илустрирана на сл. 2.16. Која е максималната вредност на jCj така што, почнувајќи со 1000 литри гориво од точката (500 - Xj), е можно да се носи доволно гориво до точката за да се заврши патувањето, како во До= 1. Еден начин да се одреди прифатлива вредност X (е како што следува. Дополнуваме гориво на пунктот (500 - Xj), одиме X (километри до точка ВОи истурете го целото гориво во складиштето, освен делот што е потребен за враќање во точката (500 - Xj). Во овој момент резервоарот станува празен. Сега го наполнуваме вториот резервоар, возиме до Xj километри ВО, подигнете во ВОгориво оставено таму, и од ВООдиме во Ц со полн резервоар. Вкупното поминато растојание се состои од три сегменти заедно X (километри и еден сегмент СонцетоДолга 500 км. Според тоа, од равенката 3x t + 500 = 1000 го наоѓаме неговото решение Xj = 500/3. Така, два резервоари (1000 l) ви дозволуваат да патувате Z> 2 = 500 +x ( = 500(1 + 1/3) км.

Ајде да размислиме k = 3. Од кој момент можете да заминете со 1500 литри гориво за да може џипот да испорача 1000 литри до точката (500 - x))? Да ја најдеме најголемата вредност на x 2 таква што, оставајќи 1500 литри гориво од точката (500 - Xj - x 2), можеме да испорачаме 1000 литри до точката (500 - Xj). Ја напуштаме точката (500 - Xj - x 2), возиме до (500 - x), го пренесуваме целото гориво освен x 2 литри и се враќаме во точката (500 - Xj - x 2) со празен резервоар. Повторувајќи ја оваа постапка, ќе потрошиме 4x 2 литри на патување и ќе оставиме (1000 - 4x 2) литри на точката (500 - x L). Сега на точката (500 - Xj - x 2) остануваат точно 500 литри. Ги пополнуваме последните 500 литри и одиме до точката (500 - Xj), откако потрошивме x 2 литри на ова.

Наоѓајќи се во точката (500 - Xj), трошиме 5x 2 литри гориво на патување. Овде се оставени вкупно (1500 - 5x 2) литри. Оваа количина треба да биде еднаква на 1000 l, т.е. x 2 = 500/5. Од ова заклучуваме дека 1500 литри ви дозволуваат да возите

Продолжувајќи го процесот на индуктивно работење наназад, го добиваме тоа Презервоарите за гориво ни дозволуваат да поминеме Днкилометри, каде Дн = 500(1 +1/3 + 1/5 + ... + 1/(2П - 1)).

Треба да ја најдеме најмалата вредност П,на кој Дн> 1000. Едноставните пресметки покажуваат дека за n = 7 имаме Д?= 997,5 км, т.е. седум цистерни или 3500 литри гориво ќе ви овозможат да патувате

• 977,5 км. Полн осми резервоар - ова би било повеќе од потребно за транспорт на 3500 литри од точката Адо точка лоцирана во
• 22,5 km (1000 - 977,5) од A На читателот му се дава можност самостојно да потврди дека 337,5 литри се доволни за испорака на 3500 литри гориво до ознаката од 22,5 km. Така, за да ја поминете пустината од I до C со автомобил, потребни ви се 3837,5 литри гориво.

Сега алгоритмот за транспорт на гориво може да се претстави на следниов начин. Почнуваме од А,со 3837,5 литри. Овде има доволно гориво за постепено транспортирање на 3500 литри до ознаката

22,5 км, каде џипот на крајот ќе заврши со празен резервоар и доволно гориво за 7 полни полнење. Ова гориво е доволно за транспорт на 3000 литри до точка 22,5 + 500/13 km од А,каде што резервоарот на автомобилот повторно ќе биде празен. Следниот транспорт ќе го доведе џипот до точка лоцирана на 22,5 + 500/13 + 500/11 km од А,со празен резервоар од автомобилот и 2500 л во магацин.

Продолжувајќи на овој начин, ние одиме напред благодарение на анализата направена со работа наназад. Наскоро џипот ќе биде на марката 500(1 - 1/3) km со 1000 литри гориво. Потоа до пунктот ќе транспортираме 500 литри гориво ВО,Ајде да ги истуриме во резервоарот на автомобилот и да возиме до точката без застанување СО(Сл. 2.17).

Ориз. 2.17.

За оние кои се запознаени со бесконечните серии, забележете го тоа ДЕте го П-ти парцијален збир на непарна хармонична серија. Бидејќи оваа серија се разминува, алгоритмот овозможува да се помине секоја пустина. Обидете се да го измените овој алгоритам за да оставите доволно гориво на различни точки во пустината за да се вратите во точката А.

Се поставува прашањето дали е можно да се помине 1000 km со помалку од 3837,5 литри гориво. Излегува дека не можеш. Доказот за оваа изјава е доста сложен. Сепак, може да се даде следниов, прилично веродостоен, аргумент. Очигледно глумиме најдобриот начинЗа До= 1. Кога До= 2 план се користи за До= 1 и потоа се активира вториот резервоар гориво за да биде што подалеку од точката ВО.Почетната премиса за Дотенкови е дека ние знаеме како да дејствуваме најдобро во случај на (До - 1) тенкови и со помош вратете се што е можно подалеку СЗОрезервоарот

Значи, во разгледуваниот проблем, методот на работа наназад е дека проблемот е решен како од крајот; методот на парцијални цели е дека тие не го решаваат целиот проблем одеднаш, туку, како што беше, во делови; и, конечно, методот на искачување се манифестира во тоа што решението не се наоѓа веднаш, туку последователно, како да му се приближува.

КОНТРОЛНИ ПРАШАЊА

• 1. Дефинирајте објект, класа, систем, модел.
• 2. Наведете ги главните типови на модели.
• 3. Што е симулационо моделирање?
• 4. Какви класификации на модели постојат?
• 5. Наведете ги главните фази на моделирање.
• 6. Што е алгоритам?
• 7. Наведете ги својствата на алгоритмот.
• 8. Кои фази се изведуваат во комплетната конструкција на алгоритмот?
• 9. Што е дијаграм на тек на алгоритам?
• 10. Дефинирајте функционален блок.
• 11. Кој алгоритам се нарекува структурен?
• 12. Наведете ги главните принципи во основата на создавањето на ефективни алгоритми.