Математическая логика

Вид материала

Документы

Содержание Шаг 1: В М ищется наименьшее число Шаг 2 Шаг 3: Если в М не осталось чисел, то перейти к шагу 4, в противном случае перейти к шагу 1; Шаг 4

Подобный материал:

• Рабочая программа по дисциплине в 2-Математическая логика и теория алгоритмов шифр, 316.78kb.
• Программы кандидатского экзамена по специальности 01. 01. 06 "Математическая логика,, 50.44kb.
• Рабочая учебная программа по дисциплине математическая логика, 72.41kb.
• Рабочей программы учебной дисциплины дв2 Математическая логика и теория алгоритмов, 50.1kb.
• Рабочая учебная программа по дисциплине «Математическая логика и теория алгоритмов», 69.99kb.
• Н. В. Папуловская Математическая логика Методическое пособие, 786.38kb.
• Уакиев Валериан Савирович рекомендуемая литература, 334.04kb.
• Аннотация программы учебной дисциплины «Дискретная математика и математическая логика, 55.65kb.
• Логика компьютера, 210.22kb.
• Вопросы по курсу: Математическая логика и теория алгоритмов (2 курс), 30.21kb.

Теория алгоритмов - раздел математической логики, в котором изучаются теоретические возможности эффективных процедур вычисления (алгоритмов) и их приложения.

Основное понятие этой теории – алгоритм – в интуитивном (наивном) понимании существует в математике довольно давно, а точные математические понятия, которые в том или ином смысле формализуют интуитивное понятие алгоритма, предложены только в середине 30-х годов 20-го века. Необходимость такой формализации была обусловлена как вопросами обоснования математики, так и вопросами доказательства алгоритмической разрешимости и неразрешимости тех или иных задач. Очевидно, что в математике доказываемый объект должен быть точно определен.

В настоящее время теорию алгоритмов делят на дескриптивную (абстрактную) и метрическую (количественную). Первая исследует алгоритмы с точки зрения устанавливаемого ими соответствия между исходными данными и результатами; к ней относятся, в частности, проблемы построения алгоритма, обладающего теми или иными свойствами, - алгоритмические (массовые) проблемы (т.е. нахождение единого метода решения бесконечной серии однотипных единичных задач). Вторая исследует алгоритмы с точки зрения сложности как самих алгоритмов, так и задаваемых ими вычислений, т.е. процессов последовательного преобразования конструктивных объектов. Важно подчеркнуть, что как сложность алгоритмов, так и сложность вычислений могут определяться различными способами. Разработка методов оценки сложности алгоритмов и вычислений имеет важное теоретическое и практическое значение, а сам поиск теоретических моделей алгоритмов происходит в трех направлениях, которые и определяют три основных класса этих моделей: арифметизации алгоритмов, концепции абстрактной машины, принципа нормализации (т.е. преобразование слов в произвольных алфавитах с помощью подстановок).


Замечание:

Абстрактная дескриптивная теория алгоритмов не учит строить конкретные алгоритмы. Этим занимается прикладная метрическая (количественная) теория алгоритмов. В отличие от абстрактной теории алгоритмов прикладная теория рассматривает не только детерминированные, но также вероятностные (стохастические) и эвристические алгоритмы. В последнем случае, кроме детерминированных или статически заданных правил, алгоритм включает также содержательные указания о целесообразном направлении процесса.

Предмет и содержание читаемого курса.


Предметом изучения в читаемом курсе являются формальные уточнения интуитивного понятия «алгоритм» с различных точек зрения: арифметизации, нормализации и построения абстрактной машины. Целью читаемой дисциплины студентам специальности 2201 является усвоение необходимости формулировать алгоритмические проблемы как проблемы решения вопроса о существовании алгоритма для решения данной бесконечной серии однотипных задач и нахождение такого алгоритма в случае, если он существует.

Содержанием курса являются следующие вопросы:

• языки операндов и алгоритмические языки;
  
• рекурсивные функции как математический вариант уточнения понятия вычислимой арифметической функции;
  
• машины Тьюринга как математический эквивалент для общего интуитивного представления об алгоритме;
  
• нормальный алгоритм Маркова;
  
• сложность алгоритма.
  

Интуитивное (наивное) понятие алгоритма как основное первичное понятие математики.

Алгоритм – точное предписание для свершения некоторой последовательности элементарных дискретных действий над исходными данными любой задачи из некоторого класса (вообще бесконечного) однотипных задач, в результате выполнения которой получится решение этой задачи.

Иначе: Конечный кортеж правил, обладающих свойствами массовости (инвариантность относительно входной информации – это так называемое уточнение понятия – решение задачи в общем виде), детерминированности (однозначность применения этих правил на каждом шаге), результативности (получение после применения этих правил информации, являющейся результатом) и элементарности (отсутствует необходимость дальнейшего уточнения правил), называется алгоритмом на конечном множестве шагов решаемой задачи.

Примеры:

1. «Проезд запрещен», «Не курить» - не алгоритмы;
   
2. «Придерживайтесь правой стороны», «Место для курения», «Вход» - не алгоритмы;
   
3. Сложение (умножение, вычитание, деление) двух чисел (т.е. N²N) столбиком – алгоритм.
   

Пример:

Упорядочить в порядке возрастания конечное множество М положительных чисел. Описание решения этой задачи в интуитивном смысле может быть:

Шаг 1: В М ищется наименьшее число

Шаг 2: Найденное число приписывается справа к возрастающей последовательности чисел R (в начальный момент R пусто) и вычеркивается из М;

Шаг 3: Если в М не осталось чисел, то перейти к шагу 4, в противном случае перейти к шагу 1;

Шаг 4: Конец. Результатом считать последовательность R, построенную к данному моменту.

Это описание, которое кажется вполне ясным, далеко от алгоритма. Действительно, если М=⁹5, ⁶2, (1/3)^/2, то в предложенном варианте решения поставленной задачи не указано, как искать наименьшее число.

Этот пример показывает, что понятие алгоритма в интуитивном смысле требует уточнения понятия данных (т.е. указать каким требованиям должны удовлетворять объекты, чтобы алгоритмы могли с ними работать), памяти, дискретности, элементарности, конечности числа шагов, направленности, детерминированности, результативности, массовости.

Пояснения:

1. Приведенное наивное (интуитивное) определение алгоритма не является точным математическим определением, а лишь объясняет смысл слова «алгоритм», в котором это слово используется в математике.
   
2. Характеристиками алгоритма являются:
   

• детерминированность (определенность) – однозначность результата процесса при заданных исходных данных;
  
• дискретность – расчлененность процесса на отдельные элементарные акты (шаги, действия), возможность выполнения которых человеком или машиной не вызывает сомнений,
  
• массовость – исходные данные для алгоритма можно выбирать из некоторого множества данных (потенциально бесконечного), т.е. алгоритм должен обеспечить решение любой задачи из класса однотипных задач.
  

Основные требования к алгоритмам.

1. Очевидно, что каждый алгоритм имеет дело с данными: входными, выходными и промежуточными. В этом плане уточнение понятия алгоритм требует и уточнения понятия данных, т.е. указать, каким требованиям должны удовлетворять объекты, чтобы алгоритмы могли с ними работать. Ясно, что эти объекты должны быть четко определены и отличимы как друг от друга, так и от «необъектов». В теории алгоритмов четкая определенность объектов обусловлена заданием их в формальном языке L=, в котором символы конечного алфавита А рассматриваются как элементарные объекты для построения более сложных объектов конечными средствами S (этот язык часто называется языком операндов в отличие от языка описания самого алгоритма – алгоритмического языка).
   
2. В дальнейшем будем различать:
   
   • описание алгоритма (т.е. инструкции или программы);
     
   • механизм реализации алгоритма (это может быть процессор), включающий средства пуска, остановки, реализации элементарных шагов, выдачи результатов и обеспечения детерминированности процесса в управлении ходом вычислений;
     
   • память данных алгоритма;
     
   • процесс реализации алгоритма, то есть последовательность шагов (действий), которая будет порождена при применении алгоритма к конечным данным.
     

Пояснения:

1. Предполагается, что описание алгоритма и механизма его реализации конечны, а память данных алгоритма может быть и бесконечной. Конечность процесса реализации алгоритма означает его результативность (сходимость), то есть остановки алгоритма после конечного числа шагов (зависящего от данных) с указанием того, что считать результатом.
   
2. Предполагается также, что память данных алгоритма однородна и дискретна, то есть состоит из одинаковых ячеек, каждая из которых может содержать только один символ алфавита данных. Вопрос о том, нужна ли одна память или несколько (в частности для входных, выходных и промежуточных данных алгоритма) может решаться по-разному.
   
3. Понятие задачи «в общем виде» уточняется при помощи понятия «массовая алгоритмическая проблема». Последняя задается серией отдельных единичных проблем и состоит в требовании найти единый алгоритм их решения (когда такого алгоритма не существует говорят, что рассматриваемая массовая алгоритмическая проблема неразрешима). Так, проблема численного решения уравнений данного типа и проблема автоматического перевода есть массовые алгоритмические проблемы: образующими их единичными проблемами являются в 1-м случае проблемы численного решения отдельных уравнений данного типа, а во 2-м случае - проблемы перевода отдельных фраз.
   
4. Алгоритмический процесс – есть процесс последовательного преобразование конструктивных объектов, происходящий дискретными шагами; каждый шаг состоит в смене одного конструктивного объекта другим. Так, при применении алгоритма вычисления (f: D² D) столбиком к паре <507, 38> последовательно возникают следующие конструктивные объекты:
   

_507 _507 _507 _507

38 38 38 38

469


Здесь возможными исходными данными служат пары чисел, возможными результатами – числа (все в десятичной системе счисления), а возможные промежуточные результаты суть трехэтажные записи вида , где q-




запись числа в десятичной системе, z- такая же запись или пустое слово, а p- запись числа в десятичной системе с допущением точек над некоторыми цифрами (точка означает заимствование из старшего разряда).


Основная терминология теории алгоритмов.


Областью применимости алгоритма называется совокупность тех объектов, к которым он применим. Про алгоритм U говорят, что он:

1. «Выявляет функцию f», коль скоро его область применимости совпадает с областью определения f, и U перерабатывает всякий х из своей области применимости в f(x);
   
2. «Разрешает множество А относительно множества Х», коль скоро он применим ко всякому х из Х и перерабатывает х из ХА в слово «да», а всякий х из Х\А в слово «нет»;
   
3. «Перечисляет множество В», коль скоро его область применимости есть натуральный ряд, а совокупность результатов есть В.
   

Функция называется вычислимой, если существует вычисляющий ее алгоритм. Множество называется разрешимым (рекурсивным) относительно Х, если существует разрешающий его относительно Х алгоритм. Множество называется перечислимым (рекурсивно-перечислимым), если либо оно пусто, либо существует перечисляющий его алгоритм.

Замечания:

1. Область возможных исходных данных и область применимости любого алгоритма суть перечислимые множества;
   
2. Для любой пары вложенных одно в другое перечислимых множеств можно подобрать алгоритм, у которого большее множество служит областью возможных исходных данных, а меньшее областью применимости.
   
3. Разрешимые и перечислимые множества являются множествами, строение которых задается с помощью тех или иных алгоритмических процедур.
   
4. Процесс выполнения алгоритма называется алгоритмическим процессом.
   

Основные теоремы теории алгоритмов.

Теорема 1: Функция f вычислима тогда и только тогда, когда перечислим ее график, то есть множество всех пар вида .

Теорема 2: Подмножество А перечислимого множества Х разрешимо относительно Х тогда и только тогда, когда А и Х\А перечислимы.

Теорема 3: Если А и В перечислимы, то АВ и АВ также перечислимы.

Теорема 4: В каждом бесконечном перечислимом множестве Х существует перечислимое подмножество с неперечислимым дополнением (в силу теоремы 2 это перечислимое подмножество будет неразрешимым относительно Х).

Теорема 5: Для каждого бесконечного перечислимого множества Х существует вычислимая функция, определенная на подмножестве этого множества и не продолжаемая до вычислимой функции, определенной на всем Х.


Параметры алгоритма.

Как правило, для данного алгоритма можно выделить семь независимых характеризующих его параметров:

1. совокупность возможных исходных данных;
   
2. совокупность возможных результатов;
   
3. совокупность возможных промежуточных результатов;
   
4. правило начала;
   
5. правило непосредственной переработки;
   
6. правило окончания;
   
7. правило извлечения результата;
   

Основная гипотеза теории алгоритмов.


Любая практическая задача, приводящая к необходимости создания эффективного вычислительного метода (алгоритма), может быть поставлена в точных математических терминах.


Алгоритмические (формальные математические) модели.


Приведенное выше «наивное» (интуитивное) понятие алгоритма как первичное (исходное) понятие математики не допускает его определения в терминах более простых понятий. Возможные уточнения понятия алгоритма приводят, строго говоря, к известному сужению этого понятия. Каждое такое уточнение состоит в том, что для каждого из семи параметров алгоритма точно описывается некоторый класс, в пределах которого этот параметр может меняться. Выбор таких классов и отличает одно уточнение от другого. Поскольку семь параметров однозначно определяют некоторый алгоритм, то выбор семи классов изменения этих параметров определяет некоторый класс алгоритма.

В настоящее время среди математических моделей алгоритмов описанного типа наиболее известными являются уточнения, предложенные А.М.Тьюрингом (модель абстрактной вычислительной машины), А.А.Марковым (нормальные алгоритмы), А.Черчем (вычислительные функции).

Так, понятие машины Тьюринга как F S¹ следующим образом может быть использовано для уточнения общего представления об алгоритме в данном алфавите, если Тьюринговским алгоритмом в алфавите А называется всякий алгоритм U следующего вида:

• фиксируется некоторая машина Тьюринга в алфавите А, то есть , здесь Q – множество внутренних состояний машины, а R – правило перехода из одной конфигурации машины к другой);
  
• задается  - слово, принимаемое в качестве исходного данного для U (A^*);
  
• строится исходная конфигурация машины a₀q₀a₀, где q₀ – начальное состояние машины q₀Q, a₀ – пустой символ, a₀А;
  
• машина, отправляясь из a₀q₀a₀, заканчивает работу в заключительной конфигурации.
  

Считается, что для всякого алгоритма U в каком-либо алфавите может быть построен тьюринговский алгоритм, дающий при одинаковых исходных данных те же самые результаты, что и алгоритм U. Это соглашение в теории алгоритмов известно как тезис Тьюринга: «Всякий алгоритм может быть реализован машиной Тьюринга».

Замечания:

1. Доказать тезис Тьюринга нельзя, поскольку само понятие алгоритма (или эффективной процедуры) является неточным. Это не теорема и не постулат математической теории, а утверждение, которое связывает теорию с теми объектами, для описания которых она создана. По своему характеру тезис Тьюринга напоминает гипотезы физики об адекватности математических моделей физическим явлениям и процессам. Подтверждением правильности тезиса Тьюринга является математическая практика, а также эквивалентные тезисы и, в частности, тезис Черча для рекурсивных функций: «Всякая функция, вычислимая некоторым алгоритмом, частично-рекурсивная».
   
2. Из сопоставления двух вышеприведенных тезисов вытекает утверждение: «Функция вычислима машиной Тьюринга тогда и только тогда, когда она частично-рекурсивна». Это утверждение об эквивалентности двух алгоритмических моделей является (в отличие от тезисов) вполне точным математическим утверждением и, следовательно, доказуемо, то есть имеют место две теоремы:
   

Теорема 1: Всякая частично-рекурсивная функция вычислима на машине Тьюринга.

Теорема 2: Всякая функция, вычислимая на машине Тьюринга частично-рекурсивная.

3. Алгоритмические модели позволяют, с одной стороны, заменить неточность утверждения о существовании эффективных процедур (алгоритмов) точными утверждениями о существовании соответствующей алгоритмической модели (например, машины Тьюринга), а с другой стороны, утверждения о несуществовании таких моделей истолковывать как утверждения о несуществовании алгоритма вообще.
   
4. Тезисы позволяют выявлять случаи невозможности алгоритмов, однако, не указывают в случае их существования пути построения удобного для практики алгоритма (Напоминание: «Теория алгоритмов не учит строить конкретные алгоритмы»).
   

Блок-схемы алгоритмов.


Связи между шагами алгоритма можно изобразить в виде графа (блок-схемы) такого, как, например, следующий:





где вершинам соответствуют шаги (блоки), а дугам – переходы между шагами. Его вершины могут быть двух видов – операторы (из этих вершин выходит одно ребро) и предикаты (или логические условия; из этих вершин выходят два ребра). Кроме того, выделяют операторы начала и конца алгоритма.

В подобных схемах шаги могут быть элементарными или могут представлять собой самостоятельные алгоритмы (блоки).

На блок-схеме хорошо видна разница между описанием алгоритма и процессом его реализации.

Описание – это граф; процесс реализации – это путь в графе. Различные пути в одном и том же графе возникают при различных данных, которые создают разные логические условия в точках разветвления.

Отсутствие сходимости алгоритма означает, что в процессе вычисления не появляются условий, ведущих к концу, и процесс идет по бесконечному пути (зацикливается).

Отметим, что блок-схема отражает связи по управлению (что делать в следующий момент, то есть какому блоку передать управление), а не по информации (где этому блоку брать исходные данные).

Очевидно, что блок-схемы являются средством описания детерминизма алгоритма.

Замечания:

1. На практике блок-схемы часть имеют предикаты (точки разветвления) не только двоичные, но и многозначные, важно лишь, чтобы верным был ровно один из возможных ответов.
   
2. Блок схема вида:
   

где блок А₁ вычисляют функцию f₁(x), а исходными данными для А₂ являются результаты А₁, называется композицией алгоритмов А₁ и А₂ (то есть эта блок-схема задает алгоритм, вычисляющий f₂(f₁(x)), то есть композицию f₁ и f₂)


Машина Тьюринга.