Методические Указания К ПРАКТИЧЕСКИМ РАБОТАМ ПО дисциплине ДИСКРЕТНАЯ МАТЕМАТИКА
СОДЕРЖАНИЕ
TOC \o "1-1" \h \z \u Практическое занятие №1. PAGEREF _Toc418608176 \h 5Практическая работa №2. PAGEREF _Toc418608177 \h 6Практическая работа №3. PAGEREF _Toc418608178 \h 8Практическая работa №4. PAGEREF _Toc418608179 \h 10Практическая работa №5. PAGEREF _Toc418608180 \h 12Практическая работa №6. PAGEREF _Toc418608181 \h 14Практическая работa №7. PAGEREF _Toc418608182 \h 17Практическая работa №8. PAGEREF _Toc418608183 \h 18Практическая работa №10 PAGEREF _Toc418608184 \h 22Практическая работa №11 PAGEREF _Toc418608185 \h 28Практическая работa №12. PAGEREF _Toc418608186 \h 29Практическая работa №13. PAGEREF _Toc418608187 \h 29Практическая работa №14. PAGEREF _Toc418608188 \h 30Практическая работa №15. PAGEREF _Toc418608189 \h 32СПИСОК ЛИТЕРАТУРЫ PAGEREF _Toc418608190 \h 34
Пояснительная записка1.1. Программа учебной дисциплины по выбору является частью основной профессиональной образовательной программы по специальностям СПО 230115 «Программирование в компьютерных системах».
1.2. Место учебной дисциплины в структуре основной профессиональной образовательной программы: общепрофессиональные дисциплины.
1.3. Цели и задачи учебной дисциплины – требования к результатам освоения учебной дисциплины:
В результате освоения учебной дисциплины обучающийся должен уметь:
Применять методы дискретной математики;
Строить таблицы истинности для формул логики;
Представлять булевы функции в виде формул заданного типа;
Выполнять операции над множествами, применять аппарат теории множеств для решения задач;
Выполнять операции над предикатами;
Исследовать бинарные отношения на заданные свойства;
Выполнять операции в алгебре вычетов;
Применять простейшие криптографические шифры для шифрования текстов;
Генерировать основные комбинаторные объекты;
Находить характеристики графов работу по защите информации.
В результате освоения учебной дисциплины обучающийся должен знать:
Логические операции, формулы логики, законы алгебры логики;
Основные классы функций, полноту множеств функций, теорему Поста;
Основные понятия теории множеств, теоретико-множественные операции и их связь с логическими операциями;
Логику предикатов, бинарные отношения и их виды;
Элементы теории отображений и алгебры подстановок;
Основы алгебры вычетов и их приложение к простейшим криптографическим шифрам;
Метод математической индукции;
Алгоритмическое перечисление основных комбинаторных объектов;
Основы теории графов;
Программа учебной дисциплины предполагает освоение следующих общих компетенций (ОК):
ОК-1. Понимать сущность и социальную значимость своей будущей профессии, проявлять к ней устойчивый интерес.
ОК-2. Организовывать собственную деятельность, определять методы и способы выполнения профессиональных задач, оценивать их эффективность и качество.
ОК-3. Решать проблемы, оценивать риски и принимать решения в нестандартных ситуациях.
ОК-4. Осуществлять поиск, анализ и оценку информации, необходимой для постановки и решения профессиональных задач, профессионального и личностного развития.
ОК-5. Использовать информационно-коммуникационные технологии для совершенствования профессиональной деятельности.
ОК-6. Работать в коллективе и команде, обеспечивать ее сплочение, эффективно общаться с коллегами, руководством, потребителями.
ОК-7. Ставить цели, мотивировать деятельность подчиненных, организовывать и контролировать их работу с принятием на себя ответственности за результат выполнения заданий.
ОК-8. Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознано планировать повышение квалификации.
ОК-9. Быть готовым к смене технологий в профессиональной деятельности.
В результате освоения учебной дисциплины, обучающиеся должны развивать профессиональные компетенции (ПК) в соответствии с основными видами профессиональной деятельности:
ПК-1.1. Выполнять разработку спецификаций отдельных компонент.
ПК-1.3. Выполнять отладку программных модулей с использованием специализированных программных средств.
ПК-2.4. Реализовывать методы и технологии защиты информации в базах данных.
Методические рекомендации включают в себя:
Перечень тем и заданий для практических работ.
Методические указания и пояснения по выполнению данных работ.
Критерии оценки практических работ.
Формы контроля за выполнением данных работ.
5. Литературу, необходимую для выполнения данных работ.
Таблица № 1
Перечень тем и заданий для практических работ
№ работы Название темы Задание для практической работы Кол-во часов
Тема 1.2. Операции над графами Практическое занятие №1. Строить граф, находить его характеристики. Применять аппарат теории графов для решения задач 2
Тема 1.5. Понятие ориентированный граф. Основные определения. Практическое занятие №2. Применение основных логических операций. 2
Тема 2.1. Формальные системы. Практическое занятие №3. Соответствие формальных систем указанным требованиям. Исчисление предикатов. Автоматизация исчисления высказываний с использованием установленных правил. 2
Тема 2.2. Логика предикатов Практическое занятие №4. Применение аппарата алгебры высказываний для работы с предикатами. 2
Практическое занятие №5. Исчисление предикатов, выполнение операций над предикатами. 2
Тема 2.4. Принцип метода математической индукции. Практическое занятие №6.Проведение доказательства методом полной математической индукции. 2
Практическое занятие №7. Установить истинность выражения методом математической индукции 2
Тема 3.2. Основы алгебры вычетов и их приложение к простейшим криптографическим шифрам. Практическое занятие №8. Выполнение операций в алгебре вычетов. Приложение алгебры вычетов к простейшим криптографическим шифрам 2
Тема 4.1. Определения конечных автоматов. Практическое занятие №9. Определение характеристик автомата. Представление событий в автомате. 2
Тема 4.2. Способы задания конечных автоматов. Практическое занятие №10. Описание работы кодового замка, составление таблицы переходов и соответствующего графа. 2
Тема 5.2. Теория рекурсивных функций. Практическое занятие №11. Рекурсивные функции. Получение функции с помощью оператора примитивной рекурсии 2
Практическое занятие №12. Рекурсивные функции. Получение функции с помощью оператора минимизации. 2
Практическое занятие №13. Использование нормальных алгоритмов при решении задач. 2
Практическое занятие №14. Использование нормальных алгоритмов при решении задач. 2
Тема 5.4. Машины Тьюринга.
Практическое занятие №15. Формализация машины Тьюринга. 2
Итого: 30
Раздел 1. Теория графов
Тема 1.2. Операции над графами
Практическое занятие №1.
Строить граф, находить его характеристики. Применять аппарат теории графов для решения задач - 2 ч
Задание 1.Дан граф:
15811510287015030451612900D
00D
Определите вид графа, степень вершин графа, постройте матрицу смежности, кратчайший путь из вершины x1 до x6
-270510-644525
Алгоритм действий
Непустое множество V = {v1, v2,…,vn} и набор Х упорядоченных пар объектов (vi, vi+1) , где viV, vi+1V, называется ориентированным графом и обозначается D(V, X).
Пары х = (v, w) называются дугами и изображаются на диаграмме следующим образом:
v
v
w
w
х
х
v
v
w
w
х
х
v– начало дуги х, w – конец дуги х.
Говорят: дуга исходит из v и заходит в w .
Пусть х – дуга. Если v конец или начало дуги, то v и х инцидентны.
Вершины v и w смежны, если (v, w) X.
Для ориентированного графа аналогично определяются понятия: петли, кратные дуги, псевдограф, мультиграф, граф.
Рассмотрим понятия: полустепень исхода и полустепень захода:
Полустепенью исхода вершины v называется число +(v) дуг орграфа D, исходящих из вершины v.
Полустепенью захода вершины v называется число -(v) дуг орграфа D, заходящих в вершину v.
Замечание: вклад каждой петли, инцидентной некоторой вершине v, равен 1, как в +(v), так и в -(v).
Для орграфа, представленного на рисунке найти полустепени захода и исхода:
16002001195705V1
00V1
V2
V3
X1
X2
X3
X4
V4
V2
V3
X1
X2
X3
X4
V4
SYMBOL 100 \f "Symbol" \s 12d+(SYMBOL 117 \f "Symbol" \s 12u1) = 2
SYMBOL 100 \f "Symbol" \s 12d-(SYMBOL 117 \f "Symbol" \s 12u1) = 0
SYMBOL 100 \f "Symbol" \s 12d+(SYMBOL 117 \f "Symbol" \s 12u2) = 2
SYMBOL 100 \f "Symbol" \s 12d-(SYMBOL 117 \f "Symbol" \s 12u2) = 3
SYMBOL 100 \f "Symbol" \s 12d+(SYMBOL 117 \f "Symbol" \s 12u3) = 0
SYMBOL 100 \f "Symbol" \s 12d-(SYMBOL 117 \f "Symbol" \s 12u3) = 1
SYMBOL 100 \f "Symbol" \s 12dSYMBOL 96 \f "Symbol" \s 12`SYMBOL 43 \f "Symbol" \s 12+(SYMBOL 117 \f "Symbol" \s 12u4) = 0
Найдем суммы степеней исходов и сумму степеней заходов:
SYMBOL 229 \f "Symbol" \s 12еSYMBOL 100 \f "Symbol" \s 12d+(SYMBOL 117 \f "Symbol" \s 12u) = 2 + 2 + 0 + 0 = 4;
SYMBOL 229 \f "Symbol" \s 12еSYMBOL 100 \f "Symbol" \s 12d-(SYMBOL 117 \f "Symbol" \s 12u) = 0 + 3 + 1 = 4 .
В данном графе 4 ребра. Замечаем, что SYMBOL 229 \f "Symbol" \s 12еSYMBOL 100 \f "Symbol" \s 12d+(SYMBOL 117 \f "Symbol" \s 12u) = SYMBOL 229 \f "Symbol" \s 12еSYMBOL 100 \f "Symbol" \s 12d+(SYMBOL 117 \f "Symbol" \s 12u) = m .Действительно, для орграфа справедливо утверждение:
Для любого ориентированного графа выполняется равенство
SYMBOL 229 \f "Symbol" \s 12еSYMBOL 100 \f "Symbol" \s 12d+(SYMBOL 117 \f "Symbol" \s 12u) = SYMBOL 229 \f "Symbol" \s 12еSYMBOL 100 \f "Symbol" \s 12d+(SYMBOL 117 \f "Symbol" \s 12u) = m,
где m – количество дуг.
Критерий оценки
ОЦЕНКА КРИТЕРИЙ
ОТЛИЧНО Задание выполнено правильно, в соответствии с требованиями к работе
ХОРОШО Задание выполнено правильно, с незначительными недоработками, которые студент может устранить самостоятельно.
УДОВЛЕТВОРИТЕЛЬНО Задание выполнено правильно, содержит некоторые недоработками, которые студент может устранить с помощью преподавателя.
НЕУДОВЛЕТВОРИТЕЛЬНО Задание не выполнено
Рекомендуемая литература:
Спирина М.С., Дискретная математика. учебник для СПО ОИЦ «Академия», 2010. 368 с.
Интернет-ресурсы:
http://school-collection.edu.ru/catalog/searchКарпова И.В. Занимательная дискретная математика /
http://www.matburo.ru/st_subject.php?p=dmТема 1.5. Понятие ориентированный граф. Основные определения.
Практическая работa №2.
Применение основных логических операций.-2 ч
Задание написать программу №1, которая определяет, является ли введенное с клавиатуры число элементом данного множества; написать программу №2, которая определяет, является ли данное множество подмножеством другого множества.
Алгоритм действий
Требование к программе №1:
с клавиатуры вводятся элементы данного множества, размерность множества 10, элементы множества целые числа.
С клавиатуры вводиться любое целое число.
На экран выводиться сообщение, является ли данное число элементом множества или не является..
Пример работы программы:
53340231140рис 1. Элемент принадлежит множеству 93980231140рис 2. Элемент не принадлежит множеству
Требование к программе №2:
С клавиатуры вводятся элементы двух множеств, размерность первого равна 10, второго 5.
Если второе множество является подмножеством первого, то на экран выводится «да», в противном случае на экран выводится «нет.
Пример работы программы:
Второе множество является подмножеством первого множества
Второе множество не является подмножеством первого множества
Критерий оценки
ОЦЕНКА КРИТЕРИЙ
ОТЛИЧНО Задание выполнено правильно, в соответствии с требованиями к работе
ХОРОШО Задание выполнено правильно, с незначительными недоработками, которые студент может устранить самостоятельно.
УДОВЛЕТВОРИТЕЛЬНО Задание выполнено правильно, содержит некоторые недоработками, которые студент может устранить с помощью преподавателя.
НЕУДОВЛЕТВОРИТЕЛЬНО Задание не выполнено
Рекомендуемая литература:
Спирина М.С., Дискретная математика. учебник для СПО ОИЦ «Академия», 2010. 368 с.
Интернет-ресурсы:
http://school-collection.edu.ru/catalog/searchКарпова И.В. Занимательная дискретная математика /
http://www.matburo.ru/st_subject.php?p=dmТема 2.1. Формальные системы.
Практическая работа №3.
Соответствие формальных систем указанным требованиям. Исчисление предикатов. Автоматизация исчисления высказываний с использованием установленных правил. -2ч
Задание Какие из следующих высказываний тождественно ложные , а какие тождественно истинные, если область определения М = R?
а) х (х +5 = х + 3) – тождественно ложное высказывание, т.к. ни при каком х равенство неверно;
б) х (х2 +х + 1 > 0) – тождественно истинное высказывание: левую часть неравенства перепишем в виде (х + ½)2 + ¾ , эта сумма больше нуля при любом х;
в) х ((х2 – 5х +6 0)(х2 – 2х + 1 >0)) – высказывание тождественно истинное, если пересечение областей истинности логически умножаемых предикатов не пусто, и ложное, в противном случае.
Алгоритм действий
Пусть имеется предикат Р(х), определенный на множестве М. Если а - некоторый элемент из множества М, то подстановка его вместо х в предикат Р(х) превращает
этот предикат в высказывание - Р(а). Такое высказывание называется единичным. Наряду с образованием из предикатов единичных высказываний в логике предикатов рассматривается еще две операции, которые превращают одноместный предикат в высказывание.
Квантор всеобщности. Пусть Р(х) — предикат, определенный на множестве М. Под выражением х Р(х) понимают высказывание, истинное, когда Р(х) истинно
для каждого элемента х из множества М и ложное, в противном случае. Это высказывание уже не зависит от х.
Соответствующее ему словесное выражение будет: «Для всякого х Р(х) истинно». Символ называют квантором всеобщности.
Переменную х в предикате Р(х) называют свободной (ей можно придавать различные значения из М), в высказывании х Р(х) переменную х называют связанной квантором .
Квантор существования. Пусть Р(х) — предикат, определенный на множестве М. Под выражением х Р(х) понимают высказывание, которое является истинным, если существует элемент х М, для которого Р(х) истинно, и ложным в противном случае. Это высказывание уже не зависит от х.
Соответствующее ему словесное выражение будет: «Существует х, при котором Р(х) истинно». Символ называют квантором существования. В высказывании х Р(х) переменная х связана квантором .
Приведем пример употребления кванторов. Пусть на множестве N натуральных чисел задан предикат Р(х): «Число х кратно 5». Используя кванторы, из данного предиката можно получить высказывания: х N Р(х) - «Все натуральные числа кратны 5»; хN P(x) — «Существует натуральное число, кратное 5». Очевидно, первое из этих высказываний ложно, а второе истинно.
Ясно, что высказывание х Р(х) истинно только в том единственном случае, когда Р(х) - тождественно истинный предикат, а высказывание х Р(х) ложно только в том единственном случае, когда Р(х) — тождественно ложный предикат.
Кванторные операции применяются и к многоместным предикатам. Пусть, например, на множестве М задан двухместный предикат Р(х,у). Применение кванторной операции к предикату Р(х,у) по переменной х ставит в соответствие двухместному предикату Р(х,у) одноместный предикат x P(x, у} (или одноместный предикат х Р(х, у)), зависящий от переменной у и не зависящий от переменной х. К ним можно применить кванторные операции по переменной у, которые приведут уже к высказываниям следующих видов:
yxP(x,y), yxP(x,y), yxP(x,y), ухР(х,у).
Например, рассмотрим предикат Р(х, у): « х кратно у », определенный на множестве N. Применение кванторных операций к предикату Р(х,у) приводит к восьми возможным высказываниям:
1. yxP(x,y) - «Для всякого у и для всякого х у является делителем х».
2. yxP(x,y) - «Существует у, которое является делителем всякого х».
3. yxP(x,y)- «Для всякого у существует х такое, что х делится на у».
4. ухР(х,у) - «Существует у и существует х такие, что у является делителем х».
5. хуP(x,y) - «Для всякого х и для всякого у у является делителем х».
6. хуP(x,y) - «Для всякого х существует такое у, что х делится на у».
7. хуP(x,y) - «Существует х и существует у такие, что у является делителем х».
8. хуР(х,у) - «Существует х такое, что для всякого у х делится на у».
Высказывания 1, 5 и 8 ложны, а высказывания 2, 3, 4, 6 и 7 истинны.
Из рассмотренных примеров видно, что в общем случае изменение порядка следования кванторов изменяет смысл высказывания, а значит, и его логическое значение (например, высказывания 3 и 8).
Рассмотрим предикат – Р(х), определенный на множестве М = {a1, a2,…, an}, содержащем конечное число элементов. Если предикат Р(х) является тождественно истинным, то истинными будут высказывания P(a1), P(a2),…, P(an). При этом истинными будут высказывание хР(х) и конъюнкция P(a1) P(a2)… P(an).
Если хотя бы для одного элемента akM P(ak) окажется ложным, то ложными будут высказывание хР(х) и конъюнкция P(a1) P(a2)… P(an). Значит, справедлива равносильность:
хР(х) P(a1) P(a2)… P(an).
Аналогичным образом можно доказать справедливость равносильности:
хР(х) P(a1)V P(a2)V…VP(an).
Значит, кванторные операции можно рассматривать как обобщение операций конъюнкции и дизъюнкции на случай бесконечных областей.
Предикат Р(х, у): «x<y» определен на множестве М=NN.
а) какие из предикатов тождественно истинные, какие тождественно ложные: хР(х, у), хР(х, у), уР(х, у), уР(х, у)?
хР(х, у) – не является ни тождественно истинным, ни тождественно ложным: при у =1 хР(х, у) = 0, т.к. нет натурального числа меньше 1; при у >1 хР(х, у) = 1, например, х =1. значит, область истинности предиката у>1.
хР(х, у) – тождественно ложный предикат, т.к. какое бы у не задать, среди натуральных чисел найдутся те, которые больше или равны у.
уР(х, у) – тождественно истинный, т.к. для всякого каждого натурального числа можно найти большее натуральное число.
уР(х, у) – тождественно ложный, т.к. какое бы х не задать, среди натуральных чисел найдутся те, которые меньше или равны х.
б) какие из высказываний истинные, какие ложные:
хуР(х, у); хуР(х, у).
хуР(х, у) – ложное высказывание, т.к. не существует натурального х меньшего любого натурального у (для у =1).
хуР(х, у) – истинное высказывание, т.к. для любого натурального х существует большее натуральное число у.
Критерий оценки
ОЦЕНКА КРИТЕРИЙ
ОТЛИЧНО Задание выполнено правильно, в соответствии с требованиями к работе
ХОРОШО Задание выполнено правильно, с незначительными недоработками, которые студент может устранить самостоятельно.
УДОВЛЕТВОРИТЕЛЬНО Задание выполнено правильно, содержит некоторые недоработками, которые студент может устранить с помощью преподавателя.
НЕУДОВЛЕТВОРИТЕЛЬНО Задание не выполнено
Рекомендуемая литература:
Спирина М.С., Дискретная математика. учебник для СПО ОИЦ «Академия», 2010. 368 с.
Интернет-ресурсы:
http://school-collection.edu.ru/catalog/searchКарпова И.В. Занимательная дискретная математика /
http://www.matburo.ru/st_subject.php?p=dmТема 2.2. Логика предикатов
Практическая работa №4.
Применение аппарата алгебры высказываний для работы с предикатами. – 2ч
Теоретические сведения
1. Понятие предиката
В алгебре логики высказывания рассматриваются как нераздельные целые и только с точки зрения их истинности или ложности. Ни структура высказываний, ни их содержание не затрагиваются. В то же время и в науке, и в практике используются заключения, существенным образом зависящие как от структуры, так и от содержания используемых в них высказываний.
Например, в рассуждении «Всякий ромб - параллелограмм; ABCD - ромб; следовательно, ABCD - параллелограмм» посылки и заключение являются элементарными высказываниями логики высказываний и с точки зрения этой логики рассматриваются как целые, неделимые, без учета их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.
В связи с этим возникает необходимость в расширении логики высказываний, в построении такой логической системы, средствами которой можно было бы исследовать и структуру тех высказываний, которые в рамках логики высказываний рассматриваются как элементарные.
Такой логической системой является логика предикатов, содержащая всю логику высказываний в качестве своей части.
Логика предикатов расчленяет элементарное высказывание на субъект (буквально — подлежащее, хотя оно и может играть роль дополнения) и предикат (буквально - сказуемое, хотя оно может играть и роль определения).
Субъект — это то, о чем что-то утверждается в высказывании; предикат - это то, что утверждается о субъекте.
Например, в высказывании «7 - простое число», «7» -субъект, «простое число» - предикат. Это высказывание утверждает, что «7» обладает свойством «быть простым числом».
Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывательную форму «х - простое число». При одних значениях х, (например, х = 13, х =17 ) эта форма дает истинные высказывания, а при других значениях х (например, х = 10 , х = 18 ) эта форма дает ложные высказывания.
Ясно, что эта высказывательная форма определяет функцию одной переменной х, определенной на множестве N, и принимающую значения из множества {1,0}.
Здесь предикат становится функцией субъекта и выражает свойство субъекта.
Определение. Одноместным предикатом Р(х) называется произвольная функция переменного х, определенная на множестве М и принимающая значения из
множества {1,0}.
Множество М, на котором определен предикат P(х) , называется областью определения предиката.
Множество всех элементов х М , при которых предикат принимает значение «истина», называется множеством истинности предиката Р(х), то есть множество истинности предиката Р(х) - это множество 1р = {х| х М, Р(х) = 1}.
Так, предикат -Р(х) - «х - простое число» определен на множестве N, а множество Iр для него есть множество всех простых чисел.
Предикат Q{x} - « sin х = 0 » определен на множестве R, а его множество истинности Iq= {x| x = k; k Z}.
Предикат F(x) - «Диагонали параллелограмма х перпендикулярны» определен на множестве всех параллелограммов, а его множеством истинности является множество всех ромбов.
Приведенные примеры одноместных предикатов выражают свойства предметов.
Рассмотрим примеры предикатов:
Р(х): «х2 + 1> 0, x R»; область определения предиката М= R и область истинности – тоже R, т.к. неравенство верно для всех действительных чисел. Таким образом, для данного предиката М = Ip . Такие предикаты называются тождественно истинными.
В(х): «х2 + 1< 0, x R»; область истинности Ip =, т.к. не существует действительных чисел, для которых выполняется неравенство. Такие предикаты называются тождественно ложными.
Определение. Предикат Р(х), определенный на множестве М, называется тождественно истинным (тождественно ложным), если 1р = М (1р = ).
Предикат sin2x+cos2x=1 – тождественно истинный, предикат - тождественно ложный.
Естественным обобщением понятия одноместного предиката является понятие многоместного предиката, с помощью которого выражаются отношения между предметами.
Примером отношения между двумя предметами является отношение «меньше» («больше»). Пусть это отношение введено на множестве Z целых чисел. Оно может быть охарактеризовано высказывательной формой «х < у»(«х > y») , где х, у Z , то есть является функцией двух переменных Р(х, у), определенной на множестве Z х Z с множеством значений {1,0}.
Определение. Двухместным предикатом Р(х,у) называется функция двух переменных х и у (субъекты предиката), определенная на множестве М =М1 М2 (х М1 , у М2 ) и принимающая значения из множества {1,0}.
Найдем значения предиката «х < у» , где х, у Z для пар (2,1), (4,4), (3,7):
Вместо х и у подставим указанные значения: Р(2,1) = 0, т.к. 2>1; Р(4,4)=0, т.к. 4 = 4; Р(3,7)=1, т.к. 3<7. областью истинности этого предиката является множество всех пар целых чисел, удовлетворяющих данному неравенству.
Рассмотрим этот же предикат, но с областью определения M = R2, тогда область его истинности можно представить графически: это все точки части плоскости (открытая, бесконечная область), лежащей ниже прямой у = х.
127444517145Ip
x
y
y = x
00Ip
x
y
y = x
В числе примеров двухместных предикатов можно назвать предикаты: Q(х, у): « х = у » -предикат равенства, определенный на множестве М = R х R , область истинности которого – все точки прямой у = х :
171450011430у
х
Ip
00у
х
Ip
Предикат F(x,y) : «х//у»- прямая х параллельна прямой у, определенный на множестве прямых, лежащих на данной плоскости.
Аналогично определяется n -местный предикат.
Определение : n – местным предикатом называется функция Q(x1, x2,…,xn), определенная на множестве М = М1 М2…Мn и принимающая на этом множестве значение из множества {1, 0}.
Предикат Р(х) является следствием предиката Q(x) (Q(x)P(x)), если IQIP.
Предикаты P(x) и Q(x) равносильны (Q(x)P(x)), если IQ=IP .
Для n –местных предикатов вводятся аналогичные понятия .
Примеры:
На множестве М= {3,4,5,6,7,8} заданы предикаты P(x) : «х – простое число», Q(x): «х – нечетное число». Составить таблицы истинности. Равносильны ли предикаты на множестве а) М; б) L = {2,3,4,5,6,7,8}; в) К = {3,4,5,6,7,8,9}?
Составим таблицы истинности предикатов на данных множествах:
М Р(х) Q(x) L Р(х) Q(x) K Р(х) Q(x)
3 1 1 2 1 0 3 1 1
4 0 0 3 1 1 4 0 0
5 1 1 4 0 0 5 1 1
6 0 0 5 1 1 6 0 0
7 1 1 6 0 0 7 1 1
8 0 0 7 1 1 8 0 0
8 0 0 9 0 1
На множестве М IP = IQ, следовательно на этом множестве предикаты равносильны. На множествах L и К условие равносильности не соблюдается.
Задание
Будут ли предикаты равносильны или один из них является следствием другого, если область определения R?
б) Р(х): «х2 0», Q(x): «2|x| = cosx».
Критерий оценки
ОЦЕНКА КРИТЕРИЙ
ОТЛИЧНО Задание выполнено правильно, в соответствии с требованиями к работе
ХОРОШО Задание выполнено правильно, с незначительными недоработками, которые студент может устранить самостоятельно.
УДОВЛЕТВОРИТЕЛЬНО Задание выполнено правильно, содержит некоторые недоработками, которые студент может устранить с помощью преподавателя.
НЕУДОВЛЕТВОРИТЕЛЬНО Задание не выполнено
Рекомендуемая литература:
Спирина М.С., Дискретная математика. учебник для СПО ОИЦ «Академия», 2010. 368 с.
Интернет-ресурсы:
http://school-collection.edu.ru/catalog/searchКарпова И.В. Занимательная дискретная математика /
http://www.matburo.ru/st_subject.php?p=dmПрактическая работa №5.
Исчисление предикатов, выполнение операций над предикатами.-2 ч
Теоретические сведения
В логике предикатов будем пользоваться следующей символикой:
Символы р, q, r, ... — переменные высказывания, принимающие два значения: 1 - истина, 0 — ложь.
Предметные переменные - х, у, z, .... которые пробегают значения из некоторого множества М; x°, у°, z°, ... -предметные константы, то есть значения предметных переменных.
Р( .), F( .) - одноместные предикатные переменные; q(.,.,...,.), R(.,.,...,.) n-местные предикатные переменные. P0(.), Q0(. , . , …,.) - символы постоянных предикатов.
Символы логических операций:, v, ,- .
Символы кванторных операций: x , x.
Вспомогательные символы: скобки, запятые.
Определение формулы логики предикатов:
Каждое высказывание как переменное, так и постоянное, является формулой (элементарной).
Если F( .,.,...,.) – n- местная предикатная переменная или постоянный предикат, а х1, х2, …, хn - предметные переменные или предметные постоянные (не обязательно все различные), то F(х1, х2, …, хn) есть формула. Такая формула называется элементарной, в ней предметные переменные являются свободными, не связанными кванторами.
Если А и В — формулы, причем такие, что одна и та же предметная переменная не является в одной из них связанной, а в другой - свободной, то слова А v В , А& В, АВ есть формулы. В этих формулах те переменные, которые в исходных формулах были свободными, являются свободными, а те, которые были связанными, являются связанными.
Если А - формула, то - формула, и характер предметных переменных при переходе от формулы А к формуле не меняется.
Если А(х) - формула, в которую предметная переменная х входит свободно, то слова xA(х) и хА(х) являются формулами, причем предметная переменная входит в них связанно.
Всякое слово, отличное от тех, которые названы формулами в пунктах 1-5, не является формулой.
Например, если Р(х) и Q(x, у) - одноместный и двухместный предикаты, а q, r - переменные высказывания, то формулами будут слова: q, Р(х), P(x)Q(x°,y),
хР(х) xQ(x, у),
Не является формулой слово: xQ(x, y) Р(х). Здесь нарушено условие п.3, так как в формулуxQ(x, y) переменная х входит связано, а в формулу Р(х) переменная х входит свободно.
Выражение у(уР(х,у))VQ(x) не является формулой, т.к. квантор всеобщности на у навешан на формулу уР(х,у), в которой переменная у уже связана квантором существования.
Выражение у, хР(х, у) не является формулой, т.к. переменной х не присвоен квантор.
Из определения формулы логики предикатов ясно, что всякая формула алгебры высказываний является формулой логики предикатов.
Задание Какие из следующих выражений являются формулами? В каждой формуле выделить свободные и связанные переменные:
Критерий оценки
ОЦЕНКА КРИТЕРИЙ
ОТЛИЧНО Задание выполнено правильно, в соответствии с требованиями к работе
ХОРОШО Задание выполнено правильно, с незначительными недоработками, которые студент может устранить самостоятельно.
УДОВЛЕТВОРИТЕЛЬНО Задание выполнено правильно, содержит некоторые недоработками, которые студент может устранить с помощью преподавателя.
НЕУДОВЛЕТВОРИТЕЛЬНО Задание не выполнено
Рекомендуемая литература:
Спирина М.С., Дискретная математика. учебник для СПО ОИЦ «Академия», 2010. 368 с.
Интернет-ресурсы:
http://school-collection.edu.ru/catalog/searchКарпова И.В. Занимательная дискретная математика /
http://www.matburo.ru/st_subject.php?p=dmТема 2.4. Принцип метода математической индукции.
Практическая работa №6.
Проведение доказательства методом полной математической индукции. – 2ч
Задание
Доказать, что при каждом натуральном n число an делится на b, если:
1) , b = 17;
2) , b = 133;
3) , b = 33;
4) , b = 11;
5) , b= 17;
6) , b = 19;
7) , b = 19;
8) , b = 18;
9) , b = 59;
10) , b = 27.
Алгоритм действий:
Пример 1. Доказать, что сумма первых n (n ) нечетных чисел равна квадрату их числа, т. е. 1 + 3 + 5 +…+ (2n - 1) = n2.
Решение. Т. к. утверждение зависит от натурального параметра n, то воспользуемся для его доказательства методом математической индукции.
1) Проверим справедливость данного утверждения для n = 1,
если n = 1, то 1 = 12;
2) предположим, что сумма первых k (k ) нечетных чисел равна квадрату числа этих чисел, т. е. . Другими словами, предположим, что наше утверждение истинно для всех, значит n от 2 до k включительно;
3) установим, исходя из равенства (2), что сумма первых k +1 нечетных чисел равна , т. е.
1 + 3 + 5 +…+ (2(k + 1) – 1) = . Действительно,
1 + 3 + 5 +…+ (2(k + 1) – 1) = 1 + 3 + 5 +… (2k + 1) = 1 + 3 + 5 +…+ (2k – 1) + (2k + 1) = [1 + 3 + 5 +…+ (2k – 1)] + (2k + 1) = + 2k + 1 = ; = (истина).
На основании принципа математической индукции делаем вывод, что сумма первых n нечетных чисел равна n2 для любого натурального n.
Пример 2. Доказать, что для n-го члена геометрической прогрессии {} со знаменателем q справедлива формула bn = .
Решение. Доказательство проводим методом математической индукции по натуральному параметру n.
1) (истина);
2) Предположим, что формула справедлива для всех натуральных значений n от 2 до k включительно, т. е.
3) , (истина)
Согласно принципу математической индукции, можно сказать, что рассматриваемая формула верна для любого натурального n.
Пример 3. Доказать, что при каждом натуральном n число делится на 6.
Решение. Обозначим число . Надо доказать, что делится на 6 при любом натуральном n:
1) (истина);
2) (предположение);
3)
(по предположению),
Если мы сумеем доказать, что , то тогда можем утверждать, что , т. е.3 и 2 взаимопростые числа.
Это доказательство проведем также методом математической индукции:
;
(предположение);
3)
(по предположению);
(по свойствам делимости).
Тогда (по свойству делимости).
Итак, и 2. Следовательно, .
Согласно методу математической индукции, мы можем сказать, что число делится на 6 для любого натурального значения n.
Пример 4. Доказать, что при каждом натуральном n справедлива формула
Решение:
1) ; 1 = 1(истина);
2) (предположение).
3) , .
Чтобы доказать, что А = В, мы можем
с помощью тождественных преобразований перевести А в В;
с помощью тождественных преобразований перевести В в А;
с помощью тождественных преобразований перевести А в С;
с помощью тождественных преобразований перевести В в С;
Воспользуемся приемом (3)
; (и).
Согласно принципу математической индукции, делаем вывод:
при N.
Критерий оценки
ОЦЕНКА КРИТЕРИЙ
ОТЛИЧНО Задание выполнено правильно, в соответствии с требованиями к работе
ХОРОШО Задание выполнено правильно, с незначительными недоработками, которые студент может устранить самостоятельно.
УДОВЛЕТВОРИТЕЛЬНО Задание выполнено правильно, содержит некоторые недоработками, которые студент может устранить с помощью преподавателя.
НЕУДОВЛЕТВОРИТЕЛЬНО Задание не выполнено
Рекомендуемая литература:
Спирина М.С., Дискретная математика. учебник для СПО ОИЦ «Академия», 2010. 368 с.
Интернет-ресурсы:
http://school-collection.edu.ru/catalog/searchКарпова И.В. Занимательная дискретная математика /
http://www.matburo.ru/st_subject.php?p=dmПрактическая работa №7.
Установить истинность выражения методом математической индукции -2 ч
Задание
Доказать, что при каждом натуральном n справедливо равенство:
1) ;
2) ;
3) ;
4) ;
5) ;
6) ;
7) ;
8) ;
9);
10)
Алгоритм действий:
Последовательность задана рекуррентным соотношением: , , , .
Докажите, что для .
Решение. Обозначим значения а, находимые по предполагаемой формуле через при .
(по условию),
(по предполагаемой формуле), (истина).
Предположим, что для всех значений n от 2 до k включительно (k-произвольное натуральное число). В частности, , , т. е.
.
Найдем и
(истина).
Согласно методу математической индукции, делаем вывод: предполагаемое утверждение истинно для .
Начало формы
Конец формы
Критерий оценки
ОЦЕНКА КРИТЕРИЙ
ОТЛИЧНО Задание выполнено правильно, в соответствии с требованиями к работе
ХОРОШО Задание выполнено правильно, с незначительными недоработками, которые студент может устранить самостоятельно.
УДОВЛЕТВОРИТЕЛЬНО Задание выполнено правильно, содержит некоторые недоработками, которые студент может устранить с помощью преподавателя.
НЕУДОВЛЕТВОРИТЕЛЬНО Задание не выполнено
Рекомендуемая литература:
Спирина М.С., Дискретная математика. учебник для СПО ОИЦ «Академия», 2010. 368 с.
Интернет-ресурсы:
http://school-collection.edu.ru/catalog/searchКарпова И.В. Занимательная дискретная математика /
http://www.matburo.ru/st_subject.php?p=dmТема 3.2. Основы алгебры вычетов и их приложение к простейшим криптографическим шифрам.
Практическая работa №8.
Выполнение операций в алгебре вычетов. Приложение алгебры вычетов к простейшим криптографическим шифрам -2 ч
Задание
Найти такое число d ¹ 1, на которое делятся числа 6п + 5 и 9л + 2. При каком значении п. это деление возможно?
Для степени y=2n (n–натуральное число) установить классы сравнимости. Установить зависимость последней цифры этой степени от ее показателя.
Алгоритм действий:
Вычетом числа a по модулю m называется остаток от деления a на m
Из определения видно, что вычеты связаны с делением с остатком.
Разделить натуральное число a на натуральное число b с остатком означает yнайти неотрицательные числа два числа q и г, причем г < b такие, что выполняется равенство
а = q·b + г
Так для чисел 187 и 12 соответствуют два числа 15 и 7, такие, что 187= 15·12+7. Это равенство часто записывается в виде 187:12 = 15(ост. 7).
Напишем названия компонентов деления с остатком:
а – делимое, b- делитель, q- частное, r – остаток.
Рассмотрим еще примеры:
а = - 12, b = 8 ® -12 = (- 2) · 8 + 4, q= -2, r=4
а = - 324, b = - 15 ® — 324 = 22 · (- 15) + 6 q=22, r=6
a = 4, b=10 ® 4=0·10+4 q=0, r=4
a = 12, b = 4 ® 12=4·3+0 q=4, r=0
Число a делится нацело на b, если остаток r = 0 или, а = qb. .Причем отношение «делиться на цело» обозначается .
Теорема. Если а и b делятся на с, то при любых целых k и j сумма ka + jb делится нас.
Критерий оценки
ОЦЕНКА КРИТЕРИЙ
ОТЛИЧНО Задание выполнено правильно, в соответствии с требованиями к работе
ХОРОШО Задание выполнено правильно, с незначительными недоработками, которые студент может устранить самостоятельно.
УДОВЛЕТВОРИТЕЛЬНО Задание выполнено правильно, содержит некоторые недоработками, которые студент может устранить с помощью преподавателя.
НЕУДОВЛЕТВОРИТЕЛЬНО Задание не выполнено
Рекомендуемая литература:
Спирина М.С., Дискретная математика. учебник для СПО ОИЦ «Академия», 2010. 368 с.
Интернет-ресурсы:
http://school-collection.edu.ru/catalog/searchКарпова И.В. Занимательная дискретная математика /
http://www.matburo.ru/st_subject.php?p=dmТема 4.1. Определения конечных автоматов.
Практическая работa №9. Определение характеристик автомата. Представление событий в автомате.- 2ч
Теоретическая часть
Определения. Конечным автоматом (в дальнейшем – просто автоматом) называется система S={A, Q, V, d, l}, в которой A={а1, ...,a.m}, Q={q1, ..., qn}, V={v1, ..., vn} — конечные множества (алфавиты), а d: Q´A—>Q и l: Q´A->V – функции, определенные на этих множествах. А называется входным алфавитом, V – выходным алфавитом, Q – алфавитом состояний, d – функцией переходов, l – функцией выходов. Если, кроме того, в автомате S выделено одно состояние, называемое начальным (обычно будет считаться, что это q1), то полученный автомат называется инициальным и обозначается (S, q); таким образом, по неинициальному автомату с п состояниями можно п различными способами определить инициальный автомат.
Поскольку функции d и l определены на конечных множествах, их можно задавать таблицами. Обычно две таблицы сводятся в одну таблицу d´l: Q´A->Q´V, называемую таблицей переходов автомата, или просто автоматной таблицей.
Пример 2.1. Таблица 2.1 задает функции переходов и выходов для автомата с алфавитами А={а1, а2, а3}, Q={q1, q2, q3, q4}, V={v1, v2}.
Еще один распространенный и наглядный способ задания автомата — ориентированный мультиграф, называемый графом переходов или диаграммой переходов. Вершины графа соответствуют состояниям; если d(qi, аj) = qk и l(qj, аj) = vl, то из qi в qj ведет ребро, на котором написаны qj и vl.
Рис. 2.1
Граф переходов для табл. 2.1 изображен на рис. 2.1. Кратные ребра не обязательны; например, два ребра из q2 в q1 можно заменить одним, на котором будут написаны обе пары a3½v1 и a2½v1. Для любого графа переходов в каждой вершине qi выполнены следующие условия, которые называются условиями корректности: 1) для любой входной буквы аj имеется ребро, выходящее из qi, на котором написано аj, (условие полноты); 2) любая буква аj, встречается только на одном ребре, выходящем из qi (условие непротиворечивости или детерминированности).
Для данного автомата S его функции ds и ls могут быть определены не только на множестве А всех входных букв, но и на множестве A* всех входных слов. Для любого входного слова a=аj1, аj2, ..., aj k выполняются следующие условия:
а) d(qi, аj) задается автоматной таблицей S;
б) для любого слова aÎA* и любой буквы aj
d(qi, aаj) = d(d(qi, a), аj) (2.1)
С помощью расширенной функции d определяется (также индуктивно) расширенная функция l:
l(qi, aаj) = l (d(qi, a), аj) (2.2)
Зафиксируем в автомате S начальное состояние q1 и каждому входному слову a=аj1, аj2, ..., ajk поставим в соответствие слово w в выходном алфавите:
w = l(q1, аj1)l(d(q1,, аj1, аj2)... l(q1, аj1,…аj1). (2.3, a)
Это соответствие, отображающее входные слова в выходные слова, называется автоматным отображением, а также автоматным (или ограниченно детерминированным) оперотором, реализуемым автоматом (S, q1). Иногда будем говорить кратко – оператор (S, q1)или оператор S (если автомат S – инициальный). Если результатом применения оператора к слову a является выходное слово w, то это будем обозначать соответственно S(q1, a)=w или S(a)=w. Число букв в слове a, как обычно, называется длиной a и обозначается |a| или l(a). Автоматное отображение также удобно определить индуктивно:
S(qi, aj)= l(qi, aj); (2.3 б)
S(qi, aаj) = S(qi, a)l (d(qi, a), аj) (2.3 б)
Автоматное отображение обладает двумя свойствами, которые следуют непосредственно из (2.3 a), (2.3 б): 1) слова a и w = S(a) имеют одинаковую длину: (свойство сохранения длины); 2) если a = a1a2 и S(a) = S(aa2) = w1w2, где |a|=|w1|, то S(ai) = w1; иначе говоря, образ отрезка длины l равен отрезку образа той же длины. Свойство 2 отражает тот факт, что автоматные операторы — это операторы без предвосхищения, т. е. операторы, которые, перерабатывая слово слева направо, «не заглядывают вперед»:
i-я буква выходного слова зависит только от первых i букв входного слова. Пример оператора с предвосхищением — оператор, который слову ставит в соответствие его отражение, т. е. слово первая буква выходного слова равна здесь последней букве входного слова.
Указанные два свойства были бы достаточными условиями автоматности отображения, если бы речь шла о бесконечных автоматах, т. е. автоматах с бесконечным Q. Для конечной автоматности этих условий недостаточно
Введенные определения (2.1)–(2.3) наглядно интерпретируются на графе переходов. Если зафиксирована вершина qi, то всякое слово однозначно определяет путь длины k из этой вершины [обозначим его (qi a)], на k ребрах которого написаны соответственно буквы . Поэтому d(qi, a) – это последняя вершина пути l(qi, a), – выходная буква, написанная на последнем ребре пути (qi a), а отображение S(qi, a) – слово, образованное k выходными буквами, написанными на k ребрах этого пути.
Пример 2.2. Для автомата S из примера 2.1 б d(q2,а3а2) = d(q2,а2а) = =q3; d(q2,а3а а) = q2; l(q2,а3а2) = v2; l(q2,а3а) = v1; l(q2,а3а а) = v1. Заметим, что d(q2,а3а) = d(q2,а3а2), но l(q2,а3а) ¹ l(q2,а3а2). Далее S(q2,а3а2)= =v1v2; S(q2,а3а2а) = v1v2 v1 , что иллюстрирует свойство 2 автоматного отображения.
Состояние qj называется достижимым из состояния qi, если существует входное слово a, такое, что d(qi, a) = qj. Автомат .S называетсясильно связным, если из любого его состояния достижимо любое другое состояние.
Автомат называется автономным, если его входной алфавит состоит из одной буквы: А={а}. Все входные слова автономного автомата имеют вид аа...а.
Теорема 2.1. Любое достаточно длинное выходное слово автономного автомата с п состояниями является периодическим (возможно, с предпериодом), причем длины периода и предпериода не превосходят п; иначе говоря, оно имеет вид sw…ww1, где w1 — начальный отрезок w; при этом 0 £ |s| £ п; 1< |w| < п.
Действительно, так как в графе автономного автомата из каждой вершины выходит только одно ребро, то его сильно связные подграфы могут быть только простыми циклами, из которых нет выходящих ребер. Поэтому в компоненте связности может быть только один цикл; остальные подграфы компоненты — это деревья, подвешенные к циклу и ориентированные в его сторону.
Пример 2.3. Граф автомата, заданного в табл. 2.2, изображен на рис. 2.2 (входные буквы на ребрах опущены; выходной алфавит V={0, 1, 2}).
Здесь и в дальнейшем символы состояний для кратности обозначений будут заменяться их индексами.
Таблица 2.2
q 1 2 3 5 6 7 8 9
а 3,0 4,0 4,0 7,0 4,2 5,0 6,1 9,0 9,1
Рис. 2.2
Задание
Критерий оценки
ОЦЕНКА КРИТЕРИЙ
ОТЛИЧНО Задание выполнено правильно, в соответствии с требованиями к работе
ХОРОШО Задание выполнено правильно, с незначительными недоработками, которые студент может устранить самостоятельно.
УДОВЛЕТВОРИТЕЛЬНО Задание выполнено правильно, содержит некоторые недоработками, которые студент может устранить с помощью преподавателя.
НЕУДОВЛЕТВОРИТЕЛЬНО Задание не выполнено
Рекомендуемая литература:
Спирина М.С., Дискретная математика. учебник для СПО ОИЦ «Академия», 2010. 368 с.
Интернет-ресурсы:
http://school-collection.edu.ru/catalog/searchКарпова И.В. Занимательная дискретная математика /
http://www.matburo.ru/st_subject.php?p=dmТема 4.2. Способы задания конечных автоматов.
Практическая работa №10
Описание работы кодового замка, составление таблицы переходов и соответствующего графа. – 2 ч
Теоретическая часть
Комбинационные схемы состоят только из логических элементов (И,ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ и т.д.). В общем случае комбинационная схема имеет несколько входов и несколько выходов. Обобщенный сигнал Х на входах комбинационной схемы представляет собой некоторую комбинацию сигналов xi на отдельных входах схем (рис.1.1).
64008068580Y
КС
x1
x2
xn
xi
ym
y2
y1
X
Рис.1.1
…
…
…
00Y
КС
x1
x2
xn
xi
ym
y2
y1
X
Рис.1.1
…
…
…
Обобщенный сигнал Y на выходах комбинационной схемы является, соответственно, комбинацией сигналов yj на отдельных её выходах. Выходной сигнал Y зависит только от входного сигнала Х, т.е. только от комбинации сигналов на входах схемы:
Y = Y(X) (1.1)
В соответствии с (1.1) комбинационная схема с несколькими входами и несколькими выходами может быть представлена в обобщенном виде так, как это показано на рис. 1.2.
1903730123190КС
X
Y
Рис.1.2
00КС
X
Y
Рис.1.2
В дальнейшем будем считать, что отдельные элементы и комбинационная схема в целом не задерживают сигнал во времени. В случае, когда задержку сигнала необходимо учитывать, необходимо этот факт отмечать специально.
Таким образом, при любом изменении сигнала на входе комбинационной схемы практически мгновенно соответственно изменяется сигнал на её выходах.
012700. . .
. . .
. . .
. . .
Автомат
с
памятью
Эп1
Эпm
. . .
Эп2
x1
x2
xn
y1
y2
yk
Yt
Qt
q1
q2
qm
Xt
. . .
Рис. 1.3
00. . .
. . .
. . .
. . .
Автомат
с
памятью
Эп1
Эпm
. . .
Эп2
x1
x2
xn
y1
y2
yk
Yt
Qt
q1
q2
qm
Xt
. . .
Рис. 1.3
При многократном поступлении одного и того же входного сигнала комбинационная схема выдает один и тот же выходной сигнал. Таким образом, сигнал на выходе комбинационной схемы не зависит от того, какие сигналы поступали на ее вход до текущего момента времени. Поэтому комбинационные схемы используются для одномоментного преобразования входного кода в выходной.
Автоматы с памятью состоят из логических элементов и элементов памяти (рис.1.3).
На рис.1.3 приняты следующие обозначения:
Эпr - элемент памяти r автомата, r = 1, 2, … m;
Xt - обобщенный входной сигнал в текущем такте;
xi - сигнал на входе i автомата, i = 1. 2. … n;
Yt - обобщенный входной сигнал в текущем такте;
Yj - сигнал на выходе j автомата, j = 1. 2. … k;
Qt - состояние автомата в текущем такте;
qm - состояние элемента памяти m , m = 1, 2, … m.
Информация, записанная в элементах памяти автомата, называется состоянием (или внутренним состоянием) автомата. Состояние автомата в целом (Q) определяется состоянием отдельных элементов памяти (qi). Основная особенность автоматов с памятью состоит в том, что сигнал на выходе автомата зависит как от входного сигнала, так и от состояния автомата.
Таким образом
Yt = Y( Xt, Qt ) (1.2)
Из уравнения (1.2) видно, что при одном и том же входном сигнале в зависимости от состояния автомат может выдавать различные выходные сигналы, т.е. различным образом реагировать на одинаковые входные сигналы. Поэтому автомат с памятью используется для выполнения определенной последовательности действий, т.е. определенного алгоритма преобразования информации.
Автоматы могут быть асинхронными и синхронными. В дальнейшем будем рассматривать синхронные автоматы. Работа синхронных автоматов происходит в дискретные моменты времени, называемые тактами. В промежутках между тактами автомат не реагирует на входные сигналы. Такты задаются с помощью генераторов синхронизирующих (тактовых) импульсов.
Содержательно автомат можно охарактеризовать как устройство, имеющее входы и выходы и находящееся в каждый из моментов дискретного времени, в одном из состояний (Qt).
Обобщенная структура автомата с памятью показана на рис.1.4, где входные и выходные сигналы, а также состояние автомата, представлены в обобщенном виде.
91440050165Автомат
с памятью
Память
Qt
Yt
Xt
Рис.1.4
00Автомат
с памятью
Память
Qt
Yt
Xt
Рис.1.4
При работе автомата в каждом такте кроме выходного сигнала формируется также новое состояние, которое зависит от входного сигнала и текущего состояния автомата:
Qt + 1 = Q ( Xt, Qt) (1.3)
Из соотношения (1.3) видно, что после начала работы автомата из состояния Q0 его последующие состояния связаны с входными сигналами следующим образом:
Q1 = Q ( X1, Q0 ), т.е. Q1 зависит от сигнала X1 и состояния Q0 ;
Q2 = Q ( X2, Q1 ), т.е. Q2 зависит от сигнала X2 и состояния Q1 ;
Но так как Q1 = Q ( X1, Q0 ), то Q2 = Q (X1, X2, Q1 ), т.е. Q2 зависит от сигналов X1 , X2 и состояния Q1 .
Аналогично можно показать, что состояние Q3 зависит от сигналов X1,X2,X3 и состояния Q2 и т.д. В приведенных выше рассуждениях индексы при X и Q означают номера тактов.
Таким образом, можно сделать вывод, что каждое состояние автомата зависит от всех входных сигналов, поступивших в предыдущих тактах, т.е. от предыстории входных сигналов.
Поскольку выходной сигнал зависит от текущего состояния, то он также определяется всей предысторией входных сигналов. Именно этим и объясняются более широкие возможности преобразования информации в автоматах с памятью по сравнению с комбинационными схемами.
В качестве примера рассмотрим два варианта построения схемы управления кодовым замком. Пусть кодовый замок имеет десять кнопок, пронумерованных цифрами от 0 до 9. И пусть, например, схема управления должна выдать сигнал на открытие замка при одновременном нажатии только кнопок 3, 5 и 8.
Если принять, что порядок нажатия кнопок безразличен, то схема управления должна реагировать только на определенную комбинацию нажатых кнопок (в данном примере на комбинацию 3, 5, 8). В этом случае такая схема управления может быть построена в виде комбинационной схемы.
Если заданы не только комбинация нажатых кнопок, но и последовательность их нажатия (например, замок должен открываться только при нажатии сначала кнопки 5, затем кнопки 3 и затем кнопки 8), то схема управления замком должна запоминать, в каком порядке были нажаты кнопки. В этом случае в состав схемы должны входить элементы памяти. Поэтому такая схема управления представляет собой автомат с памятью.
Таким образом, схема управления замком, выполненная по второму варианту, является более сложной, но при этом она обеспечивает более высокую степень защиты замка.
Существует большое количество различных структур автоматов. В общем случае любой автомат может иметь различную структуру. Однако структуру любого автомата можно преобразовать к одной из двух типовых структур:
Автомат 1-го рода или автомат Мили.
Автомат 2-го рода или автомат Мура.
Структура автомата Мили представлена на рис. 1.5.
Автомат Мили представляется в виде двух комбинационных схем и памяти, состоящей из отдельных элементов памяти.
Первая комбинационная схема (в дальнейшем будем обозначатьее КС1) имеет две группы входов. Одна группа входов является входами автомата в целом (x1, x2, …, xn ). На другую группу входов поступают сигналы из памяти автомата (qt1, qt2, …, qtk )., т.е. состояние автомата. По отношению к автомату в целом эти сигналы являются внутренними. На выходах схемы КС1 формируются сигналы (qt+11,qt+12,…,qt+1k), которые поступают на входы элементов памяти (ЭПr).
-2730562230qt1
qt2
qtk
КС1
КС2
qt+11
qt+12
qt+1k
ЭП1
ЭП2
ЭПk
…
Y1
Y3
Y2
Ym
…
Рис.1.5
…
…
00qt1
qt2
qtk
КС1
КС2
qt+11
qt+12
qt+1k
ЭП1
ЭП2
ЭПk
…
Y1
Y3
Y2
Ym
…
Рис.1.5
…
…
-210185152400X1
00X1
-21018543180X2
00X2
-21018544450Xn
00Xn
После записи в память эти сигналы в следующем такте будут представлять собой следующее состояние автомата (Qt+1). Таким образом схема КС1 является схемой формирования следующего состояния автомата.
Вторая комбинационная схема (КС2) называется выходным преобразователем и служит для формирования выходных сигналов автомата (y1, y2, …, ym ). На ее входы поступают те же сигналы, что и на входы схемы КС1. Поэтому выходные сигналы в автомате Мили зависят как от состояния, так и от входных сигналов, поступающих в данном такте. Обобщенная структура автомата Мили имеет вид, представленный на рис.1.6.
57404017780КС1
ЭП
КС2
Xt
Qt
Yt
Рис 1.6
00КС1
ЭП
КС2
Xt
Qt
Yt
Рис 1.6
Работа автомата Мили описывается в общем виде уравнениями переходов и выходов:
Yt = Y( Xt, Qt ) ; (1.4)
Qt + 1 = Q( Xt, Qt).
Уравнение (функция) переходов Qt+1=Q(Xt, Qt) определяет условия перехода автомата из одного состояния в другое. Это уравнение задает логику работы комбинационной схемы КС1.
Уравнение (функция) выходов Yt=Y(Xt,Qt ) определяет условия формирования определенных выходных сигналов. Это уравнение задает логику работы комбинационной схемы КС2.
Анализ уравнений (1.4) показывает, что логика работы автомата Мили совпадает с логикой работы автомата обобщенной структуры, представленной на рис. 1.4.
Автомат Мура имеет структуру, показанную на рис. 1.7.
60388567945КС1
ЭП
КС2
Xt
Qt
Yt
Рис 1.7
00КС1
ЭП
КС2
Xt
Qt
Yt
Рис 1.7
Эта структура внешне очень незначительно отличается от структуры автомата Мили. Как видно на рис.1.7, это отличие заключается в том, что в автомате Мура входной сигнал не поступает на комбинационную схему КС2 (схему формирования выходов).
Работа автомата Мура описывается следующими уравнениями переходов и выходов:
Yt = Y( Qt ) ; (1.5)
Qt + 1 = Q ( Xt, Qt).
Из уравнений (1.5) видно, что выходной сигнал автомата Мура зависит только от текущего состояния и не зависит от входного сигнала в данном такте. Следует особо отметить, что выходной сигнал зависит от входных сигналов, поступивших в предыдущих тактах, поскольку от них зависит текущее состояние. Таким образом, выходной сигнал автомата Мура задержан на один такт по отношению к входному сигналу
Иногда выходные сигналы автомата Мура совпадают с сигналами состояний. В этом случае автомат не имеет комбинационной схемы КС2 и называется автоматом без выходного преобразователя. Обобщенная структура такого автомата показана на рис. 1.8.
118872071755Xt
КС1
ЭП
Qt
Yt
Рис 1.8
00Xt
КС1
ЭП
Qt
Yt
Рис 1.8
Алгоритм работы автомата Мура без выходного преобразователя описывается следующими уравнениями переходов и выходов:
Yt = Qt ; (1.6)
Qt + 1 = Q ( Xt, Qt).
Задание
Укажите основное отличие автоматов с памятью от комбинационных схем по их составу.
Укажите основное отличие автоматов с памятью от комбинационных схем по логике их работы.
Чем определяется значение выходного сигнала для комбинационной схемы ?
От чего зависит выходной сигнал автомата Мили ?
От чего зависит выходной сигнал автомата Мура ?
От чего зависит следующее состояние автомата ?
Чем отличаются структуры автоматов Мили и Мура?
Чем отличаются функции выходов автоматов Мили и Мура?
Можно ли по графу автомата определить тип автомата (автомат Мили или Мура)?
Зависит ли выходной сигнал автомата Мура от предыстории входных сигналов?
Критерий оценки
ОЦЕНКА КРИТЕРИЙ
ОТЛИЧНО Задание выполнено правильно, в соответствии с требованиями к работе
ХОРОШО Задание выполнено правильно, с незначительными недоработками, которые студент может устранить самостоятельно.
УДОВЛЕТВОРИТЕЛЬНО Задание выполнено правильно, содержит некоторые недоработками, которые студент может устранить с помощью преподавателя.
НЕУДОВЛЕТВОРИТЕЛЬНО Задание не выполнено
Рекомендуемая литература:
Спирина М.С., Дискретная математика. учебник для СПО ОИЦ «Академия», 2010. 368 с.
Интернет-ресурсы:
http://school-collection.edu.ru/catalog/searchКарпова И.В. Занимательная дискретная математика /
http://www.matburo.ru/st_subject.php?p=dmТема 5.2. Теория рекурсивных функций.
Практическая работa №11
Рекурсивные функции. Получение функции с помощью оператора примитивной рекурсии 2ч
Теоретическая часть
Рекурсивные функции
Пусть имеются два множества Х и Y.
Определения
Если некоторым элементам множества Х поставлены в соответствие однозначно определенные элементы множества Y, то говорят, что задана частичная функция из Х в Y.Совокупность тех элементов множества Х, у которых есть соответствующие элементы в Y, называется областью определения функции, а совокупность тех элементов Y, которые соответствуют Х, называются совокупностью значений функции.
Если область определения функции из Х в Y совпадает с множеством Х, то функция называется всюду определенной.
Идея построения точного определения алгоритма, опирающегося на понятие рекурсивной функции
Любые дискретные данные можно закодировать натуральными числами в некоторой системе счисления.
Тогда всякое их преобразование сведется к последовательности вычислительных операций, а результат обработки будет представлять целое число.
Любой алгоритм, единый для данной числовой функции, вычисляет ее значение, а его элементарными шагами оказываются обычные арифметические и логические операции. Такие функции называются вычислимыми.
Пусть имеется класс функций типа y(x1, x2, …, xn) , особенностями которых является то, что все аргументы функции x1, x2, …, xn целочисленны, и значение функции y также выражается целым числом.
Определение
Функция y(x1, x2, …, xn) называется эффективно вычислимой, если существует алгоритм, позволяющий вычислить ее значение по известным значениям аргументов.
Поскольку понятие алгоритма в этом определении берется в интуитивном смысле, то и понятие эффективно вычислимой функции оказывается интуитивным.
Однако совокупность вычислимых функций, удовлетворяющих перечисленным ранее свойствам алгоритма, оказалась одной и той же и притом легко описываемой в обычных математических терминах. Эта точно описанная совокупность числовых функций, совпадающая с совокупностью всех вычислимых функций при самом широком до сих пор известном понимании алгоритма, носит название совокупности рекурсивных функций.
Любая алгоритмическая модель предусматривает определение элементарных шагов алгоритма и способов построения из них последовательности преобразований, обеспечивающих необходимую последовательность обработки данных.
Задание
Найти значение S2(S1, 01)
Найти значение S3( I22, I11, 01)
Критерий оценки
ОЦЕНКА КРИТЕРИЙ
ОТЛИЧНО Задание выполнено правильно, в соответствии с требованиями к работе
ХОРОШО Задание выполнено правильно, с незначительными недоработками, которые студент может устранить самостоятельно.
УДОВЛЕТВОРИТЕЛЬНО Задание выполнено правильно, содержит некоторые недоработками, которые студент может устранить с помощью преподавателя.
НЕУДОВЛЕТВОРИТЕЛЬНО Задание не выполнено
Рекомендуемая литература:
Спирина М.С., Дискретная математика. учебник для СПО ОИЦ «Академия», 2010. 368 с.
Интернет-ресурсы:
http://school-collection.edu.ru/catalog/searchКарпова И.В. Занимательная дискретная математика /
http://www.matburo.ru/st_subject.php?p=dmПрактическая работa №12.
Рекурсивные функции. Получение функции с помощью оператора минимизации. – 2ч
Задание Функция f(x,y)=x-y может быть получена с помощью оператора минимизации:
Вычислите функцию f(7,2)
Алгоритм действий
Пусть задана некоторая функция f(x, y) . Зафиксируем значение x и выясним, при каком y значение f(x, y) =0 . Более сложной оказывается задача отыскания наименьшего из тех значений y, при которых f(x, y) =0.
Поскольку результат решения такой задачи зависит от x, то и наименьшее y является функцией x.
Вводится обозначение:
(x) = y [f(x, y) =0]
(читается «наименьшее y такое, что f(x, y) =0 , а y называют -оператором или оператором минимизации).
Подобным же образом определяется функция многих переменных
( x1,…,xn) = y [f(x1,…,xn, y) =0]
Для вычисления функции можно использовать следующую процедуру:
1. Вычисляем f(x1,…,xn, 0) ; если значение равно нулю, то полагаем ( x1,…,xn) = 0 . Если ( x1,…,xn) ≠ 0 то переходим к следующему шагу.
2. Вычисляем f(x1,…,xn, 1) ; если значение равно нулю, то полагаем ( x1,…,xn) = 1 . Если f(x1,…,xn, 1) ≠ 0 , то переходим к следующему шагу и т.д.
Если окажется, что для всех y функция f(x1,…,xn, y) ≠ 0, то функция ( x1,…,xn) считается неопределенной.
Критерий оценки
ОЦЕНКА КРИТЕРИЙ
ОТЛИЧНО Задание выполнено правильно, в соответствии с требованиями к работе
ХОРОШО Задание выполнено правильно, с незначительными недоработками, которые студент может устранить самостоятельно.
УДОВЛЕТВОРИТЕЛЬНО Задание выполнено правильно, содержит некоторые недоработками, которые студент может устранить с помощью преподавателя.
НЕУДОВЛЕТВОРИТЕЛЬНО Задание не выполнено
Рекомендуемая литература:
Спирина М.С., Дискретная математика. учебник для СПО ОИЦ «Академия», 2010. 368 с.
Интернет-ресурсы:
http://school-collection.edu.ru/catalog/searchКарпова И.В. Занимательная дискретная математика /
http://www.matburo.ru/st_subject.php?p=dmПрактическая работa №13.
Использование нормальных алгоритмов при решении задач.- 2ч
Задание
Доказать, что двухместная функция f(x,y)=x+y является примитивно-рекурсивной
Найти значение функции f(3,2), если она задана следующими соотношениями:
f(0,x)=0,
f(y+1,x)=f(y,x)+x
Алгоритм действий
Пусть заданы какие-либо числовые частичные функции: n -местная g(x1,…,xn) и (n+2) - местная . h(x1,…,xn, y, k) . Говорят, что (n+1)-местная частичная функция f образуется из функций g и h посредством примитивной рекурсии, если для всех натуральных значений x1,…,xn, y справедливо:
f(x1,…,xn, 0) = g(x1,…,xn), (1)
f(x1,…,xn, y+1) = h(x1,…,xn, y+1, f(x1,…,xn,y))
Поскольку областью определения функций является множество всех натуральных чисел, частичная функция f, удовлетворяющая условиям (1), существует для всех частичных функций g и h и функция эта будет единственной.
Условия (1) задают также последовательность определения значений f на различных шагах рекурсии:
f(x1,…,xn, 0) = g(x1,…,xn),
f(x1,…,xn, 1) = h(x1,…,xn, 1, f(x1,…,xn, 0)) (2)
. . .
f(x1,…,xn, m+1) = h(x1,…,xn, m+1, f(x1,…,xn, m))
Для примитивной рекурсии используется обозначение
В этой записи R рассматривается как символ двуместной частичной операции, определенной на множестве всех частичных функций. Если g и h являются всюду определенными, то и f является всюду определенной. Важно то, что если умеем находить значения функций g и h, то значение функции f(a1,…,an, m+1) можно вычислить «механически» используя соотношения (2).
Определение
Частичная функция f(x1,…,xn) называется примитивно рекурсивной, если ее можно получить конечным числом операций суперпозиции и примитивной рекурсии, исходя лишь из простейших функций S1 , 0n и Inm .
Критерий оценки
ОЦЕНКА КРИТЕРИЙ
ОТЛИЧНО Задание выполнено правильно, в соответствии с требованиями к работе
ХОРОШО Задание выполнено правильно, с незначительными недоработками, которые студент может устранить самостоятельно.
УДОВЛЕТВОРИТЕЛЬНО Задание выполнено правильно, содержит некоторые недоработками, которые студент может устранить с помощью преподавателя.
НЕУДОВЛЕТВОРИТЕЛЬНО Задание не выполнено
Рекомендуемая литература:
Спирина М.С., Дискретная математика. учебник для СПО ОИЦ «Академия», 2010. 368 с.
Интернет-ресурсы:
http://school-collection.edu.ru/catalog/searchКарпова И.В. Занимательная дискретная математика /
http://www.matburo.ru/st_subject.php?p=dmПрактическая работa №14.
Использование нормальных алгоритмов при решении задач.-2 ч
Теоретическая часть
Определение 1: Пусть A={a1,a2,...,an} - алфавит из n различных символов, W={w1,w2,...,wn} - соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов C={c1,c2,...,cn}, такой что:
(1) ci не является префиксом для cj, при i!=j
(2) минимальна (|ci| длина кода ci)
называется минимально-избыточным префиксным кодом или иначе кодом Хаффмана.
Замечания:
Свойство (1) называется свойством префиксности. Оно позволяет однозначно декодировать коды переменной длины.
Сумму в свойстве (2) можно трактовать как размер закодированных данных в битах. На практике это очень удобно, т.к. позволяет оценить степень сжатия не прибегая непосредственно к кодированию.
В дальнейшем, чтобы избежать недоразумений, под кодом будем понимать битовую строку определенной длины, а под минимально-избыточным кодом или кодом Хаффмана - множество кодов (битовых строк), соответствующих определенным символам и обладающих определенными свойствами.
Известно, что любому бинарному префиксному коду соответствует определенное бинарное дерево.
Определение 2: Бинарное дерево, соответствующее коду Хаффмана, будем называть деревом Хаффмана.
Задача построения кода Хаффмана равносильна задаче построения соответствующего ему дерева. Приведем общую схему построения дерева Хаффмана:
Составим список кодируемых символов (при этом будем рассматривать каждый символ как одноэлементное бинарное дерево, вес которого равен весу символа).
Из списка выберем 2 узла с наименьшим весом.
Сформируем новый узел и присоединим к нему, в качестве дочерних, два узла выбранных из списка. При этом вес сформированного узла положим равным сумме весов дочерних узлов.
Добавим сформированный узел к списку.
Если в списке больше одного узла, то повторить 2-5.
Приведем пример: построим дерево Хаффмана для сообщения S="A H F B H C E H E H C E A H D C E E H H H C H H H D E G H G G E H C H H".
Для начала введем несколько обозначений:
Символы кодируемого алфавита будем выделять жирным шрифтом: A, B, C.
Веса узлов будем обозначать нижними индексами: A5, B3, C7.
Составные узлы будем заключать в скобки: ((A5+B3)8+C7)15.
Итак, в нашем случае A={A, B, C, D, E, F, G, H}, W={2, 1, 5, 2, 7, 1, 3, 15}.
A2 B1 C5 D2 E7 F1 G3 H15
A2 C5 D2 E7 G3 H15 (F1+B1)2
C5 E7 G3 H15 (F1+B1)2 (A2+D2)4
C5 E7 H15 (A2+D2)4 ((F1+B1)2+G3)5
E7 H15 ((F1+B1)2+G3)5 (C5+(A2+D2)4)9
H15 (C5+(A2+D2)4)9 (((F1+B1)2+G3) 5+E7)12
H15 ((C5+(A2+D2)4) 9+(((F1+B1)2+G3) 5+E7)12)21
(((C5+(A2+D2)4) 9+(((F1+B1)2+G3) 5+E7)12)21+H15)36
В списке, как и требовалось, остался всего один узел. Дерево Хаффмана построено. Теперь запишем его в более привычном для нас виде.
Листовые узлы дерева Хаффмана соответствуют символам кодируемого алфавита. Глубина листовых узлов равна длине кода соответствующих символов.
Путь от корня дерева к листовому узлу можно представить в виде битовой строки, в которой "0" соответствует выбору левого поддерева, а "1" - правого. Используя этот механизм, мы без труда можем присвоить коды всем символам кодируемого алфавита. Выпишем, к примеру, коды для всех символов в нашем примере:
A=0010bin C=000bin E=011bin G=0101bin
B=01001bin D=0011bin F=01000bin H=1bin
Теперь у нас есть все необходимое для того чтобы закодировать сообщение S. Достаточно просто заменить каждый символ соответствующим ему кодом:
S/="0010 1 01000 01001 1 000 011 1 011 1 000 011 0010 1 0011 000 011 011 1 1 1 000 1 1 1 0011 011 0101 1 0101 0101 011 1 000 1 1".
Оценим теперь степень сжатия. В исходном сообщении S было 36 символов, на каждый из которых отводилось по [log2|A|]=3 бита (здесь и далее будем понимать квадратные скобки [] как целую часть, округленную в положительную сторону, т.е. [3,018]=4). Таким образом, размер S равен 36*3=108 бит
Размер закодированного сообщения S/ можно получить воспользовавшись замечанием 2 к определению 1, или непосредственно, подсчитав количество бит в S/. И в том и другом случае мы получим 89 бит.
Итак, нам удалось сжать 108 в 89 бит.
Теперь декодируем сообщение S/. Начиная с корня дерева будем двигаться вниз, выбирая левое поддерево, если очередной бит в потоке равен "0", и правое - если "1". Дойдя до листового узла мы декодируем соответствующий ему символ.
Ясно, что следуя этому алгоритму мы в точности получим исходное сообщение S.
Задание однозначно декодировать коды переменной длины последовательность:
ssssoooeeerroooaayyyyyddddoeuuuuuwwwwjjjorruuuuuuuuuuxxxkhhhhhhmmmmmmgggllllllljjjj
Критерий оценки
ОЦЕНКА КРИТЕРИЙ
ОТЛИЧНО Задание выполнено правильно, в соответствии с требованиями к работе
ХОРОШО Задание выполнено правильно, с незначительными недоработками, которые студент может устранить самостоятельно.
УДОВЛЕТВОРИТЕЛЬНО Задание выполнено правильно, содержит некоторые недоработками, которые студент может устранить с помощью преподавателя.
НЕУДОВЛЕТВОРИТЕЛЬНО Задание не выполнено
Рекомендуемая литература:
Спирина М.С., Дискретная математика. учебник для СПО ОИЦ «Академия», 2010. 368 с.
Интернет-ресурсы:
http://school-collection.edu.ru/catalog/searchКарпова И.В. Занимательная дискретная математика /
http://www.matburo.ru/st_subject.php?p=dmТема 5.4. Машины Тьюринга.
Практическая работa №15.
Формализация машины Тьюринга. – 2ч
Теоретическая часть
Алфавит исчисления состоит из трех подалфавитов: А={ a0, a1, a2, a3, … , an} – внешний алфавит, который используется для записи входных значений и результатов на ленту машины; Q={q0, q1, q2, q3, … , qm}– алфавит внутренних состояний (нам удобно каждое внутреннее состояние машины обозначать одной буквой); S={l, s, r} – алфавит переходов. Здесь a0- символ пустой ячейки, q0, q1- соответственно заключительное и начальное внутренние состояния машины, а l, s, r- команды управления считывающей кареткой машины («на ячейку влево», «на месте», «на ячейку вправо»).
Работа машины определяется ее функциональной схемой или программой. Эту схему удобно представить в виде таблицы:
q1 q2 … qm
a0 …
a1 …
… … … … …
an …
Опишем работу машины Тьюринга. На ленте в ячейках написано некоторое слово. В начальный момент времени считывающая каретка находится над одной из ячеек ленты в начальном внутреннем состоянии q1. Такт машины состоит из следующих действий. По текущему внутреннему состоянию qi и записанной в обозреваемой ячейке букве aj определяется адрес ячейки таблицы. Записанное в этой ячейке слово определяет очередной шаг машины. Машина записывает в обозреваемую ячейку букву ar, переходит во внутреннее состояние qf и выполняет сдвиг по команде [st], которая представляет собой одну из трех букв l, s, r. Если очередное внутреннее состояние оказалось заключительным состоянием q0, то машина останавливается.
Рассмотрим пример машины Тьюринга и процесс ее применения к некоторому начальному слову.
Пример Зададим алфавиты. Внешний А={0, 1}. Внутренний Q={q0, q1}. Функциональная схема
q1
0 0q0s
1 1q1r
Нетрудно увидеть, что эта машина выполняет довольно разумную операцию: она сдвигается вправо до тех пор, пока не найдет ячейку, в которую записан ноль. Машина останавливается над этой ячейкой.
Пусть на ленте записано слово 01111101 и в начальный момент времени считывающая каретка находится над вторым символом слева (единицей). Нам удобно записать это в таком виде: 0q11111101 (перед обозреваемой буквой стоит символ соответствующего внутреннего состояния). Из функциональной схемы видно, что машина должна переписать в текущую ячейку единицу, остаться в состоянии q1 и сдвинуться на одну ячейку вправо: 01q1111101. Эти шаги повторяются еще 4 раза, в итоге мы получим ситуацию: 011111q101. Т. е. каретка машины дойдет до ячейки, в которой записан ноль (сама она будет в это время в состоянии q1). Теперь машина должна (согласно схеме) переписать в текущую ячейку ноль и остановиться в этой ячейке, перейдя в состояние остановки q0: 0111110q01.
Задание
Придумайте МТ, реализующую функцию Z(x)=0. Для удобства будем считать, что внешний алфавит состоит из единицы и x – символа пустой ячейки. Число ноль кодируется одной единицей, число один – двумя и так далее. Число n кодируется n+1 идущей подряд единицей. Машина должна оставить только одну единицу.
Придумайте МТ, реализующую функцию следования . Используйте кодировку из предыдущей задачи. Машина должна пририсовать к ряду единиц еще одну.
Придумайте МТ, выполняющую сложение в указанной выше кодировке. Два складываемых числа разделяются знаком *. Процесс заключается в следующем: * стирается, на ее место пишется 1, и стирается одна последняя единица.
Рассмотрите более сложный вариант сложения: два числа (серии единиц) отделены друг от друга несколькими пустыми ячейками. В начальный момент времени каретка находится левее первого числа или над первой единицей первого числа. Машина должна приписать к первому числу на одну меньше единиц, чем стоит во втором числе, и стереть второе число. После каретка должна вернуться на первую слева цифру суммы.
Реализуйте в виде МТ функцию следования для обычной десятичной записи. Для этого понадобиться найти последнюю цифру в записи числа. Если эта цифра – не девять, то заменить ее следующей и остановить работу (можно еще выйти на первую цифру слова). Если последняя цифра 9, то она заменяется на ноль, делается сдвиг влево и предпринимается попытка увеличить на единицу обозреваемую цифру. Особо надо рассмотреть случай, когда исходное число состоит только из девяток. Тогда последний шаг – запись в ближайшую слева пустую ячейку единицы.
Критерий оценки
ОЦЕНКА КРИТЕРИЙ
ОТЛИЧНО Задание выполнено правильно, в соответствии с требованиями к работе
ХОРОШО Задание выполнено правильно, с незначительными недоработками, которые студент может устранить самостоятельно.
УДОВЛЕТВОРИТЕЛЬНО Задание выполнено правильно, содержит некоторые недоработками, которые студент может устранить с помощью преподавателя.
НЕУДОВЛЕТВОРИТЕЛЬНО Задание не выполнено
Рекомендуемая литература:
Спирина М.С., Дискретная математика. учебник для СПО ОИЦ «Академия», 2010. 368 с.
Интернет-ресурсы:
http://school-collection.edu.ru/catalog/searchКарпова И.В. Занимательная дискретная математика /
http://www.matburo.ru/st_subject.php?p=dmСПИСОК ЛИТЕРАТУРЫОсновные источники
Спирина М.С., Дискретная математика. учебник для СПО ОИЦ «Академия», 2010. 368 с.Дополнительные источники, периодические профессиональные издания:
Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. — М.: Наука, 2007. 408с.
Гончарова Г.А., Мочалин А.А. Элементы дискретной математики: учеб. пособ. М.: Форум: ИНФРА М, 2007.
Кольман Э. Зих О. Занимательная логика. М.: Наука, 2008. 127с.
Куликов Л.Я., Москаленко А.И., Фомин А.А. Сборник задач на алгебре и теории чисел. М.: Просвещение, 2008.
Нефедов В.Н., Осипова В.А. Курс дискретной математики М.: Издательство МАИ, 2008. 264с.
Рембольд У. Введение в информатику для научных работников и инженеров. Уфа: УГАТУ, 2007. 445с.
Просветов Г.И. Дискретная математика: задачи и решения. Учебно-практическое пособие /– М.: Альфа-Пресс, 2009. 136 с.
Хаггарти Р. Дискретная математика для программистов / пер. с анг. под ред. С. А. Кулешова с доп. А. А. Ковалева / Допущено УМО вузов РФ по образованию в области прикладной математики в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению подготовки "Прикладная математика". – М.: ТЕХНОСФЕРА, 2003. 257с.
Шишмарев Ю.Е., Емцева Е.Д., Солодухин К.С. Дискретная математика: Сборник задач. ч.1. – Владивосток: ВГУЭС, 2000. 98с.
Интернет-ресурсы:
http://school-collection.edu.ru/catalog/searchКарпова И.В. Занимательная дискретная математика /
http://www.matburo.ru/st_subject.php?p=dmНаглядный материал
Презентации к лекциям с иллюстрациями, схемами, примерами.
Методические рекомендации к практическим работам;
Методические рекомендации к самостоятельной внеаудиторной работе;
Практические работы;
Раздаточный материал.
Технические средства
Мультимедийный проекционный комплект
Колонки
РАБОЧИЕ МЕСТА СТУДЕНТОВ
Наименование (указать характеристики и параметры) количество примечание
Системный блок 16 Depo (Neos) CPU LGA775 Pentium Dual-Core E2200(2,2gHz), ОЗУ 1GB, video(intel 82945G 128mb),6USB, 1COM, 1LAN, 1VGA, 1LPT, audio, HDD 80GB.
Клавиатура 16 Depo Computers KWD-820
манипулятор мышь 16 Depo Computers MO-A133PS00X
устройство отображения информации (монитор) 16 Aser AL1716F(Диагональ 17", Время отклика 5ms, контраст 800:1, яркость 300cd/m2 TCO'03/ MPR|| )