Математическая логика и теория алгоритмов первы..


Математическая логика и теория алгоритмов (часть 2)
Тема 1 «Теория алгоритмов»
Задание 1. Написать программу, реализующую машину Тьюринга.
М=<A, Q, П>, где
М – машина Тьюринга (МТ),
А – алфавит МТ,
Q – множество состояний МТ,
П – программа МТ.
Программа представляет собой набор команд вида:
aiqj→akqmDl, где
ai – символ из воспринимаемой ячейки,
qj - состояние МТ
ak - символ, записываемый в воспринимаемую ячейку,
qm - новое состояние МТ
Dl∈{Л, П, С} - перемещение МТ влево, вправо, остановка на месте.
Программу для МТ можно задавать в виде таблицы
q1 q2 …. qna1 akqmDla2 ….. am Исходными данными для программы являются:
алфавит МТ,
множество состояний МТ,
программа, заданная в виде таблицы,
строка символов.
Строка задается с клавиатуры, алфавит, программа и множество состояний считываются из файла.
МТ должна:
Проверить правильность программы, т.е. в программе нет символов, не принадлежащих алфавиту, и нет состояний, не принадлежащих множеству состояний. Если программа обнаруживает неправильную команду, то пользователю выдается соответствующее сообщение об ошибке.
Ввести строку символов и обработать ее в соответствии с заданной программой. Строка выводится на экран после каждой выполненной команды.
В отчете необходимо представить алгоритм работы программы, код программы и тесты. В тесты включаются различные варианты исходных данных (алфавит, программа, исходная строка, результат).
Задание 2. Написать программу, реализующую нормальный алгорифм Маркова. Исходными данными для программы являются:
алфавит НАМ
схема подстановок
строка символов.
Строка задается с клавиатуры, алфавит и схема подстановок считываются из файла.
Программа, реализующая НАМ должна:
Проверить правильность схемы подстановок т.е. в схеме нет символов, не принадлежащих алфавиту. Если программа обнаруживает неправильную команду, то пользователю выдается соответствующее сообщение об ошибке.
Ввести строку символов и обработать ее в соответствии с заданной схемой подстановок. Строка выводится на экран после каждой выполненной команды. Если НАМ не применим к строке, то выдается соответствующее сообщение.
В отчете необходимо представить алгоритм работы программы, код программы и тесты. В тесты включаются различные варианты исходных данных (алфавит, схема подстановок, исходная строка, результат).
Задание 3. Написать программу, реализующую примитивно-рекурсивные функции.
Базовый набор функций представляет собой множество P = {0(x), S(x), (x1, x2, …, xm, …, xn)}, где
0(x) – нуль функция,
S(x) – функция следования,
(x1, x2, …, xm, …, xn) – функция проецирования.
Система операций
В систему операций O входят 3 операции: суперпозиции σ, примитивной рекурсии ρ и минимизации μ.
1. Операция суперпозиции σ, получая n+1 операнд – функции f0, f1, . . . , fn , производит результат f = σ (f0, f1, ... , fn). Считая все функции зависят от одного и того же набора аргументов (можно просто объединить наборы аргументов всех участвующих в операции функций в один набор и, если j-я функция ранее не зависела от i-го аргумента, то мы считаем этот аргумент несущественным для данной функции), можно задать формулу для вычисления значений вновь образованной функции f:f(x1, x2, . . . , xk) = f0 ( f1 (x1,. . . , xk), . . . , fn (x1,. . . , xk)).
Здесь k – количество переменных в объединенном наборе переменных функций с индексами от 1 до n.
Первый операнд (f0) операции суперпозиции играет отличающуюся от других операндов роль – он задает формирование сложной функции. Поэтому аргументы функции f0 не входят в перечень аргументов результата операции суперпозиции, но количество их должно быть равно n. Это требование не ограничивает применимость операции суперпозиции, так как при большем (>n) количестве аргументов функции f0 мы всегда можем расширить перечень операндов операции σ, добавив необходимое количество тождественных функций; тогда часть аргументов f0 перейдет в состав аргументов функции-результата.
Все рассматриваемые функции являются частичными, т.е. не всюду определенными; могут существовать такие комбинации значений аргументов, для которых значение функции не существует. Например, функция f(x) = x/2 определена только на подмножестве четных значений аргумента; функция f(x) = x – 3 не определена для значений аргумента, равных 0, 1, 2. В таких случаях и функция-результат f операции суперпозиции не существует для некоторых комбинаций значений аргументов. Точнее, f(a1, . . . , ak) не существует, если не существует хотя бы одно из значений f1(a1, . . . , ak), . . . , fn(a1, ..., ak) или, если эти значения существуют и равны b1, . . . , bn , то не существует значение f0(b1, . . . , bn ). Таким образом, функция f также является частичной. Подобные замечания можно сделать и в отношении следующих двух операций.
2. Операция примитивной рекурсии ρ имеет два операнда, f = ρ (g, h). Первый операнд, g, зависит от n аргументов, n >= 0, а второй операнд, h, имеет в общем случае два дополнительных аргумента, хотя в том и другом случае некоторые аргументы могут быть несущественными. Функция-результат f определяется следующими уравнениями примитивной рекурсии:

Здесь рекурсия производится по последнему аргументу функции f: ее значение при аргументе y+1 вычисляется через ее же значение при аргументе, равном y, которое, в свою очередь, вычисляется через значение функции f при аргументе, равном y–1, и так далее до значения аргумента, равного 0, при котором процесс определения через себя (возвратный процесс, процесс рекурсии) заканчивается.Можно, наоборот, процесс вычисления значения f(x1, x2, . . . , xn , y) начинать всегда с 0, получая значение в соответствии с первым уравнением (начальным условием), а затем в соответствии со вторым уравнением вычислять значения функции при аргументах, равных 1, 2, 3, . . . и так далее до достижения значения y (итерационный процесс).
Примеры:
1. Сложение неотрицательных целых чисел, Add(x, y) = x + y задается следующими уравнениями:

Здесь функция – тождественная функция, а функция h = S зависит существенным образом только от последнего своего аргумента, а именно от Add(x,y).
2. Умножение Mult(x,y) = x*y задается уравнениями

которые используют уже построенную функцию сложения чисел и известные соотношения x*0 = 0, x*(y +1) = x + x*y.
3. Возведение в степень Power(x, y) = xy. Уравнения имеют вид

4. Всюду определенное уменьшение на единицу, т.е. функция, которую можно задать следующими соотношениями (не рекурсивно):

Уравнения с использованием примитивной рекурсии и суперпозиции задают эту функцию в виде

т.е. функция g = 0, а функция h зависит только от предпоследнего аргумента (y).
Класс функций, получаемых из базовых посредством конечного числа операций двух типов – суперпозиции и примитивной рекурсии, называется классом примитивно рекурсивных функций Pпр . В этот класс, кроме приведенных выше, входят многие функции. Их общим свойством является то, что они всюду определены.
Программа должна реализовать ПРФ, рассмотренные в примерах 1-4, используя базовый набор функций и операции суперпозиции и рекурсии.
В отчете приводится код функций и тесты.

Приложенные файлы

  • docx 8958331
    Размер файла: 38 kB Загрузок: 0

Добавить комментарий