Свойства алгоритмов.
1. Дискретность. Поэтому правило, порождающее непрерывный характер процесса решения задачи, не является алгоритмом.
Примеры:
«Уходя, гасите свет» - примитивный алгоритм.
«Не курить» - непрерывный процесс, не являющийся алгоритмом.
2. Массовость. Алгоритм должен решать не одну конкретную задачу (ограниченное множество неизменных исходных данных), а серию однотипных задач.
Массовость алгоритма – это допустимость всех объектов соответствующего класса, а не допустимость какого-либо их количества.
3. Детерминированность. Реализация алгоритма является детерминированным (определенным) процессом. Всякий раз при запуске алгоритма с одинаковыми исходными данными должен получаться одинаковый результат, т. е. алгоритм может быть повторен сколько угодно раз.
4. Потенциальная осуществимость алгоритма. Говорят, что алгоритм применим к допустимому исходному данному, если с его помощью можно получить искомый результат. Иначе, хотя исходное данное и допустимо, но алгоритм к нему не применим.
Отвлекаясь от реальной ограниченности времени и ресурсов, необходимых для выполнения алгоритма, требуют лишь того, чтобы алгоритмический процесс заканчивался после конечного числа шагов, и чтобы на каждом шаге не было препятствий для его выполнения. В этом случае считают, что алгоритм применим к исходному данному и потенциально (а не реально) осуществим.
5. Понятность. Алгоритм понятен для исполнителя, если он знает, как его выполнять (know how). Возникает вопрос: что именно должен знать исполнитель?
Свойство понятности можно истолковать как наличие алгоритма, определяющего процесс выполнения заданного алгоритма. В этом случае исполнителями могут быть любые объекты. Тогда исполнителю должен быть известен алгоритм (руководство к действию) для решения всех других алгоритмов, соответствующих исполнителю. Т. о. возникает рекурсивное определение.
6. Корректность. Если алгоритм создан для решения определенной задачи (заданного набора исходных данных), то для любого исходного данного из этого набора должно формироваться правильное решение.
7. Эффективность. Данное свойство определяет быстродействие и связано с понятием вычислительной сложности алгоритма.
Эмпирические алгоритмы, как правило, не являются эффективными. Теоретические алгоритмы являются корректными и эффективными, но могут быть реально неосуществимы.
Логика предикатов.
Алфавит языка логики предикатов включает следующие группы символов:
- предметные константы: a, b, c,…;
- предметные переменные: x, y, z,…;
- функциональные символы: f, g, h,…;
- предикатные символы: P, Q, R,…;
- логические связки: ¬, &, v, →, ↔;
-
кванторы:
Кроме того, для задания порядка операций могут использоваться скобки.
Множество D объектов, о которых ведется рассуждение, называется областью интерпретации языка логики предикатов. Предметные константы соответствуют конкретным элементам множества D, а предметы переменные могут принимать значения множества D.
Функциональные символы соответствуют функциям, заданным на области интерпретации. Функциональный символ вместе со списком аргументов образует функциональную форму. Например, если D – множество чисел, то функциональная форма f(x,y) может интерпретироваться как двуместная функция сложения чисел: x+y.
Термом является всякая предметная константа, предметная переменная либо функциональная форма. Аргументами функциональной формы могут быть любые термы, например f(a, x, g(c, z)).
Понятие формул в логике предикатов определяется следующим образом:
- всякий атом есть формула;
- если А и В – формулы, то ¬А, А&В, АvВ, А→В, А↔В также формулы;
-
если А
–
формула и х
–
переменная, то
-
формулы;
- других формул нет
Квантор
всеобщности соответствует словосочетанию
«для всех», т.е. формула вида интерпретируется
как высказывание: «Для всех объектов
области интерпретации выполняется
свойство Р».
Квантор существования соответствует
слову «существует». Например, формула
вида интерпретируется как высказывание:
«Существует пара объектов в области
интерпретации, которые находятся в
отношении Q».
Квантор вместе с переменной называется квантификацией. Область действия некоторой квантификации есть формула, к которой применяется эта функция.
Для того, чтобы записать некоторое утверждение на языке логики предикатов необходимо:
- зафиксировать множество объектов, о которых идет речь, как область интерпретации;
- выделить функциональные связи и отношения (свойства), упоминаемые в данном утверждении и сопоставить им функциональные и предикатные символы соответствующей местности;
- определить логическую структуру утверждения, включая области действия кванторов, и записать утверждение в виде формулы.