Концепцията на алгоритъма в интуитивен смисъл, основните свойства на алгоритъма

Интуитивният определянето на алгоритъма

Интуитивен, тоест, формирана въз основа на опит. През 19-ти век от новата ера - Al Harezmi пътува от страна в страна, в резултат на т.нар дойде терминът "algoritmi", т.е. "алгоритъм". Ал Harezmi разработени правилата на аритметиката. интуитивно алгоритъм се определя като (училище) ясно и точно инструкция изпълнител да направи определена последователност от действия за постигане на определена цел. Предписание по друг начин - на поръчката. Изпълнител - това е нещо, което може да се приеме нареждане, и да го прилагат, както е надарен със способността да изпълняват определен набор от действия, под влиянието на система за поръчки (команди).

Алгоритъм (Референтен библиотека програмист) - обикновено се формира на определен език и определяне на процеса на превръщане на необходимите валидни данни и отговаря на следните качества:

1. Маса.
2. Потенциалното осъществимост.
3. Разбираемост.
4. Увереност.

Алгоритъм - е точно формулирано по определен език крайно описание на общ метод се основава на използването на изпълними елементарни Tats контрол върху броя на търкаляне.

Начини за представяне на интуитивни алгоритми

• чрез графичен или словесно описание (графично - блокова диаграма език)
• в табличен вид
• формули последователност
• на езика за програмиране или език за програмиране

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

1. Форма на представяне на научни резултати
2. Ръководство за действие, когато решението вече е учил програми
3. Инструмент, който ви позволява да запаметите умствена работа
4. Стъпка решения за автоматизация на проблеми
5. Инструмент или устройство, изследвания на нови проблеми.
6. Средства за описване математика
7. Едно от средствата за описване сложни процеси

алгоритъм принципи на дизайна за приложения

Най-важният компонент на програмата е развитието на алгоритми. В първата фаза преобладава оперативен подход (а първите компютри), т.е. алгоритъм е ориентирана към специфични операции (задача, сравнение условен (безусловно) скок, аритметични). Тя се основава на специфичните особености на компютъра. Структурния подход (външен вид на третото поколение (70)) - логика програма структура може да се изрази чрез комбинация от три основни структури (Бом-Yakopini теорема):

Структурната подход е модулни програми и алгоритми и надолу издатина (проблем е разделен на няколко подзадачи). (Пример - Pascal)

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

Декларативен подход (въведена през 40-те години) е насочена към обхвата на проблемите на изкуствения интелект. Програмист описва свойствата на първоначалните данни, които трябва да имат свойства водят. И никакви алгоритъм задачи, които трябва да се определят автоматично от системата.

• логична версия (Prologue) - задача описва набор от правила и факти по някакъв формален език.
• функционален (Lispt) - описан функционални връзки между факти.

Разработване на идеята за паралелно програмиране и др.

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

Друга причина вид строителство точен алгоритъм е неясно понятие за една елементарна стъпка в интуитивен определение. Когато в началото на 20 математик век се обърна към изучаване на свойствата на сложни обекти (матрици, детерминанти), концепцията за началната стъпка на престанали да съществуват и имаше нужда от точна дефиниция на понятието "алгоритъм" - е обща за всички видове алгоритми. Тя трябва да бъде официално строг и отговаря интуитивно. Което води до самостоятелна наука - теорията на алгоритмите, която изучава методи за доказване на свойствата на математически процедури и т.н. Появата на компютърните технологии е показал, че на базата на компютърни науки трябва да се основава на концепцията за "алгоритъм". Първата основна работа по теория на алгоритмите са получени в средата на 30-те години. И през 1931 г., Гьодел доказва, че някои математически задачи не могат да бъдат решени чрез алгоритми от определен клас. И в средата на 30-те години, Тюринг полага основите на теорията на алгоритмите. В началото на 50-те години на най-съществения принос на Колмогоров и Марков. Теоретичните подходи за определяне на строг определението на термина "алгоритъм" изолиран 3 грешки:

1. Свързан е с понятието "изчислимите функции" и частични рекурсивни функции.
2. Благодарение на математиката на машината. Алгоритмичната процес - процес, който може да направи машината правилно подредени в математически термини, описан тесните класове машини: машина Тюринг, Великия пост; Доказано е, че е възможно да се приложат всички известни алгоритмични процеси чрез тези машини.
3. Това, свързани с концепцията за "нормално алгоритъм" и развива своята марка през 1954 година.

Въпреки различните подходи, се докаже, че всички те са равностойни.

Марков нормалните алгоритми

През 1954 г., А. А. Марков предложи схема, в която като в машина на Тюринг преведени думи, но въз основа на други принципи, а именно - че няма понятие за "лента" и означава незабавен достъп до различните части на преобразуваните думи. Тази схема се нарича Марков нормално алгоритъм.

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

Смяната изпълнява процес подмяна и края (спира)

Подреден набор от дума двойки (където А1 ... An - може да бъде както знак и дума) свързани със стрелки на два вида. Всяка двойка представлява пермутация формула за заместване на конвертираните subwords в една дума. Извършване на нормалното алгоритъм е разделена на барове. Всеки цикъл включва първо търсене заповед на приложимата формула заместване и използването на тази формула. Първият цикъл започва с проверка: дали дума A1 част на входната дума, че е фактор.

Например, в "компютърни науки" думата е появата на думата "институт". Ако е включен, той subword заменен от дясната страна - В1, и т.н. По този начин, когато има промяна на входния думата чрез заместване с subword на друга. Ако няма запис, той проверява втората двойка и т.н. Ако се опитате да се прилага формулата за смяна има множество случаи на Гай, тя се заменя с най-лявата влизането, и ако не може да се приложи някаква формула, тогава има опит да се прилага следната формула. Процесът на извършване на нормална алгоритъм завършва в следните случаи:

• или всички формули не са валидни, тоест, с една дума преработени, че няма повторения на всеки ляв.
• или просто се използва крайната формула, свързан край стрелка.

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

Ако по време на изпълнение на нормалния брой пъти на алгоритъма се прилагат ∞ unkillable формула, алгоритъмът не се прилага за преработени вход дума. Отляво и отдясно части могат да съдържат празни думи. За да запишете празната дума не изисква специално предназначение, както и преобразуване на думата може лесно да бъде преместена от друг и да се премести.

Преминаване от други начини за описване на алгоритмите за нормалното алгоритъм се нарича представителство в нормална форма или нормализиране.

Пример: Кодиране 0 и 1 азбука [а, Ь, с].

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

Две прости достатъчна индикация за приложимост на нормалния алгоритъм:

1. във всички формули, като се замести от лявата страна, не е празна, а от дясната страна не включват буквите, срещащи се в десния хълбок.
2. всяко правило смяна дясната страна е по-кратък от ляво.

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

Пример: конструиране на алгоритъм за приписване всяка дума азбука [а, Ь, с] на полето писмо. За разлика от Тюринг машина, нормалната алгоритъм има няма директен достъп до десния край на входната дума. * Ние се въведе за отбелязване туристическите атракции в думата. Ние ще приложи алгоритъма в съответствие със следната схема:

1. * Отдайте се на ляво.
2. * Ако не е последната дума, а след това да го промените на места с следното писмо.
3. * На мястото на буквата А, и да се спре този процес.

Сравнение на различни схеми за алгоритмична

Ако е възможно да се намали проблема с някои нерешени проблеми, ние показваме, че този проблем е нерешим. Помислете за самостоятелно прилагане на схема Марков. Алгоритъмът може да се свърши, но може - не. Затова Марков алгоритъм може да бъде разделена на две: за самостоятелно прилагане, за които съществува алгоритъм, за които не съществува.

Алгоритъмът, който със сигурност може да реши всеки проблем, т.е. алгоритъм за разпознаване не съществува, това е, това означава, че проблемът за себе си е неразтворим. Ако вземем algoritma →, а след това не samopimenim, a- samoprimenim. За конкретни случаи, можете да определите точно, но няма универсален алгоритъм, което означава, че няма алгоритъм, който ще разреши всички проблеми на себе си класа.