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

Картографиране на алгоритмичен модел

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

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

При проблеми, зададени на втория клас, в резултат на изпълнението на алгоритъма, отговорът на въпроса е: „Вярно ли е твърдението, че x М "? или, което е едно и също нещо, проверява валидността на предиката x М и един от двата възможни резултата са дадени: ИСТИНСКИ или ЛЪЖЕН. Този клас може да се счита за разновидност на първия, тъй като предикатът е функция, която приема две стойности в зависимост от условието. Независимо от това разделянето на тези класове проблеми е полезно, тъй като води до две важни концепции на теорията на алгоритмите - изчислима функция и разрешим набор.

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

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

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





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

Пример 4.11

Сложност на алгоритъма

Еднородно азбучно двоично кодиране. Байт код

Пример 7.7

Пример 7.9

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

2019 @ ailback.ru