АЛГОРИТМ

1. Проблема визначення поняття «алгоритм».
2. Поняття «алгоритму».
3. Наявність вихідних даних і деякого результату.
4. Детермінованість.
5. Результативність.
6. Визначеність.
7. Форми подання алгоритмів.
8. Формалізація поняття алгоритмів. Теорія алгоритмів.
9. Історія кінцевих автоматів: машина Посту і машина Тьюринга.
10. Сучасний погляд на алгоритмізацію.

АЛГОРИТМ - система правил, сформульована на зрозумілому виконавцеві мові, яка визначає процес переходу від допустимих вихідних даних до деякого результату і має властивості масовості, кінцівки, визначеності, детермінованості.

Слово «алгоритм» походить від імені великого середньоазіатського вченого 8-9 ст. Аль-Хорезмі (Хорезм - історична область на території сучасного Узбекистану). З математичних робіт Аль-Хорезмі до нас дійшли тільки дві - алгебраїчна (від назви цієї книги народилося слово алгебра) і арифметична. Друга книга довгий час вважалася втраченою, але в 1857 в бібліотеці Кембріджського університету був знайдений її переклад на латинську мову. У ній описані чотири правила арифметичних дій, практично ті ж, що використовуються і зараз. Перші рядки цієї книги були переведені так: «Сказав Алгоритми. Віддамо належну хвалу Богу, нашому вождю і захиснику ». Так ім'я Аль-Хорезмі перейшло в Алгоритми, звідки і з'явилося слово алгоритм. Термін алгоритм використовувався для позначення чотирьох арифметичних операцій, саме в такому значенні він і увійшов в деякі європейські мови. Наприклад, в авторитетному словнику англійської мови Webster's New World Dictionary, виданому в 1957, слово алгоритм забезпечено позначкою «застаріле» і пояснюється як виконання арифметичних дій за допомогою арабських цифр.

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

Проблема визначення поняття «алгоритм».

Протягом багатьох століть поняття алгоритму пов'язувалося з числами і відносно простими діями над ними, та й сама математика була, по більшій частині, наукою про обчисленнях, наукою прикладної. Найчастіше алгоритми представлялися у вигляді математичних формул. Порядок елементарних кроків алгоритму задавався розстановкою дужок, а самі кроки полягали у виконанні арифметичних операцій і операцій відносини (перевірки рівності, нерівності і т.д.). Часто обчислення були громіздкими, а обчислення вручну - трудомісткими, але суть самого обчислювального процесу залишалася очевидною. У математиків не виникало потреба в усвідомленні і строгому визначенні поняття алгоритму, в його узагальненні. Але з розвитком математики з'являлися нові об'єкти, якими доводилося оперувати: вектори, графи, матриці, безлічі і ін. Як визначити для них однозначність або як встановити кінцівку алгоритму, які кроки вважати елементарними? У 1920-х завдання точного визначення поняття алгоритму стала однією з центральних проблем математики. У той час існувало дві точки зору на математичні проблеми:

Всі проблеми алгоритмічно розв'язні, але для деяких алгоритм ще не знайдений, оскільки ще не розвинені відповідні розділи математики.

Є проблеми, для яких алгоритм взагалі не може існувати.

Ідея про існування алгоритмічно нерозв'язних проблем виявилася вірною, але для того, щоб її обґрунтувати, необхідно було дати точне визначення алгоритму. Спроби виробити таке визначення привели до виникнення теорії алгоритмів, до якої ввійшли праці багатьох відомих математиків - К.Гедель , К.Черч, С.Кліні, А. Тьюрінг , Е.Пост, А.Марков, А.Колмогоров і багато інших.

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

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

Поняття «алгоритму».

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

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

Наявність вихідних даних і деякого результату.

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

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

Детермінованість.

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

Результативність.

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

Визначеність.

На кожному кроці алгоритму у виконавця має бути достатньо інформації, щоб його виконати. Крім того, виконавцю потрібно чітко знати, яким чином він виконується. Кроки інструкції повинні бути досить простими, елементарними, а виконавець повинен однозначно розуміти сенс кожного кроку послідовності дій, що становлять алгоритм (при обчисленні площі прямокутника будь-якому виконавцеві потрібно вміти множити і трактувати знак «x» саме як множення). Тому питання про вибір форми подання алгоритму дуже важливий. Фактично мова йде про те, якою мовою записаний алгоритм.

Форми подання алгоритмів.

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

Наприклад, опис алгоритму Евкліда знаходження НСД (найбільшого загального дільника) двох цілих позитивних чисел може бути представлено у вигляді трьох кроків. Крок 1: Розділити m на n. Нехай p - залишок від ділення.

Крок 2: Якщо p дорівнює нулю, то n і є вихідний НСД.

Крок 3: Якщо p не дорівнює нулю, то зробимо m рівним n, а n рівним p. Повернутися до кроку 1.

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

Одним з поширених способів запису алгоритмів є запис на мові блок-схем. Запис являє собою набір елементів (блоків), з'єднаних стрілками. Кожен елемент - це «крок» алгоритму. Елементи блок-схеми діляться на два види. Елементи, які містять інструкцію виконання якої-небудь дії, позначають прямокутниками, а елементи, що містять перевірку умови - ромбами. З прямокутників завжди виходить тільки одна стрілка (входити може кілька), а з ромбів - дві (одна з них позначається словом «так», інша - словом «ні», вони показують, відповідно, виконано чи ні перевіряється умова).

На малюнку представлена ​​блок-схема алгоритму знаходження НСД:

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

Формалізація поняття алгоритмів. Теорія алгоритмів.

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

Історія кінцевих автоматів: машина Посту і машина Тьюринга.

Машина Поста - абстрактна обчислювальна машина, запропонована Постом (Emil L.Post), яка відрізняється від машини Тьюринга більшою простотою. Обидві машини «еквівалентні» і були створені для уточнення поняття «алгоритм».

У 1935 американський математик Пост опублікував в «Журналі символічної логіки» статтю ФІНІТНОГО комбінаторні процеси, формулювання 1. У цій статті і з'явилася одночасно в Працях Лондонського математичного товариства статті англійського математика Тьюринга Про обчислюваних числах з додатком до проблеми вирішення були дані перші уточнення поняття «алгоритм». Важливість ідей Посту полягає в тому, що був запропонований найпростіший спосіб перетворення інформації, саме він побудував алгоритмічну систему (алгоритмічна система Посту). Пост довів, що його система володіє алгоритмічної повнотою. У 1967 професор В.Успенскій переказав ці статті з нових позицій. Він ввів термін «машина Посту». Машина Поста - абстрактна машина, яка працює по алгоритмам, розробленим людиною, вона вирішує наступну проблему: якщо для вирішення завдання можна побудувати машину Посту, то вона алгоритмічно вирішити. У 1970 машина Посту була розроблена в металі в Сімферопольському університеті. Машина Тьюринга була побудована в металі в 1973 в Малій Кримської Академії Наук.

Абстрактна машина Посту є безперервні стрічки, розділену на однакові клітини, кожна з яких може бути або порожній, або заповненої міткою «V». У машини є головка, яка може переміщатися уздовж стрічки на одну клітку вправо або вліво, наносити в клітку стрічки мітку, якщо цієї мітки там раніше не було, прати мітку, якщо вона була, або перевіряти наявність в клітці мітки. Інформація про заповнених мітками клітинах стрічки характеризує стан стрічки, яке може змінюватися в процесі роботи машини. У кожен момент часу головка знаходиться над однією з клітин стрічки і, як кажуть, оглядає її. Інформація про розташування головки разом зі станом стрічки характеризує стан машини Посту. Робота машини Поста полягає в тому, що головка пересувається уздовж стрічки (на одну клітку за один крок) вліво або вправо, завдає або стирає мітки, а також розпізнає, чи є мітка в клітці відповідно до заданої програми, що складається з окремих команд.

Машина Тьюринга складається з лічильної стрічки (розділеної на комірки і обмеженою зліва, але не справа), яка читає і друкарській головки, механізму протягування стрічки та операційного виконавчого пристрою, який може знаходитися в одному з дискретних станів q 0, q 1, ..., qs, що належать деякої кінцевої сукупності (алфавітом внутрішніх станів), при цьому q 0 називається початковим станом. Читаюча і друкарська головка може читати букви робочого алфавіту A = {a 0, a 1, ..., at}, прати їх і друкувати. Кожна осередок стрічки в кожен момент часу зайнята буквою з безлічі А. Найчастіше зустрічається буква а 0 - «пробіл». Головка знаходиться в кожен момент часу над деякою осередком стрічки - поточної робочої осередком. Стрічкопротяжний механізм може переміщати стрічку так, що головка виявляється над сусідньою осередком стрічки, при цьому можлива ситуація виходу за лівий край стрічки, яка є аварійною (неприпустимою), або машинного зупинки, коли машина виконує припис про зупинку.

Сучасний погляд на алгоритмізацію.

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

Анна Чугайнова