sutkova-mlta

программа markov или другой тестер для проверки правильности работы алгоритма Маркова.

Методика выполнения работы:

1)Изучить представление данных и применение к ним последовательности правил алгоритма Маркова.

2)Доказать вычислимость функции по Маркову (задание 2 из лабораторной № 3).

3)Протестировать алгоритм Маркова на всевозможных значениях аргументов функции.

4)Продемонстрировать преподавателю работу алгоритма Маркова.

Требования к отчету:

Отчет по лабораторной должен содержать титульный лист, последовательность правил алгоритма Маркова.

Защита лабораторной, помимо теоретических вопросов, включает выполнение практического задания по построению алгоритма Маркова, предложенного преподавателем.

2.5 Лабораторная работа № 5

Тема: Рекурсивные функции. Оценка сложности алгоритмов.

Цели и задачи работы: изучение рекурсивного программирования, методов разработки эффективных алгоритмов, методики оценки порядка сложности алгоритма.

Теоретические сведения о работе приведены в конспекте лекций, литературе [1-3].

Описание используемых средств для выполнения работы : операционная система Windows ХР/7, Visual Studio 2008-2010.

Методика выполнения работы:

1)Изучить технологию использования стека при рекурсивном программировании.

2)Написать рекурсивную программу решения поставленной задачи.

3)Протестировать программу.

31

4) Оценить порядок временной сложности разработанного рекурсивного алгоритма.

Требования к отчету:

Отчет по лабораторной должен содержать титульный лист, задание, текст программы, тесты, расчет временной сложности.

Защита лабораторной включает теоретические вопросы.

Индивидуальные задания:

1.Дано число m. Требуется в последовательности цифр 1 2 3 4 … 9 расставить знаки «+» и «-« так, чтобы значением получившегося выражения было число m. Например, m=122. Знаки расставляются как 12+34-5-6+78+9.

2.В аудитории стоят M компьютеров, на жестком диске каждого из которых имеется некоторое известное количество свободной памяти. Можно ли инсталлировать на них заданное число N программных систем, если каждая система требует для размещения не менее S[j] (j=1,…,N) памяти.

3.Имеются N двузначных чисел. Можно ли их соединить знаками сложения и умножения, чтобы получить заданное число S?

4.На веревке висят прямоугольные скатерти и салфетки так, что они занимают всю веревку. Один предмет был украден. Можно ли перевесить оставшиеся предметы так, чтобы веревка снова стала занятой полностью? Длина веревки, количество предметов и размеры каждого предмета известны.

5.Имеется N контейнеров высоты H. Задано множество предметов, каждый из которых имеет свою высоту. Можно ли разместить предметы в этих контейнерах так, чтобы груз не выступал над контейнером?

6.Для заданного набора слов требуется построить линейный кроссворд. Если окончание одного слова совпадает с началом следующего более чем в одной букве (например, ЛОГИКА-КАСКАД), то такие слова можно объединить в цепочку. Нужно получить любую такую цепочку.

32

7.Для заданного набора слов требуется построить линейный кроссворд минимальной длины. Если окончание одного слова совпадает с началом следующего более чем в одной букве (например, ЛОГИКА-КАСКАД), то такие слова можно объединить в цепочку, представляющую собой линейный кроссворд.

8.Построить цепочку из имеющегося набора костей

домино.

9.Разместить на шахматной доске максимальное количество коней так, чтобы они не находились друг у друга «под боем».

10.Задан набор слов. Построить из них любую цепочку таким образом, чтобы символ в начале следующего совпадал с одним из символов в середине предыдущего (не первым и не последним).

11.Задан массив целых чисел. Построить из них любую последовательность таким образом, чтобы последняя цифра предыдущего числа совпадала с первой цифрой следующего.

12.Задача раскраски карты. Страны на карте заданы матрицей смежности. Если страны i,j имеют на карте общую границу, то элемент матрицы A[i,j] равен 1, иначе 0. Смежные страны не должны иметь одинакового цвета. «Раскрасить» карту минимальным количеством цветов.

13.Задача проведения границы на карте («создание военных блоков»). Страны на карте заданы матрицей смежности. Если страны i,j имеют на карте общую границу, то элемент матрицы A[i,j] равен 1, иначе 0. Необходимо разбить страны на две группы так, чтобы количество пар смежных стран из противоположных групп было минимальным.

14.В последовательности символов могут встречаться только цифры и знаки "+", при этом последовательность представляет собой формулу сложения однозначных чисел. Напишите рекурсивную функцию, определяющую значение формулы.

15.Напишите рекурсивную программу для формирования разметки линейки. При нанесении делений на линейку на ней

33

должна быть метка в точке ½ длины шкалы, метка немного покороче через каждые ¼ длины, еще более короткая через 1/8 длины и так далее. Количество разбиений – степень двойки - задается.

16.Имеется N домов и K красок. Проверить, можно ли покрасить дома имеющимся набором красок, чтобы цвет повторялся не раньше, чем через 2 дома.

17.В группе из N студентов каждый студент назвал трех человек, с которыми хотел бы делать лабораторную в паре. Составить пары из группы, если это возможно.

18.Требуется найти минимальный путь обхода всего множества городов, не посещая один и тот же город дважды (задача коммивояжера).

19.Имеется M типов материалов и K типов клеев, каждый из которых пригоден для склеивания нескольких типов материалов. Требуется попарно склеить P (P<=M) известных типов материалов. Найти минимальное число клеев, которые потребуются для этого.

20.Напишите рекурсивную функцию, проверяющую правильность расстановки скобок в строке. При правильной расстановке выполняются условия:

(а)количество открывающих и закрывающих скобок

равно.

(б)внутри любой пары открывающая – соответствующая закрывающая скобка, скобки расставлены правильно.

Примеры неправильной расстановки: )(, ())(, ())(() и т.п.

21.В строке могут присутствовать скобки как круглые, так и квадратные скобки. Каждой открывающей скобке соответствует закрывающая того же типа (круглой – круглая, квадратнойквадратная). Напишите рекурсивную функцию, проверяющую правильность расстановки скобок в этом случае. Пример неправильной расстановки: ( [ ) ].

22.Число правильных скобочных структур длины 6 равно

5:()()(), (())(), ()(()), ((())), (()()). Напишите рекурсивную программу генерации всех правильных скобочных структур

34

длины 2n. Указание: правильная скобочная структура минимальной длины «()». Структуры большей длины получаются из структур меньшей длины, двумя способами:

(а) если меньшую структуру взять в скобки,

(б) если две меньших структуры записать последовательно.

23.Создайте процедуру, печатающую все возможные перестановки для целых чисел от 1 до N.

24.Создайте процедуру, печатающую все подмножества множества {1, 2, …, N}.

25.Создайте процедуру, печатающую все возможные представления натурального числа N в виде суммы других натуральных чисел.

2.6 Лабораторная работа № 6.

Тема: Преобразования формул логики высказываний и предикатов.

Цели и задачи работы: изучение конструирования формул алгебры высказываний и предикатов, тавтологий, способов равносильных преобразований и вывода.

Теоретические сведения о работе приведены в конспекте лекций, литературе [1-7].

Описание используемых средств для выполнения работы : листы бумаги, пишущий инструмент.

Методика выполнения работы:

1)Изучить способы равносильного преобразования формул высказываний и предикатов, логический вывод.

2)Выполнить индивидуальные задания (по 1 из каждого

пункта).

Требования к отчету:

Отчет по лабораторной должен содержать титульный лист, задания, последовательность преобразований или логический вывод с пояснениями.

Защита лабораторной включает теоретические вопросы.

35

Индивидуальные задания:

1. Пусть A обозначает высказывание “Я увлекаюсь теннисом”, а B обозначает высказывание “Я изучаю

2)¬A→ A. 7) (A A)→ A.

3)A ¬A. 8) (A A)→ A.

4)A ¬A. 9) (A A)→(A A).

5)A↔¬A. 10) ¬(A↔¬A) .

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

1)(A→ B)→((A C)→(B C)).

2)((A→ B) (B→C))→(A→C).

3)((A B)↔ B)↔(B→ A).

4)(A→ B)↔(¬B→¬A).

5)((A→ B)→ A)→ A.

6)¬A→(A→ B) .

7)(¬A→ B) ¬(A B).

8)(A→ B)→(¬B→¬A).

9)(A→C)→((B→C)→(A B→C)).

10)(A→ B)→((A C)→(B C)).

4. Доказать, что первая формула логически влечет вторую формулу.

1)¬(A B); ¬(A B).

2)A; B→ A.

3)(A→ B)(B→C); A→C .

4)A→ B; (A C)→(B C).

36

5)A→C ; (B→C)→(A B→C).

6)A; ¬¬A.

7)¬A; A→ B.

8)A→ B; (A C)→(B C).

9)A→ B; ¬B→¬A.

10)A→(B→C); (A→ B)→(A→C).

5. Построить вывод формулы.

1)(A→ B)→((A→(B→C))→(A→C)).

2)(A→ B)→((B→C)→(A→C)) .

3)(A→B)→((B→C)→((C →D)→ (A→ D))) .

4)¬A→(A→ B) .

5)¬¬A→ A.

6)A→¬¬A.

7)(A→¬¬B)→(A→ B).

8)(¬¬ A→ B)→(A→ B).

9)(A→B)→(¬B→¬A).

10)A→(¬B→¬(A→ B)) .

11)(A→ B)→((¬B→ A)→ B).

12)((A→B)→ A)→ A.

6. Записать инверсию формулы в предваренной нормальной форме.

1)x¬A(x).

2)x(A(x)¬B(x)).

3)x¬A(x) .

4)x(A(x)→ yB( y)).

5)x(A(x)B(x)C(x)).

6)x(A(x)→ B(x)).

7)x(A(x)↔ B(x)).

8)x(A(x) yB( y)).

9)x(A(x)→ B(x)) x(C(x) ¬D(x)).

10)x y z(A(x, y, z)→ B(x, y, z)).

37

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

1 Игошин, В. И. Математическая логика и теория алгоритмов: учеб. пособие /В. И. Игошин.-М.: Академия, 2008. – 448 с. - 25 экз.

2 Крючкова, Е.Н. Математическая логика и теория алгоритмов: учебное пособие / Е.Н. Крючкова. – Барнаул, изд-во АлтГТУ, 2010. - Режим доступа: http//elib.alstu.ru, свободный

3 Судоплатов, С.В. Математическая логика и теория алгоритмов: учебник /С. В. Судоплатов, Е. В. Овчинникова.- Новосибирск: НГТУ, 2010.- 255 с. - 2 экз.

4 Соболева, Т.С. Дискретная математика: [учеб. для вузов по специальностям "Информатика и вычисл. техника", "Информ. системы", "Информ. безопасность"] /Т. С. Соболева, А. В. Чечкин ; под ред. А. В. Чечкина.-М.: Академия, 2006. - 254 с. – 11 экз.

5 Лавров, И.А. Математическая логика : [учеб. пособие для вузов по техн. и естеств.-науч. специальностям] / И. А. Лавров ; под ред. Л. Л. Максимовой. - М. : Академия, 2006. – 239 с. – 11 экз.

6 Успенский В.А. Вводный курс математической логики: [учеб. пособие] /В. А. Успенский , Н. К. Верещагин, В. Е. Плиско.-М.: ФИЗМАТЛИТ, 2007125 с. – 3 экз.

7 Мендельсон Эллиот. Введение в математическую логику: переводное издание /Э. Мендельсон; пер. с англ. Ф. А. Кабакова .-М.: Наука, 1984. - 319 с. – 14 экз.

38

Лариса Иннокентьевна Сучкова

Учебно-методическое пособие по выполнению лабораторных работ по

дисциплине

«Математическая логика и теория алгоритмов»

Издано в авторской редакции

Подписано в печать 10.01.2012. Формат 60х84 1/16. Печать – цифровая. Усл.п.л. 2,32.

Тираж 55 экз. Заказ 2012 -

Отпечатано в типографии АлтГТУ, 656038, г. Барнаул, пр-т Ленина, 46 тел.: (8–3852) 36–84–61

Лицензия на полиграфическую деятельность ПЛД №28–35 от 15.07.97 г.

39