Сборник контрольных работ по учебной дисциплине Дискретная математика для специальности 09.02.05
МЕТОДИЧЕСКАЯ РАЗРАБОТКА ДЛЯ ПРЕПОДАВАТЕЛЕЙ
Ульяновский авиационный колледж
МАТЕМАТИЧЕСКИЙ И ОБЩИЙ ЕСТЕСТВЕННОНАУЧНЫЙ ЦИКЛ
Дискретная математика
Контрольные работы
для специальности СПО базовой подготовки
09.02.05 Прикладная информатика (по отраслям)
Ульяновск
2016
ДИСКРЕТНАЯ МАТЕМАТИКА. КОНТРОЛЬНЫЕ РАБОТЫ : метод. указания для преподавателей. Специальности 09.02.05 / Г. А. Камышова. – Ульяновск: УАвиаК, 2011.
Методические указания содержат 5 контрольных работ. Перед каждой контрольной работой имеется структура индивидуального варианта данной работы, время выполнения, оценивание заданий, критерии отметок, примерный вариант решения и задания по вариантам.
Одобрено и утверждено на заседании ЦМК программирования и вычислительной техники
(протокол № 2 от 15.09.2010 г.)
Ред.2, изм. 15%
(протокол №6 от 13.01.2016г.)
Рецензенты:
Афиногенова В.П.
Преподаватель компьютерных дисциплин высшей категории Ульяновского авиационного колледжа
Харитонова Е.В.
Старший преподаватель высшей математики Института авиационных технологий и управления УлГТУ
Отзывы и предложения направлять по адресу:
432067, г. Ульяновск, проспект Созидателей, 13
телефон (8-422) 20-56-71, 20-09-20
факс: 54-54-66
E-mail: [ Cкачайте файл, чтобы посмотреть ссылку ]
Содержание
ВВЕДЕНИЕ 5
КОНТРОЛЬНЫЕ РАБОТЫ 6
КР № 1 Множества и отображения 6
КР № 2 Формулы логики и булевы функции 10
КР № 3 Комбинаторные конфигурации 14
КР № 4 Предикаты. Бинарные отношения 17
КР № 5 Основы теории графов 20
ИСТОЧНИКИ ЛИТЕРАТУРЫ 27
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
Основная цель создания контрольно – оценочных средств по рубежному контролю заключается в определении качества знаний и умений студентов по окончании каждого раздела учебной дисциплины (контрольные работы по разделам), их соответствие требованиям ФГОС СПО.
Согласно требованиям к результатам освоения учебной дисциплины «Дискретная математика» обучающийся:
ДОЛЖЕН УМЕТЬ:
применять методы дискретной математики;
выполнять операции над множествами, применять аппарат теории множеств для решения задач;
выполнять операции над отображениями и подстановками;
строить таблицы истинности для формул логики;
представлять булевы функции в виде формул заданного типа;
определять полноту множества функций
определять вид комбинаторных объектов;
генерировать основные комбинаторные объекты;
выполнять операции над предикатами;
выполнять операции в алгебре вычетов;
применять простейшие криптографические шифры для шифрования текстов;
выполнять доказательство методом математической индукции;
исследовать бинарные отношения на заданные свойства;
представлять графы в памяти ЭВМ;
находить характеристики графов;
применять алгебру высказываний к синтезу и анализу схем дискретного действия;
строить бесконтактные схемы из функциональных элементов
ДОЛЖЕН ЗНАТЬ:
основные понятия теории множеств, теоретико-множественные операции и их связь с логическими операциями;
элементы теории отображений и алгебры подстановок;
логические операции, формулы логики, законы алгебры логики;
основные классы функций, полноту множеств функций, теорему Поста;
логику предикатов, бинарные отношения и их виды;
основы алгебры вычетов и их приложение к простейшим криптографическим шифрам;
метод математической индукции;
алгоритмическое перечисление основных комбинаторных объектов;
основы теории графов;
элементы теории автоматов.
Задания рубежного контроля (контрольных работ) выполняются в любой последовательности в течение 45 минут, из которых 5 минут отводится на вводное инструктирование по порядку оформления, правилам выполнения заданий и 40 минут отводится для ответов на задания выполняемого варианта. Баллы, полученные за выполненные задания, суммируются и выставляется отметка.
Результаты рубежного контроля (контрольных работ) используются для оценки достижений обучающихся.
УЧЕБНАЯ ДИСЦИПЛИНА «ДИСКРЕТНАЯ МАТЕМАТИКА»
Специальность 09.02.05
Базовая подготовка
КОНТРОЛЬНАЯ РАБОТА № 1
МНОЖЕСТВА И ОТОБРАЖЕНИЯ
Цель: Проверка и закрепление знаний и умений по применению операций над множествами и построению диаграмм Эйлера-Венна; Проверить и закрепить знания и навыки по решению уравнений с подстановками, по решению задач шифрования простейшими криптографическими шифрами; проверка и закрепление знаний и умений работы с простейшими криптографическими шифрами.
Проверяемые умения и знания:
Структура индивидуального варианта:
№
Наименование темы
1
ИЗОБРАЖЕНИЕ МНОЖЕСТВА НА ДИАГРАММЕ ЭЙЛЕРА-ВЕННА
Изображение на диаграмме Эйлера – Венна заданного множества, выполняя построение по действиям, отмечая на каждом шаге полученное множество с помощью штриховки определенного вида.
2
ДЕЙСТВИЯ НАД МНОЖЕСТВАМИ
Перечисление всех элементов множества, которое является декартовым произведением или декартовой степенью двух или трех указанных множеств.
3
РЕШЕНИЕ УРАВНЕНИЙ С ПОДСТАНОВКАМИ
Решение уравнений с подстановками вида axb = c, где a, b, c – заданные подстановки, x – искомая подстановка.
4
ПРОСТЕЙШИЕ КРИПТОГРАФИЧЕСКИЕ ШИФРЫ
Шифрование сообщений с помощью перестановочного шифра или шифра замены.
Время выполнения: 45 минут
Оценивание заданий: по 1,7 балла каждое
Критерии отметок: «5» ( 4,8
«4» 3,8 – 4,7
«3» 2,8 – 3,7
«2» 1,8 – 2,7
«1» 0 – 1,7
ПРИМЕЧАНИЕ: 1. Не разрешается пользоваться справочниками, таблицами, выходить из аудитории.
2. Отметка ставится только на основании правильных решений.
УЧЕБНАЯ ДИСЦИПЛИНА «ДИСКРЕТНАЯ МАТЕМАТИКА»
Специальность 09.02.05
Базовая подготовка
КОНТРОЛЬНАЯ РАБОТА № 1
МНОЖЕСТВА И ОТОБРАЖЕНИЯ
ВАРИАНТ № 1.
1. Изобразить на диаграмме Эйлера – Венна множество A ( (B ( (A ( C))
2. Перечислить все элементы множества А(В, если А={1,4,-5} B={7,9,-1}
3. Решить уравнение с подстановками вида axb=c, где a, b, c – заданные подстановки:
a = 13 EMBED Equation.3 1415 b = 13 EMBED Equation.3 1415 c = 13 EMBED Equation.3 1415
4. Зашифровать сообщение «Контрольная работа» с помощью перестановочного шифра с ключом a=13 EMBED Equation.3 1415
ВАРИАНТ № 2.
1. Изобразить на диаграмме Эйлера – Венна множество (A \ B)\C)
2. Перечислить все элементы множества В(A, если А={1,4,-5} B={7,9,-1}
3. Решить уравнение с подстановками вида ахв=с, где а, в, с – заданные подстановки:
a = 13 EMBED Equation.3 1415 b = 13 EMBED Equation.3 1415 c = 13 EMBED Equation.3 1415
4. Зашифровать сообщение «Контрольная работа» с помощью шифра замены с ключом 3
ВАРИАНТ № 3.
1. Изобразить на диаграмме Эйлера – Венна множество (A \ B) ( (A \ C)
2. Перечислить все элементы множества А(В(C, если А={1,4,-5} B={7,9,-1} C={0,2}
3. Решить уравнение с подстановками вида ахв=с, где а, в, с – заданные подстановки:
a = 13 EMBED Equation.3 1415 b = 13 EMBED Equation.3 1415 c = 13 EMBED Equation.3 1415
4. Зашифровать сообщение «Контрольная работа» с помощью перестановочного шифра с ключом a=13 EMBED Equation.3 1415
ВАРИАНТ № 4.
1. Изобразить на диаграмме Эйлера – Венна множество (A \ C) \ B
2. Перечислить все элементы множества C(В(A, если А={1,4,-5} B={7,9,-1} C={0,2}
3. Решить уравнение с подстановками вида ахв=с, где а, в, с – заданные подстановки.
a = 13 EMBED Equation.3 1415 b = 13 EMBED Equation.3 1415 c = 13 EMBED Equation.3 1415
4. Зашифровать сообщение «Контрольная работа» с помощью шифра замены с ключом 4
ВАРИАНТ № 5.
1. Изобразить на диаграмме Эйлера – Венна множество A ( (B ( C)
2. Перечислить все элементы множества C(В(A, если А={1,-5} B={7,6,9} C={0,2}
3. Решить уравнение с подстановками вида ахв=с, где а, в, с – заданные подстановки:
a = 13 EMBED Equation.3 1415 b = 13 EMBED Equation.3 1415 c = 13 EMBED Equation.3 1415
4. Зашифровать сообщение «Контрольная работа» с помощью перестановочного шифра с ключом a=13 EMBED Equation.3 1415
ВАРИАНТ № 6.
1. Изобразить на диаграмме Эйлера – Венна множество A \ (A ( B)
2. Перечислить все элементы множества А(В(C, если А={1,4} B={9,-1} C={0,2}
3. Решить уравнение с подстановками вида ахв=с, где а, в, с – заданные подстановки:
a = 13 EMBED Equation.3 1415 b = 13 EMBED Equation.3 1415 c = 13 EMBED Equation.3 1415
4. Зашифровать сообщение «Контрольная работа» с помощью шифра замены с ключом 5.
УЧЕБНАЯ ДИСЦИПЛИНА «ДИСКРЕТНАЯ МАТЕМАТИКА»
Специальность 09.02.05
Базовая подготовка
КОНТРОЛЬНАЯ РАБОТА № 2
ФОРМУЛЫ ЛОГИКИ И БУЛЕВЫ ФУНКЦИИ
Цель: Проверка и закрепление знаний и умений: - по представлению сложных высказываний через простые с помощью формул логики; - по построению таблиц истинности, построению СДНФ; - по нахождению минимальной ДНФ; - по определению полноты системы булевых функций.
Проверяемые умения и знания:
Структура индивидуального варианта:
№
Наименование темы
1
ФОРМУЛЫ ЛОГИКИ
Выделение элементарных высказываний в составном высказывании, обозначение их буквами, подчеркивание логических связок, запись составного высказывания в виде формулы.
2
ПОСТРОЕНИЕ ТАБЛИЦЫ ИСТИННОСТИ И СДНФ
Построение таблицы истинности и совершенной дизъюнктивной нормальной формы (СДНФ) по заданной функции трёх переменных f(x1,x2,x3)
3
НАХОЖДЕНИЕ МИНИМАЛЬНОЙ ДНФ
Нахождение минимальной ДНФ для функции трёх переменных f(x1,x2,x3).
4
ПОЛНОТА СИСТЕМЫ ФУНКЦИЙ
Определение полноты системы функций разными методами.
Время выполнения: 45 минут
Оценивание заданий: по 1,7 балла каждое
Критерии отметок: «5» ( 4,8
«4» 3,8 – 4,7
«3» 2,8 – 3,7
«2» 1,8 – 2,7
«1» 0 – 1,7
ПРИМЕЧАНИЕ: 1. Не разрешается пользоваться справочниками, таблицами, выходить из аудитории.
2. Отметка ставится только на основании правильных решений.
УЧЕБНАЯ ДИСЦИПЛИНА «ДИСКРЕТНАЯ МАТЕМАТИКА»
Специальность 09.02.05
Базовая подготовка
КОНТРОЛЬНАЯ РАБОТА № 2
ФОРМУЛЫ ЛОГИКИ И БУЛЕВЫ ФУНКЦИИ
ВАРИАНТ № 1.
1. В составном высказывании выделить элементарные составляющие, обозначить их буквами, подчеркнуть логические связки и записать в виде формулы:
"если a>0 или b>0, то ab>0"
2. Задана функция от трёх переменных f(x1,x2,x3). По заданной функции построить таблицу истинности, совершенную дизъюнктивную нормальную форму (СДНФ):
f(x1,x2,x3)=(x1((x2(13 EMBED Equation.3 14153)) ((x2(x3)
4. Найти минимальную ДНФ для функции трёх переменных f(x1,x2,x3).
3. Определить, является ли полной система функций. Указать, какой метод для этого применялся: {x( y}
ВАРИАНТ № 2.
1. В составном высказывании выделить элементарные составляющие, обозначить их буквами, подчеркнуть логические связки и записать в виде формулы:
"данное число делится на 2 и делится на 3 или не делится на 6"
2. Задана функция от трёх переменных f(x1,x2,x3). По заданной функции построить таблицу истинности, совершенную дизъюнктивную нормальную форму (СДНФ):
f(x1,x2,x3)=(x1( (x2(13 EMBED Equation.3 14153)) ((x2(x3)
3. Найти минимальную ДНФ для функции трёх переменных f(x1,x2,x3).
4. Определить, является ли полной система функций. Указать, какой метод для этого применялся: {x(y}
ВАРИАНТ № 3.
1. В составном высказывании выделить элементарные составляющие, обозначить их буквами, подчеркнуть логические связки и записать в виде формулы:
"если ab(0 или a(0, то b(0"
2. Задана функция от трёх переменных f(x1,x2,x3). По заданной функции построить таблицу истинности, совершенную дизъюнктивную нормальную форму (СДНФ):
f(x1,x2,x3)=(x1 ( (x2(x3)) ( (x2(x3)
3. Найти минимальную ДНФ для функции трёх переменных f(x1,x2,x3).
4. Определить, является ли полной система функций. Указать, какой метод для этого применялся: {13 EMBED Equation.3 1415, x(y, x(y}
ВАРИАНТ № 4.
1. В составном высказывании выделить элементарные составляющие, обозначить их буквами, подчеркнуть логические связки и записать в виде формулы.
"Если я поеду на автобусе, то опоздаю на работу, или я воспользуюсь такси"
2. Задана функция от трёх переменных f(x1,x2,x3). По заданной функции построить таблицу истинности, совершенную дизъюнктивную нормальную форму (СДНФ):
f(x1,x2,x3)=(x2 ( (x1(x3)) ( (x1(x2)
3. Найти минимальную ДНФ для функции трёх переменных f(x1,x2,x3).
4. Определить, является ли полной система функций. Указать, какой метод для этого применялся: {13 EMBED Equation.3 1415, x(y}
ВАРИАНТ № 5.
1. В составном высказывании выделить элементарные составляющие, обозначить их буквами, подчеркнуть логические связки и записать в виде формулы:
" если ab=0 или a=0, то b=0"
2. Задана функция от трёх переменных f(x1,x2,x3). По заданной функции построить таблицу истинности, совершенную дизъюнктивную нормальную форму (СДНФ):
f(x1,x2,x3)=(x2 ( (x1(x3)) ( (x1(x2)
3. Найти минимальную ДНФ для функции трёх переменных f(x1,x2,x3).
4. Определить, является ли полной система функций. Указать, какой метод для этого применялся: {13 EMBED Equation.3 1415, x(y }
ВАРИАНТ № 6.
1. В составном высказывании выделить элементарные составляющие, обозначить их буквами, подчеркнуть логические связки и записать в виде формулы.
"Давление падает и система не работает"
2. Задана функция от трёх переменных f(x1,x2,x3). По заданной функции построить таблицу истинности, совершенную дизъюнктивную нормальную форму (СДНФ):
f(x1,x2,x3)=(x2 ( (x1(x3)) ( (x1(x2)
3. Найти минимальную ДНФ для функции трёх переменных f(x1,x2,x3).
4. Определить, является ли полной система функций. Указать, какой метод для этого применялся: {0,1, x(y, x(y}
УЧЕБНАЯ ДИСЦИПЛИНА «ДИСКРЕТНАЯ МАТЕМАТИКА»
Специальность 09.02.05
Базовая подготовка
КОНТРОЛЬНАЯ РАБОТА № 3
КОМБИНАТОРНЫЕ КОНФИГУРАЦИИ
Цель: Проверить и закрепить знания и навыки по решению комбинаторных задач, проверить и закрепить знания и навыки по созданию генераторов комбинаторных объектов.
Проверяемые умения и знания:
Структура индивидуального варианта:
№
Наименование темы
1
КОМБИНАТОРНЫЕ ОБЪЕКТЫ БЕЗ ПОВТОРЕНИЙ
Решение задач, содержащих комбинаторные объекты без повторений.
2
КОМБИНАТОРНЫЕ ОБЪЕКТЫ С ПОВТОРЕНИЯМИ
Решение задач, содержащих комбинаторные объекты с повторениями.
3
ГЕНЕРАТОР КОМБИНАТОРНЫХ ОБЪЕКТОВ
Выписывание результатов работы генератора сочетаний или генератора перестановок (без повторения).
Время выполнения: 45 минут
Оценивание заданий: по 1,7 балла каждое
Критерии отметок: «5» ( 4,8
«4» 3,8 – 4,7
«3» 2,8 – 3,7
«2» 1,8 – 2,7
«1» 0 – 1,7
ПРИМЕЧАНИЕ: 1. Не разрешается пользоваться справочниками, таблицами, выходить из аудитории.
2. Отметка ставится только на основании правильных решений.
УЧЕБНАЯ ДИСЦИПЛИНА «ДИСКРЕТНАЯ МАТЕМАТИКА»
Специальность 09.02.05
Базовая подготовка
КОНТРОЛЬНАЯ РАБОТА № 3
КОМБИНАТОРНЫЕ КОНФИГУРАЦИИ
ВАРИАНТ № 1.
Сколько имеется четырехзначных чисел, у которых каждая следующая цифра меньше предыдущей?
Сколько всего существует различных показаний n приборов по m показателям?
Выписать результаты работы генератора перестановок для n=3.
ВАРИАНТ № 2.
На собрании должны выступить четыре человека А, В, С, D. Сколькими способами их можно разместить в списке ораторов, если В не может выступить до того момента, пока не выступит А?
Сколько всего существует различных восьмизначных двоичных чисел?
Выписать результаты работы генератора сочетаний для n=5, k=3.
ВАРИАНТ № 3.
В некоторых видах спортивных соревнований исходом является определение участников, занявших 1-е, 2-е и 3-е места. Сколько всего возможно различных исходов, если в соревнованиях участвуют 80 человек.
Сколько всего существует перестановок из слова "Windows"?
Выписать результаты работы генератора перестановок для n=4.
ВАРИАНТ № 4.
Сколько имеется пятизначных чисел, у которых каждая следующая цифра больше предыдущей?
В магазине 5 сортов тульских пряников. Купить нужно 20 штук любых сортов или одного сорта. Сколько всего существует различных вариантов покупки?
Выписать результаты работы генератора сочетаний для n=5, k=2.
ВАРИАНТ № 5.
На собрании должны выступить пять человек А,В,С,D,E. Сколькими способами их можно разместить в списке ораторов, если D не может выступить до того момента, пока не выступит B?
Сколькими способами можно рассадить n вновь прибывших гостей среди m гостей, уже сидящих за круглым столом?
Выписать результаты работы генератора сочетаний для n=5, k=4.
ВАРИАНТ № 6.
В некоторых видах спортивных соревнований исходом является определение участников, занявших 1-е, 2-е и 3-е места. Сколько всего возможно различных исходов, если в соревнованиях участвуют 8 человек.
Трое детей собрали в саду 63 яблока и распределили их между собой. Сколькими способами можно было распределить яблоки между детьми?
Выписать результаты работы генератора сочетаний для n=6, k=4.
УЧЕБНАЯ ДИСЦИПЛИНА «ДИСКРЕТНАЯ МАТЕМАТИКА»
Специальность 09.02.05
Базовая подготовка
КОНТРОЛЬНАЯ РАБОТА № 4
ПРЕДИКАТЫ. БИНАРНЫЕ ОТНОШЕНИЯ. ВЫЧЕТЫ
Цель: Проверка и закрепление знаний и умений по построению таблиц истинности для предикатов, по определению области истинности предикатов, по нахождению значений выражений с кванторными операциями, по представлению бинарных отношений различными способами, по определению свойств бинарных отношений, по определению отношений эквивалентности, проверить умение решать уравнения в классах вычетов.
Проверяемые умения и знания:
Структура индивидуального варианта
№
Наименование темы
1
ПРЕДИКАТЫ
Определение области истинности и построение таблицы значений предиката.
2
КВАНТОРНЫЕ ОПЕРАЦИИ
Решение задач с кванторами всеобщности и кванторами существования.
3
БИНАРНЫЕ ОТНОШЕНИЯ
Задание бинарного отношения, определение свойств бинарного отношения.
4
ВЫЧЕТЫ ПО МОДУЛЮ m
Решение уравнений в алгебре вычетов; определение разрешимости уравнений в алгебре вычетов по модулю m
Время выполнения: 45 минут
Оценивание заданий: по 1,7 балла каждое
Критерии отметок: «5» ( 4,8
«4» 3,8 – 4,7
«3» 2,8 – 3,7
«2» 1,8 – 2,7
«1» 0 – 1,7
ПРИМЕЧАНИЕ: 1. Не разрешается пользоваться справочниками, таблицами, выходить из аудитории.
2. Отметка ставится только на основании правильных решений.
УЧЕБНАЯ ДИСЦИПЛИНА «ДИСКРЕТНАЯ МАТЕМАТИКА»
Специальность 09.02.05
Базовая подготовка
КОНТРОЛЬНАЯ РАБОТА № 4
ПРЕДИКАТЫ. БИНАРНЫЕ ОТНОШЕНИЯ. ВЫЧЕТЫ
ВАРИАНТ № 1.
Построить таблицу значений предиката R(x,y)="животное x входит в класс y" x(M1={кошка, лягушка, муха, слон, собака, комар} y(M2={земноводные, насекомые, млекопитающие} и определить область истинности.
Пусть дан предикат P(x)="x делится на 3 без остатка" x(N=множество натуральных чисел. Определить значение выражения (xP(x) и значение выражения (xP(x). Объяснить.
Задать бинарное отношение "быть строго меньше" с помощью матрицы, если М={1,2,3,4,5,6,7} и определить свойства бинарного отношения.
Решить уравнение в алгебре вычетов по модулю 7: 36х+8=16.
ВАРИАНТ № 2.
Построить таблицу значений предиката R(x,y,z)="x+y(z" x,y,z(M={1,2} и определить область истинности.
Пусть дан предикат P(x)="x делится на 3 без остатка" x({3,6,9,27}. Определить значение выражения (xP(x). Объяснить.
Задать бинарное отношение "быть делителем" с помощью фактор-множества, если М={1,2,3,4,5,6,7} и определить его свойства.
Решить уравнение в алгебре вычетов по модулю 5: 4х+3=15.
ВАРИАНТ № 3.
Определить область истинности предиката P(x)="предмет x является цветком" x(M M={роза, ваза, стол, ромашка, герань} и построить таблицу значений этого предиката.
Пусть даны предикаты P(x)="x четное число", Q(x)="x нечетное число" x(N=множество натуральных чисел. Определить значение выражения (x(P(x)(Q(x)). Объяснить.
Задать бинарное отношение "иметь общий делитель отличный от единицы" перечнем дуг на множестве М={1,2,3,4,5,6,7} и определить его свойства.
Решить уравнение в алгебре вычетов по модулю 3: 2х+8=13.
ВАРИАНТ № 4.
Определить область истинности предиката P(x,y)="x=y" x,y(M M={1,2,3} и построить таблицу значений этого предиката.
Пусть даны предикаты P(x)="x четное число", Q(x)="x делится на 4 без остатка"; x(N=множество натуральных чисел. Определить значение выражения (x(Q(x)( P(x)). Объяснить.
Задать с помощью графа бинарное отношение "иметь один и тот же остаток от деления на 3" на множестве М={1,2,3,4,5,6,7} и определить его свойства.
Решить уравнение в алгебре вычетов по модулю 2: 5х+10=13.
ВАРИАНТ № 5.
Определить область истинности предиката P(x,y)="город x является столицей y" x(M1={Ульяновск, Самара, Москва, Киев} y(М2={Россия, Беларусь, Украина, Германия} и построить таблицу значений этого предиката.
Пусть даны предикаты P(x)="x четное число", Q(x)="x нечетное"; x(N=множество натуральных чисел. Определить значение выражения (x(Q(x)( P(x)). Объяснить.
Задать с помощью матрицы бинарное отношение "быть не меньше" на множестве М={1,2,3,4,5,6,7} и определить его свойства.
Решить уравнение в алгебре вычетов по модулю 11: 10х+8=22.
ВАРИАНТ № 6.
Определить область истинности предиката R(x,y)="x является валютой страны y" x(M1={рубль, доллар, фунт стерлингов} y(M2={США, Россия, Украина, Беларусь} и построить таблицу значений этого предиката.
Пусть дан предикат P(x)="x четное число", x(М={1,2,3,4,5,6,7}. Определить значение выражения (x P(x). Объяснить.
Определить свойства бинарного отношения "быть делителем", определенного на множестве М, где М={1,2,3,4,5,6,7} и задать его перечнем дуг.
Решить уравнение в алгебре вычетов по модулю 13: 27х+15=44.
УЧЕБНАЯ ДИСЦИПЛИНА «ДИСКРЕТНАЯ МАТЕМАТИКА»
Специальность 09.02.05
Базовая подготовка
КОНТРОЛЬНАЯ РАБОТА № 5
ОСНОВЫ ТЕОРИИ ГРАФОВ
Цель: Проверка знаний основных определений по основам теории графов и умений по построению графов различных типов.
Проверяемые умения и знания:
Структура индивидуального варианта
№
Наименование темы
1
ОСНОВЫ ТЕОРИИ ГРАФОВ
Тестирование по определениям темы.
2
ЭЙЛЕРОВЫ ГРАФЫ
Выполнение заданий на построение эйлеровых графов.
3
ГАМИЛЬТОНОВЫ ГРАФЫ
Выполнение заданий на построение гамильтоновых графов.
4
ЦИКЛИЧЕСКИ СВЯЗНЫЕ ГРАФЫ
Выполнение заданий на построение циклически связных графов.
Время выполнения: 45 минут
Оценивание заданий: по 1,7 балла каждое
Критерии отметок: «5» ( 4,8
«4» 3,8 – 4,7
«3» 2,8 – 3,7
«2» 1,8 – 2,7
«1» 0 – 1,7
ПРИМЕЧАНИЕ: 1. Не разрешается пользоваться справочниками, таблицами, выходить из аудитории.
Отметка ставится только на основании правильных решений.
УЧЕБНАЯ ДИСЦИПЛИНА «ДИСКРЕТНАЯ МАТЕМАТИКА»
Специальность 09.02.05
Базовая подготовка
КОНТРОЛЬНАЯ РАБОТА № 5
ОСНОВЫ ТЕОРИИ ГРАФОВ
ВАРИАНТ № 1
1. Совокупность множеств V (точек) и Е (линий), между которыми определено отношение инцидентности, причем каждый элемент е из Е инцидентен ровно двум элементам v1 и v2 из множества V, называется . ..
неориентированным графом 3) мультиграфом
ориентированным графом 4) пустым графом
2. Граф, содержащий кратные ребра, называется . ..
гамильтонов
циклически связный
мультиграф
эйлеров
3. Граф, у которого множество вершин - пусто, называется . . .
неориентированным графом
ориентированным графом
пустым графом
мультиграфом
4. Конечная или бесконечная последовательность ребер, такая что каждые два соседних ребра имеют общую инцидентную вершину, причем каждое ребро встречается не более одного раза, называется ...
маршрутом 3) простой цепью
цепью 4) циклом
5. Конечная или бесконечная последовательность ребер, такая что каждые два соседних ребра имеют общую инцидентную вершину, причем каждое ребро встречается не более одного раза, любая вершина графа инцидентна не более чем двум его ребрам, а начальная вершина совпадает с конечной вершиной, называется .
маршрутом 3) циклом
цепью 4) простым циклом
6. Граф, который можно изобразить одним росчерком пера, причем процесс такого изображения начинается и заканчивается в одной точке, называется .. .
гамильтоновым
циклически связным
мультиграфом
эйлеровым
7. Нарисовать 2 эйлеровых графа (не менее 8 вершин).
8. Нарисовать 2 гамильтоновых графа (не менее 10 вершин), указать простой цикл, проходящий через все вершины графа, другим цветом или более жирно.
9. Нарисовать 2 циклически связных графа (не менее 8 вершин).
ВАРИАНТ № 2
1. Ребро S и вершина V(U) называются ..., если ребро S соединяет вершины V и U
смежными
инцидентами
связными
ориентированными
2. Последовательность ребер такая, что каждые два соседних ребра имеют общую инцидентную вершину, причем начальная вершина и конечная совпадают, называется ..
маршрутом
циклическим маршрутом
циклом
простым циклом
3. Совокупность множеств V (точек) и Е (линий), между которыми определено отношение инцидентности, причем каждый элемент е из Е инцидентен ровно двум элементам v1 и v2 из множества V, называется ...
мультиграфом
ориентированным графом
неориентированным графом
пустым графом
4. Граф, содержащий кратные ребра, называется ...
циклически связный
гамильтонов
эйлеров
мультиграф
5. Граф, содержащий простой цикл, проходящий через все вершины графа, называется ...
циклически связный
гамильтонов
эйлеров
мультиграф
6. Граф, содержащий направленные ребра, называется ...
неориентированным графом
ориентированным графом
мультиграфом
пустым графом
7. Нарисовать 2 эйлеровых графа (не менее 8 вершин).
8. Нарисовать 2 гамильтоновых графа (не менее 10 вершин), указать простой цикл, проходящий через все вершины графа, другим цветом или более жирно.
9. Нарисовать 2 циклически связных графа (не менее 8 вершин).
ВАРИАНТ № 3
1. Последовательность ребер такая, что каждые два соседних ребра имеют общую инцидентную вершину, причем начальная вершина и конечная совпадают, называется .. .
маршрутом
циклическим маршрутом
циклом
простым циклом
2. Граф, содержащий кратные ребра, называется . ..
мультиграф
гамильтонов
циклически связный
эйлеров
3. Ребро, соединяющее вершину саму с собой, называется ...
дуга
петля
цикл
простой цикл
4. Конечная или бесконечная последовательность ребер, такая, что каждые два соседних ребра имеют общую инцидентную вершину, причем каждое ребро встречается не более одного раза, называется ...
маршрутом
цепью
простой цепью
циклом
5. Граф называется .. ., если через любые две вершины рассматриваемого графа может проходить простой цикл
гамильтоновым
эйлеровым
циклически связным
ориентированным
6. Граф, содержащий простой цикл, проходящий через все вершины графа, называется . . .
циклически связным
мультиграфом
гамильтоновым
эйлеровым
7. Нарисовать 2 эйлеровых графа (не менее 8 вершин).
Нарисовать 2 гамильтоновых графа (не менее 10 вершин), указать простой цикл, проходящий через все вершины графа, другим цветом или более жирно.
Нарисовать 2 циклически связных графа (не менее 8 вершин).
ВАРИАНТ № 4
1. Совокупность множеств V (точек) и Е (линий), между которыми определено отношение инцидентности, причем каждый элемент е из Е инцидентен ровно двум элементам V1 и V2 из множества V, называется ...
ориентированным графом
неориентированным графом
мультиграфом
пустым графом
2. Граф, содержащий кратные ребра, называется ...
гамильтонов
мультиграф
эйлеров
циклически связный
3. Конечная или бесконечная последовательность ребер, такая, что каждые два соседних ребра имеют общую инцидентную вершину, причем каждое ребро встречается не более одного раза, называется ...
маршрутом 3) циклом
простой цепью 4) цепью
4. Граф, который можно изобразить одним росчерком пера, причем процесс такого изображения начинается и заканчивается в одной точке, называется ...
гамильтоновым
эйлеровым
циклически связным
мультиграфом
5. Граф, содержащий простой цикл, проходящий через все вершины графа, называется...
циклически связный
эйлеров
мультиграф
гамильтонов
6. Конечная или бесконечная последовательность ребер, такая, что каждые два соседних ребра имеют общую инцидентную вершину, причем каждое ребро встречается не более одного раза, любая вершина графа инцидентна не более чем двум его ребрам, называется ...
цепью
простой цепью
циклом
простым циклом
7. Нарисовать 2 эйлеровых графа (не менее 8 вершин).
8. Нарисовать 2 гамильтоновых графа (не менее 10 вершин), указать простой цикл, проходящий через все вершины графа, другим цветом или более жирно.
Нарисовать 2 циклически связных графа (не менее 8 вершин).
ИСТОЧНИКИ ЛИТЕРАТУРЫ
Асеев Г. Г. Дискретная математика / Г. Г. Асеев, О. М. Абрамов, Д. Э. Ситников. – Ростов н/Д: «Феникс», Харьков: «Торсинг», 2003.
Введение в криптографию / под общ. ред. В. В. Ященко – СПб.: Питер, 2001.
Гончарова Г. А. Элементы дискретной математики: учеб. пособие / Г. А. Гончарова, А. А. Мочалин – М.: ФОРУМ: ИНФРА-М, 2004. (Серия «Профессиональное образование)
Горбатов В. А. "Основы дискретной математики" / В. А. Горбатов. – М.: Высшая школа, 1986.
Иванов Б. Н. «Дискретная математика» (Алгоритмы и программы) / Б. Н. Иванов. – М. Лаборатория Базовых Знаний, 2002.
Камышова Г. А. Дискретная математика. Конспект лекций : учеб. пособие / Г. А. Камышова. – 2003.
Кузнецов О. П. Дискретная математика для инженера / О. П. Кузнецов, Г. М. Адельсон-Вельский. – И. : Энергоиздат, 1988.
Москинова Г. И. Дискретная математика. Математика для менеджера в примерах и упражнениях: учеб. пособие / Г. И. Москинова. – М.: Логос, 2002.
Новиков Ф. А. Дискретная математика для программистов / Ф. А. Новиков. -СПб.: Питер, 2001.
Сигорский В. П. Математический аппарат инженера / В. П. Сигорский. - Киев: Техника, 1975.
13PAGE 15
13PAGE 14415
Root Entry