Відмінності між версіями «* Розвиток теорії алгоритмів»

Версія за 20:04, 23 жовтня 2011

Вперше поняття алгоритму з’явилося в працях Е. Бореля (1912) та Г. Вейля (1921). Першими формальними моделями алгоритмічно обчислюваних функцій були λ-означувані функції (Алонзо Черч, 1932) та загальнорекурсивні функції (Курт Гедель, 1934). Вказані класи визначались як функції, графіки яких породжуються відповідно численням λ-конверсій та численням Ербрана-Геделя. В 1936 році Стівен Коул Кліні поширив поняття загальнорекурсивної функції на випадок часткових функцій, ввівши поняття частково рекурсивної функції, та описав клас таких функцій в чисто функціональних термінах. В 1943 році Еміль Пост запропонував модель обчислюваних функцій на основі введеного ним числення спеціального вигляду (канонічних систем). Для формалізації самого поняття алгоритму були запропоновані точні математичні описи алгоритмічної машини та обчислюваності на ній. Першою формальною моделлю алгоритмічної машини була машина Тюрінга (Алан Тюрінг, Еміль Пост, 1936). Із пізніших моделей відзначимо нормальні алгоритми (А. Марков, І952) та регістрові машини (Д. Шепердсон, Г. Стерджіс, 1963). В 1936 р. А. Черч та С. Кліні довели збіг класів загально-рекурсивних та λ-означуваних функцій. На основі цього факту та аналізу ідей, які привели до вказаних понять, А. Черч висунув тезу про збіг класу АОФ з класом загальнорекурсивних функцій. С. Кліні узагальнив цю тезу для випадку часткових функцій. Доведений А. Тьюрінгом в 1937 р. збіг класів частково рекурсивних функцій та функцій, обчислюваних на машинах Тюрінга, стало ще одним підтвердженням тези Черча. Пізніше такі збіги були встановлені для всіх відомих формальних моделей АОФ. Тому є всі підстави вважати, що кожна із названих вище формальних моделей адекватно уточнює інтуїтивне поняття АОФ. Теорія алгоритмів виникла як розділ математичної логіки, поняття алгоритму тісно пов'язане з поняттям числення. Перші та найчисельніші застосування теорія алгоритмів має саме в математичній логіці. Теорія алгоритмів є теоретичним фундаментом програмування, вона має застосування всюди, де зустрічаються алгоритмічні проблеми (основи математики, теорія інформації, теорія керування, конструктивний аналіз, обчислювальна математика, теорія ймовірності, лінгвістика, економіка та ін.).

Слово алгоритм походить від імені перського вченого, астронома та математика Аль-Хорезмі. Приблизно 825 до н. е. він написав трактат, в якому описав придуману в Індії позиційну десяткову систему числення. В першій половині XII століття книжка потрапила до Європи в перекладі латинською мовою під назвою Algoritmi de numero Indorum. Вважається, що перше слово в перекладі відповідає невдалій латинізації імені Аль-Хорезмі, а назва перекладу звучить як «Алгорітмі про індійську лічбу». Через невірне тлумачення слова Algoritmi як іменника в множині ним стали називати метод обчислення.

Баронеса Ада Лавлейс, яку вважають першим програмістом. Перший алгоритм, призначений для виконання на автоматичному обчислювальному пристрої (комп'ютері), описала Ада Лавлейс в 1843 році. Алгоритм мав обчислювати числа Бернуллі й працювати на аналітичній машині Беббіджа. Цей алгоритм вважається першою комп'ютерною програмою, а його розробниця, Ада Лавлейс — першим програмістом[4]. З 1930-тих років починається бурхливий розвиток галузі дослідження алгоритмів та становлення інформатики в її сучасному вигляді. В 1935 році Стівен Кліні розробив перше формулювання теорії рекурсії, та показав еквівалентність розробленої системи частково рекурсивним функціям. В 1936 році незалежно були опубліковані роботи Алана Тюринга та Еміля Поста, в яких наведено схожі системи для визначення поняття алгоритму. А вже в 1937 році було доведено еквівалентність різних визначень[5]. Машина Тюринга[1] пропонувала конструкцію, придатну для автоматичної інтерпретації. Побудована під впливом Алана Тюринга у Великобританії обчислювальна система ACE (завершена в 1950 році), та системи, побудовані за архітектурою фон Неймана в США та в інших країнах (в СРСР — МЕСМ, розроблена в 1950 році в Інституті електротехніки АН УРСР групою вчених під керівництвом Сергія Лебедєва), були першими універсальними обчислювальними пристроями, які повністю задовольняли вимоги обчислювальності[6]. Протягом 1935—1960 років було розроблено численні ідеї та технології, які лягли в основу сучасної інформатики. Формальні засоби для представлення алгоритмів мали не лише теоретичну значимість. Розробка алгоритмічних мов для програмування обчислювальних пристроїв розпочалась в 1951 році з публікації німецького інженера Ганса Рутісхаузера (нім. Heinz Rutishauser). Спочатку важливою здавалась проблема нотації, її досліджував Олексій Ляпунов, але поступово вона відійшла на другий план[7]. Перша мова програмування, Планкалькуль (нім. Plankalkül) була розроблена Конрадом Цузе в 1946 році, але через відсутність компіляторів виконання написаних цією мовою програм було неможливим. Опис мови був надрукований у 1972 році, а в 2000 році був створений компілятор для підмножини мови.[8] В середині 1950-тих було розроблено мову програмування Фортран Джоном Бакусом з IBM. В кінці 1950-тих було розроблено Алгол та Кобол; для навчальних цілей Бейсік (1963) та Паскаль (початок 1970-тих). Для системного програмування в Bell Laboratories було розроблено C[9]. λ-Числення дало поштовх до створення в кінці 1950-тих функційної мови програмування Лісп. На основі ідей Ліспу було створено Scheme. Мова ML була розроблена Робіном Мілнером в кінці 1970-тих. В кінці 1980-тих була створена мова Haskell[10]. Під впливом досліджень в галузі штучного інетелекту розроблено парадигму логічного програмування. На відміну від імперативної та функційної парадигм, логічне програмування не вимагає від розробника описувати спосіб розв'язання поставленої задачі. Planner — перша мова логічного програмування, була розроблена в 1969 році. На початку 1970-тих був розроблений Пролог, який згодом став найпоширенішою мовою логічного програмування зі стандартом ISO, затвердженим у 1995 році.