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

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

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

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

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

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

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

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

5. Масов алгоритъм: първоначалната система от количества може да бъде избрана от някакъв набор.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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





Прочетете също:

Пълномащабни и информационни модели

Пример 3.1

Модели проверени и непроверени

Глава 8. Формализиране на представянето на алгоритми

Пример 7.7

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

2019 @ ailback.ru