- •Алгоритм приведения к сднф:
- •Правила вывода
- •Символы логики предикатов
- •Кванторы всеобщности и существования. Свободные и связные переменные лп.
- •Равносильные и приведенные формулы лп. Теорема о существовании приведенной формулы.
- •Выводимость в ип:
- •Логические основы эвм. Простейшие преобразователи информации. Структурная формула. Функциональная схема.
- •Свойства нечетких множеств
- •Алгоритм — это упорядоченный набор однозначных выполнимых шагов.
- •Свойства:
- •Теорема. Всякая частично рекурсивная функция f является вычислимой функцией.
- •Определение алгоритма применимого к слову. Определение алгоритма над алфавитом. Простая и заключительная подстановки в теории нормальных алгоритмов Маркова. Схема алгоритма.
- •Нумерация алгоритмов. Нумерация машин Тьюринга. Существование невычислимых по Тьюрингу функций.
- •Примеры алгоритмически неразрешимых проблем.
-
Нумерация алгоритмов. Нумерация машин Тьюринга. Существование невычислимых по Тьюрингу функций.
Множество всех алгоритмов счетно. Ведь любой алгоритм можно задать конечным описанием, а множество всех конечных слов в фиксированном алфавите счетно. Счетность множества алгоритмов означает наличие взаимно-однозначного соответствия между алгоритмами и числами натурального ряда, т.е. функции типа , взаимно-однозначно отображающей слова в алфавите, выбранном для описания алгоритмов в числа натурального ряда. Такая функцияназывается нумерацией алгоритмов, а ее аргумент- номером алгоритмапри нумерации.
Для формального анализа различных проблем, связанных с машинами Тьюринга, удобно каждой машине присвоить числовой номер – целое положительное число. Способ Геделя основан на том, что, как известно из арифметики, любое целое положительное число A можно единственным способом представить в виде произведения простых множителей в виде:
Здесь -i-й простой множитель числа А; ni – степень, с которой данный множитель входит в разложение числа А
Теперь посмотрим, как получить геделевский номер машины Тьюринга. Такая машина задана своими правилами. Каждое правило можно представить как строку символов
Мы уже знаем, как читать такую строку: если машина находится в состоянии Qi и читает символ Sj, то она переходит в состояние Qk , записывает символ Sz вместо Sj и выполняет действие A={оставить ленту на месте; сдвинуть ленту влево на одну ячейку; сдвинуть ленту вправо на одну ячейку}.
Проблема остановки имеет следующую формулировку: найти алгоритм, позволяющий по номеру машины Тьюринга и произвольной конфигурации определить, придет ли данная машина в заключительное состояние, начав работать в этой конфигурации.
Проблема самоприменимости является частным случаем проблемы остановки и заключается в том, чтобы определить, применима ли машина к своему номеру.
-
Примеры алгоритмически неразрешимых проблем.
Проблема остановки имеет следующую формулировку: найти алгоритм, позволяющий по номеру машины Тьюринга и произвольной конфигурации определить, придет ли данная машина в заключительное состояние, начав работать в этой конфигурации.
Проблема самоприменимости является частным случаем проблемы остановки и заключается в том, чтобы определить, применима ли машина к своему номеру. Проблема эквивалентности алгоритмов; По двум произвольным заданным алгоритмам (например, по двум машинам Тьюринга) определить, будут ли они выдавать одинаковые выходные результаты на любых исходных данных.
-
Меры сложности алгоритмов. Временная и емкостная сложность. Переборные и распознавательные задачи.
сложность алгоритма – количество необходимых для решения задачи ресурсов как функция от ее размера.
Рассмотрим некоторые из них:
1. Временная сложность алгоритма – «время» выполнения алгоритма, измеряемое в «шагах» (инструкциях алгоритма, которые необходимо выполнить для достижения результата)
2. Емкостная сложность алгоритма – необходимый для работы алгоритма объём памяти машины.
3. Схемная сложность алгоритма – минимальный размер схемы из функциональных элементов, вычисляющей заданную (булеву) функцию .
4. Коммуникационная сложность алгоритма – минимальное число бит, которыми нужно обменяться участникам вычисления некоторой функции .
В дальнейшем будем подробно рассматривать вычисление временной сложности алгоритмов. Этот критерий является важным, но не единственным при оценке эффективности алгоритмов. Например, в силу следующих соображений
1. Эффективный по времени алгоритм может быть неэффективным по объему памяти.
2. Эффективные по времени, но сложные алгоритмы нежелательны, если готовые программы будут поддерживать лица, не участвовавшие в их написании.
3. В численных алгоритмах точность и устойчивость не менее важны, чем их временная эффективность.
4. Если программа будет использована только несколько раз, стоимость её написания превосходит стоимость времени ее выполнения. Финансово более выгоден алгоритм простой в реализации.
Переборная задача характеризуется экспоненциальным множеством вариантов, среди которых нужно найти решение, и может быть решена алгоритмом полного перебора. Переборный алгоритм имеет экспоненциальную сложность и может хорошо работать только для небольших размеров задачи. С ростом размера задачи число вариантов быстро растет, и задача становится практически неразрешимой методом перебора.
распознавательные задачи – задачи, имеющие распознавательную форму. В распознавательной форме суть задачи сводится к распознаванию некоторого свойства, а ее решение – один из двух ответов: «да» или «нет». С точки зрения математической логики задаче распознавания свойства соответствует предикат Р(х), где х – множество фактических значений входных переменных задачи.