Вход

Контрольная работа по предмету «Теория алгоритмов» Вариант 3 Тишин

Рекомендуемая категория для самостоятельной подготовки:
Контрольная работа*
Код 267243
Дата создания 09 мая 2015
Страниц 10
Мы сможем обработать ваш заказ (!) 1 апреля в 12:00 [мск]
Файлы будут доступны для скачивания только после обработки заказа.
1 230руб.
КУПИТЬ

Описание

Решить задачи № 3.1.3, 3.1.4, 3.2.3, 3.3.1, 4.1.4, 4.1.5, 4.1.6. из Учебника В.В. Тишина
"Дискретная математика в примерах и задачах".

В табл.3.1.3 и везде далее наш 3-й вариант, т.е. строка под №3

Задание 3.1.3
1. Написать формулу числовой функции f(x1, x2, …, xn), вычислимой машиной Тьюринга с множеством внутренних состояний {0, 1, 2, 3, 4, 5, 6}, где 0 – заключительное, а 1 – начальные состояния, если машина задана своей программой.
2. Проверить работу машины Тьюринга с некоторым набором значений аргументов.
Решение

Задание 3.1.4
1. По данному коду N(T) восстановить программу машины Тьюринга.
2. Выяснить, является ли машина Е самоприменимой или несамоприменимой.
При составлении N(T) использована следующая кодировка:
П – 1, Л – 12, Н – 13, λ – 14, 1 – 15, * – 16, s0 – 17, ...

Содержание

Задание 3.1.3 3
Задание 3.1.4 4
Задание 3.2.3 5
Задание 3.3.1 6
Задание 4.1.4 7
Задание 4.1.5 8
Задание 4.1.6 8
Список использованных источников 10

Введение

-

Фрагмент работы для ознакомления

1А, λ*Аs1 s0Как видим, при работе над своим кодом машина Тьюринга перешла в своё заключительное состояние, значит, она является самоприменимой.Задание 3.2.31. Написать формулу для функции y=f(x1, x2, …, xn), вычисляемой нормальным алгоритмом.2. Проверить работу алгоритма над некоторым набором значений аргументов.n=21*1→**1**→****→.1111Решение1. Вначале мы имеем запись изображения набора аргументов 1x+1*1y+1. Запишем последовательность слов, получающихся при работе данного нормального алгоритма над словом 1x+1*1y+1:1x1*11y, 1x-11**1y, 1x-21**1y, …, **1y, 1y+4.fx,y=y+32. Проверим работу алгоритма над изображение набора аргументов (1, 0): 11*1, 1**, **, 1111.И над изображение набора аргументов (0, 2): 1*111, **11, 111111.Видим, что f(1, 0)=0+3=3, f(0, 2)=2+3=5, что и планировалось получить.Задание 3.3.1Найти функцию f(x, y), полученную из функций g(x) и h(x, y, z) по схеме примитивной рекурсии.g(x)=xh(x, y, z)=x+y-zРешениеНайдём несколько значений функции f:f(x,0)=g(x)=x;f(x,1)=h(x,0,f(x,0))=h(x,0,x)=x+0-x=0;f(x,2)=h(x,1,f(x,1))=h(x,1,0)=x+1-0=x+1;f(x,3)=h(x,2,f(x,2))=h(x,2,x+1)=x+2-(x+1)=1;f(x,4)=h(x,3,f(x,3))=h(x,3,1)=x+3-1=x+2;f(x,5)=h(x,4,f(x,4))=h(x,4,x+2)=x+4-(x+2)=2;f(x,6)=h(x,5,f(x,5))=h(x,5,2)=x+5-2=x+3;f(x,7)=h(x,6,f(x,6))=h(x,6,x+3)=x+6-(x+3)=3;Возникает предположение, что f(x,y)={(y+1)/2}•2•x+[y/2]. Докажем это методом математической индукции, проведя индукцию по y::1) Проверка при y=0.f(x,0)=x={(0+1)/2}•2•x+[0/2];2) Допустим, что предположение верно при y=n, то есть верна формула f(x,n)={(n+1)/2}•2•x+[n/2];3) Докажем, что предположение верно и при y=n+1, то есть докажем справедливость формулы f(x,n+1)={((n+1)+1)/2}•2•x+[(n+1)/2]f(x,n+1) = h(x,n,f(x,n)) = h(x,n,{n/2}•x+[n/2]) = x+n-({(n+1)/2}•2•x+[n/2]) = x+n-{(n+1)/2}•2•x-[n/2] = (1-{(n+1)/2}•2)•x+(n-[n/2]) = {((n+1)+1)/2}•2•x+[(n+1)/2]На основании метода математической индукции утверждаем, что предположение справедливо для всех yϵN0.Ответ: f(x,n)={(n+1)/2}•2•x+[n/2].Задание 4.1.4Предикаты P и Q определены на множестве {a,b,c}.1. Найти предикат, равносильный предикату R, но не содержащий кванторов.2. Выяснить, может ли предикат R быть выполнимым, но не тождественно истинным.zyP(y,z)xQ(x,y)Решение1. zyP(y,z)xQ(x,y) = ( yP(y,a) ˅ yP(y,b) ˅ yP(y,c) ) Q(а,y)Q(b,y)Q(c,y) = ( (P(a,a)P(b,a)P(c,a)) ˅ (P(a,b)P(b,b)P(c,b)) ˅ (P(a,c)P(b,c)P(c,c)) ) Q(а,y)Q(b,y)Q(c,y)2. Пусть P(y,z) – тождественно истинный предикат. Тогда высказывание (P(a,a)P(b,a)P(c,a)) ˅ (P(a,b)P(b,b)P(c,b)) ˅ (P(a,c)P(b,c)P(c,c)) истинно, а выражение zyP(y,z)xQ(x,y) равносильно выражению Q(а,y)Q(b,y)Q(c,y).Если положить Q(a,a)=Q(b,a)=Q(c,a)=1, Q(a,b)=0, то R(a)=1111=1; R(b)=10…=0.Итак, предикат R(y) может быть выполнимым, но не тождественно истинным.Задание 4.1.51. Представить в приведённой форме предикат D варианта №.(xyT(x,y)→R(x,z))|xP(x,y)2. Представить в предварённой нормальной форме предикат D варианта №+1.(xyP(y,z,t)|R(x,y,z))yT(x,y,t)Решение1.

Список литературы

1. Аляев Ю.А. Тюрин С.Ф. Дискретная математика и математическая логика. – М.: Финансы и статистика, 2006. – 368 с.
2. Гуц А.К. Математическая лоrика и теория алrоритмов. – Омск: Издательство Наследие. Диалог-Сибирь, 2003. – 108 с.
3. Иванов Е.А. «Логика: Учебник для юридических вузов». – М.: Бек, 1996.
4. Марков А. А., Нагорный Н. М. Теория алгорифмов, изд. 2. – М.: ФАЗИС, 1996.
5. Марков А. А. Элементы математической логики. – М.: Изд-во МГУ, 1984.
6. Светлов В.А. Логика: Учебник. – М.: Логос, 2012.
7. Свободная онлайн-энциклопедия Википедия [Электронный ресурс]. – Режим доступа: http://ru.wikipedia.org/
8. Судоплатов С.В., Овчинникова Б.В. Математическая логика и теория алгоритмов: Учебник – М.: ИНФРА-М; Новосибирск: Изд-во НГТУ, 2004. – 224 с. – (Высшее образование).
9. В.А. Успенский, А.Л. Семёнов Теория алгоритмов: основные открытия и приложения – М., Наука, 1987, 288 c.
Очень похожие работы
Пожалуйста, внимательно изучайте содержание и фрагменты работы. Деньги за приобретённые готовые работы по причине несоответствия данной работы вашим требованиям или её уникальности не возвращаются.
* Категория работы носит оценочный характер в соответствии с качественными и количественными параметрами предоставляемого материала. Данный материал ни целиком, ни любая из его частей не является готовым научным трудом, выпускной квалификационной работой, научным докладом или иной работой, предусмотренной государственной системой научной аттестации или необходимой для прохождения промежуточной или итоговой аттестации. Данный материал представляет собой субъективный результат обработки, структурирования и форматирования собранной его автором информации и предназначен, прежде всего, для использования в качестве источника для самостоятельной подготовки работы указанной тематики.
bmt: 0.00485
© Рефератбанк, 2002 - 2024