Головна

Введення в теорію алгоритмів.

  1.  A.3.1. Вступ
  2.  A.5.1. Вступ
  3.  I. Вступ
  4.  I. ВСТУП
  5.  I. Вступ
  6.  I. Вступ
  7.  I. ВСТУП

Історія виникнення теорії алгоритмів. Визначення поняття "Алгоритм", основні вимоги, що пред'являються до алгоритму. Класифікації алгоритмічних моделей. Машина Поста.

Першим що дійшли до нас алгоритмом в його інтуїтивному розумінні як кінцевої послідовності елементарних дій, що вирішують поставлену задачу, вважається запропонований Евклідом в III столітті до нашої ери алгоритм знаходження найбільшого спільного дільника двох чисел.

Згаданий вище алгоритм Евкліда, алгоритм Гаусса рішення системи лінійних рівнянь над полем і безліч інших прикладів алгебри і теорії чисел, всі ці алгоритмічні проблеми вирішені шляхом вказівки дозволяють процедур. Для отримання результатів такого типу, досить інтуїтивного поняття алгоритму.

Кілька прикладів інтуїтивного поняття алгоритму: (с4 -с5)

алгоритм - Точний набір інструкцій, що описують порядок дій виконавця для досягнення результату рішення задачі за кінцевий час.

У старій трактуванні замість слова «порядок» використовувалося слово «послідовність», але в міру розвитку паралельності в роботі комп'ютерів слово «послідовність» стали замінювати більш загальним словом «порядок». Це пов'язано з тим, що робота якихось інструкцій алгоритму може бути залежна від інших інструкцій або результатів їх роботи. Таким чином, деякі інструкції повинні виконуватися строго після завершення роботи інструкцій, від яких вони залежать. Незалежні інструкції або інструкції, що стали незалежними через завершення роботи інструкцій, від яких вони залежать, можуть виконуватися в довільному порядку, паралельно або одночасно, якщо це дозволяють використовувані процесор і операційна система.

алгоритм - Це зрозумілі і точні приписи виконавцю здійснити кінцеве число кроків, спрямованих на вирішення поставленого завдання.

«Алгоритм - це кінцевий набір правил, який визначає послідовність операцій для вирішення конкретного безлічі завдань і має п'ятьма важливими рисами: кінцівку, визначеність, введення, висновок, ефективність». (Д. Кнут)

«Алгоритм - це будь-яка система обчислень, які виконуються за строго визначеними правилами, яка після будь-якого числа кроків свідомо призводить до вирішення поставленого завдання». (А. Колмогоров)

«Алгоритм - це точне розпорядження, що визначає обчислювальний процес, що йде від варійованих вихідних даних до шуканого результату».

(А. Марков)

Різні визначення алгоритму, в явній або неявній формі, постулюють наступний ряд загальних вимог (формальні властивості алгоритмів) (С6)

дискретність - Алгоритм повинен представляти процес вирішення завдання як порядок виконання деякого кінцевого безлічі елементарних кроків. При цьому для виконання кожного кроку алгоритму потрібно кінцевий відрізок часу, тобто перетворення вихідних даних в результат здійснюється в часі дискретно. Типовий приклад безлічі елементарних кроків - система команд ЕОМ.

Детермінованість (визначеність). У кожен момент часу наступний крок роботи однозначно визначається станом системи, т. Е. Після кожного кроку вказується, який крок слід виконувати далі або вказується, коли слід роботу алгоритму вважати закінченою. Ця вимога відповідає логічній природі ЕОМ.

зрозумілість - Алгоритм повинен включати тільки ті команди, які доступні виконавцю і входять в його систему команд. Відповідає можливостям ЕОМ.

Завершаемості (кінцівку) - При коректно заданих вихідних даних алгоритм повинен завершувати роботу і видавати результат за кінцеве число кроків.

Масовість (універсальність). Алгоритм повинен бути застосовний до різних наборів вихідних даних.

Отже, довгий час поняття алгоритму вважалося само собою зрозумілим.

Математика звикла до того, що завдання, які вона ставила поступово вирішувалися, але як раз, в той час, виникла ідея що ряд проблем не має рішення (не просто вони поки не відомі, а не має взагалі) т. Е. Існують нерозв'язні завдання . Немає алгоритму їх вирішення.

А як довести, що алгоритму не існує? Для цього і потрібно точне поняття алгоритму.

Т. е. Поняття алгоритму виникло давно, але як предмет математичного дослідження це поняття було розглянуто тільки на початку XX. Алгоритм став точним математичним об'єктом, про який можна доводити теореми.

Отже, теорія алгоритмів виникла, як галузь, у відповідь на потребу докази нерозв'язності деяких проблем, і стала займатися дослідженням того, що таке алгоритм і з появою обчислювальних машин знайшла своє головне застосування в інформатиці.

Інтуїтивне визначення алгоритму не дозволяє розглядати властивості

алгоритмів як властивості формальних об'єктів. Тому математичне визначення алгоритму необхідно з наступних причин:

1) тільки при наявності формального визначення алгоритму можна зробити висновок про можливість розв'язання або нерозв'язності будь-яких проблем;

2) це дає можливість для порівняння алгоритмів, призначених для вирішення однакових завдань;

3) це дає можливість для порівняння різних проблем за складністю алгоритмів їх вирішення.

Що ж в інтуїтивному понятті алгоритму потребує уточнення? Незручності словесних визначень пов'язані з проблемою однозначного трактування термінів. У таких визначеннях повинен бути, хоча б неявно, зазначений виконавець дій або розпоряджень, а також вказані його обчислювальні можливості, т. Е. Операції які є для нього елементарними.

Шляхи уточнення цього поняття (алгоритму) різні і призводять до різних алгоритмическим моделям, які власне і є предметами розгляду теорії алгоритмів.

У теорії алгоритмів уточнення поняття алгоритму прийнято проводити наступним чином: спочатку формулюються ті елементи цього поняття, які потребують уточнення та ці вимоги є загальними для всіх різних алгоритмічних моделей, хоча акценти в цих моделях різні, а конкретні уточнення призводять до різних алгоритмическим моделям.

Схема визначення поняття «алгоритм»: (С7)

Поняття даних.Алгоритм працює з даними. Вимоги до даних: повинні формуватися з будь-якого кінцевого безлічі символів - алфавіту. Далі із символів алфавіту формуються послідовності символів - слова. Найчастіше алгоритму дозволяється працювати не з будь-якими словами в алфавіті, а побудованими за певними правилами, званим граматикою мови. Т. е. Те, що називається правильно побудованими виразами (ланцюжками).

Пам'ять. Не у всіх алгоритмічних моделях пам'ять присутній явно, але так чи інакше ясно, що дані повинні бути десь записані (як вхідні, так і ті що виникають в процесі обчислення). Повинні бути визначені осередки пам'яті і має бути встановлено відповідність між одиницями даних і одиницями пам'яті. Можна вважати, що в одній одиниці пам'яті записується один символ алфавіту.

Елементарний крок. Не виходить ввести загальне поняття елементарності. Набагато простіше зафіксувати кінцеве число елементарних кроків. При цьому елементарний крок повинен працювати з фіксованим і невеликим числом одиниць пам'яті.

Детермінованість.Те, що забезпечує однозначність результату. Суду входять: правило ініціації (початок алгоритму) з чого почати обробку, правила визначення наступного кроку і закінчення алгоритму (яким чином ми зрозуміємо, що це остаточний результат і де він знаходиться в пам'яті).

Результативність. Природна вимога це результативність. Алгоритм переймається тим, якщо він застосуємо, зупиняється і дає результат, який вважається рішенням завдання при всіх можливих даних, відповідних завдання. Це питання не завжди вирішується позитивно.

Перші фундаментальні роботи по теорії алгоритмів були опубліковані незалежно в 1936 році Аланом Тьюрингом, Алоізом Черчем і Емілем Постом. Запропоновані ними формально строгі визначення поняття алгоритму пов'язані з введенням спеціальних математичних конструкцій - формальних алгоритмічних систем або моделей обчислень.

 



 Стратегії алгоритмів. |  Основні типи алгоритмічних моделей. (С8)

 Основи аналізу алгоритмів. |  Машина Поста. |  Машина Поста складається з (с11) |  Практичні завдання. |  Машина Тьюринга. |  Граф переходів |  Визначення обчислюваності по Тьюрингу. (С25) |  Приклади (С27-С29) |  Послідовна композиція МТ. (С30-С31) |  Операція розгалуження (умовний оператор). (С32-С33) |

© um.co.ua - учбові матеріали та реферати