Резюме Формализиране на понятието - алгоритъм - Група реферати, есета, доклади, курсови и дипломни работи
ФОРМАЛИЗИРАНЕ НА КОНЦЕПЦИЯТА НА "АЛГОРИТЪМА"
1.1. ФОРМУЛИРАНЕ НА ПРОБЛЕМА
Понятието алгоритъм, представено в предишния раздел, може да се нарече алгоритъм в интуитивен смисъл. Той има неясен, неформален характер, отнася се до някои не точно определени, но интуитивни неща. Например, когато дефинирахме и обсъждахме свойствата на алгоритъма, изхождахме от възможностите на определен изпълнител на алгоритъма. Присъствието му се предполагаше, но за него не се знаеше нищо категорично. Говорейки на езика на математиката, ние не сме дали нито аксиоматично, нито изчерпателно конструктивно определение на изпълнител.
Свойствата на алгоритмите, установени в предишния раздел, трябва да се нарекат емпирични. Те се разкриват въз основа на обобщаване на свойствата на алгоритмите от различно естество и имат приложен характер. Тези свойства са достатъчни за практическо програмиране, за създаване на широк спектър от програми за компютри, CNC машини, индустриални роботи и др. Като фундаментална научна концепция обаче алгоритъмът изисква по-подробно проучване. Невъзможно е без изясняване на понятието "алгоритъм", по-строго описание на него или, както се казва, без да се формализира.
Има няколко подхода за формализиране на понятието "алгоритъм":
• теория на крайни и безкрайни автомати;
• теория на изчислимите (рекурсивни) функции;
Всички тези подходи, възникнали исторически независимо един от друг, се оказаха впоследствие равностойни. Основната цел на формализирането на понятието алгоритъм е следната: да се подходи към решението на задачата за алгоритмична разрешимост на различни математически задачи, т.е. да отговори на въпроса дали може да се изгради алгоритъм, който да води до решението на проблема. Ще разгледаме формулирането на този проблем и някои резултати от теорията на алгоритмичната разрешимост на проблемите, но първо ще обсъдим формализирането на концепцията за алгоритъм в теорията на автоматите на примера на машини на Пост и Тюринг, както и нормални алгоритми на Марков, а след това - основите на теорията на рекурсивните функции. Идеите за λ-смятане на Църквата са реализирани в езика за програмиране LISP (Глава 3).
В същото време алгоритъм, формално дефиниран от някой от известните методи, не може да замени в практическото програмиране това, което наричахме алгоритми в предишния раздел. Основната причина е, че официалната дефиниция рязко стеснява обхвата на разглежданите проблеми, което прави много практически важни проблеми недостъпни за разглеждане.
1.2. ПОЩ МАШИНА
Абстрактни (т.е. съществуващи не всъщност, а само във въображението) машини Post и Turing, предназначени да докажат различни твърдения за свойствата на програмите за тях, бяха предложени независимо една от друга (и почти едновременно) през 1936 г. от американския математик Емил Пост и английският математик Алън Тюринг. Тези машини са универсални изпълнители, които са напълно детерминирани, позволявайки ви да „въведете“ първоначалните данни и след изпълнението на програмите да „прочетете“ резултата. Пощенската машина е по-малко популярна, въпреки че е много по-проста от машината на Тюринг. С негова помощ можете да научите първите умения за съставяне на компютърни програми.
Абстрактната машина на Post е безкрайна лента, разделена на еднакви клетки, всяка от които може да бъде празна или запълнена с знак „V“, а глава, която може да се движи по лентата с един квадрат надясно или наляво, може да бъде маркирана в лентата квадрат, ако тази марка не е била там преди, изтрийте марката, ако е била, или проверете за наличие на марка в клетката. Информацията за запълнените клетки на лентата характеризира състоянието на лентата, което може да се промени по време на работата на машината. Във всеки момент от времето главата („-“) е над една от клетките на лентата и, както се казва, я изследва. Информация за местоположението на главата заедно със състоянието на лентата характеризира състоянието на пощенската машина, фиг. 1.16.
Фигура 1.16. Публикувайте абстрактна машина
Командата Post machine има следната структура:
където n е поредният номер на командата, K е действието, извършено от главата, m е номерът на следващата команда, която трябва да бъде изпълнена.
Има общо шест команди на машината за поща, Фигура 1.17:
Фигура 1.1. Команди за пощенски машини.
Ситуациите, при които главата трябва да постави знак там, където вече съществува, или, обратно, да изтрие знак там, където не съществува, са извънредни (неприемливи).
Програма за пощенска машина е непразен списък от команди, така че 1) на n-то място е командата с номер n; 2) числото m на всеки отбор съвпада с номера на която и да е команда в списъка.
От гледна точка на свойствата на алгоритмите, изследвани с помощта на машината Post, причините за спирането на машината по време на изпълнението на програмата представляват най-голям интерес:
1) спиране по команда "стоп"; такова спиране се нарича ефективно и показва коректността на алгоритъма (програмата);
2) спиране при изпълнение на невалидна команда; в този случай спирането се нарича неефективно;
3) колата никога не спира; в този и в предишния случай имаме работа с неправилен алгоритъм (програма).
Ще разберем от първоначалното състояние на главата срещу празна клетка вляво от най-левия етикет на лентата. Помислете за изпълнението на някои типични елементи от програмите на Post machine.
1. Нека бъде дадено първоначалното състояние на главата и се изисква да напишете два етикета на празна лента: един в раздела под главата, вторият вдясно от него. Това може да стане с помощта на следната програма (резултатът от нейното изпълнение е показан вдясно от командата):
