- •Методические указания и задания
- •Задание на лабораторную работу
- •Способы задания множеств. Операции над множествами. Основные соотношения алгебры множеств
- •Теоретическая справка
- •Способы задания множеств
- •Операции над множествами
- •Основные законы алгебры множеств:
- •Задание к лабораторной работе.
- •Контрольные вопросы.
- •Отношения на множествах
- •Теоретическая справка
- •Способы задания отношений
- •Свойства бинарных отношений
- •Функциональные отношения
- •Например:
- •Задание к лабораторной работе
- •Основные понятия комбинаторики
- •Правило произведения Теоретико – множественная формулировка правила произведения
- •Комбинаторная формулировка правила произведения
- •Сложный выбор объектов
- •Соединения без повторений
- •Перестановки
- •Размещения из n элементов по m
- •Решение:
- •Сочетания
- •Свойства сочетаний
- •Соединения с повторениями
- •Размещения с повторениями
- •Сочетания с повторениями
- •Формулы пересчета для основных видов комбинаторных соединений
- •Принцип включения- исключения
- •Частные случаи формулы включений и исключений
- •Задача о беспорядках
- •Задача o встречах
- •Перестановки без фиксированных пар
- •Распределения объектов по ячейкам
- •Распределение одинаковых объектов
- •Вместимость ячеек задана
- •Распределение различных объектов по ячейкам с учётом их порядка в различных ячейках Вместимость ячеек неограниченна, ячейки могут быть пустыми
- •Вместимость ячеек неограниченна, ячейки не могут быть пустыми
- •Задания к лабораторной работе
- •Вариант №1.
- •Вариант №2.
- •Вариант №3.
- •Вариант №4.
- •Вариант №5.
- •Вариант №6.
- •Вариант №7.
- •Вариант №8.
- •Вариант №9.
- •Вариант №10.
- •Вариант №11.
- •Вариант №12.
- •Вариант №13.
- •Вариант №14.
- •Вариант №15.
- •Вариант №16.
- •Вариант №17.
- •Вариант №18.
- •Вариант №19.
- •Вариант №20.
- •Вариант №21.
- •Вариант №22.
- •5.Сколькими способами можно переставить буквы в слове «тартар», чтобы одинаковые буквы не шли друг за другом? Вариант №23.
- •Вариант №24.
- •Вариант №25.
- •Вариант №26.
- •Вариант №27.
- •Вариант №28.
- •Вариант №29.
- •Вариант №30.
- •Контрольные вопросы
- •8. Сформулировать общую постановку задачи распределения объектов по ячейкам.
- •Булевы функции. Законы алгебры логики. Аналитические способы описания. Полные системы функций
- •Теоретическая справка Определение функции алгебры логики
- •Табличный способ представления фал
- •Графическое представление фал
- •Функции алгебры логики одного аргумента
- •Функции алгебры логики двух аргументов
- •Элементарные функции алгебры логики
- •Условные приоритеты булевых функций
- •Выражение одних элементарных функций через другие
- •Аналитическая запись фал
- •Дизъюнктивная нормальная форма (днф)
- •Дизъюнктивная совершенная нормальная форма (дснф)
- •Алгоритм перехода от табличного задания функции к дснф
- •Конъюнктивная совершенная нормальная форма
- •Алгоритм построения конъюнктивной совершенной нормальной формы
- •Полные системы фал
- •Задание к лабораторной работе
- •Контрольные вопросы
- •Методы минимизации функций алгебры логики.
- •Теоретическая справка Основные определения
- •Минимизация фал на кубе
- •Метод Квайна минимизации булевых функций
- •Метод Мак-Класки минимизации булевых функций
- •Графический метод минимизации: карты Карно и диаграммы Вейча
- •Основные принципы построения карт Карно
- •Задание к лабораторной работе
- •Алгоритм генерации варианта
- •Контрольные вопросы
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Методические указания и задания
к лабораторным работам
по курсу “Основы дискретной математики“, часть I
(для студентов специальности 080407 “Компьютерный эколого-экономический мониторинг”)
Утверждено на заседании кафедры прикладной математики и информатики протокол № 4 от 19.12.2005
Донецк – 2005
УДК 518.551071
Методические указания и задания к лабораторным работам по курсу “Основы дискретной математики” (для студентов специальности 080407 “Компьютерный эколого-экономический мониторинг”) / сост.: И.А. Назарова, А. А. Григорюк – Донецк: ДонНТУ, 2005. - 74с.
Приведены теоретические сведения, методические рекомендации, контрольные вопросы и задания для выполнения лабораторных работ по следующим разделам дискретной математики:
комбинаторика;
булева алгебра;
теория множеств и отношений.
Составители: Назарова И. А., ст. преп.
Григорюк А. А., асс.
Рецензент: Теплинский С. В., к.т.н., доц.
Лабораторная работа № 1
Системы счисления
Цель работы: приобретение практических навыков перевода из одной системы счисления в другую, выполнение арифметических операций в различных системах счисления.
Теоретическая справка
Правила перевода из одной с.с. в другую:
Дано число x, представленное в системе счисления с основаниемa. Перевод в систему с основанием в:
целая часть:
Следует делить x(a) на в(a) до тех пор, покаx(a)>в(a)и записывать остатки от деления справа на лево. Полученное из этих остатков число и будетx(в);
дробная часть:
Следует умножать дробную часть x(a) на в(a), записывать последовательно полученную целую часть этого умножения на дробную часть числаx(в), потом обнулять эту целую часть и повторять процесс снова.
Например:
Перевести 12,35(10) в (2)
12 mod 2=0;
6 mod 2=0;
3 mod 2=1;
1 mod2=1;
Итак, 12(10)=1100(2);
0,35*2
0,70*2
1,40*2
0,80*2
1,60*2
……….
Этот процесс может продолжаться до бесконечности.
Итак, 0,35(10)=0,0101…(2)
Между с.с. с основаниями 2, 8, 16 существует особая связь.
Чтобы перевести число из двоичной с.с. в восьмиричную цифру, и записывать полученные цифры в такой же последовательности, как стояли соответствующие им тройки.
Для перевода в шестнадцатиричную с.с. надо брать по 4 разряда и поступать аналогичным образом.
Обратный перевод основан на тех же принципах.
Двоично-десятичная запись строится путём перевода этим способом «10» числа «2» с.с.
Задание на лабораторную работу
Сформировать два десятичных числа XиYследующим образом. ЧислоX– смешанная десятичная дробь, целая часть которой равна дате рождения студента, дробная часть – номер месяца рождения студента. ЧислоY– смешанная десятичная дробь, целая часть которой – номер месяца рождения, дробная часть – последние две цифры года рождения студента плюс порядковый номер студента в журнале по модулю 100.
Перевести числа XиYиз десятичной в двоичную, восьмиричную и шестнадцатиричную системы счислений. Точность полученного числа не менее исходного.
Составить таблицы сложения, вычитания, умножения в 2, 8, 16 системах счислений.
Выполнить сложение, вычитание, умножение чисел XиYв перечисленных системах счисления, используя результаты пункта 3.
Контрольныевопросы.
Что такое система счисления?
Какая система называется позиционной?
Дайте определение оснований системы счисления?
Что такое развёрнутая запись числа?
Правила перевода из одной системы счисления в другую для целых и дробных чисел?
Связь между двоичной и восьмиричной (шестнадцатиричной) системами счислений?
Что такое двоично-десятичный код?
Лабораторная работа № 2