Дискретная математика (190,00 руб.)

Стр.1

Стр.2

Стр.3

Стр.4

Стр.77

Министерство образования и науки Российской Федерации Федеральное агентство по образованию Ярославский государственный университет им. П. Г. Демидова Университетский колледж Дискретная математика Практикум Рекомендовано Научно-методическим советом университета для студентов, обучающихся по специальности Автоматизированные системы обработки информации и управления (по отраслям) Ярославль 2010 1

Стр.1

УДК 517.929 ББК В 174я72 Д 48 Рекомендовано Редакционно-издательским советом университета в качестве учебного издания. План 2009/10 года Рецензент педагогический совет Университетского колледжа Составитель И. А. Сурикова Д 48 Дискретная математика: практикум / сост. И. А. Сурикова; Яросл. гос. ун-т им. П. Г. Демидова. – Ярославль : ЯрГУ, 2010. – 76 с. Предназначен для студентов, обучающихся по специальности 230103.51 Автоматизированные системы обработки информации и управления (по отраслям) (дисциплина «Дискретная математика», блок ОПД), очной формы обучения. УДК 517.929 ББК В 174я72  Ярославский государственный университет им. П. Г. Демидова, 2010 Учебное издание Дискретная математика Практикум Составитель Сурикова Ирина Александровна Редактор, корректор И. В. Бунакова Верстка Е. Л. Шелехова Подписано в печать 04.02.10. Формат 6084 1/16. Бум. офсетная. Гарнитура "Times NewRoman". Усл. печ. л. 4,42. Уч.-изд. л. 2,63. Тираж 50 экз. Заказ Оригинал-макет подготовлен в редакционно-издательском отделе Ярославского государственного университета им. П. Г. Демидова. Отпечатано на ризографе. Ярославский государственный университет им. П. Г. Демидова. 150000, Ярославль, ул. Советская, 14. 2

Стр.2

Пояснительная записка Практикум по дискретной математике предназначен для самостоятельной работы студентов. При изучении учебной дисциплины «Дискретная математика» у студентов формируется базовый уровень знаний для освоения других общепрофессиональных и специальных дисциплин. Данные материалы используются при изучении таких дисциплин, как «Основы алгоритмизации и программирования», «Архитектура ЭВМ и вычислительных систем», «Базы данных», «Теория вероятностей и математическая статистика», «Математические методы», «Технология разработки программных продуктов», «Разработка и эксплуатация удаленных баз данных», «Пакеты прикладных программ». Дискретная математика является фундаментом математической кибернетики. Аппарат дискретной математики необходим при создании и эксплуатации современных ЭВМ, средств передачи и обработки информации, автоматизированных систем управления и проектирования; поэтому знание основ данной дисциплины абсолютно необходимо для современного специалиста в области информатики и вычислительной техники. В результате изучения дисциплины студент должен знать: – аппарат алгебры логики и теорию булевых функций; – основы теории множеств; – логику предикатов и бинарных отношений; – алгебру подстановок; – основы алгебры вычетов; – простейшие криптографические шифры; – метод математической индукции; – методику генерирования основных комбинаторных объектов; – основы теории графов и теории автоматов; уметь: – строить таблицы истинности для формул логики и упрощать формулы логики; – представлять булевы функции в виде формул заданного типа, проверять множество булевых функций на полноту; 3

Стр.3

– выполнять операции над множествами, применять аппарат теории множеств для решения задач; – выполнять операции над предикатами, записывать области истинности предикатов, формализовывать предложения с помощью логики предикатов; – исследовать бинарные отношения на заданные свойства; – выполнять операции над подстановками; – выполнять операции в алгебре вычетов; – применять простейшие криптографические шифры; – доказывать утверждения с помощью метода математической индукции; – генерировать основные комбинаторные объекты; – находить характеристики графов, выделять их структурные особенности, исследовать на заданные свойства, строить для них структурные представления заданных типов; – строить автоматы с заданными свойствами. 4

Стр.4

Оглавление Пояснительная записка ....................................................................................... 3 Раздел 1. Формулы логики .............................................................................. 5 Основные логические операции ........................................................................ 5 Дизъюнктивная и конъюнктивная нормальные формы ................................. 8 Законы логики ...................................................................................................... 9 Упражнения ....................................................................................................... 10 Раздел 2. Булевы функции ............................................................................. 11 Совершенная ДНФ ........................................................................................... 11 Совершенная КНФ ............................................................................................ 12 Сокращенные ДНФ ........................................................................................... 12 Операция двоичного сложения. Многочлен Жегалкина .............................. 15 Важнейшие замкнутые классы. Теорема Поста ............................................. 18 Упражнения ....................................................................................................... 20 Раздел 3. Основы теории множеств ............................................................. 23 Упражнения ....................................................................................................... 25 Раздел 4. Предикаты. Бинарные отношения ............................................. 26 Упражнения ....................................................................................................... 28 Раздел 5. Алгебра подстановок ..................................................................... 30 Упражнения ....................................................................................................... 33 Раздел 6. Основы алгебры вычетов и их приложение к простейшим криптографическим шифрам ......................................................... 34 Шифрование ....................................................................................................... 35 Упражнения ....................................................................................................... 37 Раздел 7. Алфавитное кодирование ............................................................. 38 Упражнения ....................................................................................................... 40 Раздел 8. Метод математической индукции .............................................. 41 Упражнения ....................................................................................................... 42 Раздел 9. Алгоритмическое перечисление (генерирование) комбинаторных объектов ................................................................ 42 Упражнения ....................................................................................................... 45 Раздел 10. Основы теории графов ................................................................ 45 Неориентированные графы .............................................................................. 46 Ориентированные графы .................................................................................. 56 Упражнения ....................................................................................................... 61 Раздел 11. Элементы теории автоматов ..................................................... 69 Упражнения ....................................................................................................... 72 Рекомендуемая литература ........................................................................... 75 77

Стр.77