Файл: Методические указания к выполнению контрольной работы по дисциплине Дискретная математика для обучающихся 2 курса.doc
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 25.10.2023
Просмотров: 78
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Варианты заданий и методические указания
к выполнению контрольной работы по дисциплине
«Дискретная математика» для обучающихся __2___ курса
ВАРИАНТЫ КОНТРОЛЬНЫХ РАБОТ
Выбор варианта по последней цифре номера зачетной книжке
Выбор варианта задания по последней цифре номера зачетной книжки обучающегося.
Задание 1.
Решить задачу.
В-1. На школьный вечер танцев собрались ребята 9-х, 10-х и 11-х классов. Вести хоровод приглашаются 10 школьников. Сколькими способами можно составить хоровод при условии участия в нем хотя бы одного одиннадцатиклассника? (55)
В-2. На студенческий вечер собрались юноши и девушки 8 факультетов университета (в том числе математического и филологического). Для исполнения народных танцев приглашаются 10 студентов. Сколькими способами можно выбрать эту десятку при условии участия в ней хотя бы одного студента математического и хотя бы одного студента филологического факультета? (6435)
В-3. На Всемирный фестиваль молодежи прибыла молодежь пяти континентов мира. Возникла необходимость организовать делегацию из восьми представителей разных стран для оглашения клятвы борцов за мир. Сколькими способами можно было образовать делегацию при условии участия в ней представителей всех континентов? (35)
В-4. В гастрономе имеются конфеты трех наименований. Конфеты упакованы в коробки трех видов – для каждого наименования своя коробка. Сколькими способами можно заказать набор из пяти коробок? (21)
В-5. Сколько автомашин модно обеспечить 6-значными номерами? (106)
В-6. Сколько 5-значных чисел можно образовать из цифр 0 и 1? (16)
В-7. В одном государстве (сказочном) не найдется двух человек, у которых оказался бы одинаковый состав зубов: либо у них разное число зубов, либо зубов нет в разных местах. Оцените наибольшую численность населения в этом государстве, если максимальное число зубов у одного человека 32. (Не больше 232)
В-8. Сколькими способами можно отослать 6 писем разным адресатам, если их будут разносить 3 курьера и заранее известно, какому курьеру какое достанется письмо? (729)
В-9. Четыре студента сдают экзамен. Сколько может быть вариантов распределения оценок, если известно, что так или иначе все они экзамены сдали? (81)
В-0. Три парня и три девушки решили после окончания школы поступить на работу в своем родном городе. В городе имеются 3 завода, на которые берут только мужчин, 2 – где нужны женщины и 2 – которые принимают на работу и мужчин и женщин. Сколькими способами пять выпускников могут распределиться по заводам города? (2000)
Задание 2.
В произвольном связном графе
у которого ребра 
взвешены числами 
, найти:а) минимальное остовное дерево с помощью алгоритма Краскала;
б) минимальное остовное дерево с помощью алгоритма Прима;
в) составить матрицу смежности и матрицу инцидентности;
г) вычислить радиус и диаметр графа, указать центральные и периферийные вершины;
д) построить дополнение для данного графа;
е) найти все инварианты графа (вектор степеней графа, число внешней устойчивости, число внутренней устойчивости, хроматическое число, число компонент связности, число Хадвигера);
Задание 3.
Составить таблицы истинности формул.
В1.
.В2.
.В3.
.В4.
.В5.
.В6.
.В7.
.В8.
.В9.
.В0.
.Задание 4.
Проверить, будут ли эквивалентны следующие формулы с помощью эквивалентных преобразований.
В1.
и 
.В2.
и 
.В3.
и
.В4.
и .В5.
и 
.В6.
и 
.В7.
и 
.В8.
и 
В9.
и 
.В10.
и 
.Задание 5.
С помощью эквивалентных преобразований приведите формулу к ДНФ, КНФ, СДНФ, СКНФ. Проверьте правильность полученного результата, используя табличный способ построения этих форм.
В1.
.В2.
.В3.
.В4.
.В5.
.В6.
.В7.
.В8.
.В9.
.В0.
.
Задание 6. Построить детерминированный конечный автомат, распознающий язык
В-1.
– множество слов, имеющих подслово ddcba в алфавите 
В-2.
– множество слов, начинающихся буквой a и заканчивающихся буквой с в алфавите В-3.
– множество слов, в которых буква d встречается ровно 3 раза в алфавите В-4.
– множество слов, содержащих четное количество букв b в алфавите В-5.
– множество слов, в которых буква a встречается 2 раза, а буква c – 1 раз в алфавите В-6.
– множество слов, в которых каждая цифра кратна 3 в алфавите 
В-7.
– множество слов, в которых расстояние между буквой c и ближайшей буквой d не больше 3 в алфавите В-8.
– множество слов, у которых вторая и предпоследняя буква – d в алфавите В-9.
– множество слов, у которых вторая и предпоследняя буква – d в алфавите В-10.
– множество симметричных слов длины 6 в алфавите
Задание 7. Построить конечные автоматы, распознающие объединение, пересечение, разность языков, заданных автоматами
и 
| Номер варианта | | |
| В-1. |  |  |
| В-2. |  |  |
| В-3. |  |  |
| В-4. | |  |
| В-5. |  | |
| В-6. | | |
| В-7. |  |  |
| В-8. |  |  |
| В-9. |  |  |
| В-0. |  | |