Авиационно инженерство Административно право Административно право Беларус Алгебра Архитектура Безопасност на живота Въведение в професията „психолог” Въведение в икономиката на културата Висша математика Геология Геоморфология Хидрология и хидрометрия Хидросистеми и хидравлични машини Културология Медицина Психология икономика дескриптивна геометрия Основи на икономически т Oria професионална безопасност Пожарна тактика процеси и структури на мисълта, Професионална психология Психология Психология на управлението на съвременната фундаментални и приложни изследвания в апаратура социалната психология социални и философски проблеми Социология Статистика теоретичните основи на компютъра автоматично управление теория на вероятностите транспорт Закон Turoperator Наказателно право Наказателно-процесуалния управление модерна производствена Физика Физични феномени Философски хладилни инсталации и екология Икономика История на икономиката Основи на икономиката Икономика на предприятията Икономическа история Икономическа теория Икономически анализ Развитие на икономиката на ЕС Спешни ситуации ВКонтакте Однокласници Моят свят Facebook LiveJournal Instagram
border=0

Дефиниция на алгоритъма на Lax

Исторически, терминът "алгоритъм" произлиза от фамилното име на узбекския математик от 9-ти век Мохамед ибн Муса ал-Хорезми, който първо формулира правилата на четири основни аритметични операции. Първоначално тези правила се наричаха алгоритми, но след това терминът се развиваше предимно в математиката - всеки метод на изчисление, който е един и същ за определен клас входни данни, например намиране на производна функция, стана алгоритъм. Една от най-важните задачи на преподаването на математика е именно овладяването на общите изчислителни алгоритми. С други думи, ако ученик се научи да умножава колона от две числа, то се приема, че той не усвоява умножението на определени избрани числа, а универсален метод (алгоритъм), който по-късно може да се използва за намиране на произведението от всяка двойка крайни числа.

Има много подобни примери, а не само в математиката - терминът “алгоритъм” е станал обичайно. Във връзка с това възниква въпросът: възможно ли е да се конструира общо и точно определение на алгоритъм (понятието "всеки алгоритъм"), например, за да се използва за разграничаване дали съвкупността от индикации е алгоритъм или не? На ниво здрав разум можем да кажем, че алгоритъмът е точно дефинирана (еднозначна) последователност от прости (елементарни) действия, които осигуряват решение на всеки проблем от даден клас. Въпреки това, това твърдение не може да се приеме като строго определение на алгоритъма, тъй като използва други неопределени понятия - еднозначност, елементарност и т.н. Концепцията може да бъде изяснена чрез определяне на списък от общи свойства, които са характерни за алгоритмите. Те включват:

1. Дискретността на алгоритъма означава, че алгоритъмът е разделен на отделни стъпки (действия), а следващата стъпка може да се извърши само след като всички операции в предишната стъпка са завършени. В този случай, наборът от междинни данни е краен и се получава съгласно определени правила от данните от предходната стъпка.

2. Детерминизмът на алгоритъма се състои в това, че множеството от междинни стойности във всяка стъпка е еднозначно определено от системата от стойности, налични в предходната стъпка. Това свойство означава, че резултатът от изпълнението на алгоритъм не зависи от това кой (или какво) го изпълнява (т.е. от изпълнителя на алгоритъма), а се определя само от входните данни и стъпките (последователността от действия) на самия алгоритъм.

3. Елементарни стъпки: законът за получаване на последваща система от ценности от предишната трябва да бъде прост и локален. Коя стъпка (действие) може да се счита за елементарна, се определя от характеристиките на изпълнителя на алгоритъма.

4. Насоченост на алгоритъма: ако методът за получаване на последващи количества от каквито и да е начални, не води до резултат, трябва да се посочи какво трябва да се счита за резултат от алгоритъма.

5. Алгоритъм за маса : началната система от стойности може да бъде избрана от определен набор.

Последното свойство означава, че един алгоритъм, т.е. една и съща последователност от действия, в общия случай, може да се използва за решаване на определени класни (т.е. много) задачи. За практиката, и по-специално за решаването на проблем на компютър, това свойство е от съществено значение, тъй като, като правило, потребителската стойност на дадена програма е по-висока, колкото по-сходни задачи позволява да се реши. Въпреки това, за да изградим алгоритмична теория, това свойство не е съществено и задължително.

Концепцията на алгоритъма, до известна степен определена от изброяването на свойства 1-5, също не може да се счита за строга, тъй като формулировката на свойствата използва термините „стойност“, „метод“, „прост“, „локален“ и други, чието точно значение не е установено. Впоследствие, тази дефиниция ще се нарича nonstrict / и (понякога се нарича интуитивно) понятие за алгоритъм.

Възниква въпросът: наистина ли е важно и необходимо да имаме точна дефиниция на алгоритъм, ако е възможно да се създават и прилагат алгоритми без него (и дори без използване на самия термин)? Особено след като интуитивната концепция на алгоритъма, макар и не строга, беше толкова ясна, че е била практически до 20-ти век. не е имало ситуации, при които математиците биха се разминали дали даден процес е алгоритъм. Ситуацията се промени значително в началото на 20-ти век, когато бяха формулирани такива проблеми, чието алгоритмично решение не беше очевидно. Всъщност, за да се докаже съществуването на алгоритъм, е необходимо просто да се реши този проблем, като се използва набор от добре познати техники, или, при тяхно отсъствие, да се предложат нови техники - в такива ситуации интуитивната концепция на алгоритъма е достатъчна, за да се гарантира, че описаният процес е алгоритъм. Много по-трудно е да се докаже, че е невъзможно да се изгради алгоритъм за решаване на определена задача (или клас от задачи) - без точна дефиниция на алгоритъма, този проблем губи смисъла си.

Друга причина, която изискваше изграждането на точна дефиниция на алгоритъма, беше неяснотата на понятието „елементарна стъпка” при извършване на алгоритмични действия. Макар че математиката изучаваше числови обекти, действията с тях бяха сведени до определена последователност от изчислителни операции, а аритметичните операции бяха считани за елементарни, както и няколко логически, свързани с проверка на връзките между величините (равенство, неравенство, повече, по-малко и т.н.). Въпреки това, по-късно, математиката се обърна към изучаването на свойствата и действията със сложни обекти - вектори, матрици, множества, функции - и понятието за елементарен характер на стъпката на алгоритъма вече не беше очевидно. Например, възможно ли е да се обмисли приемането на интеграла или транспонирането на матрицата като елементарна стъпка?

В случаите, когато задачата позволява да се конструират няколко алгоритми за решаване, от теоретична и практическа гледна точка, от съществено значение е да се сравнят и да се избере най-ефективният алгоритъм, който също е невъзможен без стриктното му дефиниране.

Така стана необходимо да се дефинира точно понятието "всеки алгоритъм", т.е. като обща дефиниция за всички възможни типове алгоритми. През 20-те. XX век. Изграждането на дефиницията на алгоритъма се превърна в един от централните математически проблеми. Тази дефиниция, от една страна, трябва да съответства на същността на интуитивната концепция на алгоритъма, а от друга страна, да бъде формално строга. Опитите да се формулира такава концепция доведе до появата през 30-те години на миналия век. XX век на теорията на алгоритмите като независима наука, която, заедно с математическата логика, изучава основните средства на математиката - методи на доказване, методи за конструиране на аксиоматични теории, свойства на математическите процедури и др. започна бързото развитие на изчислителната техника и на науките, свързани с нейното функциониране и използване, се оказа, че теорията на алгоритмите също трябва да бъде в основата на тези науки , тъй като компютърът може само да изпълнява процедури, които могат да бъдат представени като алгоритми. Всяка програма не е нищо повече от запис на алгоритъм на език, който изпълнителят може да „разбере“ - компютър. По този начин от практическа гледна точка е важно също да се изясни понятието за алгоритъм.

Уточняването на концепцията на алгоритъма се извършва в рамките на алгоритмичните модели. Моделът определя набор от инструменти, използването на които е допустимо при решаване на проблем, т.е. списък на елементарни стъпки, начини за определяне на следващата стъпка и т.н. Алгоритмичните модели могат да бъдат теоретични и практични. От теоретична гледна точка най-голям интерес представляват модели, които, от една страна, биха били универсални, т.е. ще позволи да се опише всеки алгоритъм, а от друга страна, възможно най- прост, т.е. ще използва минималните средства за решаване на проблема. Изискването за простота е важно, за да се подчертаят действително необходимите елементи и свойства на алгоритъма и да се докажат общите твърдения за тези свойства. В практическите и приложните модели, удобството на програмирането и изчислителната ефективност е по-значимо, следователно техните средства - набор от елементарни стъпки и т.н. - са много по-богати и по-сложни, което прави теоретичния анализ труден.

В теоретичните подходи за конструиране на строго дефиниране на понятието за алгоритъм исторически се открояват три основни направления.

Първата посока е свързана с разглеждането на алгоритми, които позволяват да се изчисли стойността на числените функции в зависимост от целочислените стойности на аргументите - такива функции се наричат изчислими. Концепцията за изчислима функция не е строга, както е понятието за алгоритъм. Въпреки това, благодарение на произведенията на А. Църква, К. Гьодел, С. Клайне, е обоснована идентичността на класа на навсякъде определените изчислими функции с класа на частично рекурсивните функции, който е строго дефиниран. Това ни позволи да ограничим проблема за алгоритмичната разрешимост до доказателство за възможността (или невъзможността) за конструиране на рекурсивна функция, която решава проблема. Именно по този начин А. Черч успява да докаже неразрешимостта на един от проблемите на математическата логика, смятането на истината за предикатите.

Втората посока е свързана с машинната математика. Основната идея на тази посока е, че алгоритмичните процеси са процеси, които могат да се изпълняват от подходящо подредена “машина”. В съответствие с тази идея те описват доста тесни класове машини в точни математически термини, но е доказано, че с помощта на тези машини е възможно да се извършат или имитират всички алгоритмични процеси, които всъщност някога са били описани от математиците. Този подход е разработен в творбите на Е. Пост и А. Търинг едновременно с горепосочения подход. Доказателството за алгоритмичната разрешимост на проблема се свежда до доказателство за съществуването на машина, която я решава.

Третата посока е свързана с концепцията за нормални алгоритми, въведена и разработена от руския математик А. А. Марков в началото на 50-те години. XX век.

В следващите раздели всички три области ще бъдат обсъдени по-подробно. Но преди да се обърна към това, бих искал да отбележа, че стриктно формализираният подход при дефиниране на понятието „алгоритъм“ се използва само директно в математическата теория на алгоритмите, където се изследват общите свойства на алгоритмите, провежда се доказателство за алгоритмична разрешимост и т.н. включително в компютърните науки, стриктната формализация може да доведе до значително усложняване на задачата; В същото време можете да посочите няколко ситуации, в които е допустимо отклонение от него.

1. Използването на изпълнители, способни да изпълняват сложни команди. Определението на термина "изпълнител на алгоритъм" е очевидно:

Изпълнителят на алгоритъма е субект или устройство, способен правилно да тълкува описанието на алгоритъма и да изпълнява списъка от действия, съдържащи се в него.

Инструкции за извършване на действия за всеки изпълнител са формулирани на определен език, включително набор от официални думи, обозначаващи действия (команди), както и синтактични правила за комбинирането им. Наборът от валидни команди формира система от екипи на изпълнителната власт (SKI). Различните SKI на различни изпълнители могат да променят описанието на действията. Както ще бъде показано по-долу, елементарно (най-просто) действие при обработката на дискретна информация е заместването на един символ с друг. Възможно е обаче да се изгради абстрактен или реален уред, който да може да изпълни цяла верига от такива елементарни действия според определеното в него правило - някакъв вид комплексно (интегрално) действие. При конструирането на алгоритъм за такъв художник, разработчикът трябва само да уточни последователността на интегралните команди и тяхното преобразуване в верига от наистина елементарни стъпки ще бъде извършено от самия изпълнител. Такава "многоетапна" алгоритмизация се използва широко в управлението на компютрите.

Наистина елементарно трябва да се имат предвид действията на процесора (въпреки че техният общ брой в съвременните процесори достига няколкостотин или дори хиляди) - те се наричат машинни команди и техните обозначения са машинни кодове. Първото (най-ниско) ниво, при което се отклонява от машинните кодове, е асемблерният код - вътрешен (т.е. зависим от устройството) език. Съчетаването на елементарни действия в сложни команди на това ниво все още не се случва и общият брой на асемблерните команди съвпада с броя на командните процесори, но символичната форма на представяне на машинни кодове и регистрите на процесорите е мнемонична, което е по-удобно за потребителя, отколкото за двоичния машинен код.

Превод на мнемонични в машинни команди се извършва от асемблерна програма ; с нея се занимава програмистът като изпълнител. Команди, които обединяват редица елементарни действия се появяват в езиците за програмиране на високо ниво, например, в текста на програмата е достатъчно да напишете “Write”, а преводачът на езика ще го преведе в поредица от елементарни стъпки: прекъсвания, прехвърляния и др. Оказва се, че преводачът на езика за програмиране. Още по-голяма степен на интегриране на елементарни команди може да бъде осигурена от приложната програма, която е изпълнител по отношение на крайния потребител. SKI на такъв артист включва всички контролни команди, представени под формата на менюта, екранни бутони, прозорци за настройка и други елементи на интерфейса. Използването на една команда може да предизвика верига от сложни действия, например подравняването на много редове от текст.

Така, когато се пишат алгоритми, ситуации са възможни, когато езикът на представяне на алгоритъма е формален, но използва сложни команди, които самият изпълнител превежда до нивото на наистина елементарни действия.

2. Допустимостта на не-строга формализация на представянето на алгоритми, ако изпълнителят е лице. Човек има собствено мислене и знание, въз основа на което може да компенсира неточностите на алгоритъма, да извършва действия и да постига резултати. Такива алгоритми трябва да се считат за още по-малко строги от тези, разглеждани в началото на раздела, тъй като, като правило, те нямат всички изброени свойства. Примерите включват рецепти за готвене, инструкции за използване на домакински уреди, алгоритми за решаване на училищни проблеми.

3. Разширяване на приложимостта на концепцията на алгоритъма към поредица от дискретни действия. По дефиниция, алгоритъмът задължително трябва да бъде свързан с обработката на дискретна информация. Същият термин се използва и за определяне на действия за управление на изпълнител, който не преобразува директно информация. Например, в училищния курс по информатика, широко се използват педагогически изпълнители „Рисувачка”, „Паркеткик”, „Костенурка”, чиято SKI включва придвижване по екрана и извършване на определени операции („нарисувайте линия”, „лежи керемида” и др.). Същото се отнася и за инструкциите за управление на всички устройства и устройства.





Вижте също:

Пример А.5

Дефиниция на системата

Пример 9.3

Пример 7.2

Пример 9.1

Връщане към съдържанието: Теоретични основи на компютърните науки

2019 @ ailback.ru