Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

2Дискретка / Экзамен / ДМ Билеты

.pdf
Скачиваний:
60
Добавлен:
27.03.2015
Размер:
305.21 Кб
Скачать

ПАСПОРТ Комплекта контролирующих материалов (КМ)

по дисциплине Дискретная математика специальность, для которой разработан комплект КМ

010503 – Математическое обеспечение и администрирование информационных систем; квалификация математик-программист

1.Контролирующие материалы составлены на основании Государственного образовательного стандарта высшего профессионального образования по специальности 351500 – Математическое обеспечение и администрирование информационных систем.

Регистрационный номер 72 мжд/СП, дата утверждения 10.03.2000 г.

2.Вид контроля: итоговый

3.Содержание контроля:

3.1.Системы счисления.

3.2.Теория множеств.

3.3.Теория переключательных функций.

3.4.Исчисление предикатов

3.5.Комбинаторика.

3.6.Исчисление высказываний.

3.7.Теория графов.

4.Цели контроля представлены в виде содержательно-деятельностной матрицы.

1.1.Соответствие заданий КМ целям дисциплины:

Номер взаданиябилете

1

2

3

4

5, 7

6

Уровень усвоения

Содержание

Модуль 1. Системы счисления Модуль 2. Теория множеств

Модуль 3. Теория переключательных функций

Модуль 5. Исчисление предикатов

Модуль 6. Комбинаторика

Модуль 7. Теория графов

Модуль 4. Исчисление высказываний

Иметь представле ние о ...

Знать

Уметь ...

Иметь опыт ...

...

Владеть ...

 

6, 7

 

8

13

9, 10

14, 15

1116

1214, 17

9, 10

1.2. Соответствие заданий КМ содержанию дисциплины:

Номер цели

Уровень

Описание цели курса

Задания

курса по

усвоения

 

комплекта К

списку

 

 

(текст или

 

 

 

№ из

 

 

 

варианта)

6

Знать

основные алгоритмы перевода чисел между

1

 

 

системами счисления

 

7

Знать

основные понятия и законы теории множеств

1

8

Знать

алгоритмы приведения булевых функций к

2

 

 

нормальной форме и построения минимальных

 

 

 

форм, понятие полноты системы функций и

 

 

 

способы её проверки по классам Поста

 

 

9

Знать

основы исчисления высказываний, алгоритмы и

3, 6

 

 

приёмы построения выводов и доказательств

 

10

Знать

приёмы построения и описания моделей на

3, 6

 

 

языке исчисления предикатов, способы проверки

 

 

 

истинности утверждений, основы формальной

 

 

 

логики Аристотеля

 

 

 

11

Знать

основные понятия и законы комбинаторики

4

12

Знать

основные понятия и алгоритмы теории графов

5

13

Уметь

приводить

переключательные функции к

2

 

 

дизъюнктивной нормальной форме и строить

 

 

 

минимальную форму. Определять полноту

 

 

 

системы переключательных функций

 

 

14

Уметь

строить и грамотно излагать доказательства,

3, 5

 

 

проверять логическую непротиворечивость

 

 

 

выводов

 

 

 

 

15

Уметь

описывать модель явления на языке исчисления

3

 

 

предикатов

 

 

 

 

16

Уметь

распознавать основные комбинаторные

 

4

 

 

конфигурации и вычислять их количество

 

17

Уметь

определять

основные

свойства

графа,

5, 7

 

 

исследовать его планарность, представлять его

 

 

 

в виде матрицы, находить компоненты

 

 

 

связности и кратчайший путь между

 

 

 

вершинами

 

 

 

 

5.Форма КМ: для письменной аттестации.

6.Шкала измерений: "отлично", "хорошо", "удовлетворительно", "неудовлетворительно".

По каждой задаче студент получает оценку: "неудовлетворительно" – задача не решена, "удовлетворительно" – задача решена частично,

"хорошо" – задача решена, но в решении есть неточности и недочеты, "отлично" – задача решена полностью, при решении студент показал

приобретенные знания и навыки решения.

Общая оценка средняя оценка по всем задачам.

7.Время, отведенное для выполнения письменной части КМ - 2 часа.

8.Инструкция по формированию комплекта КМ.

Экзамен состоит из письменной (практической) и устной (теоретической)

части и включает решение задач по пройденному материалу и ответы на теоретические вопросы. Письменная часть экзамена состоит из билета, включающего 7 задач. Устная часть экзамена проходит путем собеседования по решенным задачам и базовым понятиям курса (определения и свойства, формулировки теорем).

Министерство общего

 

 

 

 

 

Экзаменационный билет №

1

образования РФ

 

 

По дисциплине

ГОСУДАРСТВЕННЫЙ

 

 

Дискретная математика

 

ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

 

Факультет

Прикладной математики и информатики

Курс I

 

 

 

 

1. Найти δP , ρP ,

P1 , P o P ,

P o P1

для отношения

 

 

 

 

P = {(x, y) x΢, y ΢

y делится на x без остатка}.

 

2. Минимизировать функцию

f (x, y, z, p) = xy Ú xzp Ú yz методом Блейка.

 

3. В модели

L; М1,Ж1,Р2 ,С2 , Е2 , где L множество людей,

 

 

 

M (x)

" x мужчина",

Ж(x)

" x женщина",

 

С(x, y)

" x и y супруги", Р(x, y)

" x и ребенок y ",

 

 

Е(x, y) " x и y один и тот же человек";

 

 

формализовать утверждения:

а) "у каждого есть отец и мать",

б) " x незаконнорожденный".

 

4. Из цифр 0,1, 2, 3, 4, 5 составлены всевозможные четырехзначные числа так, что в каждом числе нет

 

одинаковых цифр. Сколько получилось четных чисел?

 

 

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

6. Построить вывод B É ( A É C) ÷¾ A Ù B É C .

7. Используя алгоритм укладки, построить плоский граф, изоморфный заданному, или доказать его непланарность. Для начального шага алгоритма использовать выделенный цикл.

Составили Рояк С.Х. Дата 4 января 2007 г.

Утверждаю: Зав. кафедрой ______________________

Министерство общего образования РФ

ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

 

Экзаменационный билет №

2

По дисциплине

Дискретная математика

 

Факультет Прикладной математики и информатики

Курс I

1. Найти δP ,

ρP , P1 , P o P ,

P o P1 для отношения P = {(x, y)

 

x΢, y ΢ y делится на x без остатка}.

 

2. Минимизировать функцию

f (x, y, z, p) = (0001 1010 1000 1110) методом карт Карнапа.

Определить принадлежность классам Поста.

3. В модели

L; М1,Ж1,Р2 ,С2 , Е2

, где L множество людей,

 

 

 

M (x)

" x мужчина",

Ж(x) " x женщина",

 

 

 

С(x, y) " x и y супруги",

Р(x, y) " x и ребенок y ",

 

 

 

Е(x, y) " x и y один и тот же человек",

 

 

 

 

 

 

 

 

 

формализовать утверждения:

а) "у каждого есть бабушка", б) " x тесть y ".

 

 

4. На книжной полке помещается 30 томов. Сколькими способами их можно

 

 

расставить, чтобы при этом первый и второй тома не стояли рядом?

 

 

5. Доказать, что для любых трех вершин v, w, p из существования цепей

 

 

из v в w и из w в p следует существование цепи из v в p.

 

 

6. Построить вывод: C É D ÷¾ A Ù C É A Ù D .

7. Используя алгоритм укладки, построить плоский граф, изоморфный заданному, или доказать его непланарность. Для начального шага алгоритма использовать выделенный цикл.

Составили Рояк С.Х. Дата 4 января 2007 г.

Утверждаю: Зав. кафедрой ______________________

образования РФ

 

 

 

Экзаменационный билет №

3

Министерство общего

 

 

 

 

 

 

 

 

 

ГОСУДАРСТВЕННЫЙ

По дисциплине

Дискретная математика

 

 

ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет

Прикладной математики и информатики

Курс I

 

 

1. Какова мощность множеств A´ B и A U B , если A = {[1,2],[1,3],[4,5],[4,6]}, B = {1,2,3}?

 

 

2. Найти все простые импликанты функции f (x, y, z, p) = xy Ú xzp Ú yz .

 

 

 

 

 

 

 

Выписать СДНФ и СКНФ

 

 

 

 

 

 

 

 

 

3. В модели

L; М1,Ж1,Р2 ,С2 , Е2

, где L множество людей,

 

 

 

 

 

 

M (x)

" x мужчина",

Ж(x)

" x женщина",

 

 

 

 

 

 

С(x, y) " x и y супруги",

Р(x, y) " x и ребенок y ",

 

 

Е(x, y) " x и y один и тот же человек",

 

 

 

 

 

 

формализовать утверждения:

 

 

 

 

 

 

 

 

 

а) "у некоторых людей есть братья",

б) " x внебрачная дочь y ".

 

 

4. На полке стоят m книг в черных переплетах и n книг в синих переплетах, причем все книги разные. Сколькими способами можно расставить книги так, чтобы книги в черных переплетах стояли рядом?

5. Доказать, что граф содержит остовное дерево тогда и только тогда, когда он связен. 6. Построить вывод: B É C ÷¾ A Ù B É A Ù C .

7. Используя алгоритм укладки, построить плоский граф, изоморфный заданному, или доказать его непланарность. Для начального шага алгоритма использовать выделенный цикл.

Составили Рояк С.Х. Дата 4 января 2007 г.

Утверждаю: Зав. кафедрой ______________________

образования РФ

 

 

 

Экзаменационный билет №

4

Министерство общего

 

 

 

 

 

 

 

ГОСУДАРСТВЕННЫЙ

 

По дисциплине

Дискретная математика

 

 

ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

 

Факультет

Прикладной математики и информатики

Курс I

 

 

 

1. Построить рефлексивное, антисимметричное, не транзитивное бинарное отношение.

 

 

2. Используя метод Квайна, определить, какие элементы множества K = {x, z , xy, zy, p}

 

 

являются простыми импликантами функции: f (x, y, z) = (00101111)

 

 

3. В модели L;

М1,Ж1,Р2 ,С2 , Е2

, где L множество людей,

 

 

 

 

M (x)

" x мужчина",

Ж(x) " x женщина",

 

 

 

 

 

 

С(x, y) " x и y супруги",

Р(x, y) " x и ребенок y ",

 

 

 

Е(x, y) " x и y один и тот же человек",

 

 

 

 

 

 

 

 

формализовать утверждения:

а) "у некоторых людей есть сестры", б) " x внебрачный сын y ".

 

 

4. Среди всех чисел от 1 до 10n каких больше: тех, для записи которых используется цифра 9, или тех, которые записываются без нее?

5. Доказать, что каждый непростой цикл можно разбить на два или более простых. 6. Построить вывод: B É C ÷¾ A Ú B É A Ú C .

7. Используя алгоритм укладки, построить плоский граф, изоморфный заданному, или доказать его непланарность. Для начального шага алгоритма использовать выделенный цикл.

Составили

Рояк С.Х.

Дата 4 января 2007 г.

Утверждаю: Зав. кафедрой ______________________

Министерство общего образования РФ

ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

 

Экзаменационный билет №

5

По дисциплине

Дискретная математика

 

Факультет Прикладной математики и информатики

Курс I

1. Перевести число 4012 в двоичную, восьмеричную и шестнадцатеричную системы счисления. 2. Минимизировать функцию f (x, y, z, p) = (0101 1001 0111 0000) методом карт Карнапа.

Определить принадлежность классам Поста.

3. В модели ¥; S3, P3 , где

 

S (x, y, z) " x + y = z ",

P(x, y, z) " xy = z ",

формализовать утверждения:

а) " x = 0 ", б) " x четное число".

4. Садовник должен в течение трех дней посадить 10 деревьев.

Сколькими способами он может распределить по дням работу, если будет сажать не менее одного дерева в день?

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

6. Построить вывод: B É C ÷¾ A Ù B É A Ù C .

7. Используя алгоритм укладки, построить плоский граф, изоморфный заданному, или доказать его непланарность. Для начального шага алгоритма использовать выделенный цикл.

Составили

Рояк С.Х.

Дата 4 января 2007 г.

Утверждаю: Зав. кафедрой ______________________

Министерство общего образования РФ

ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

 

Экзаменационный билет №

6

По дисциплине

Дискретная математика

 

Факультет Прикладной математики и информатики

Курс I

1. Построить не рефлексивное, симметричное, антисимметричное бинарное отношение.

2. Минимизировать функцию f (x, y, z, p) = xy Ú xzp Ú yz

3. В модели L;

М1,Ж1,Р2 ,С2 , Е2 , где L множество людей,

M (x)

" x мужчина",

Ж(x) " x женщина",

С(x, y) " x и y супруги",

Р(x, y) " x и ребенок y ",

 

 

Е(x, y) " x и y один и тот же человек";

 

формализовать утверждения:

 

 

а) "некоторые супруги имеют детей только женского пола",

 

б) " x внук y ".

 

 

 

 

4. Сколько четырехзначных чисел, делящихся на 5, можно составить из цифр 0, 1, 3, 5, 7, если каждое число не должно содержать одинаковых цифр?

5. Из полного 100-вершинного графа выкинули 98 ребер. Доказать, что он остался связным. 6. Построить вывод: A É C ÷¾ D Ù A É D Ù C .

7. Используя алгоритм укладки, построить плоский граф, изоморфный заданному, или доказать его непланарность. Для начального шага алгоритма использовать выделенный цикл.

Составили Рояк С.Х. Дата 4 января 2007 г.

Утверждаю: Зав. кафедрой ______________________

Министерство общего

 

 

 

Экзаменационный билет №

7

образования РФ

 

 

 

ГОСУДАРСТВЕННЫЙ

 

 

По дисциплине

Дискретная математика

 

ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

 

Факультет

Прикладной математики и информатики

Курс I

 

 

 

 

1. Пусть X множество прямых. Какими свойствами обладает бинарное отношение:

 

P = {(x, y) xÎ X , y Î X

x перпендикулярна y}.

 

 

 

2. Используя метод Квайна, найти все минимальные ДНФ функции

f (x, y, z) = (01111110).

 

3. В модели

L;

М1,Ж1,Р2 ,С2 , Е2

, где L множество людей,

 

 

M (x)

" x мужчина",

Ж(x) " x женщина",

 

 

С(x, y) " x и y супруги",

Р(x, y) " x и ребенок y ",

 

 

Е(x, y) " x и y один и тот же человек";

 

 

формализовать утверждения:

 

 

 

 

 

а) «некоторые супруги бездетны»,

б) « x свекровь y ».

 

 

4. На конференции должны выступить докладчики A ,

B , C и D , причем B не может выступать раньше A .

Сколькими способами можно установить очередность выступлений?

 

5. Пусть G граф с n ³ 2 вершинами, доказать эквивалентность следующих утверждений:

1) G связный и содержит n -1 ребро; 2) G связный, а удаление любого ребра делает его несвязным. 6. Построить вывод: B É C ÷¾ B Ú A É C Ú A .

7. Используя алгоритм укладки, построить плоский граф, изоморфный заданному, или доказать его непланарность. Для начального шага алгоритма использовать выделенный цикл.

Составили Рояк С.Х. Дата 4 января 2007 г.

Утверждаю: Зав. кафедрой ______________________

Министерство общего

 

 

Экзаменационный билет №

8

образования РФ

 

 

ГОСУДАРСТВЕННЫЙ

По дисциплине

Дискретная математика

 

ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет

Прикладной математики и информатики

Курс I

 

 

 

1. Пусть X множество прямых. Какими свойствами обладает бинарное

 

отношение P = {(x, y) xÎ X , y Î X

x параллельна y}.

 

 

2. Найти все тупиковые ДНФ функции

f (x, y, z, p) = (0011 1100 0011 0101) .

 

3. В модели

L;

М1,Ж1,Р2 ,С2 , Е2 , где L множество людей,

 

 

M (x)

" x мужчина",

Ж(x) " x женщина",

 

 

С(x, y) " x и y супруги",

 

Р(x, y) " x и ребенок y ",

 

 

Е(x, y) " x и y один и тот же человек";

 

 

формализовать понятия:

 

 

 

б) " x внучка y ".

 

а) "некоторые супруги имеют детей только мужского пола",

 

4. Сколько ожерелий можно составить из 20 различных бусинок?

 

 

5. Пусть G граф с n ³ 2 вершинами, доказать эквивалентность следующих утверждений:

 

1) G связный и содержит n -1 ребро;

2) Любая пара вершин в графе G соединена единственной цепью.

6. Построить вывод: A É C ÷¾ D Ú A É D Ú C .

 

 

 

7. Используя алгоритм укладки, построить плоский граф, изоморфный заданному, или доказать его

 

непланарность. Для начального шага алгоритма использовать выделенный цикл.

 

Составили

Рояк С.Х.

Дата 4 января 2007 г.

Утверждаю: Зав. кафедрой ______________________

Соседние файлы в папке Экзамен