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

Сравнение на алгоритмичните модели

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

Всички алгоритмични задачи могат да бъдат разделени на две големи групи: първата е задачите, свързани с изчисляването на стойността на дадена функция; втората е задачите, свързани с разпознаването на принадлежността на даден обект към даден набор (което е еквивалентно на получаване на отговор на въпроса: има ли обект дадено свойство?). В първия случай Q- алгоритъмът започва да работи с първоначалните данни - думата P, съставена на базата на азбуката A, и в краен брой стъпки (преобразувания) трябва да спре и да даде резултат P k = f Q (P). Резултатът зависи (е функция) от изходната дума, както и от последователността на обработка, т.е. алгоритъм. В този случай изчислението се разбира в широк смисъл - като азбучна трансформация.

В задачите, свързани с втория клас, като резултат от изпълнението на алгоритъма, получаваме отговор на въпроса: „Дали твърдението, че x е вярно? М ? или, което е същото, предикатът x се проверява M и издаде един от двата възможни резултата: TRUE или FALSE. Този клас може да се счита за вариант на първия, тъй като предикатът е функция, която заема две стойности в зависимост от състоянието. Независимо от това, разделянето на тези класове проблеми е полезно, тъй като води до две важни концепции на теорията на алгоритмите - изчислима функция и решаващ набор.

Функцията се нарича изчислима, ако има алгоритъм, който изчислява неговата стойност.

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

Както беше споменато по-рано, тези определения не са формално строги, т.е. те не ни позволяват да предвидим дали дадена функция ще се окаже изчислима или не (или, което е същото: как можем да определим естеството на функцията, възможно ли е да се конструира алгоритъм за неговото изчисляване?). Поради тази причина тезата на Църквата, която твърди, че всяка частично рекурсивна функция е изчислима, е много важна за изграждането на теория на алгоритмите. С други думи, ако успяхме да изградим функцията, използвайки суперпозиция, рекурсия и минимизиране на най-простата аритметика, тогава има алгоритъм, който го изчислява. Това беше последвано от тезата на Тюринг, която твърди, че за всяка изчислима функция може да се изгради машина на Тюринг, която да я изчисли. Може да се докаже, че Post-алгоритмите са редуцирани до алгоритми, реализирани чрез частично рекурсивни функции. Обратното също е вярно. По-специално, проблемите, решени за пощенската машина в раздел 7.3.2, са пример за реализация на една от най-простите рекурсивни функции - пряко следната функция. По-късно беше доказана теорема за приспособимостта на един алгоритмичен модел за друг, в резултат на което бяха получени изказвания като: "всяка рекурсивна функция може да бъде изчислена с помощта на съответната машина на Тюринг" или "за всеки проблем, решен от машината на Тюринг, има решаващ нормален алгоритъм Марков" Така всички модели се оказват еквивалентни, което показва дълбок смисъл, защото резултатът от обработката на информация, разбира се, се определя от естеството на функцията (алгоритъм) и входните данни, но не зависи от вида на алгоритмичния модел.





Вижте също:

Пример А.4

Представяне на елементарни данни в RAM

Пример 7.9

Глава 10. Модели и системи

Тестови въпроси и задачи

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

2019 @ ailback.ru