sutkova-mlta
.pdfМинистерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Алтайский государственный технический
университет им. И.И.Ползунова»
Сучкова Л.И.
Учебно-методическое пособие по выполнению лабораторных работ
по дисциплине
«Математическая логика и теория алгоритмов»
Барнаул – 2012
УДК 004.42
Сучкова, Л.И. Учебно-методическое пособие по выполнению лабораторных работ по дисциплине «Математическая логика и теория алгоритмов» / Л.И. Сучкова; АлтГТУ им. И.И. Ползунова. – Барнаул, Изд-во АлтГТУ, 2012. - 40 c.
В учебно-методическом пособии изложены основные требования к выполнению и оформлению отчетов по лабораторным работам по дисциплине «Математическая логика и теория алгоритмов». Пособие предназначено для студентов, обучающихся по направлениям 230100 «Информатика и вычислительная техника» и 090900 «Информационная безопасность».
Методические указания рассмотрены на заседании кафедры «Вычислительных систем и информационной безопасности», протокол № 5 от 22.12.2011 г.
Рецензент: А.Г. Якунин, д.т.н., профессор, зав. кафедрой вычислительных систем и информационной безопасности АлтГТУ
2
Содержание
1Общие положения…………………………………………… 4
1.1Цели и задачи выполнения лабораторных работ………. 4
1.2Тематика и организация выполнения лабораторных работ…………………………………………………………… 4 2 Лабораторный практикум………………………………….. 6
2.1Лабораторная работа № 1………………………………... 6
2.2Лабораторная работа № 2………………………………... 9
2.3Лабораторная работа № 3……………………………….. 17
2.4Лабораторная работа № 4……………………………….. 30
2.5 Лабораторная работа № 5………..……………………… |
31 |
2.6 Лабораторная работа № 6……..………………………… |
35 |
Список литературы………………………………………….. |
38 |
3
1 Общие положения
1.1 Цели и задачи выполнения лабораторных работ
Лабораторный практикум по дисциплине «Математическая логика и теория алгоритмов» служит для практического закрепления теоретических навыков, полученных в ходе изучения лекционного материала и материала практических занятий и формирования необходимых компетенций.
Цели выполнения лабораторных работ:
-закрепление теоретических знаний по дисциплине и применение этих знаний при решении поставленных задач (доказательство принадлежности функции классу, построение машины Тьюринга и алгоритма Маркова, разработка эффективной функции и написание программы, выполнение логического вывода, доказательство эквивалентности высказываний);
-развитие навыков выполнения самостоятельной работы,
атакже ее оформления и представления результатов проделанной работы.
1.2 Тематика и организация выполнения лабораторных работ
Для посещения лабораторных занятий студенческая группа делится на подгруппы, посещающие занятия в отведенные для них часы. Это позволяет использовать индивидуальный подход к обучению, отвечать на возникшие вопросы и способствует лучшему усвоению материала.
На каждую лабораторную работу выдается общее задание, соответствующее изучаемому теоретическому материалу, и индивидуальный вариант задания. Задания выдаются по мере изучения материала и для лабораторных 1-5 предполагают разработку алгоритма и создание программного продукта. Лабораторная работа № 6 предполагает выполнение
4
доказательства эквивалентности формул исчисления высказываний и предикатов. Студент должен в соответствии с темой выполнить задание и оформить отчет о проделанной работе .
Для каждой лабораторной работы предусмотрены сроки ее выполнения и защиты. Каждая работа оценивается по стобалльной шкале. В случае выполнения и/или защиты работы после установленного срока, оценка может быть снижена.
Для каждой лабораторной работы необходимо:
-продемонстрировать работу программного продукта или модели алгоритма на тестере,
-представить доказательство или расчеты, если это требуется по заданию;
-представить отчет о выполнении лабораторной работы,
-пройти устную (ответы на вопросы преподавателя) и/или письменную защиту.
По всем темам лабораторных работ студент может выполнять задания, различающиеся по уровню сложности. Уровень сложности выполняемых заданий влияет на рейтинг защиты работы. При выполнении студентом по лабораторной работе задания с низким уровнем сложности максимальный рейтинг защиты не может превышать 40 баллов.
5
2 Лабораторный практикум
2.1 Лабораторная работа № 1
Тема: Доказательство примитивной рекурсивности функции. Написание программы вычисления значения функции в заданной точке, соответствующей доказательству.
Цели и задачи работы: изучение способов доказательства примитивной рекурсивности, разработка простейшей рекурсивной программы.
Теоретические сведения о работе и пример программы приведены в конспекте лекций, литературе [1-3].
Описание используемых средств для выполнения работы : операционная система Windows ХР/7, Visual Studio 2008-2010.
Методика выполнения работы:
1.Изучить способы доказательства примитивной рекурсивности функций.
2.Доказать примитивную рекурсивность функции с использованием оператора суперпозиции и примитивной рекурсии (задание 1).
3.Написать рекурсивную и нерекурсивную программу вычисления значения функции f, полученной оператором примитивной рекурсии R над функциями g и h (задание 2).
4.Отладить и протестировать программы.
5.Продемонстрировать преподавателю работу программ.
Требования к отчету:
Отчет по лабораторной должен содержать титульный лист, доказательства примитивной рекурсивности и тексты рекурсивной и нерекурсивной программ.
Защита лабораторной, помимо теоретических вопросов, включает выполнение практического задания по доказательству примитивной рекурсивности функции, предложенной преподавателем.
6
Индивидуальные задания:
А. Задания с обычным уровнем сложности
№ 1. |
|
|
|
|
|
№ 11. |
|
|
|
|
|
||
|
|
y |
|
|
|
|
1) |
|
|
|
Nx+ y+1 |
||
1) |
∏(xi |
+ i) |
|
|
a |
x+1x+2 |
|
|
|||||
|
i=0 |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|||
2) |
g(x) = x+1 |
|
2) g(x) = x+2 |
|
|
|
|||||||
|
h (x, y, t) = xt+y. |
|
|
h(x, y, t) = t+xy+1. |
|
|
|||||||
№ 2. |
|
|
Nx |
|
№ 12. |
|
|
|
N2y |
||||
1) |
|
xx |
|
|
|
1) |
min(x2 |
+ y,2y |
|
) |
|||
Количество |
повторений |
X |
|
|
|
|
|
|
|
||||
равно Y+1. |
|
|
2) g(x) = x+2 |
|
|
|
|||||||
2) |
g (x, y, z) = (x+z)y |
|
|
h(x, y, t) = (t+1)(x+y) |
|
||||||||
|
h (x, y, z, t, v) = (v+z)(x+2yt) |
|
|
|
|
|
|
|
|||||
№ 3. |
xxx+1Nx+ y |
|
№ 13. |
|
|
|
|
|
|||||
1) |
|
|
1) |
(x +1)23Nx+2 |
|
||||||||
2) g(x, y) = x+y 1 |
|
2) g(x, y) = x+y |
|
|
|||||||||
h(x, y, z, t) = (t+x)(x+y) |
|
|
h(x, y, z, t) = tx+yz |
|
|
||||||||
№ 4. |
|
|
|
|
|
№ 14. |
|
(z+y!+1)N(z |
+y!+x) |
||||
1) |
|
|
Nx+3 |
|
1) |
|
|
||||||
|
2 |
34 |
|
|
|
(x!+y)(z+y!) |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2) g(x, y, z) = (2x+y)z |
|
2) g(x, y, z) = x+2y+z |
|
|
|||||||||
h(x, y, z, t, v) = vz(x+y) |
|
|
h(x, y, z, t, v) = vx+yt |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||
№ 5. |
|
|
|
|
|
№ 15. |
|
|
|
N(x+t) |
|||
1) |
|
|
|
|
|
|
1) |
+ t + a)(x+t+a−1) |
|||||
y |
i |
|
+ j) |
|
|
(x |
|
|
|||||
∑ |
∏(2 |
|
|
|
|
|
|
|
|
|
|||
i=0 j=0 |
|
|
|
|
|
2) g(x, y) = y!+x! |
|
|
|||||
2) g(x, y) = 2x |
|
|
|
||||||||||
|
|
h(x, y, t, v) = v+2x+y t |
|
||||||||||
h(x, y, z, t) = 2t(x+y) |
|
|
|
||||||||||
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
№ 6. |
|
|
№ 16. |
|
|
|
||
1) |
N2 |
|
+ xy+4 |
1) |
|
(x+ y)!+1N |
(x+ y)!+z! |
|
|
xx+1 |
|
|
|
|
|||
|
|
|
|
(x + y)! |
|
|||
2) g(x) = x 2 |
|
2) g(x,y,z)=x+z+2 |
|
|||||
|
h(x, y, t) = xy+2t |
h(x,y,z,t,v)=(v+1)(t+xy) |
||||||
№ 7. |
|
|
№ 17. |
|
|
|
||
1) |
|
|
|
1) |
|
x |
|
|
y |
|
|
xx y |
+ ∑yi+1 |
||||
∑x2i + max(x +1, y) |
|
|
i=0 |
|
||||
i=0 |
|
|
2) g(x,y)=2x+3y |
|
||||
2) g(x, y) = y+1 |
|
|||||||
h(x,y,z,t)=(t+z+1)(x+y) |
||||||||
|
h(x, y, z, t) = tx |
|||||||
|
|
|
|
|
||||
№ 8. |
x+1Nx+1 |
№ 18. |
|
Nx!+ max(x, y) |
||||
|
(x +1) |
1) |
|
|||||
1) |
|
|
x! |
x!+1 |
|
|||
|
|
|
|
|
|
|||
Количество повторений - Y+1. |
|
|
|
|
||||
2) g(x) = 2x+1 |
|
2) g(x,y)=xy |
|
|||||
|
h(x, y, t) = (t+1)(x+y) |
h(x,y,z,t)=2t+x+3yz |
||||||
№ 9. |
|
N3 |
№ 19. |
|
|
|
||
1) |
|
|
1) 2x +1 |
|
||||
|
(x + 3)x+2x+1 |
∑ |
(xi + ix ) |
|
||||
|
|
|
|
i=0 |
|
|
||
2) |
g(x) = 2x |
|
|
2) g(x)=x!+1 |
|
|||
|
h(x, y, t) = t+2xy |
h(x,y,z)=x min(z+y,x) |
||||||
№ 10. |
|
|
№ 20. |
|
|
|
||
1) |
|
|
|
1) |
|
N2y+3 |
|
|
y |
|
|
|
x |
y+1 |
|
||
∏(xi + i) |
|
|
|
|
|
|||
i=0 |
|
|
2) g(x,y,z)=2x+3y+z |
|
||||
2) g(x, y t) = x+t+2 |
h(x,y,z,t,v)=x+2y+z+t+2v |
|||||||
|
h (x, y, z, t, v) = (v+2x)(t+xy) |
|||||||
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
|
|
|
|
Б. Задания с низким уровнем сложности
№ 21. |
№ 26. y |
+i |
||
1) 2x+y |
1) |
∑2x |
||
|
|
|
i=0 |
|
2) g (x, y, z) = x+y+z |
2) g(x) = 3x |
|
||
|
h(x, y, z, t,v) = (v+1)(x+z) |
|
h(x, y, t) = (2x+3t)y |
|
№ 22. |
№ 27. |
|
||
1) max{x,y}+1 |
1) ( x+y)! |
|
||
2) g(x, y) = x+y |
2) g(x, y, z) = x+z+2 |
|||
|
h (x, y, z, t) = tx |
|
h(x, y, z, t, v) = (v+1)(t+xy) |
|
№ 23. |
№ 28. |
|
||
1) min{x,y} |
1) min(2x+1, y) |
|||
2) g(x) = 2x |
2) g(x) = 3x+1 |
|||
|
h (x, y, t) = t+x |
|
h(x, y, t) = (3xy+t)(t+1) |
|
№ 24. |
№ 29. |
|
||
|
y |
|
x |
y |
1) |
∑ xi |
1) max {y , x } |
||
|
i=0 |
2) g(x, t) = xt+1 |
||
|
|
|||
2) g(x, y, z) = (x+y)z |
|
h (x, y, t, z) = (zx+yt)x |
||
|
h (x, y, z, t, v) = (v+x)(y+z) |
|
|
|
№ 25. |
№ 30. |
|
||
1) xxy; |
1) |
y+1 |
|
|
2) g(x, y) = 2x+3y |
|
∑ x2i |
|
|
|
h(x, y, z, t) = (t+1)(x+y) |
|
i=0 |
|
|
|
|
|
|
|
|
2) g(x, y) = y+x |
||
|
|
|
h (x, y, z, t) = t(x+y) |
|
2.2 Лабораторная работа № 2
Тема: Ограниченный оператор минимизации. Доказательство ПРФ и ЧРФ.
Цели и задачи работы: изучение способов доказательства примитивной рекурсивности с использованием теорем о сумме(произведении) ПРФ и ограниченного оператора
9
минимизации, изучение доказательства ЧРФ, разработка программы, реализующей вычисление функции, ПР которой доказана с применением ограниченного -оператора.
Теоретические сведения о работе приведены в конспекте лекций, литературе [1-3].
Описание используемых средств для выполнения работы : операционная система Windows ХР/7, Visual Studio 2008-2010.
Методика выполнения работы:
1.Изучить ограниченный оператор минимизации, доказательство частичной рекурсивности функций.
2.Доказать примитивную рекурсивность функции с использованием либо ограниченного оператора минимизации, либо теорем о сумме (произведении) ПРФ. (задания 1,2).
3.Доказать ЧРФ (задание 3).
4.Написать программу вычисления значения функции, ПР которой доказана с использованием ограниченного оператора минимизации.
5.Отладить и протестировать программу.
6.Продемонстрировать преподавателю работу программ. Требования к отчету:
Отчет по лабораторной должен содержать титульный
лист, доказательства примитивной и частичной рекурсивности функций и текст программы.
Защита лабораторной, помимо теоретических вопросов, включает выполнение практического задания по доказательству примитивной или частичной рекурсивности функции, предложенной преподавателем.
Индивидуальные задания:
А. Задания с обычным уровнем сложности
№ 1.
1) Простое число с номером x.
10