ПРАКТИЧЕСКИЙ РАЗДЕЛ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНЫХ РАБОТ

Контрольные работы и индивидуальные практические задания выполняются на базе представленного лекционного курса. Если задание не понятно, то следует отправить электронный запрос на почтовый ящик преподавателя. По всем практическим занятиям и контрольным работам содержится девять вариантов. Ваш вариант определяется так. Номер Вашей зачетки делите на 9 и берете целочисленный остаток, к которому добавляете 1. Пример. Пусть номер зачетки 542402-16. Берете число 54240216 и делите на 9. Получаете в остатке 6. Номер Варианта= 6+1=7.

Задание состоит из п.п. А, Б. Сначала прочитайте все внимательно.

Отчет по работе оформлять так – написать теоретическое введение, а затем представить задание и его решение.

КОНТРОЛЬНАЯ РАБОТА 1. Реализовать машину Тьюринга согласно варианту.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КР №1

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

УКАЗАНИЯ ПО ВЫБОРУ ВАРИАНТА

Ваш вариант определяется так. Номер Вашей зачетки делите на 9 и берете целочисленный остаток, к которому добавляете 1. Пример. Пусть номер зачетки 542402-16. Берете число 54240216 и делите на 9. Получаете в остатке 6. Номер Варианта= 6+1=7.

Задание состоит из п.п. А, Б. Сначала прочитайте все внимательно.

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

ВАРИАНТЫ ЗАДАНИЙ

1. На вход поступает последовательность из 0 и 1. Машина должна записать ее в обратном порядке. Пример 0001110 заменяется на 0111000.

2. На вход поступает последовательность из 0 и 1. Машина должна заменить каждый второй 0 на 1. Пример. 000111 заменяется на 010111.

3. На вход поступает последовательность из 0 и 1. Машина должна выдать 0 если число 0-ей больше и 1 – в противном случае. Пример. 000011. Машина выдает 0.

4. На вход поступает последовательность из 0 и 1. Машина должна выдать 1, если не встречается комбинация 011 в данной последовательности и 0 – в противном случае. Пример 0001001. Машина выдает 1.

5. На вход поступает последовательность из 0 и 1. Машина должна заменить каждые два подряд идущих нуля одной единицей. Пример 00010100 заменяется на 101011.

6. На вход поступает последовательность из 0 и 1. Машина должна выдать 1, если число пар 01 четное, и 0 – если нечетное. Пример 001001 выдаем 1.

7. На вход поступает последовательность из 0 и 1. Машина должна поменять местами соседние элементы по парам. Пример. 0100101001 заменяется на 1000010110.

8. На вход поступает последовательность из 0 и 1. Машина должна заменить каждую единицу на 01. Пример. 00110010 заменяется на 00010100010.

9. На вход поступает последовательность из 0 и 1. Машина должна дописать к ней слева единицу. Пример. 011001 заменяется на 1011001 (слева появилась 1).

Б. Для демонстрации правильности работы Вашей машины Тьюринга написать программу на Паскале или С, которая работает по правилам Вашей машины Тьюринга, чтобы можно было убедиться в правильности Вашей машины. Текст программы приложить к отчету.

КОНТРОЛЬНАЯ РАБОТА 2. Решить задачу ВЫПОЛНИМОСТЬ по варианту.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КР №2

Контрольное задание состоит в решении системы логических уравнений. Описание решения дать в развернутом виде. Задание состоит из п.п. А, Б. Пункт А определяет, каким методом решить систему уравнений. Пункт Б определяет, какую систему нужно решить. Сначала прочитайте все внимательно.

УКАЗАНИЯ ПО ВЫБОРУ ВАРИАНТА

Выберите Ваш вариант алгоритма (пункт А) решения следующим образом. Номер Вашей зачетки делите на 3 и берете целочисленный остаток, к которому добавляете 1. Пример. Пусть номер зачетки 542402-16. Берете число 54240216 и делите на 3. Получаете в остатке 0. Номер Варианта = 0+1=1 (метод резолюций Робинсона).

Ваш вариант Б задачи ВЫПОЛНИМОСТЬ определяется так. Номер Вашей зачетки делите на 7 и берете целочисленный остаток, к которому добавляете 1. Пример. Пусть номер зачетки 542402-16. Берете число 54240216 и делите на 7. Получаете в остатке 0. Номер Варианта= 0+1=1.

ВАРИАНТЫ ЗАДАНИЙ

А.

1. Методом резолюций Робинсона.

2. Методом отсечения литер.

3. Методом групповых резолюций.

В. Варианты задачи ВЫПОЛНИМОСТЬ.

Прежде всего, договоримся, как кодируются дизъюнкты. Они кодируются последовательностью чисел, например, 1,-2,4,-6. Эта последовательность задает следующий дизъюнкт: . В Вашем варианте будет представлено несколько дизъюнктов. Из п.А Вы выбираете метод и применяете его к Вашей задаче ВЫПОЛНИМОСТЬ. Вы должны показать работу метода по шагам с разъяснением.

Вариант 1. 1,-2,4,-6

2,-4

4,6

3, -6

-3, -4

5,-6

-5

Вариант 2. 1,-2,3

2,3

4,5

3, -5

-3, -4

5,

-4,-5

Вариант 3. 1,-2,-4

2,-3

4,-5

-3, -5

-3, -4

-5,

-4,-5

4

Вариант 4. -1,-2,-3

-2,3

3,5

3, -5

-3, -4

5,

4

Вариант 5. 1,-2,3

-2,-3

-1

-3, -5

5,

-2,-5

Вариант 6. 1,-2

2,-3

4,5

3, -5

-3, -4

5,

-4,-5

Вариант 7. 1,-2,3

-2,-3

-3, 4

3, -5

-3, -4

5,

-4,-5