 3.2. Логическое программирование. Клаузы Хорна и метод резолюций       3.3. Язык логического программирования Пролог   Основные синтаксические конструкции:      
3.4. Модальная логика
3.5. Нечеткая логика
3.6. Темпоральная логика
4. Алгоритмы и вычислимость
4.1. Задачи и алгоритмы
Задача (массовая проблема) - некоторый общий вопрос, на который должен быть дан ответ.
Как правило задача имеет 1 или несколько параметров. Фиксированное значение параметров образует исходные данные задачи, которые будем называть входом.
Задав вход массовой проблемы, мы образуем индивидуальную задачу. Таким образом массовую проблему можно рассматривать как множество индивидуальных задач.
Массовая проблема характеризуется:
1) Точным описанием допустимых значений параметров (множество допустимых входов).
2) Заданием условий, которым должен удовлетворять ответ.
Пример задачи.
1. Определить наибольший общий делитель чисел X и Y.
Вход: натуральные числа X и Y.
Ответ: максимальное натуральное число Z, такое, что X%Z=0 и Y%Z=0. (Под операцией % понимается остаток от деления).
Для решения каждой задачи требуются определенные вычислительные ресурсы. Величина, которая численно характеризует объем вычислительных ресурсов, минимально необходимых для решения задачи, называется сложностью задачи. Важно, что сложность задачи может зависеть от входа и в общем случае является функцией некоторых характеристик входа.
Неформальное определение алгоритма: алгоритм решения массовой проблемы П - это пошаговая процедура, которая за конечное время решает любую из индивидуальных задач I принадлежащих П.
Алгоритм должен обладать следующими свойствами:
Описание алгоритма конечно, при этом предполагается, что существует объект, понимающий и выполняющий это описание. Такой объект назовем вычислителем.
1) Должны быть четко указаны условия остановки процесса и что следует считать результатом процесса. (Свойство результативности)
2) Алгоритм решения массовой проблемы П должен быть способен решить любую из индивидуальных задач I принадлежащих П, потратив на решение индивидуальной задачи конечное время. (Свойство называется массовостью.)
3) Процесс решения одной и той же индивидуальной задачи протекает одинаково. (Свойство называется детерминированностью.)
Не для каждого алгоритма очевидно, что он приводит в правильному решению поставленной задачи. Если правильность алгоритма не очевидна, то алгоритм нуждается в доказательстве.
Данное выше определение алгоритма достаточно для большинства применений, но не для всех, ибо существуют такие задачи, для которых построение алгоритма невозможно. Если задача поставлена, то удовлетворительными можно считать два результата ее решения: решение проставленной задачи или доказательство того факта, что решение задачи невозможно. Для такого доказательства не годится неформальное определение алгоритма. Не является удовлетворительным и сведение понятия алгоритма до какого-нибудь из известных языков программирования по причине их сложности.
Понятие алгоритма связано: во-первых с массовой проблемой, которую он призван решать, во-вторых с вычислителем, который будет этот алгоритм выполнять. Различные подходы к формализации понятия алгоритма формализуют как понятие задачи, так и понятие вычислителя.
4.2. Машина Тьюринга
Первый подход к формализации алгоритма связан с формализацией понятия вычислителя, т. е. к построению очень простого, но функционально полного вычислителя. Таким вычислителем является машина Тьюринга.
Неформальное описание.
Машина Тьюринга состоит из:
- бесконечной в обе стороны ленты;
- вычислительной головки.
В каждый момент времени (такт) головка находится в некотором состоянии и обозревает одну позицию на ленте, в которой находится символ (обозреваемый символ).
Головка может выполнить одно из четырех действий:
1) Записать в обозреваемую позицию на ленте новый символ.
2) Переместиться на одну позицию влево по ленте.
3) Переместиться на одну позицию вправо по ленте.
4) Больше ничего не делать.
Действие головки однозначно определяется парой: (<текущее состояние головки> <обозреваемый символ>) и задается программой. Если в программе текущая пара не существует, то головка останавливается.
Функция называется вычислимой по Тьюрингу, если существует такая машина Тьюринга, которая вычисляет ее значения для тех наборов значений аргументов, для которых функция определена, и работающая вечно, если для данного набора значений аргументов функция не определена.
Условимся значения x1, x2 ,…,xn аргументов располагать на ленте в виде слова:
Переработка слова начинается из стандартного положения q1, когда обозревается крайняя правая единица слова. Если функция f определена на данном наборе аргументов, то на ленте в результате останется f(x1,…,xn) записанных подряд единиц, иначе – машина работает бесконечно. При эти условиях будем говорить, что машина Тьюринга вычисляет данную функцию.
Композиция машин Тьюринга. Пусть заданы
Для каких функций возможно их вычисление с помощью машины Тьюринга? Многочисленные исследования показали, что каждая функция, для вычисления значения которой существует какой-нибудь алгоритм, оказалась вычислимой посредством некоторой машины Тьюринга, что дало повод выдвинуть следующую гипотезу.
Тезис Тьюринга (основная гипотеза теории алгоритмов):
4.3. Рекурсивные функции
Рекурсивные функции – другой способ уточнения понятия алгоритма.
С каждым алгоритмом однозначно связана функция, которую он вычисляет (т.е. сопоставляет допустимым исходным данным результат).
Для всякой ли функции существует вычисляющий ее алгоритм? Как описать такие алгоритмически вычислимые функции?
Исследование этих и других вопросов привело к созданию теории рекурсивных функций.
Дадим описание класса вычислимых (рекурсивных) функций.
Ограничимся рассмотрением функций, которые вместе со своими аргументами принимают значения в множестве всех целых неотрицательных чисел. Функции возьмем частичные, т.е., определенные не для всех значений аргументов.
Сначала объявим простейшие (базисные) функции:
O(x) = 0 (одноместная нуль-функция, которая при любом значении x принимает значение 0);
S(x) = x+1 (одноместная функция следования, принимающая на числе x значение x+1);
 (n-местная функция-проектор, принимающая на наборе чисел (x1, …, xn) значение xm, 1 ≤ m ≤ n; n = 1, 2,…).
Очевидно, что базисные функции вычислимы (правильно вычислимы по Тьюрингу).
Далее на множестве всех рассматриваемых функций введем следующие операторы.
Оператор суперпозиции. Говорят, что частичная функция f(x1, …, xn) получена из частичных функций g(y1, …, ym), h1(x1, …, xn), …, hm(x1, …, xn) с помощью оператора суперпозиции, ели для всех x1, …, xn справедливо равенство: f(x1, …, xn) = g(h1(x1, …, xn), …, hm(x1, …, xn)).
2) Оператор примитивной рекурсии. Говорят, что функция f(x1, …, xn, xn+1) получена из функций g(x1, …, xn) и h(y1, …, yn+2) с помощью оператора примитивной рекурсии, если для любых x1, …, xn, y справедливы равенства:
f(x1, …, xn, 0)= g(x1, …, xn),
f(x1, …, xn, y+1)= g(x1, …, xn,y, f(x1, …, xn, y)).
Функция называется примитивно рекурсивной, если она может быть получена из простейших функций (определенных выше) при помощи конечного числа применений операторов суперпозиции и примитивной рекурсии.
3) Оператор минимизации. Говорят, что
Очевидно, что каждый из трех введенных операторов сохраняет свойство вычислимости функций.
Функция называется частично рекурсивной, если она может быть получена из простейших функций при помощи конечного числа применений операторов суперпозиции, примитивной рекурсии и минимизации.
Если функция всюду определена и частично рекурсивна, то она называется общерекурсивной.
Из данного определения и приведенных выше замечаний о вычислимости базисных функций и о сохранении вычислимости операторами суперпозиции, примитивной рекурсии и минимизации следует, что всякая частично рекурсивная функция является вычислимой.
Вместе с обратным предложение (гипотеза) называется как
Тезис Черча. Любая функция тогда и только тогда вычислима, когда она частично рекурсивна.
Иными словами, любой алгоритм над данными в цифровой форме может быть построен как последовательность операций суперпозиции, примитивной рекурсии и минимизации над базисными функциями от исходных данных. Исторически именно это предложение было первым точным математическим определением понятия алгоритма.
Как и тезис Тьюринга, эта гипотеза не может быть доказана строго математически, она подтверждается практикой, опытом.
После введения определений алгоритма в виде машины Тьюринга и нормального алгоритма Маркова (см. далее) была доказана равносильность всех трех этих определений.
4.4. Нормальные алгоритмы Маркова
Мы будем называть алфавитом всякое конечное множество символов (знаков, букв, цифр и т.п.). Все символы в алфавите будем называть его буквами. Словом в алфавите называется всякий набор букв этого алфавита. Алгоритм, для которого слова в алфавите A служат исходными данными и результатами работы, называется алгоритмом в алфавите A.
Конкатенацией (соединением) слов P=a1a2…an и Q=b1b2…bm называется слово PQ = a1a2…anb1b2…bm. Эта операция ассоциативна: слова P(QS) и (PQ)S совпадают и записываются как PQS.
К словам в любом алфавите мы относим и так называемое пустое слово, обозначаемое Λ и обладающее следующим свойством: ΛP = PΛ = P для любого слова P.
Если R=PQS, то говорят, что слово Q входит в слово R и данное вхождение Q в R называют левым, если не существует слов P´ и S´ таких, что R = P´QS´ и длина P´ меньше длины P . Другими словами, это первое вхождение слова Q в слово R.
Если P и Q - слова в алфавите A и символы → и · не входят в A, то слова P→Q и P→·Q называются формулами Марковской подстановки в алфавите A. Заметим, что здесь каждое из слов P и Q может быть пустым словом.
Формула подстановки P→Q называется простой, формула P→·Q - заключительной.
Пусть P→(·)Q обозначает любую из формул подстановки P→Q или P→·Q.
Конечная последовательность формул подстановки в алфавите A
P1→(·)Q1, P2→(·)Q2, …, Pr→(·)Qr
называется схемой в алфавите A.
Она определяет следующий алгоритм A переработки любого слова R в алфавите A:
Пусть R0 = R.
Шаг i алгоритма A (i = 0, 1, 2, …). Если ни одно из слов P1, P2, …, Pr не входит в Ri, то работа алгоритма заканчивается и Ri будет его результатом A(R); в противном случае находим в схеме первую (с наименьшим номером m) формулу подстановки Pm→(·)Qm такую, что Pm входит в Ri, и подставляем Qm вместо левого вхождения Pm в Ri; результат такой подстановки обозначаем Ri+1 (в этом случае пишем A: Ri→(·)Ri+1 и читаем «A переводит Ri в Ri+1». Если формула подстановки Pm→(·)Qm заключительная, то работа алгоритма заканчивается и его результатом A(R) является Ri+1; в противном случае переходим к шагу i+1.
Возможно, что описанный процесс никогда не закончится. В таком случае мы говорим, что алгоритм A неприменим к слову R и его результат A(R) неопределен.
Алгоритм A, определенный таким образом, называется нормальным алгоритмом Маркова в алфавите A, а определяющая его схема - схемой алгоритма A.
Пример1.
Пусть А={a, b} – алфавит, а схема нормального алгоритма следующая:
Применим алгоритм к слову aabab:
Пример2.
Пусть A = {+, 1} и алгоритм A имеет схему: 1+1→ 11, + → +, 1→·1.
Тогда, например, A: 111+1+11→1111+11→ 111111→·111111. Данный алгоритм неприменим к словам в алфавите А, которые или начинаются с буквы +, или заканчиваются этой буквой, или содержат две рядом стоящие такие буквы, а в остальных словах в алфавите А стирает все буквы +, т.е. осуществляет сложение натуральных чисел в представлении числа n словом из n единиц.
Функция f, заданная на некотором множестве слов алфавита А, называется нормально вычислимой, если найдется расширение В алфавита А и такой нормальный алгоритм в В, что каждое слово Q в алфавите А из области определения функции f этот алгоритм перерабатывает в слово f(Q).
Гипотеза А.А. Маркова (принцип нормализации Маркова): для вычисления функции, заданной в некотором алфавите, существует алгоритм тогда и только тогда, когда функция нормально вычислима.
Другими словами: всякий алгоритм эквивалентен некоторому нормальному алгоритму Маркова. Это утверждение нельзя доказать, и оно не является теоремой. Скорее, это есть точное определение (одно из) понятия алгоритма, а именно: алгоритмом называется то и только то, что является нормальным алгоритмом Маркова, т.е. может быть определено схемой в некотором алфавите.
Понятия нормально вычислимой функции, вычислимой по Тьюрингу и частично рекурсивной равносильны:
4.5. Алгоритмически неразрешимые проблемы
Алгоритмическая проблема (массовая проблема) – проблема, в которой требуется найти единый алгоритм решения серии однотипных единичных задач.
Проблема называется алгоритмически не разрешимой, если не существует алгоритма ее решения. Под алгоритмом при этом, естественно, подразумевается алгоритм в его точном определении - нормальный алгоритм Маркова, машина Тьюринга и т.п.
Нумерация алгоритмов.
Множество всех алгоритмов счетно (т.к. алгоритм можно задать конечным описанием – словом, а множество всех конечных слов в конечном алфавите счетно), как и множество натуральных чисел, т.е. существует взаимно-однозначное соответствие между этими двумя множествами.
Нумерацией алгоритмов назовем функцию, которая каждому алгоритму А ставит в соответствие число n – номер алгоритма А.
Нумерация всех алгоритмов есть и нумерация всех вычислимых функций, если считать ее номером номер некоторого алгоритма, который ее вычисляет.
Нумерация машин Тьюринга.
Проблема распознавания самоприменимых машин Тьюринга алгоритмически неразрешима.
На основании этой теоремы устанавливается и другая алгоритмически не разрешимая проблема:
Проблема распознавания применимых машины Тьюринга алгоритмически неразрешима.
Другие алгоритмически неразрешимые проблемы:
Проблема остановки: не существует алгоритма, который по номеру x любого алгоритма и исходным данным y определял бы, остановится алгоритм при этих данных, или нет.
Проблема определения общерекурсивности алгоритма, т.е. проблема определения того, ко всяким ли допустимым начальным данным применим алгоритм, неразрешима.
Десятая проблема Гильберта – нахождения алгоритма, определяющего, имеет ли уравнение вида F(x,y,z)=0, где F(x,y,z)-многочлен с целыми показателями степеней и целыми коэффициентами, целочисленное решение, алгоритмически неразрешима.
Проблема эквивалентности алгоритмов – определить по двум произвольным заданным алгоритмам (например, по двум машинам Тьюринга), будут ли они выдавать одинаковые выходные результаты на любых исходных данных, неразрешима.
И др.
5. Анализ алгоритмов
|
