Властивості алгоритму

ЛЕКЦІЯ 1. Вступ. Інтуїтивне поняття алгоритму.

КОНСПЕКТ ЛЕКЦІЙ

Поняття алгоритму інтуїтивно зрозуміло і часто використовується в математиці. Додавання і множення чисел “стовпчиком”, що відомо ще зі школи, формула обчислення коренів квадратного рівняння, перемножування двох матриць за правилом “рядок на стовпець” є алгоритмами. Безліч прикладів можна продовжити. У сучасній практиці під алгоритмом часто розуміють програму, а критерієм існування алгоритму вважають можливість його запрограмувати. Однак це не зовсім так. Спочатку дамо поняття алгоритму.

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

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

· Дискретність інформації. Кожен алгоритм має справа з даними – вхідними, проміжними і вихідними. Ці дані представляються у виді у виді кінцевих слів у деякому алфавіті.

· Дискретність роботи алгоритму. Алгоритм виконується по кроках і при цьому на кожнім кроці виконується тільки одна операція.

· Виконуваність операцій. В алгоритмі не повинне бути нездійсненних операцій. Наприклад, не можна в програмі надати змінній значення “нескінченність”, – така операція була б нездійсненною. Кожна операція обробляє визначену ділянку в оброблюваному слові.

· Скінченність алгоритму. Скінченність алгоритму означає, що опис алгоритму повинен бути скінченим. Крім цього, робота самого алгоритму також повинна бути кінцева, тобто після кінцевого числа кроків алгоритм повинний закінчувати свою роботу. Для програм, зокрема це означає, що алгоритм не повинний “зацикливаться”. Робота алгоритму завершується видачею результату. Тому кінцівка алгоритму тісно зв'язана з його результативністю: здатністю видавати результат.

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

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

Дата добавления: 2014-01-07