Властивості алгоритму 1
Значення слова алгоритм дуже схоже зі значенням слів рецепт, інструкція. Однак будь-який алгоритм на відміну від рецепта або способу обов'язково має такі властивості.
1. Виконання алгоритму розбивається на послідовність закінчених дій-кроків. Тільки виконавши одну дію (команду), можна приступати до виконання наступного. Це властивість алгоритму називається дискретністю. Провести кожну окрему дію виконавцю наказує спеціальна вказівка в записі алгоритму (команда).
2. Зрозумілість - алгоритм не повинен містити приписів, зміст яких може сприйматися виконавцем неоднозначно, тобто запис алгоритму повинна бути настільки чіткою і повною, щоб у виконавця не виникало потреби в ухваленні будь-яких самостійних рішень. Алгоритм завжди розрахований на виконання «не роздумуючи" виконавця. Алгоритм складається з команд, що входять в СКІ.
Розглянемо відомий приклад "побутового" алгоритму - алгоритм переходу вулиці: "Подивися наліво. Якщо машин немає, дійди до середини вулиці. Якщо є, почекай, поки вони проїдуть, і т.д. ". Уявіть собі ситуацію: машина зліва є, але вона не їде - у неї змінюють колесо. Якщо ви думаєте, що виконавець алгоритму повинен чекати, то ви зрозуміли цей алгоритм. Якщо ж ви вирішили, що вулицю переходити можна, вважаючи алгоритм підправленим зважаючи на непередбачені (на вашу думку!) Обставин, то ви не засвоїли поняття алгоритму.
3. детермінованість (визначеність і однозначність). Кожна команда алгоритму визначає однозначне дію виконавця, і має бути однозначно визначено, яка команда виконується наступною. Тобто якщо алгоритм багаторазово застосовується до одного і того ж набору вихідних даних, то на виході він отримує кожен раз один і той же результат.
4. Результативність - виконання алгоритму має закінчитися за кінцеве число кроків, і при цьому повинен бути отриманий результат рішення задачі. В якості одного з можливих результатів може бути і встановлення того факту, що завдання рішень не має.
Властивість результативності містить в собі властивість кінцівки - завершення роботи алгоритму за кінцеве число кроків.
5. Масовість - алгоритм придатний для вирішення будь-якої задачі з деякого класу задач, тобто алгоритм правильно працює на деякій множині вихідних даних, яке називається областю застосовності алгоритму.
Властивість масовості визначає скоріше якість алгоритму, а не відноситься до обов'язкових властивостями (як дискретність, зрозумілість і ін.). Існують алгоритми, область застосовності яких обмежується єдиним набором вхідних даних або навіть їх відсутністю (наприклад, отримання фіксованого числа вірних цифр числа p). Правильніше говорити про те, що алгоритм повинен бути застосований до будь-яких даних зі своєї області визначення, і слово масовість не завжди підходить для опису такої властивості.
поняття алгоритму
Узагальнивши вищесказане, сформулюємо таке поняття алгоритму.
Алгоритм - зрозуміле і точне розпорядження виконавцю на виконання кінцевої послідовності дій, що приводить від вихідних даних до шуканого результату.
Наведене визначення не є визначенням в математичному сенсі слова, тобто це не формальне визначення (формальне визначення алгоритму см. в статті "Теорія алгоритмів").
Відзначимо, що для кожного виконавця набір допустимих дій (СКІ) завжди обмежений - не може існувати виконавця, для якого будь-яка дія є допустимим. Перефразований міркування І. Канта обґрунтовує сформульоване твердження наступним чином: "Якби такий виконавець існував, то серед його допустимих дій було б створення такого каменю, який він не може підняти. Але це суперечить допустимості дії «Підняти будь-який камінь» ".
Цікаво, що існують завдання, які людина, взагалі кажучи, вміє вирішувати, не знаючи при цьому алгоритм її вирішення. Наприклад, перед людиною лежать фотографії кішок і собак. Завдання полягає в тому, щоб визначити, кішка або собака зображена на конкретній фотографії. Людина вирішує цю задачу, але написати алгоритм вирішення цієї задачі поки надзвичайно складно.
З іншого боку, існують завдання, для яких взагалі неможливо побудувати процедуру вирішення. Причому даний факт можна строго довести. Про це ви можете прочитати в статті "Алгоритмічно нерозв'язні проблеми" 2.