Методические указания по выполнению контрольной работы

В соответствии с учебным планом по дисциплине «Дискретная математика» каждый студент должен выполнить одну домашнюю контрольную работу (по приведенным в данной брошюре вариантам) в сроки, установленные учебным графиком.

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

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

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

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

При изучении учебного материала и подготовке к контрольным работам рекомендуется использовать учебники и учебные пособия, электронные ресурсы, приведенные выше в разделе «Литература», а также данную брошюру.

После проверки контрольная работа студента получает оценку «Допускается к собеседованию» или «Не допускается к собеседованию».

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

1. Работа должна быть выполнена в школьной тетради, имеющей широкие (не менее 3 см) поля для замечаний рецензента.

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

3. Перед решением каждой задачи нужно привести (распечатать) полностью ее условие.

4. Следует придерживаться той последовательности при решении задач, в какой они даны в задании, строго сохраняя при этом нумерацию примеров (задач).

5. Не допускается замена задач контрольной работы другими заданиями.

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

7. В конце работы приводится список использованной литературы (указывают автора, название, издательство, год издания), ставится дата окончания работы и подпись.

Если работа получила в целом положительную оценку («Допускается к собеседованию»), но в ней есть отдельные недочеты (указанные в тетради), то нужно сделать соответствующие исправления и дополнения в той же тетради (после имеющихся решений и записи «Работа над ошибками») и предъявить доработку на собеседовании. Если работа «Не допускается к собеседованию», ее необходимо в соответствии с требованиями преподавателя частично или полностью переделать. Повторную работу надо выполнить в той же тетради (если есть место) или в новой с надписью на обложке «Повторная», указав фамилию преподавателя, которым работа была ранее не зачтена. Вместе с незачтенной работой, повторную работу представить снова на проверку.

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

Студенты, не получившие зачета по контрольной работе, к экзаменационному зачету не допускаются. Если в соответствии с учебным графиком контрольная работа должна быть выполнена с частичным использованием КОПР, то для получения зачета по этой работе необходимо дополнительно представить протокол ответа студента о работе с КОПР. Зачтенные работы предъявляются на экзаменационном зачете и не подлежат возвращению после успешной сдачи экзаменационного зачета.

Для допуска к экзаменационному зачету необходимо также получить зачет по компьютерному тестированию, если оно предусмотрено учебным графиком по дисциплине «Дискретная математика».

ВАРИАНТЫ КОНТРОЛЬНОЙ РАБОТЫ[6]

ВАРИАНТ 1

(для студентов, номера личных дел которых оканчиваются цифрой 1)

1. Даны множества чисел: , , и универсальное множество .

Найти множества чисел , . Являются ли множества Е и D равными? эквивалентными? включающими одно в другое ( или )? пересекающимися, но не включающими одно в другое? непересекающимися ( )?

2. Двенадцать работников отдела делятся на четыре равные по численности рабочие группы, которые занимаются разными задачами. В каждой назначается старший. Сколько возможно вариантов распределения людей по группам и назначения старшего в каждой группе?

Решить задачу, используя комбинаторику.

3. Установить вид формулы алгебры логики:

.

4. Упростить формулу:

.

Проверить результат, используя таблицу истинности.

5.

Для нагруженного графа, представленного на рисунке, построить остовное дерево минимальной стоимости. Определить его стоимость.

6. Определить функцию , полученную из функций и по схеме примитивной рекурсии.

ВАРИАНТ 2

(для студентов, номера личных дел которых оканчиваются цифрой 2)

1. Даны множества чисел: , , и универсальное множество .

Найти множества чисел , . Являются ли множества Е и D равными? эквивалентными? включающими одно в другое ( или )? пересекающимися, но не включающими одно в другое? непересекающимися ( )?

2. Из 100 работников фирмы 42 владеют английским языком, 30 – французским, 28 – немецким. Десять человек – знают английский и немецкий, 8 – знают французский и немецкий, 5 – английский и французский. Три человека знают все три языка. Сколько работников фирмы не знают ни одного языка?

Решить задачу, используя теорию множеств.

3. Установить вид формулы алгебры логики:

.

4. С помощью таблицы истинности найти СДНФ и СКНФ булевой функции .

5.Дана матрица:

Построить ориентированный граф, для которого матрица A является матрицей смежности. Найти матрицу инцидентности.

Являются ли полученный граф связным?

6. Определить функцию , полученную из функций и по схеме примитивной рекурсии.

ВАРИАНТ 3

(для студентов, номера личных дел которых оканчиваются цифрой 3)

1. Даны множества чисел: , , и универсальное множество .

Найти множества чисел , . Являются ли множества Е и D равными? эквивалентными? включающими одно в другое ( или )? пересекающимися, но не включающими одно в другое? непересекающимися ( )?

2. На фирму должна приехать проверка из центрального офиса. На проверку могут приехать директор, главный бухгалтер и старший менеджер. Накануне были получены три телеграммы: 1) директор не приедет, приедет главный бухгалтер; 2) приедут главный бухгалтер и старший менеджер; 3) приедет или директор, или главный бухгалтер. Одна из телеграмм была послана по ошибке. Приехал один проверяющий. Кто это был?

Решить задачу, используя алгебру логики.

3. Установить вид формулы алгебры логики:

.

4. Упростить формулу:

.

Проверить результат, используя таблицу истинности.

5.На множестве V={0; 1; 2; 3; 4} задано отношение f: x > y +1. Построить орграф данного отношения.

6. Определить функцию , полученную из функций и по схеме примитивной рекурсии.

ВАРИАНТ 4

(для студентов, номера личных дел которых оканчиваются цифрой 4)

1. Даны множества чисел: , , и универсальное множество .

Найти множества чисел , . Являются ли множества Е и D равными? эквивалентными? включающими одно в другое ( или )? пересекающимися, но не включающими одно в другое? непересекающимися ( )?

2. В шахматном турнире по круговой системе участвуют семь шахматистов. Известно, что игрок A сыграл шесть партий, B – пять, C и D – по три, E и F – по две, а G – одну. С кем сыграл игрок C?

Задачу решить, используя теорию графов.

3. Установить вид формулы алгебры логики:

.

4. С помощью таблицы истинности найти СДНФ и СКНФ булевой функции .

5.

Для графа, представленного на рисунке, найти матрицу смежности и остовное дерево. Определить цикломатическое число.

6. Определить функцию , полученную из функций и по схеме примитивной рекурсии.

ВАРИАНТ 5

(для студентов, номера личных дел которых оканчиваются цифрой 5)

1. Даны множества чисел: , , и универсальное множество .

Найти множества чисел , . Являются ли множества Е и D равными? эквивалентными? включающими одно в другое ( или )? пересекающимися, но не включающими одно в другое? непересекающимися ( )?

2. Из 71 школьников в волейбол играют 51, в футбол – 45, в баскетбол – 31. Во все три игры играют 8 ребят, в волейбол и футбол – 28, в волейбол и баскетбол – 20, в футбол и баскетбол – 16. Сколько школьников играют только в баскетбол?

Решить задачу, используя теорию множеств.

3. Установить вид формулы алгебры логики:

.

4. Упростить формулу:

.

Проверить результат, используя таблицу истинности.

5.

Для нагруженного графа, представленного на рисунке, построить остовное дерево минимальной стоимости. Определить его стоимость.

6. Определить функцию , полученную из функций и по схеме примитивной рекурсии.

ВАРИАНТ 6

(для студентов, номера личных дел которых оканчиваются цифрой 6)

1. Даны множества чисел: , , и универсальное множество .

Найти множества чисел , . Являются ли множества Е и D равными? эквивалентными? включающими одно в другое ( или )? пересекающимися, но не включающими одно в другое? непересекающимися ( )?

2. Из группы в 15 человек должны быть выделены бригадир и 4 члена бригады. Сколькими способами это можно сделать?

Решить задачу, используя комбинаторику.

3. Установить вид формулы алгебры логики:

.

4. С помощью таблицы истинности найти СДНФ и СКНФ булевой функции .

5. Дана матрица:

Построить ориентированный граф, для которого матрица B является матрицей инцидентности. Найти матрицу смежности.

6. Определить функцию , полученную из функций и по схеме примитивной рекурсии.

ВАРИАНТ 7

(для студентов, номера личных дел которых оканчиваются цифрой 7)

1. Даны множества чисел: , , и универсальное множество .

Найти множества чисел , . Являются ли множества Е и D равными? эквивалентными? включающими одно в другое ( или )? пересекающимися, но не включающими одно в другое? непересекающимися ( )?

2. Чемпионат по футболу проводится по круговой системе. За победу в матче дается два очка, за ничью – одно, а за поражение нуль. Если две команды набирают одинаковое количество очков, то место определяется по разности забитых и пропущенных мячей. Чемпион набрал семь очков, второй призер – пять, третий – три. Сколько очков набрала команда, занявшая последнее место?

Задачу решить, используя теорию графов.

3. Установить вид формулы алгебры логики:

.

4. Упростить формулу:

.

Проверить результат, используя таблицу истинности.

5.

Для орграфа, представленного на рисунке, найти матрицу смежности и матрицу инцидентности. Есть ли у данного графа циклы? Если есть, то приведите пример простого цикла.

6. Определить функцию , полученную из функций и по схеме примитивной рекурсии.

ВАРИАНТ 8

(для студентов, номера личных дел которых оканчиваются цифрой 8)

1. Даны множества чисел: , , и универсальное множество .

Найти множества чисел , . Являются ли множества Е и D равными? эквивалентными? включающими одно в другое ( или )? пересекающимися, но не включающими одно в другое? непересекающимися ( )?

2. Согласно опросу 250 телезрителей 95 из них нравится смотреть новости, 125 предпочитают смотреть спорт, 125 – комедии, 25 – новости и комедии, 45 – спорт и комедии, 35 – новости и спорт, 5 любят смотреть три вида программ. Сколько телезрителей смотрят спорт и комедии, но не смотрят новости?

Решить задачу, используя теория множеств.

3. Установить вид формулы алгебры логики:

.

4. С помощью таблицы истинности найти СДНФ и СКНФ булевой функции .

5. Даны матрицы:

и

Построить неориентированные графы, для которых матрица A является матрицей смежности, а матрица B – матрицей инцидентности.

6. Определить функцию , полученную из функций и по схеме примитивной рекурсии.

ВАРИАНТ 9

(для студентов, номера личных дел которых оканчиваются цифрой 9)

1. Даны множества чисел: , , и универсальное множество .

Найти множества чисел , . Являются ли множества Е и D равными? эквивалентными? включающими одно в другое ( или )? пересекающимися, но не включающими одно в другое? непересекающимися ( )?

2. На фирму должна приехать проверка из центрального офиса. На проверку могут приехать директор, главный бухгалтер и старший менеджер. Накануне были получены три телеграммы: 1) приедут или директор, или главный бухгалтер со старшим менеджером; 2) приедут директор и старший менеджер; 3) директор не приедет, приедет главный бухгалтер. Верной была только одна телеграмма. Приехали двое проверяющих. Кто это были?

Решить задачу, используя алгебру логики.

3. Установить вид формулы алгебры логики:

.

4. Упростить формулу:

.

Проверить результат, используя таблицу истинности.

5. На множестве V={0; 1; 2; 3; 4} задано отношение f: x = y(mod 2). Построить неориентированный граф данного отношения. Является ли этот граф связным? Найдите максимальную клику полученного графа.

6. Определить функцию , полученную из функций и по схеме примитивной рекурсии.

ВАРИАНТ 10

(для студентов, номера личных дел которых оканчиваются цифрой 0)

1. Даны множества чисел: , , и универсальное множество .

Найти множества чисел , . Являются ли множества Е и D равными? эквивалентными? включающими одно в другое ( или )? пересекающимися, но не включающими одно в другое? непересекающимися ( )?

2. Из лаборатории, в которой работает 20 человек, 5 сотрудников должны уехать в командировку. Сколько может быть различных составов этой группы, если начальник лаборатории, его заместитель и главный инженер одновременно уезжать не должны?

Решить задачу, используя комбинаторику.

3. Установить вид формулы алгебры логики:

.

4. С помощью таблицы истинности найти СДНФ и СКНФ булевой функции .

5.

Для графа, представленного на рисунке, найти матрицу смежности и матрицу инцидентности. Привести пример максимальной клики.

6. Определить функцию , полученную из функций и по схеме примитивной рекурсии.

Литература и электронные ресурсы

Основная литература

1. Галушкина Ю.И., Марьямов А.Н. Конспект лекций по дискретной математике. – М.: АЙРИС-пресс, 2007.

2. Гисин В.Б, Зададаев С.В., Орел О.Е. Руководство к решению задач по дискретной математике. .– М.: Финуниверситет, 2012.

3. Кремер Н.Ш., Путко Б.А., Тришин И.М. Математика для экономистов: от Арифметики до Эконометрики. Учебно-справочное пособие. / Под ред. Н.Ш. Кремера.– М.: Юрайт, 2014.

Дополнительная литература

4. Гисин В.Б. Лекции по дискретной математике. Ч. 1, 2. – М.: Финакадемия, 2003.

5. Кузнецов О.П. Дискретная математика для инженера. Спб.: Лань, 2009.

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

7. Палий И.А. Дискретная математика. Курс лекций. – М.: Эксмо, 2008.

8. Плотников А.Д. Дискретная математика. – М.: Новое знание, 2008.

9. Тюрин С.В., Аляев Ю.А. Дискретная математика. Практическая дискретная математика и математическая логика. – М.: Финансы и статистика, Инфра-М, 2010.

10. Шапорев С.Д. Дискретная математика. Курс лекций и практических занятий. – БХВ-Петербург, 2009.

Электронные ресурсы

1. Дискретная математика. Обзорная установочная лекция для студентов 2 курса направления «Бизнес-информатика». (http://repository.vzfei.ru.).

2. Компьютерная обучающая программа по дисциплине «Дискретная математика» (КОПР2 – М) – URL: http://repository.vzfei.ru. Доступ по логину и паролю.

3. Дискретная математика. Учебно-методическое пособие /под ред. Н.Ш. Кремера ] – М.: 2015 (электронная\ версия в разделе «Образовательные ресурсы» на сайте «Финансовый университет» ‒ заочное обучение). – URL: http://repository.vzfei.ru .

4. Н.Ш. Кремер, И.М Эйсымонт. Математика. Методические указания по проведению и выполнению контрольных работ с частичным использованием КОПР.– М.: ВЗФЭИ, 2009. 2015 (электронная\ версия в разделе «Образовательные ресурсы» на сайте «Финансовый университет» ‒ заочное обучение)( http://repository.vzfei.ru)..

5. Электронная библиотека ( http://www.bibliotekar.ru) .

Содержание

Введение………………………………………………………………………. 3

Содержание дисциплины и методические рекомендации по ее изучению. 4

Тема 1. Множества, функции, отношения …………………………… 5

Тема 2. Комбинаторика………………………………………………… .8

Тема 3. Математическая логика ……………………………………… 10

Тема 4. Теория графов…………………………………………….…… 15

Тема 5. Теория алгоритмов……………………………………………. 21

Вопросы для самопроверки………………………………………………… 29

Задачи для самоподготовки………………………………………………… 31

Методические указания по выполнению контрольной работы………….. 32

Варианты контрольной работы…………………………………………….. 34

Литература и электронные ресурсы……………………………………….. 44

Дискретная математики. Учебно-методическое пособие для студентов первого курса бакалавриата, , обучающихся по заочной форме по направлению «Бизнес-информатика». Под ред. проф. Н.Ш. Кремера. – М.: Финуниверситет, 2015.

[1] Учитывая, что учебный материал дисциплины недостаточно отражен в доступных для студента-заочника пособиях, содержание отдельных тем дается более подробно, чем это принято в методических пособиях (указаниях).

[2] Под универсальным множеством здесь понимается множество, включающее все множества, участвующие в рассматриваемой задаче.

[3] Множество называется счетным, если оно эквивалентно множеству натуральных чисел (его элементы можно перенумеровать).

[4] Здесь и далее для упрощения записи логическую связку ↔ заменяем обычным знаком равенства = .

[5] Учебный материал, отмеченный знаком *, не является обязательным.

[6] Напоминаем, что номер личного дела совпадает с номером студенческого билета и зачетной книжки студента.