|
|
| (не показано одну проміжну версію цього учасника) |
| Рядок 1: |
Рядок 1: |
| − | Зміст
| + | [[1 частина]] |
| − | Вступ
| + | |
| − | 1. Історія. | + | |
| − | 2. Визначення.
| + | |
| − | 2.1. Неформальне визначення.
| + | |
| − | 2.2. Формальне визначення.
| + | |
| − | 3. Відкриття Алана Тюринга.
| + | |
| − | 4. Машина Тюринга.
| + | |
| − | 5. Література.
| + | |
| | | | |
| − | | + | [[2 частина]] |
| − | | + | ''Зміст'' |
| − | | + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | Вступ
| + | |
| − | | + | |
| − | | + | |
| − | Алгор́итм, алгорифм (латинізов. Algorithmi, від імені перського математика IX ст. аль-Хорезмі) — система правил виконання обчислювального процесу, що обов'язково приводить до розв'язання певного класу задач після скінченного числа операцій.[1] При написанні комп'ютерних програм алгоритм описує логічну послідовність операцій. Для візуального зображення алгоритмів часто використовують блок-схеми.
| + | |
| − | Кожен алгоритм є списком добре визначених інструкцій для розв'язання задачі. Починаючи з початкового стану, інструкції алгоритму описують процес обчислення, які відбуваються через послідовність станів, які, зрештою, завершуються кінцевим станом. Перехід з одного стану до наступного не обов'язково детермінований — деякі алгоритми містять елементи випадковості.
| + | |
| − | Поняття алгоритму належить до первісних понять математики, таких, як множина чи натуральне число. Обчислювальні процеси алгоритмічного характеру (арифметичні дії над цілими числами, знаходження найбільшого спільного дільника двох чисел тощо) відомі людству з глибокої давнини. Проте, в явному вигляді поняття алгоритму сформувалося лише на початку XX століття.
| + | |
| − | Часткова формалізація поняття алгоритму почалась зі спроб розв'язання задачі розв'язності (нім. Entscheidungsproblem), яку сформулював Давид Гільберт в 1928 році. Наступні формалізації були необхідні для визначення ефективної обчислювальності[2] або «ефективного методу»[3]; до цих формалізацій належать рекурсивні функції Геделя-Ербрана-Кліні 1930, 1934 та 1935 років, λ-числення Алонзо Черча 1936 р., «Формулювання 1» Еміля Поста 1936 року, та машина Тюринга, розроблена Аланом Тюрингом протягом 1936, 1937 та 1939 років.
| + | |
| − | | + | |
| − | | + | |
| − |
| + | |
| − | | + | |
| − | Сторінка з «Алгебри» аль-Хорезмі— персидського математика, від імені якого походить слово алгоритм.
| + | |
| − | Основна ідея, що лежить в основі машини Тюринга, дуже проста. Машина Тюринга — це абстрактна машина (автомат), що працює зі стрічкою окремих комірок, в яких записано символи. Машина також має голівку для запису та читання символів із комірок, яка може рухатись вздовж стрічки. На кожному кроці машина зчитує символ з комірки, на яку вказує голівка, та, на основі зчитаного символу й внутрішнього стану робить наступний крок. При цьому, машина може змінити свій стан, записати інший символ в комірку, або пересунути голівку на одну комірку ліворуч або праворуч.[14]
| + | |
| − | На основі дослідження цих машин було висунуто тезу Тюринга (основна гіпотеза алгоритмів):
| + | |
| − | Для знаходження значень функції, заданої в деякому алфавіті, тоді і лише тоді існує деякий алгоритм, коли функція обчислювана за Тюрингом, тобто, коли її можна обчислити на придатній машині Тюринга.
| + | |
| − | Ця теза є аксіомою, постулатом, і не може бути доведена математичними методами, оскільки алгоритм не є точним математичним поняттям.
| + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | 1. Історія.
| + | |
| − | Слово алгоритм походить від імені перського вченого, астронома та математика Аль-Хорезмі. Приблизно 825 до н. е. він написав трактат, в якому описав придуману в Індії позиційну десяткову систему числення. В першій половині XII століття книжка потрапила до Європи в перекладі латинською мовою під назвою Algoritmi de numero Indorum. Вважається, що перше слово в перекладі відповідає невдалій латинізації імені Аль-Хорезмі, а назва перекладу звучить як «Алгорітмі про індійську лічбу». Через невірне тлумачення слова Algoritmi як іменника в множині ним стали називати метод обчислення.
| + | |
| − | Перший алгоритм, призначений для виконання на автоматичному обчислювальному пристрої (комп'ютері), описала Ада Лавлейс в 1843 році. Алгоритм мав обчислювати числа Бернуллі й працювати на аналітичній машині Беббіджа. Цей алгоритм вважається першою комп'ютерною програмою, а його розробниця, Ада Лавлейс — першим програмістом[4].
| + | |
| − | | + | |
| − |
| + | |
| − | | + | |
| − | З 1930-тих років починається бурхливий розвиток галузі дослідження алгоритмів та становлення інформатики в її сучасному вигляді. В 1935 році Стівен Кліні розробив перше формулювання теорії рекурсії, та показав еквівалентність розробленої системи частково рекурсивним функціям. В 1936 році незалежно були опубліковані роботи Алана Тюринга та Еміля Поста, в яких наведено схожі системи для визначення поняття алгоритму. А вже в 1937 році було доведено еквівалентність різних визначень[5].
| + | |
| − | Машина Тюринга пропонувала конструкцію, придатну для автоматичної інтерпретації. Побудована під впливом Алана Тюринга у Великобританії обчислювальна система 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 році[11] .
| + | |
| − | | + | |
| − | 2. Визначення
| + | |
| − | | + | |
| − | Неформальне визначення
| + | |
| − | Кожен алгоритм передбачає існування початкових (вхідних) даних та в результаті роботи призводить до отримання певного результату. Робота кожного алгоритму відбувається шляхом виконання послідовності деяких елементарних дій. Ці дії називають кроками, а процес їхнього виконання називають алгоритмічним процесом. В такий спосіб відзначають властивість дискретності алгоритму[12].
| + | |
| − | Важливою властивістю алгоритмів є масовість, або можливість застосування до різних вхідних даних. Тобто, кожен алгоритм покликаний розв'язувати клас однотипних задач.
| + | |
| − | Необхідною умовою, якій задовольняє алгоритм, є детермінованість, або визначеність. Це означає, що виконання команд алгоритму відбувається у єдиний спосіб та призводить до однакового результату для однакових вхідних даних.
| + | |
| − | Вхідні дані алгоритму можуть бути обмежені набором припустимих вхідних даних. Застосування алгоритму до неприпустимих вхідних даних може призводити до того, що алгоритм ніколи не зупиниться, або потрапить в тупіковий стан (зависання) з якого не зможе продовжити виконання.
| + | |
| − | | + | |
| − | Формальне визначення
| + | |
| − | Різноманітні теоретичні проблеми математики та прискорення розвитку фізики та техніки поставили на порядок денний точніше визначення поняття алгоритму.
| + | |
| − | Перші спроби уточнення поняття алгоритму та його дослідження здійснювали в першій половині XX століття Алан Тюринг, Еміль Пост, Жак Ербран, Курт Гедель, Андрій Марков, Алонзо Черч. Було розроблено декілька означень поняття алгоритму, але згодом було з'ясовано, що всі вони визначають одне й те саме поняття (теза Черча).[13]
| + | |
| − | Теза Черча — твердження, згідно з яким, клас алгоритмічно-обчислюваних функцій збігається з класом частково-рекурсивних функцій, функцій обчислюваних за Тюрінгом та інших формальних уточнень інтуїтивного поняття алгоритм. З неї випливає, що якщо функція належить до класу певної формалізації алгоритмічно-обчислюваної функції, то вона є алгоритмічно-обчислювана. Теза не доводиться. А еквівалентність класів формалізмів підлягає доведенню, що і було зроблено. Названа на честь американського математика Алонзо Черча. Також виділяють тезу Черча-Тюрінга.
| + | |
| − | | + | |
| − | 4. Відкриття Алана Тюринга.
| + | |
| − | Тест Тюрінга — тест на означення того, чи машинний інтелект можна ототожнити із людським. Відомий англійський учений Алан Тюрінг сформулював тезу, спрямовану на визначення моменту, з якого машину можна вважати інтелектуальною. Нехай експерт за допомогою телефону або подібного віддаленого пристрою спілкується з кимось (або чимось), що може бути як людиною, так і машиною.
| + | |
| − | Опис . Експерт дає певні тести-завдання. За результатами відповідей він повинен визначити, з ким він має справу — з людиною чи з ЕОМ. Якщо він приймає комп'ютер за людину, комп'ютер може вважатися інтелектуальним. Така перевірка дістала назву тесту Тюрінга.
| + | |
| − | | + | |
| − | Маши́на Тю́ринга — математичне поняття, введене для формального уточнення інтуітивного поняття алгоритму. Названа на честь англійського математика Алана Тюринга, який запропонував це поняття у 1936. Аналогічну конструкцію машини згодом і незалежно від Тюринга ввів американський математик Еміль Пост.
| + | |
| − | Основна ідея, що лежить в основі машини Тюринга, дуже проста. Машина Тюринга — це абстрактна машина (автомат), що працює зі стрічкою, що складається із окремих комірок, в яких записано символи. Машина також має голівку для запису та читання символів із комірок і яка може рухатись вздовж стрічки. На кожному кроці машина зчитує символ із комірки, на яку вказує голівка та, на основі зчитаного символу та внутрішнього стану, робиться наступний крок. При цьому, машина може змінити свій стан, записати інший символ в комірку або пересунути голівку на одну комірку ліворуч або праворуч.
| + | |
| − | Формальні визначення алгоритму з'явилися в тридцятих-сорокових роках 20 століття. Одним із перших було визначення англійського математика Алана Тюринга, який у 1936 році описав схему деякої гіпотетичної (абстрактної) машини і запропонував називати алгоритмами те, що вміє робити така машина. При цьому визначенні, якщо щось не може бути зроблено машиною Тюринга, це вже не алгоритм. Інакше кажучи, Тюринг формалізував правила виконання дій за допомогою опису роботи деякої конструкції.
| + | |
| − | У кожної машини Тюринга є стрічка, потенційно нескінченна в обидві сторони. Є скінченна множина символів стрічки S0, …, Sn, що називається алфавітом машини. У кожен момент часу кожна комірка може бути зайнята не більш ніж одним символом. Машина має деяку скінченну множину внутрішніх станів q0, q1, …, qn. У кожен даний момент часу машина знаходиться лише в одному із цих станів.
| + | |
| − | Нарешті, є голівка, яка у кожен даний момент часу знаходиться на одній із комірок стрічки. Машина діє не безупинно, а лише у дискретні моменти часу. Якщо у якийсь момент t голівка сприймає комірку (тобто знаходиться на комірці), що містить символ Si, і машина знаходиться у внутрішньому стані qj, то дія машини визначена однією із чотирьох дій:
| + | |
| − | 1. голівка затирає символ Si, і записує у тій же комірці новий символ Sk,
| + | |
| − | 2. голівка пересувається в сусідню ліву комірку,
| + | |
| − | 3. голівка пересувається в сусідню праву комірку,
| + | |
| − | 4. машина зупиняється.
| + | |
| − | У випадках (1)-(3) машина переходить у новий внутрішній стан qr, і готова знову до дії у наступний момент t + 1. Припустимо, що символ S0 представляє порожню комірку, і отже, голівка завжди сприймає деякий символ.
| + | |
| − | Перші три з можливих дій машини можуть бути описані відповідно такими упорядкованими четвірками, які називаються командами:
| + | |
| − | 1.
| + | |
| − | 2.
| + | |
| − | 3.
| + | |
| − | Тут перші два символа — це відповідно внутрішні стани машини і сприйнятий символ, наступні три визначають дію машини (запис голівкою символу Sk, або переміщення голівки на одну комірку вліво, або переміщення голівки на одну комірку вправо) та новий стан машини. Якщо стрічка вкладена в машину Тюринга, голівка машини встановлена на одну із комірок стрічки і машина приведена в один із своїх внутрішніх станів, то машина починає оперувати на стрічці: її голівка пише і стирає символи і пересувається з однієї комірки в іншу. Якщо при цьому машина колись зупиняється, то стрічка, яка знаходиться в ній в цей момент, називається результатом застосування машини до даної стрічки.
| + | |
| − | Незважаючи на свій простий устрій, машина Тюринга може виконувати складні перетворення слів. Спочатку, коли стрічка містить вхідне слово, автомат знаходиться проти деякої з комірок і у якомусь стані. У залежності від вибору початкової комірки, утворяться різні результати роботи машини Тюринга. У процесі своєї роботи машина Тюринга буде ніби перестрибувати з однієї комірки програми на іншу, відповідно до інформації на стрічці і вказівками в командах програми, поки не дійде до команди, яка переведе автомат у кінцевий стан.
| + | |
| − | | + | |
| − | Можливості машини Тюринга. Багатство можливостей конструкції Тюринга виявляється в тому, що якщо якісь алгоритми A та B реалізуються машинами Тюринга, то можна будувати програми машин Тюринга, які реалізують композиції алгоритмів A та B, наприклад, виконати A, потім виконати B або виконати A. Якщо в результаті утворилося слово так, то виконати B. У протилежному випадку не виконувати B або виконувати по черзі A, B, поки B не дасть відповідь ні.
| + | |
| − | У інтуїтивному сенсі такі композиції є алгоритмами. Тому їхня реалізація за допомогою машини Тюринга служить одним із засобів обґрунтування універсальності конструкції Тюринга.
| + | |
| − | Реалізованість таких композицій доводиться у загальному вигляді, незалежно від особливостей конкретних алгоритмів A та B. Доведення полягає в тому, що вказується засіб побудови з програм A та B програми потрібної композиції. Нехай, наприклад, потрібно побудувати машину , еквівалентну послідовному виконанню алгоритмів A та B. Поки виконується алгоритм A, у програмі працює частина A без урахування частини B. Коли алгоритм A дійде до кінця, то замість зупинки відбудеться перехід у перший стан частини B, і потім частина B буде працювати звичайним чином, наче частини A і не було.
| + | |
| − | Аналогічно конструюють й інші композиції машин Тюринга; щораз будуються загальні правила: що на що змінювати у вихідних програмах.
| + | |
| − | Описуючи різноманітні алгоритми для машин Тюринга і стверджуючи реалізованість усіляких композицій алгоритмів, Тюринг переконливо показав розмаїтість можливостей запропонованої їм конструкції, що дозволило йому виступити з такою тезою:
| + | |
| − | Всякий алгоритм може бути реалізований відповідною машиною Тюринга.
| + | |
| − | Це основна гіпотеза теорії алгоритмів у формі Тюринга. Одночасно ця теза є формальним визначенням алгоритму. Завдяки їй можна доводити існування або неіснування алгоритмів, створюючи відповідні машини Тюринга або доводячи неможливість їхньої побудови. Завдяки цьому з'являється загальний підхід до пошуку алгоритмічних рішень.
| + | |
| − | Якщо пошук рішення наштовхується на перешкоду, то можна використовувати цю перешкоду для доведення неможливості рішення, спираючись на основну гіпотезу теорії алгоритмів. Якщо ж при доказі неможливості виникає своя перешкода, то вона може допомогти просунутися в пошуку рішення, хоча б частково усунувши стару перешкоду. Так, по черзі намагаючись довести то існування, то відсутність рішення, можна поступово наблизитися до розуміння суті поставленної задачі.
| + | |
| − | Довести тезу Тюринга не можна, тому що в його формулюванні не визначене поняття всякий алгоритм, тобто ліва частина тотожністі. Його можна тільки обґрунтувати, представляючи різноманітні відомі алгоритми у вигляді машин Тюринга. Додаткове обґрунтування цієї тези складається в тому, що пізніше було запропоновано ще декілька загальних визначень поняття алгоритму і щораз вдавалося довести, що, хоча нові алгоритмічні схеми і виглядають інакше, вони в дійсності еквівалентні машинам Тюринга:
| + | |
| − | усе, що реалізовано в одній з цих конструкцій, можна зробити і в інших
| + | |
| − | Ці твердження доводяться строго, тому що в них мова йде вже про тотожність формальних схем.
| + | |
| − | | + | |
| − |
| + | |
| − | | + | |
| − | Польскі спеціалісти по криптографії винайшли в 1918 р. машину Enigma, электромеханічний роторний кодуючий пристрій, який переводить відкритий текст в закодований. Хоча пристрій напочатку створювався для захисту фінансових даних, під час другої світової війни німецькі військові побачили в ньому потенціал для захисту передаючих даних. Геніальний математик Алан Тюринг (Alan Turing) розробив спосіб взлому кодів Enigma, що дозволило вооружоним силам союзників розробити Colossus, машину, в заслугу якій американці часто ставлять раннє завершення війни.
| + | |
| − | | + | |
| − |
| + | |
| − | | + | |
| − | | + | |
| − | 1949 г. -- Алан Тюринг, прочитав работу Шеннона, на аркуші написав программу для шахматного поєдинку и вручну відслідив її дії в поєдинку з самим собой. Поєдинок Тюринга з створеною ним програмою можна вважати першим поєдинком "Людина проти комп’ютера", не дивлячись на відутність в грі справжнього комп’ютера.
| + | |
| − | | + | |
| − | Премія Тюрінга (англ. Turing Award) — найпрестижніша премія в галузі інформатики, щорічно присуджується Асоціацією обчислювальної техніки за видатні досягнення у цій галузі. Премія спонсорується корпораціями Intel та Google і зараз супроводжується нагородою в 250 000 доларів США. Премію названо на честь видатного англійського вченого Алана Тюрінга, математика, фахівця з криптографії, який отримав перші глибокі результати щодо теорії алгоритмів та обчислювальної складності задовго до появи перших комп'ютерів.
| + | |
| − |
| + | |
| − | | + | |
| − | Вперше Премію Тюрінга було присуджено Алану Перлісу (1966 року) за розвиток технології створення компіляторів. Пізніше її отримали Ніклаус Вірт та Пітер Наур за видатний внесок у розробку мов програмування.
| + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | 1. Українська радянська енциклопедія / ред. М. Бажан; 2-е видання. — К., 1974—1985, том 1, Алгоритм.
| + | |
| − | 2. Kleene 1943 in Davis 1965:274
| + | |
| − | 3. Rosser 1939 in Davis 1965:225
| + | |
| − | 4. Fuegi, J. and Francis, J. «Lovelace & Babbage and the creation of the 1843 'notes'.» Annals of the History of Computing 25 #4 (October-December 2003): Digital Object Identifier
| + | |
| − | 5. (Розділ «Algorithms» в Bauer, 2010)
| + | |
| − | 6. (Розділ «Algorithms» в Bauer, 2010)
| + | |
| − | 7. (Розділ «Algorithmic Languages» в Bauer, 2010)
| + | |
| − | 8. (Розділ 3.2 в O'Regan, 2008)
| + | |
| − | 9. (Розділ 3.3 в O'Regan, 2008)
| + | |
| − | 10. (Розділ 3.5 в O'Regan, 2008)
| + | |
| − | 11. (Розділ 3.6 в O'Regan, 2008)
| + | |
| − | 12. (Игошин, с. 314)
| + | |
| − | 13. (Игошин, с. 317)
| + | |
| − | 14. Basics: The Turing Machine (with an interpreter!. Good Math, Bad Math (9 лютого 2007).
| + | |
