960741
столько раз учителя, ученики и родители
посетили сайт «Инфоурок»
за прошедшие 24 часа
+Добавить материал
и получить бесплатное
свидетельство о публикации
в СМИ №ФС77-60625 от 20.01.2015
Дистанционные курсы профессиональной переподготовки и повышения квалификации для педагогов

Дистанционные курсы для педагогов - курсы профессиональной переподготовки от 1.410 руб.;
- курсы повышения квалификации от 430 руб.
Московские документы для аттестации

ВЫБРАТЬ КУРС СО СКИДКОЙ ДО 90%

ВНИМАНИЕ: Скидка действует ТОЛЬКО до конца апреля!

(Лицензия на осуществление образовательной деятельности №038767 выдана ООО "Столичный учебный центр", г.Москва)

ИнфоурокДругоеДругие методич. материалыСборник контрольных работ по учебной дисциплине "Дискретная математика" для специальности 09.02.05

Сборник контрольных работ по учебной дисциплине "Дискретная математика" для специальности 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: aircol@mv.ru

Содержание



ВВЕДЕНИЕ 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 = hello_html_m5db0a45c.gif b = hello_html_m524e905a.gif c = hello_html_862c89d.gif


4. Зашифровать сообщение «Контрольная работа» с помощью перестановочного шифра с ключом a=hello_html_25a36c0c.gif


ВАРИАНТ № 2.

1. Изобразить на диаграмме Эйлера – Венна множество (A \ B)\C)

2. Перечислить все элементы множества ВA, если А={1,4,-5} B={7,9,-1}

3. Решить уравнение с подстановками вида ахв=с, где а, в, с – заданные подстановки:

a = hello_html_35a1c463.gif b = hello_html_m524e905a.gif c = hello_html_862c89d.gif


4. Зашифровать сообщение «Контрольная работа» с помощью шифра замены с ключом 3


ВАРИАНТ № 3.

1. Изобразить на диаграмме Эйлера – Венна множество (A \ B) (A \ C)

2. Перечислить все элементы множества АВC, если А={1,4,-5} B={7,9,-1} C={0,2}

3. Решить уравнение с подстановками вида ахв=с, где а, в, с – заданные подстановки:

a = hello_html_m5db0a45c.gif b = hello_html_m659594a4.gif c = hello_html_862c89d.gif


4. Зашифровать сообщение «Контрольная работа» с помощью перестановочного шифра с ключом a=hello_html_7c67d602.gif





ВАРИАНТ № 4.

1. Изобразить на диаграмме Эйлера – Венна множество (A \ C) \ B

2. Перечислить все элементы множества CВA, если А={1,4,-5} B={7,9,-1} C={0,2}

3. Решить уравнение с подстановками вида ахв=с, где а, в, с – заданные подстановки.

a = hello_html_m5db0a45c.gif b = hello_html_m524e905a.gif c = hello_html_m4615882a.gif


4. Зашифровать сообщение «Контрольная работа» с помощью шифра замены с ключом 4


ВАРИАНТ № 5.

1. Изобразить на диаграмме Эйлера – Венна множество A (B C)

2. Перечислить все элементы множества CВA, если А={1,-5} B={7,6,9} C={0,2}

3. Решить уравнение с подстановками вида ахв=с, где а, в, с – заданные подстановки:

a = hello_html_3f2108b.gif b = hello_html_m524e905a.gif c = hello_html_862c89d.gif

4. Зашифровать сообщение «Контрольная работа» с помощью перестановочного шифра с ключом a=hello_html_2b423d75.gif


ВАРИАНТ № 6.

1. Изобразить на диаграмме Эйлера – Венна множество A \ (A B)

2. Перечислить все элементы множества АВC, если А={1,4} B={9,-1} C={0,2}

3. Решить уравнение с подстановками вида ахв=с, где а, в, с – заданные подстановки:

a = hello_html_m5db0a45c.gif b = hello_html_ma29f73.gif c = hello_html_862c89d.gif

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(x2hello_html_53e5a2b.gif3)) (x2x3)


4. Найти минимальную ДНФ для функции трёх переменных f(x1,x2,x3).


3. Определить, является ли полной система функций. Указать, какой метод для этого применялся: {x y}


ВАРИАНТ № 2.

1. В составном высказывании выделить элементарные составляющие, обозначить их буквами, подчеркнуть логические связки и записать в виде формулы:

"данное число делится на 2 и делится на 3 или не делится на 6"


2. Задана функция от трёх переменных f(x1,x2,x3). По заданной функции построить таблицу истинности, совершенную дизъюнктивную нормальную форму (СДНФ):

f(x1,x2,x3)=(x1 (x2hello_html_53e5a2b.gif3)) (x2x3)


3. Найти минимальную ДНФ для функции трёх переменных f(x1,x2,x3).


4. Определить, является ли полной система функций. Указать, какой метод для этого применялся: {xy}


ВАРИАНТ № 3.

1. В составном высказывании выделить элементарные составляющие, обозначить их буквами, подчеркнуть логические связки и записать в виде формулы:

"если ab0 или a0, то b0"


2. Задана функция от трёх переменных f(x1,x2,x3). По заданной функции построить таблицу истинности, совершенную дизъюнктивную нормальную форму (СДНФ):

f(x1,x2,x3)=(x1 (x2x3)) (x2x3)


3. Найти минимальную ДНФ для функции трёх переменных f(x1,x2,x3).


4. Определить, является ли полной система функций. Указать, какой метод для этого применялся: {hello_html_m197f47f9.gif, xy, xy}

ВАРИАНТ № 4.

1. В составном высказывании выделить элементарные составляющие, обозначить их буквами, подчеркнуть логические связки и записать в виде формулы.

"Если я поеду на автобусе, то опоздаю на работу, или я воспользуюсь такси"


2. Задана функция от трёх переменных f(x1,x2,x3). По заданной функции построить таблицу истинности, совершенную дизъюнктивную нормальную форму (СДНФ):

f(x1,x2,x3)=(x2 (x1x3)) (x1x2)


3. Найти минимальную ДНФ для функции трёх переменных f(x1,x2,x3).


4. Определить, является ли полной система функций. Указать, какой метод для этого применялся: {hello_html_m197f47f9.gif, xy}


ВАРИАНТ № 5.

1. В составном высказывании выделить элементарные составляющие, обозначить их буквами, подчеркнуть логические связки и записать в виде формулы:

" если ab=0 или a=0, то b=0"

2. Задана функция от трёх переменных f(x1,x2,x3). По заданной функции построить таблицу истинности, совершенную дизъюнктивную нормальную форму (СДНФ):

f(x1,x2,x3)=(x2 (x1x3)) (x1x2)


3. Найти минимальную ДНФ для функции трёх переменных f(x1,x2,x3).


4. Определить, является ли полной система функций. Указать, какой метод для этого применялся: {hello_html_53e5a2b.gif, xy }


ВАРИАНТ № 6.

1. В составном высказывании выделить элементарные составляющие, обозначить их буквами, подчеркнуть логические связки и записать в виде формулы.

"Давление падает и система не работает"


2. Задана функция от трёх переменных f(x1,x2,x3). По заданной функции построить таблицу истинности, совершенную дизъюнктивную нормальную форму (СДНФ):

f(x1,x2,x3)=(x2 (x1x3)) (x1x2)


3. Найти минимальную ДНФ для функции трёх переменных f(x1,x2,x3).


4. Определить, является ли полной система функций. Указать, какой метод для этого применялся: {0,1, xy, xy}



УЧЕБНАЯ ДИСЦИПЛИНА «ДИСКРЕТНАЯ МАТЕМАТИКА»

Специальность 09.02.05

Базовая подготовка


КОНТРОЛЬНАЯ РАБОТА № 3

КОМБИНАТОРНЫЕ КОНФИГУРАЦИИ


  • Цель: Проверить и закрепить знания и навыки по решению комбинаторных задач, проверить и закрепить знания и навыки по созданию генераторов комбинаторных объектов.


  • Проверяемые умения и знания:


  • Структура индивидуального варианта:


КОМБИНАТОРНЫЕ ОБЪЕКТЫ БЕЗ ПОВТОРЕНИЙ

Решение задач, содержащих комбинаторные объекты без повторений.

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.

  1. Сколько имеется четырехзначных чисел, у которых каждая следующая цифра меньше предыдущей?


  1. Сколько всего существует различных показаний n приборов по m показателям?


  1. Выписать результаты работы генератора перестановок для n=3.


ВАРИАНТ № 2.

  1. На собрании должны выступить четыре человека А, В, С, D. Сколькими способами их можно разместить в списке ораторов, если В не может выступить до того момента, пока не выступит А?


  1. Сколько всего существует различных восьмизначных двоичных чисел?


  1. Выписать результаты работы генератора сочетаний для n=5, k=3.


ВАРИАНТ № 3.

  1. В некоторых видах спортивных соревнований исходом является определение участников, занявших 1-е, 2-е и 3-е места. Сколько всего возможно различных исходов, если в соревнованиях участвуют 80 человек.


  1. Сколько всего существует перестановок из слова "Windows"?


  1. Выписать результаты работы генератора перестановок для n=4.


ВАРИАНТ № 4.

  1. Сколько имеется пятизначных чисел, у которых каждая следующая цифра больше предыдущей?


  1. В магазине 5 сортов тульских пряников. Купить нужно 20 штук любых сортов или одного сорта. Сколько всего существует различных вариантов покупки?


  1. Выписать результаты работы генератора сочетаний для n=5, k=2.


ВАРИАНТ № 5.

  1. На собрании должны выступить пять человек А,В,С,D,E. Сколькими способами их можно разместить в списке ораторов, если D не может выступить до того момента, пока не выступит B?


  1. Сколькими способами можно рассадить n вновь прибывших гостей среди m гостей, уже сидящих за круглым столом?


  1. Выписать результаты работы генератора сочетаний для n=5, k=4.


ВАРИАНТ № 6.

  1. В некоторых видах спортивных соревнований исходом является определение участников, занявших 1-е, 2-е и 3-е места. Сколько всего возможно различных исходов, если в соревнованиях участвуют 8 человек.

  2. Трое детей собрали в саду 63 яблока и распределили их между собой. Сколькими способами можно было распределить яблоки между детьми?

  3. Выписать результаты работы генератора сочетаний для n=6, k=4.

УЧЕБНАЯ ДИСЦИПЛИНА «ДИСКРЕТНАЯ МАТЕМАТИКА»

Специальность 09.02.05

Базовая подготовка


КОНТРОЛЬНАЯ РАБОТА № 4

ПРЕДИКАТЫ. БИНАРНЫЕ ОТНОШЕНИЯ. ВЫЧЕТЫ


  • Цель: Проверка и закрепление знаний и умений по построению таблиц истинности для предикатов, по определению области истинности предикатов, по нахождению значений выражений с кванторными операциями, по представлению бинарных отношений различными способами, по определению свойств бинарных отношений, по определению отношений эквивалентности, проверить умение решать уравнения в классах вычетов.

  • Проверяемые умения и знания:


  • Структура индивидуального варианта

1

ПРЕДИКАТЫ

Определение области истинности и построение таблицы значений предиката.

2

КВАНТОРНЫЕ ОПЕРАЦИИ

Решение задач с кванторами всеобщности и кванторами существования.

3

БИНАРНЫЕ ОТНОШЕНИЯ

Задание бинарного отношения, определение свойств бинарного отношения.

4

ВЫЧЕТЫ ПО МОДУЛЮ m

Решение уравнений в алгебре вычетов; определение разрешимости уравнений в алгебре вычетов по модулю m


  • Время выполнения: 45 минут


  • Оценивание заданий: по 1,7 балла каждое


  • Критерии отметок: « 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.

  1. Построить таблицу значений предиката R(x,y)="животное x входит в класс y" xM1={кошка, лягушка, муха, слон, собака, комар} yM2={земноводные, насекомые, млекопитающие} и определить область истинности.


  1. Пусть дан предикат P(x)="x делится на 3 без остатка" xN=множество натуральных чисел. Определить значение выражения xP(x) и значение выражения xP(x). Объяснить.


  1. Задать бинарное отношение "быть строго меньше" с помощью матрицы, если М={1,2,3,4,5,6,7} и определить свойства бинарного отношения.


  1. Решить уравнение в алгебре вычетов по модулю 7: 36х+8=16.


ВАРИАНТ № 2.

  1. Построить таблицу значений предиката R(x,y,z)="x+yz" x,y,zM={1,2} и определить область истинности.


  1. Пусть дан предикат P(x)="x делится на 3 без остатка" x{3,6,9,27}. Определить значение выражения xP(x). Объяснить.


  1. Задать бинарное отношение "быть делителем" с помощью фактор-множества, если М={1,2,3,4,5,6,7} и определить его свойства.


  1. Решить уравнение в алгебре вычетов по модулю 5: 4х+3=15.


ВАРИАНТ № 3.

  1. Определить область истинности предиката P(x)="предмет x является цветком" xM M={роза, ваза, стол, ромашка, герань} и построить таблицу значений этого предиката.


  1. Пусть даны предикаты P(x)="x четное число", Q(x)="x нечетное число" xN=множество натуральных чисел. Определить значение выражения x(P(x)Q(x)). Объяснить.


  1. Задать бинарное отношение "иметь общий делитель отличный от единицы" перечнем дуг на множестве М={1,2,3,4,5,6,7} и определить его свойства.


  1. Решить уравнение в алгебре вычетов по модулю 3: 2х+8=13.






ВАРИАНТ № 4.

  1. Определить область истинности предиката P(x,y)="x=y" x,yM M={1,2,3} и построить таблицу значений этого предиката.

  2. Пусть даны предикаты P(x)="x четное число", Q(x)="x делится на 4 без остатка"; xN=множество натуральных чисел. Определить значение выражения x(Q(x) P(x)). Объяснить.

  3. Задать с помощью графа бинарное отношение "иметь один и тот же остаток от деления на 3" на множестве М={1,2,3,4,5,6,7} и определить его свойства.

  4. Решить уравнение в алгебре вычетов по модулю 2: 5х+10=13.



ВАРИАНТ № 5.

  1. Определить область истинности предиката P(x,y)="город x является столицей y" xM1={Ульяновск, Самара, Москва, Киев} yМ2={Россия, Беларусь, Украина, Германия} и построить таблицу значений этого предиката.

  2. Пусть даны предикаты P(x)="x четное число", Q(x)="x нечетное"; xN=множество натуральных чисел. Определить значение выражения x(Q(x) P(x)). Объяснить.

  3. Задать с помощью матрицы бинарное отношение "быть не меньше" на множестве М={1,2,3,4,5,6,7} и определить его свойства.

  4. Решить уравнение в алгебре вычетов по модулю 11: 10х+8=22.



ВАРИАНТ № 6.

  1. Определить область истинности предиката R(x,y)="x является валютой страны y" xM1={рубль, доллар, фунт стерлингов} yM2={США, Россия, Украина, Беларусь} и построить таблицу значений этого предиката.

  2. Пусть дан предикат P(x)="x четное число", xМ={1,2,3,4,5,6,7}. Определить значение выражения x P(x). Объяснить.

  3. Определить свойства бинарного отношения "быть делителем", определенного на множестве М, где М={1,2,3,4,5,6,7} и задать его перечнем дуг.

  4. Решить уравнение в алгебре вычетов по модулю 13: 27х+15=44.

УЧЕБНАЯ ДИСЦИПЛИНА «ДИСКРЕТНАЯ МАТЕМАТИКА»

Специальность 09.02.05

Базовая подготовка

КОНТРОЛЬНАЯ РАБОТА № 5

ОСНОВЫ ТЕОРИИ ГРАФОВ


  • Цель: Проверка знаний основных определений по основам теории графов и умений по построению графов различных типов.

  • Проверяемые умения и знания:

  • Структура индивидуального варианта


ОСНОВЫ ТЕОРИИ ГРАФОВ

Тестирование по определениям темы.

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. Не разрешается пользоваться справочниками, таблицами, выходить из аудитории.

  1. Отметка ставится только на основании правильных решений.




УЧЕБНАЯ ДИСЦИПЛИНА «ДИСКРЕТНАЯ МАТЕМАТИКА»

Специальность 09.02.05

Базовая подготовка

КОНТРОЛЬНАЯ РАБОТА № 5

ОСНОВЫ ТЕОРИИ ГРАФОВ


ВАРИАНТ № 1

1. Совокупность множеств V (точек) и Е (линий), между которыми определено отношение инцидентности, причем каждый элемент е из Е инцидентен ровно двум элементам v1 и v2 из множества V, называется . ..

  1. неориентированным графом 3) мультиграфом

  2. ориентированным графом 4) пустым графом


2. Граф, содержащий кратные ребра, называется . ..

  1. гамильтонов

  2. циклически связный

  3. мультиграф

  4. эйлеров

3. Граф, у которого множество вершин - пусто, называется . . .

  1. неориентированным графом

  2. ориентированным графом

  3. пустым графом

  4. мультиграфом


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

  1. маршрутом 3) простой цепью

  2. цепью 4) циклом


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

  1. маршрутом 3) циклом

  2. цепью 4) простым циклом


6. Граф, который можно изобразить одним росчерком пера, причем процесс такого изображения начинается и заканчивается в одной точке, называется .. .

  1. гамильтоновым

  2. циклически связным

  3. мультиграфом

  4. эйлеровым


7. Нарисовать 2 эйлеровых графа (не менее 8 вершин).


8. Нарисовать 2 гамильтоновых графа (не менее 10 вершин), указать простой цикл, проходящий через все вершины графа, другим цветом или более жирно.


9. Нарисовать 2 циклически связных графа (не менее 8 вершин).


ВАРИАНТ № 2


1. Ребро S и вершина V(U) называются ..., если ребро S соединяет вершины V и U

  1. смежными

  2. инцидентами

  3. связными

  4. ориентированными


2. Последовательность ребер такая, что каждые два соседних ребра имеют общую инцидентную вершину, причем начальная вершина и конечная совпадают, называется ..

  1. маршрутом

  2. циклическим маршрутом

  3. циклом

  4. простым циклом


3. Совокупность множеств V (точек) и Е (линий), между которыми определено отношение инцидентности, причем каждый элемент е из Е инцидентен ровно двум элементам v1 и v2 из множества V, называется ...

  1. мультиграфом

  2. ориентированным графом

  3. неориентированным графом

  4. пустым графом


4. Граф, содержащий кратные ребра, называется ...

  1. циклически связный

  2. гамильтонов

  3. эйлеров

  4. мультиграф


5. Граф, содержащий простой цикл, проходящий через все вершины графа, называется ...

  1. циклически связный

  2. гамильтонов

  3. эйлеров

  4. мультиграф


6. Граф, содержащий направленные ребра, называется ...

  1. неориентированным графом

  2. ориентированным графом

  3. мультиграфом

  4. пустым графом


7. Нарисовать 2 эйлеровых графа (не менее 8 вершин).


8. Нарисовать 2 гамильтоновых графа (не менее 10 вершин), указать простой цикл, проходящий через все вершины графа, другим цветом или более жирно.


9. Нарисовать 2 циклически связных графа (не менее 8 вершин).



ВАРИАНТ № 3

1. Последовательность ребер такая, что каждые два соседних ребра имеют общую инцидентную вершину, причем начальная вершина и конечная совпадают, называется .. .

  1. маршрутом

  2. циклическим маршрутом

  3. циклом

  4. простым циклом


2. Граф, содержащий кратные ребра, называется . ..

  1. мультиграф

  2. гамильтонов

  3. циклически связный

  4. эйлеров


3. Ребро, соединяющее вершину саму с собой, называется ...

  1. дуга

  2. петля

  3. цикл

  4. простой цикл


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

  1. маршрутом

  2. цепью

  3. простой цепью

  4. циклом


5. Граф называется .. ., если через любые две вершины рассматриваемого графа может проходить простой цикл

  1. гамильтоновым

  2. эйлеровым

  3. циклически связным

  4. ориентированным


6. Граф, содержащий простой цикл, проходящий через все вершины графа, называется . . .

  1. циклически связным

  2. мультиграфом

  3. гамильтоновым

  4. эйлеровым


7. Нарисовать 2 эйлеровых графа (не менее 8 вершин).


  1. Нарисовать 2 гамильтоновых графа (не менее 10 вершин), указать простой цикл, проходящий через все вершины графа, другим цветом или более жирно.


  1. Нарисовать 2 циклически связных графа (не менее 8 вершин).

ВАРИАНТ № 4


1. Совокупность множеств V (точек) и Е (линий), между которыми определено отношение инцидентности, причем каждый элемент е из Е инцидентен ровно двум элементам V1 и V2 из множества V, называется ...

  1. ориентированным графом

  2. неориентированным графом

  3. мультиграфом

  4. пустым графом


2. Граф, содержащий кратные ребра, называется ...

  1. гамильтонов

  2. мультиграф

  3. эйлеров

  4. циклически связный


3. Конечная или бесконечная последовательность ребер, такая, что каждые два соседних ребра имеют общую инцидентную вершину, причем каждое ребро встречается не более одного раза, называется ...

  1. маршрутом 3) циклом

  2. простой цепью 4) цепью


4. Граф, который можно изобразить одним росчерком пера, причем процесс такого изображения начинается и заканчивается в одной точке, называется ...

  1. гамильтоновым

  2. эйлеровым

  3. циклически связным

  4. мультиграфом


5. Граф, содержащий простой цикл, проходящий через все вершины графа, называется...

  1. циклически связный

  2. эйлеров

  3. мультиграф

  4. гамильтонов


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

  1. цепью

  2. простой цепью

  3. циклом

  1. простым циклом


7. Нарисовать 2 эйлеровых графа (не менее 8 вершин).


8. Нарисовать 2 гамильтоновых графа (не менее 10 вершин), указать простой цикл, проходящий через все вершины графа, другим цветом или более жирно.


  1. Нарисовать 2 циклически связных графа (не менее 8 вершин).

ИСТОЧНИКИ ЛИТЕРАТУРЫ


  1. Асеев Г. Г. Дискретная математика / Г. Г. Асеев, О. М. Абрамов, Д. Э. Ситников. – Ростов н/Д: «Феникс», Харьков: «Торсинг», 2003.

  2. Введение в криптографию / под общ. ред. В. В. Ященко – СПб.: Питер, 2001.

  3. Гончарова Г. А. Элементы дискретной математики: учеб. пособие / Г. А. Гончарова, А. А. Мочалин – М.: ФОРУМ: ИНФРА-М, 2004. (Серия «Профессиональное образование)

  4. Горбатов В. А. "Основы дискретной математики" / В. А. Горбатов. – М.: Высшая школа, 1986.

  5. Иванов Б. Н. «Дискретная математика» (Алгоритмы и программы) / Б. Н. Иванов. – М. Лаборатория Базовых Знаний, 2002.

  6. Камышова Г. А. Дискретная математика. Конспект лекций : учеб. пособие / Г. А. Камышова. – 2003.

  7. Кузнецов О. П. Дискретная математика для инженера / О. П. Кузнецов, Г. М. Адельсон-Вельский. – И. : Энергоиздат, 1988.

  8. Москинова Г. И. Дискретная математика. Математика для менеджера в примерах и упражнениях: учеб. пособие / Г. И. Москинова. – М.: Логос, 2002.

  9. Новиков Ф. А. Дискретная математика для программистов / Ф. А. Новиков. -СПб.: Питер, 2001.

  10. Сигорский В. П. Математический аппарат инженера / В. П. Сигорский. - Киев: Техника, 1975.




Общая информация

Номер материала: ДБ-277689

Похожие материалы

Вам будут интересны эти курсы:

Курс «Мерчендайзинг»
Курс профессиональной переподготовки «Маркетинг: теория и методика обучения в образовательной организации»
Курс профессиональной переподготовки «Управление персоналом и оформление трудовых отношений»
Курс повышения квалификации «Методика написания учебной и научно-исследовательской работы в школе (доклад, реферат, эссе, статья) в процессе реализации метапредметных задач ФГОС ОО»
Курс повышения квалификации «Организация научно-исследовательской работы студентов в соответствии с требованиями ФГОС»
Курс профессиональной переподготовки «Организация и предоставление туристских услуг»
Курс профессиональной переподготовки «Клиническая психология: организация реабилитационной работы в социальной сфере»
Курс повышения квалификации «Организация практики студентов в соответствии с требованиями ФГОС медицинских направлений подготовки»
Курс повышения квалификации «Разработка бизнес-плана и анализ инвестиционных проектов»
Курс профессиональной переподготовки «Организация маркетинга в туризме»
Курс профессиональной переподготовки «Основы организации рекреационной деятельности и лечебного туризма»
Курс повышения квалификации «Методы и инструменты современного моделирования»
Курс повышения квалификации «Актуальные вопросы банковской деятельности»
Курс профессиональной переподготовки «Политология: взаимодействие с органами государственной власти и управления, негосударственными и международными организациями»
Курс профессиональной переподготовки «Методика организации, руководства и координации музейной деятельности»

Благодарность за вклад в развитие крупнейшей онлайн-библиотеки методических разработок для учителей

Опубликуйте минимум 3 материала, чтобы БЕСПЛАТНО получить и скачать данную благодарность

Сертификат о создании сайта

Добавьте минимум пять материалов, чтобы получить сертификат о создании сайта

Грамота за использование ИКТ в работе педагога

Опубликуйте минимум 10 материалов, чтобы БЕСПЛАТНО получить и скачать данную грамоту

Свидетельство о представлении обобщённого педагогического опыта на Всероссийском уровне

Опубликуйте минимум 15 материалов, чтобы БЕСПЛАТНО получить и скачать данное cвидетельство

Грамота за высокий профессионализм, проявленный в процессе создания и развития собственного учительского сайта в рамках проекта "Инфоурок"

Опубликуйте минимум 20 материалов, чтобы БЕСПЛАТНО получить и скачать данную грамоту

Грамота за активное участие в работе над повышением качества образования совместно с проектом "Инфоурок"

Опубликуйте минимум 25 материалов, чтобы БЕСПЛАТНО получить и скачать данную грамоту

Почётная грамота за научно-просветительскую и образовательную деятельность в рамках проекта "Инфоурок"

Опубликуйте минимум 40 материалов, чтобы БЕСПЛАТНО получить и скачать данную почётную грамоту

Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.