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

Общи подходи

Точно описание на класа на частично рекурсивните функции заедно с тезата на Църквата дава едно от възможните решения на проблема за усъвършенстване на понятието за алгоритъм. Това решение обаче не е съвсем ясно, тъй като концепцията за изчислима функция е вторична на концепцията за алгоритъм. Въпросът е, възможно ли е да се изясни директно самото понятие за алгоритъм и след това с негова помощ да се определи точно и класа на изчислимите функции? Такава посока на търсене доведе до изграждането на клас от алгоритмични модели, различни от рекурсивните. Основната му идея е, че алгоритмичните процеси са процеси, които могат да се извършват по определен начин от машина, като по този начин се симулира изпълнението на отделни операции от хората. Функционирането на такава машина е изпълнението на някой алгоритъм. Въз основа на свойствата на алгоритъма (раздел 7.1) е възможно да се формулират общи изисквания за такива машини:

1) естеството на тяхното функциониране трябва да бъде дискретно, т.е. се състои от отделни стъпки *, всяка от които се изпълнява само след завършване на предишното;

* In допълнителни инструкции за изпълнението на стъпката ще се наричат екип.

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

3) преди започване на работа машината е снабдена с първоначалните данни от зоната за дефиниране на алгоритъма;

4) за краен брой машинни стъпки трябва да се получи резултат (или информация за това, което се счита за резултат);

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

Колкото по-проста е структурата (т.е. устройството) на описаната машина и колкото по-елементарни са нейните стъпки, толкова по-голяма е причината да се смята, че работата й е изпълнението на алгоритъма. За да отговорим на въпроса кои стъпки от работата на машината трябва да се припишат на елементарните, нека се върнем към факта, че се интересуваме от трансформацията на информацията, представена от някаква крайна азбука. Изискването за крайността на азбуката е очевидно следствие от факта, че решението трябва да се получи в краен брой стъпки. Ако информацията не е представена в дискретна форма, например реално число, тогава нейната обработка в общия случай може да съдържа безкраен брой стъпки (например намирането на цифрите от числото n или извличането на квадратен корен от 2). Така алгоритъмът се оказва крайната последователност от действия, извършвани върху данните, представени с помощта на крайна азбука. Имайки това предвид, става ясно от дефиницията на алгоритъма, който В. М. Глушков дава [12, с.38]:

Един алгоритъм е всяка ограничена система от правила за преобразуване на информация (данни) върху всяка крайна азбука.

Нека изходните данни от домейна на алгоритъма да бъдат представени с азбука А и да образуват крайна последователност от знаци { a 1 ... a n } - тази последователност се нарича дума. В резултат на алгоритъма ще се формира нова дума { b 1 ... b m }, представена, общо взето, в друга азбука 6. На пръв поглед, за да се извърши такава трансформация, се разграничават следните елементарни операции (стъпки):

1) подмяната на един символ от първоначалната дума a i със знака b j от азбуката B ;

2) премахване на знака на оригиналната дума;

3) добавянето на оригиналната дума на знака от азбуката Б.

Ако обаче в азбуката е включен азбучен знак , добавянето на което към думата отляво или отдясно не променя думата (аналог на числовата нула), тогава е лесно да се види, че операцията (2) не е нищо повече от заместване на a i с празен знак и операция (3) е заместването на празния знак със знака b j . По този начин всички възможни азбучни преобразувания се свеждат до операция (1) - заместване на един символ с друг. Поради тази причина функционирането на една абстрактна машина се свежда до факта, че тя наблюдава героите (т.е. чете ги и ги разпознава), записани в паметта (като безкрайна лента), и в зависимост от състоянието и вида на символа , заменя го с друг символ; след това преминава в ново състояние, чете следващия знак и т.н. пред екипа да спре работата. Тъй като такива машини са чисто модел, теоретична конструкция, те се наричат абстрактни машини и се разглеждат като една от възможните универсални алгоритмични системи.

Концепцията на алгоритъма като абстрактна машина беше представена почти едновременно (1936 - 1937) от английския математик Алън Тюринг и американския му колега Емил Пост. Високата значимост на техните конструкции е и в това, че те в абстрактна форма очакват основните основни характеристики на устройствата за обработка на данни (компютри), които се появяват едва след 8-9 години.





Вижте също:

Понятието за логически запис

Алгоритмична машина

Пример 2.1

Компютърно кодиране и обработка на подписани цели числа

Затворени и отворени системи

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

2019 @ ailback.ru