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

Поточна версія на 23:12, 1 листопада 2012

1. Алгоритм

Теорія алгоритмів – окремий розділ математики який вивчає загальні властивості алгоритмів, виник в 30-х роках XX ст.

Задача теорії алгоритмів – створення формальних моделей алгоритмів, надання алгоритмам точного математичного визначення і дослідження їх властивостей.

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

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

Областю застосовності алгоритму називається сукупність тих об‘єктів, до яких його можна застосувати, тобто в застосуванні до яких він дає результат. Про алгоритм A кажуть, що він:

1) «обчислює функцію f», коли його область застосування збігається з областю визначення f, і A перетворює будь-який х зі своєї області застосування в f(х);

2) «розв‘язує множину M відносно множини X», коли він застосовується до будь-якого х з X, і перетворює будь-який х з X∩M (з перетину множин) на слово «так», а будь-який х з Х\M (різниці множин) — на слово «ні»;

3) «перераховує множину B», коли його область застосування є натуральний ряд, а сукупність результатів є B.

Функція називається обчислюваною, якщо існує алгоритм, що її обчислює.

Множина називається розв‘язною відносно X, якщо існує алгоритм, що розв‘язує її відносно X.

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

Детальний аналіз поняття «алгоритм» виявляє, що (I) область можливих вихідних даних і область застосовності будь-якого алгоритму є перераховуваними множинами. Своєю чергою, (II) для будь-якої пари вкладених одна в другу перераховуваних множин можна підібрати алгоритм, у якого більша множина слугує областю можливих вихідних даних, а менша – областю застосовності.

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

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

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

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

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

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

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