Математическая логика и теория алгоритмов презентация

Математическая логика и теория алгоритмов
На этой лекции:
Понятие алгоритма
Нормальные алгоритмы Маркова
Вычислимые функции

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

Понятие алгоритма
Способы задания
Графический
Табличный
Перечислением правил
Замечание:
Различные способы задания алгоритмов могут быть (а могут и не быть) эквивалентными.
переход

Понятие алгоритма
Неформальный алгоритм
Нет четко заданного определения, невозможно записать математически строго.
Формальный алгоритм
Математически четко заданный алгоритм
Требуется математическая формальная модель описания алгоритмов.
Модель описания понятия алгоритма.

Понятие алгоритма
Формальные способы описания понятия алгоритма:
Нормальный алгоритм Маркова (Марков А.А. в 1947г.)
Машина Тьюринга
Машина Поста
Автоматное программирование
Рекурсивная функция (теория вычислимости)

Нормальный алгоритм Маркова
Это скучный слайд с терминологией
Нормальный алгоритм Маркова задаётся своим алфавитом и своей схемой.
Алфавит представляет собой непустое множество символов, включающее символ пустого слова. Любое непустое слово алфавита составлено из символов алфавита.
Пример:
Алфавит:
Слова:
Схема алгоритма задаётся конечным упорядоченным (это важно) набором формул подстановок.
Подстановки:
Входными данными алгоритма может являться произвольная строка символов над указанным алфавитом.
Формализованная модель алгоритма
Пустое слово
Набор команд

Нормальный алгоритм Маркова
Это скучный слайд с терминологией
Алгоритмический процесс заключается в многократном применении операции подстановки к строке входных данных.
Структура операции подстановки:
Останов процесса:
Набор команд
данные

Пример 1
Алфавит:
Строка данных:
Система подстановок:
Алгоритмический процесс:
Выходная строка данных:
данные
Набор команд
результат

Пример 2
Алфавит:
Строка данных:
Система подстановок:
Алгоритмический процесс:
Вывод: алгоритм неприменим

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

Увеличение числа на единицу
Алфавит:
Система подстановок:
Разделитель разрядов (визуализация переполнения), где
Слева – разряды, которые надо увеличит
Справа –уже увеличенные разряды
Добрались до пустого разряда, в который происходит перенос

Увеличение числа на единицу
Алфавит:
Система подстановок:
Разделитель разрядов (визуализация переполнения), где
Слева – разряды, которые надо увеличит
Справа –уже увеличенные разряды
Добрались до пустого разряда, в который происходит перенос

Логическое сложение двух бинарных чисел
Алфавит:
Система подстановок:
Логическое сложение = ИЛИ (OR) (V)
A or B, A OR B, A ИЛИ B, А или В, A V B, A v B

Вычислимые функции

Вычислимая функция
Это скучный слайд с терминологией
Функция f называется вычислимой, если существует алгоритм, перерабатывающий всякий объект x, для которого определена функция f, в объект f(x), и не применимый ни к какому x, для которого функция f не определена.
Пример:
Функция f(x)=x+1 согласно представленному определению, является вычислимой, т.к. нам удалось построить нормальный алгоритм Маркова увеличения числа на 1.

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

Вычислимая функция
Это скучный слайд с терминологией
Функцию f:X→Y будем называть частичной, если она определена не для всех значений x∈X. Множество тех x∈X, для которых однозначно определяется значение функции f, будем называть областью определения функции f.
Будем называть далее простейшими функции:
Пример 2 – алгоритма Маркова (слайд-11) – когда алгоритм не применим к некоторым последовательностям входных данных

Вычислимая функция
Это скучный слайд с терминологией
Замечание:
Рекурсия является удобным способом вычисления значений функций.
Замечание:
Рекурсивные функции являются вычислимыми по определению. Есть основания полагать, что верно и обратное.

Примитивно рекурсивная функция
Это скучный слайд с терминологией
Пусть даны частичные функции g и h. Частичная функция f получена из функций g и h примитивной рекурсией, если:
Замечание:
Для n=0 указанные уравнения принимают вид:
Номер шага 0,1,2,3,4 …
Доказательство по индукции
Арифметическая прогрессия
Функция вычисления факториала

Примитивно рекурсивная функция
Это скучный слайд с терминологией
Частичная функция f называется примитивно рекурсивной относительно множества частичных функций Ω, если f получается из функций множества Ω и простейших функций конечным числом операций подстановки и примитивной рекурсии.
Если Ω = Ø, то функция f получается только из простейших функций и её называют просто примитивно рекурсивной.

Примитивно рекурсивная функция
Пример:
- примитивно рекурсивная функция
Пример:
- примитивно рекурсивная функция

Частично рекурсивная функция
Это скучный слайд с терминологией
Пусть дана частичная функция f. Операцией минимизации назовём функцию M:
Частичная функция f называется частично рекурсивной относительно множества частичных функций Ω, если f получается из функций множества Ω и простейших функций конечным числом операций подстановки, примитивной рекурсии и минимизации.
Пример:
- частично рекурсивная функция

Вычислимая функция
Это скучный слайд с терминологией
рекурсивные функции:
1) Множество частично рекурсивных функции
Множество вычислимых функций
Множество частично рекурсивных функции («рекурсивные функции, определенные на части множества возможных аргументов»)
Множество общерекурсивных функций («рекурсивные функции, определенные на всём множестве возможных аргументов»)
Общерекурсивные функции — это подмножество частично рекурсивных функций, определённых для всех значений аргументов
Доказал Гёдель
3) Множество общерекурсивных функций
2) Множество примитивно рекурсивных функции
? Функция Аккермана – вычислимая, но не примитивно-рекурсивная

Тезис Чёрча
Это скучный слайд с терминологией
Класс алгоритмически вычислимых частичных функций совпадает с классом всех частично рекурсивных функций.
Замечание:
Доказать или опровергнуть тезис Чёрча нельзя, потому как он представляет утверждение относительно понятия алгоритмически вычислимой функции, которое не является строгим.

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