Відмінності між версіями «*Теорія алгоритмів як дисципліна»

Поточна версія на 18:06, 22 жовтня 2012

Теорія алгоритмів - дисципліна що вивчає як саме поняття алгоритму, так і поняття алгоритмічної розв'язності задач. Перші, та найчисленніші застосування теорія алгоритмів мала в математичній логіці, адже вона виникла саме як розділ математичної логіки. Теорія алгоритмів є фундаментом програмування та інформатики.

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

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

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

Пошук формальних моделей алгоритму проводився в двох напрямах:

1. Опис точного математичного поняття алгоритмічної машини та обчислюваності на ній. Першою формальною моделлю алгоритмічної машини, була машина Тьюрінга, яка моделювала елементарні дії при реалізації алгоритму людиною (А. Тьюрінг, Е. Пост 1936). Зараз відомо багато різновидностей машин Тьюрінга. З пізніших формальних моделей алгоритмів відзначимо також нормальні алгоритми (А. Марков 1952) та регістрові машини (Д. Шепердсон, Г. Стерджіс 1963). Модифікація регістрових машин - машини з натуральночисельними регістрами.

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

Першими формальними моделями алгоритмічно обчислюваних функцій були лямбда-означувані функції (А.Чорч 1932) та загальнорекурсивні функції (К. Гьодель 1934). Вказані класи визначались як функції, графіки яких породжуються численнями λ-конверсій і численнями Ербана-Гьоделя. У 1936 р. С. Кліні поширив поняття загальнорекурсивної функції на випадок часткових функцій, увівши поняття частково рекурсивної функції, а також описав клас частково рекурсивних функцій у чисто функціональних термінах. У 1943 р. Е. Пост запропонував модель обчислюваних функцій на основі введених ним числень спеціального вигляду (канонічних систем).

У 1936 р. А. Чорч і С. Кліні довели, що класи загальнорекурсивних та λ-означуваних функцій збігаються. На основі цього факту та аналізу ідей, які привели до вказаних понять, А. Чорч висунув знамениту тезу, про збіг класу АОФ із класом загальнорекурсивних функцій. С. Кліні узагальнив цю тезу для випадку часткових функцій. Доведений А. Тьюрінгом у 1937 р. збіг класів ЧРФ і функцій обчислюваних на машині Тьюрінга, став ще одним підтвердженням тези Чорча. Пізніше такі збіги були встановлені для всіх відомих формальних моделей АОФ. Тому є всі підстави вважати, що кожна з названих вище формальних моделей адекватно уточнює інтуїтивне поняття АОФ.