diskr_matem
.pdf№ |
Название темы |
Номера задач |
|
||
темы |
|
По пособию [1] |
По пособию [2] |
|
По |
|
|
|
|
|
пособию[3] |
|
|
3-е практ. занят., |
Разд.1.1, прим.1‒ 4, |
|
|
|
Множества, |
1 – 5 |
упр.1‒ 8; |
|
|
|
4-е практ. занят., |
разд.1.2, прим.1,2,. |
|
5.1, 13.7, |
|
1 |
функции, |
|
|||
4 – 24 |
упр.10,11; |
|
13.8 |
||
|
отношения |
|
|||
|
|
разд.1.3, прим.1,2, |
|
|
|
|
|
|
|
|
|
|
|
|
упр.12‒ 15 |
|
|
2 |
Комбинаторика |
5-е практ. занят., |
Разд.3.1, прим.1‒ 6, |
|
1.10 – 1.15 |
1 – 14 |
упр.1‒ 16, 19‒ 26 |
|
|||
|
|
|
|
||
|
|
1-е практ. занят., |
Разд.1.4, прим.1‒ 4, |
|
|
3 |
Математическая |
1 – 24 |
упр.16‒ 19, 21,22; |
|
13.1 – 13.6 |
логика |
2-е практ. занят., |
разд.1.5, прим.1‒ 3, |
|
||
|
|
|
|||
|
|
1 – 12а |
упр.23‒ 31 |
|
|
|
|
7-е практ. занят., |
Разд.7.1, прим.2‒ 5, |
|
|
4 |
Теория графов |
1 – 16 |
упр.1‒ 3, 8‒ 11; |
|
14.1 – 14.4 |
|
разд.7.2, прим.1,2, |
|
|||
|
|
|
|
|
|
|
|
|
упр.15,16 |
|
|
|
Теория |
11-е практ. |
|
|
|
5 |
занят., 1 – 13 |
‒ |
|
14.5 – 14.6 |
|
алгоритмов |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
Методические указания по выполнению контрольной работы
В соответствии с учебным планом по дисциплине «Дискретная математика» каждый студент должен выполнить одну домашнюю
31
контрольную работу (по приведенным в данной брошюре вариантам) в сроки, установленные учебным графиком.
По контрольной работе студенты вечерних и дневных групп проходят собеседование. На собеседовании выясняется, насколько глубоко усвоен пройденный материал и соответствуют ли знания студента и его навыки в решении задач качеству представленной работы. Зачет по каждой контрольной работе студенты получают лишь после успешного прохождения собеседования.
Номер варианта контрольной работы определяется по последней цифре номера личного дела студента, который совпадает с номером его зачетной книжки и студенческого билета.
Сроки представления домашней контрольной работы на проверку указаны в индивидуальном графике студента, а для студентов дневных групп также сообщаются во время осенней установочной сессии. Однако эти сроки являются крайними. Чтобы работа была своевременно проверена, а при необходимости доработана и сдана повторно, ее надлежит представить значительно раньше указанного срока. Студентам дневных групп рекомендуется свою домашнюю контрольную работу выполнять во время установочной сессии, на которой излагается учебный материал. Это даст возможность студенту использовать свое пребывание в институте для консультаций по всем возникшим при выполнении работы вопросам. После окончания сессии в течение двух недель работу необходимо окончательно завершить, а затем представить на проверку.
Если в ходе написания работы у студента появятся вопросы или затруднения в решении задач контрольного задания, он может обратиться в институт за устной или письменной консультацией (например, по электронной почте на форум кафедры).
При изучении учебного материала и подготовке к контрольным работам рекомендуется использовать учебники и учебные пособия, электронные ресурсы, приведенные выше в разделе «Литература», а также данную брошюру.
После проверки контрольная работа студента получает оценку «Допускается к собеседованию» или «Не допускается к собеседованию».
Контрольная работа содержит набор заданий, при выполнении которых необходимо соблюдать следующие правила.
1.Работа должна быть выполнена в школьной тетради, имеющей широкие (не менее 3 см) поля для замечаний рецензента.
2.На обложке тетради следует указать фамилию, имя, отчество (полностью), факультет, специальность, курс, номер личного дела, вариант и номер контрольной работы, а также фамилию преподавателя к которому направляется данная работа на проверку.
3.Перед решением каждой задачи нужно привести (распечатать) полностью ее условие.
32
4.Следует придерживаться той последовательности при решении задач, в какой они даны в задании, строго сохраняя при этом нумерацию примеров (задач).
5.Не допускается замена задач контрольной работы другими заданиями.
6.Решения задач должны сопровождаться развернутыми пояснениями, нужно привести в общем виде используемые формулы с объяснением употребляемых обозначений, а окончательный ответ следует выделить.
7.В конце работы приводится список использованной литературы (указывают автора, название, издательство, год издания), ставится дата окончания работы и подпись.
Если работа получила в целом положительную оценку («Допускается к собеседованию»), но в ней есть отдельные недочеты (указанные в тетради), то нужно сделать соответствующие исправления и дополнения в той же тетради (после имеющихся решений и записи «Работа над ошибками») и предъявить доработку на собеседовании. Если работа «Не допускается к собеседованию», ее необходимо в соответствии с требованиями преподавателя частично или полностью переделать. Повторную работу надо выполнить в той же тетради (если есть место) или в новой с надписью на обложке «Повторная», указав фамилию преподавателя, которым работа была ранее не зачтена. Вместе с незачтенной работой, повторную работу представить снова на проверку.
Контрольная работа не зачитывается, если ее вариант не совпадает с последней цифрой номера личного дела студента или она выполнена по вариантам прошлых лет.
Студенты, не получившие зачета по контрольной работе, к экзаменационному зачету не допускаются. Если в соответствии с учебным графиком контрольная работа должна быть выполнена с частичным использованием КОПР, то для получения зачета по этой работе необходимо дополнительно представить протокол ответа студента о работе с КОПР. Зачтенные работы предъявляются на экзаменационном зачете и не подлежат возвращению после успешной сдачи экзаменационного зачета.
Для допуска к экзаменационному зачету необходимо также получить зачет по компьютерному тестированию, если оно предусмотрено учебным графиком по дисциплине «Дискретная математика».
ВАРИАНТЫ КОНТРОЛЬНОЙ РАБОТЫ6
6 Напоминаем, что номер личного дела совпадает с номером студенческого билета и зачетной книжки студента.
33
ВАРИАНТ 1
(для студентов, номера личных дел которых оканчиваются цифрой 1)
1. Даны множества чисел: |
A |
2, 3, 5, 6 , |
В |
5, 6, 7, 8 , |
С |
3, 4, 6, 8 |
и |
|||||||
универсальное множество U |
2, 3, 4, 5, 6, 7, 8, 9 . |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Найти множества чисел |
D |
С |
В |
В \ А |
|
А |
С , E |
А |
C С |
В . |
||||
Являются ли множества Е и D равными? эквивалентными? включающими |
||||||||||||||
одно в другое ( D E или E |
D )? пересекающимися, но не включающими |
|||||||||||||
одно в другое? непересекающимися ( D |
E |
)? |
|
|
|
|
|
|
|
|
|
|
||
2.Двенадцать работников отдела делятся на четыре равные по численности рабочие группы, которые занимаются разными задачами. В каждой назначается старший. Сколько возможно вариантов распределения людей по группам и назначения старшего в каждой группе?
Решить задачу, используя комбинаторику.
3.Установить вид формулы алгебры логики:
|
|
|
|
L A B C |
A B C . |
||
4. Упростить формулу:
A B A
A .
Проверить результат, используя таблицу истинности.
v1 |
4 |
v2 |
|
||
3 |
|
4 |
|
1 |
3
v5 |
2 |
|
|
5 |
|
|
5 |
|
|
|
|
|
|
v4 |
5.
Для нагруженного графа, представленного на рисунке, построить остовное дерево минимальной стоимости. Определить его стоимость.
v3 |
6. |
Определить функцию f x, y , полученную из функций g x х и |
h x, y, z |
z по схеме примитивной рекурсии. |
ВАРИАНТ 2
(для студентов, номера личных дел которых оканчиваются цифрой 2)
34
1. Даны множества чисел: A |
0, 1, 3, 4 |
, В 3, 4, 5, 6 , С |
1, 2, 4, 6 и |
|||||||
универсальное множество U |
0, 1, 2, 3, 4, 5, 6, 7 . |
|
|
|
|
|
||||
|
|
|
|
|
|
|
||||
Найти множества чисел D А |
В С В , E |
В |
А |
С В \ А . |
||||||
Являются ли множества Е и D равными? эквивалентными? включающими |
||||||||||
одно в другое ( D E или E |
D )? пересекающимися, но не включающими |
|||||||||
одно в другое? непересекающимися ( D |
E |
)? |
|
|
|
|
|
|||
2.Из 100 работников фирмы 42 владеют английским языком, 30 – французским, 28 – немецким. Десять человек – знают английский и немецкий, 8 – знают французский и немецкий, 5 – английский и французский. Три человека знают все три языка. Сколько работников фирмы не знают ни одного языка?
Решить задачу, используя теорию множеств.
3.Установить вид формулы алгебры логики:
|
|
|
|
|
|
|
|
|
L |
A |
B |
C |
|
A |
B C . |
||
4. С помощью таблицы истинности найти СДНФ и СКНФ булевой |
||||||||
функции f x1 , x2 x1 x2 x1 |
x2 . |
|
|
|
|
|
|
|
5. Дана матрица: |
|
|
|
|
|
|
|
|
|
|
0 |
1 |
1 |
0 |
1 |
|
|
|
|
0 |
0 |
1 |
0 |
0 |
|
|
|
A |
1 |
0 |
0 |
0 |
0 . |
|
|
|
|
1 |
0 |
1 |
0 |
0 |
|
|
|
|
0 |
0 |
0 |
1 |
0 |
|
|
Построить ориентированный граф, для которого матрица A является матрицей смежности. Найти матрицу инцидентности.
Являются ли полученный граф связным?
6. |
Определить функцию f x, y , полученную из функций g x х и |
h x, y, z |
х z по схеме примитивной рекурсии. |
ВАРИАНТ 3
(для студентов, номера личных дел которых оканчиваются цифрой 3)
35
1. Даны множества чисел: |
A |
1, 2, 4, 5 , |
В |
4, 5, 6, 7 , |
|
С |
2, 3, 5, 7 и |
||||||||
универсальное множество U |
1, 2, 3, 4, 5, 6, 7, 8 . |
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Найти множества чисел |
D |
A |
C |
B |
С , |
E |
B |
C |
A C \ В . |
||||||
Являются ли множества Е и D равными? эквивалентными? включающими |
|||||||||||||||
одно в другое ( D E или E |
D )? пересекающимися, |
но не включающими |
|||||||||||||
одно в другое? непересекающимися ( D |
E |
)? |
|
|
|
|
|
|
|
|
|
|
|||
2.На фирму должна приехать проверка из центрального офиса. На проверку могут приехать директор, главный бухгалтер и старший менеджер. Накануне были получены три телеграммы: 1) директор не приедет, приедет главный бухгалтер; 2) приедут главный бухгалтер и старший менеджер; 3) приедет или директор, или главный бухгалтер. Одна из телеграмм была послана по ошибке. Приехал один проверяющий. Кто это был?
Решить задачу, используя алгебру логики.
3.Установить вид формулы алгебры логики:
L 
A B
C 
A B C 
.
4. Упростить формулу:
A B
B A .
Проверить результат, используя таблицу истинности.
5. На множестве V={0; 1; 2; 3; 4} задано отношение f: x > y +1. Построить орграф данного отношения.
6. |
Определить функцию f x, y , полученную из функций g x х и |
h(x, y, z) |
x y z по схеме примитивной рекурсии. |
ВАРИАНТ 4
(для студентов, номера личных дел которых оканчиваются цифрой 4)
36
1. Даны множества чисел: |
A |
0, 1, 3, 4 , |
В 3, 4, 5, 6 , |
С |
1, 2, 4, 6 |
|
и |
|||||
универсальное множество U |
0, 1, 2, 3, 4, 5, 6, 7 . |
|
|
|
|
|
|
|||||
Найти множества чисел |
|
|
|
|
|
С \ В , E |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
D |
|
В |
C \ A |
A |
C С |
B |
. |
|||||
Являются ли множества Е и D равными? эквивалентными? включающими |
||||||||||||
одно в другое ( D E или E |
D )? пересекающимися, но не включающими |
|||||||||||
одно в другое? непересекающимися ( D |
|
E |
)? |
|
|
|
|
|
|
|||
2.В шахматном турнире по круговой системе участвуют семь шахматистов. Известно, что игрок A сыграл шесть партий, B – пять, C и D – по три, E и F – по две, а G – одну. С кем сыграл игрок C?
Задачу решить, используя теорию графов.
3.Установить вид формулы алгебры логики:
|
|
|
|
|
|
|
L |
A |
|
B |
B A B A . |
||
4. С помощью таблицы истинности найти СДНФ и СКНФ булевой |
||||||
функции f x1 , x2 x1 x2 |
x1 |
x2 . |
||||
e1
1 |
e |
2 |
2 |
|
|
|
e3 e5 e6
3
5 |
e |
7 |
|
|
e4
4
5.
Для графа, представленного на рисунке, найти матрицу смежности и остовное дерево. Определить цикломатическое число.
6. Определить функцию f x, y , полученную из функций g( x ) x и h x , y , z z2 по схеме примитивной рекурсии.
ВАРИАНТ 5
(для студентов, номера личных дел которых оканчиваются цифрой 5)
37
1. Даны множества чисел: |
A |
2, 3, 5, 6 |
, В |
5, 6, 7, 8 , |
С 3, 4, 6, 8 |
и |
|||||
универсальное множество U |
2, 3, 4, 5, 6, 7, 8, 9 . |
|
|
|
|
|
|||||
Найти множества чисел |
|
|
|
|
A , E |
|
|
|
A . |
||
D |
|
A B |
C |
C |
A \ B C |
||||||
Являются ли множества Е и D равными? эквивалентными? включающими |
|||||||||||
одно в другое ( D E или E |
D )? пересекающимися, |
но не включающими |
|||||||||
одно в другое? непересекающимися ( D |
|
E |
)? |
|
|
|
|
|
|||
2.Из 71 школьников в волейбол играют 51, в футбол – 45, в баскетбол
–31. Во все три игры играют 8 ребят, в волейбол и футбол – 28, в волейбол и баскетбол – 20, в футбол и баскетбол – 16. Сколько школьников играют только в баскетбол?
Решить задачу, используя теорию множеств.
3.Установить вид формулы алгебры логики:
L 
A B
A C 
A C .
4. Упростить формулу:
A B A B .
Проверить результат, используя таблицу истинности.
5.
v1 |
|
|
|
4 |
1 |
|
|
9 |
|
||
|
|
||
v4 |
6 |
|
|
3 |
v5 |
v2 |
|
5 |
7 |
||
8 |
|||
|
|
||
|
2 |
|
v3 |
Для нагруженного графа, представленного на рисунке, построить остовное дерево минимальной стоимости. Определить его стоимость.
6. Определить функцию f x, y , полученную из функций g x 1 и h x , y , z xz по схеме примитивной рекурсии.
ВАРИАНТ 6
(для студентов, номера личных дел которых оканчиваются цифрой 6)
38
1. Даны множества чисел: |
A 0, 1, 3, 4 |
, |
В |
3, 4, 5, 6 , |
С |
1, 2, 4, 6 |
и |
|||||||
универсальное множество U |
0, 1, 2, 3, 4, 5, 6, 7 . |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Найти множества чисел |
D |
A \ B |
C |
|
A |
C , |
E |
A |
C |
A \ C |
B . |
|||
Являются ли множества Е и D равными? эквивалентными? включающими |
||||||||||||||
одно в другое ( D E или E |
D )? пересекающимися, |
но не включающими |
||||||||||||
одно в другое? непересекающимися ( D |
E |
)? |
|
|
|
|
|
|
|
|
|
|||
2.Из группы в 15 человек должны быть выделены бригадир и 4 члена бригады. Сколькими способами это можно сделать?
Решить задачу, используя комбинаторику.
3.Установить вид формулы алгебры логики:
|
|
|
|
|
|
|
|
|
|
|
|
L |
A |
B |
C |
A |
B |
C . |
|
||
4. С помощью таблицы истинности найти СДНФ и СКНФ булевой |
||||||||||
функции f x1 , x2 x1 x2 |
x1 |
x2 . |
|
|
|
|
|
|
|
|
5. Дана матрица: |
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
|
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
0 |
|
B |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
|
0 . |
|
|
0 |
0 |
0 |
0 |
1 |
1 |
0 |
|
0 |
|
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
||
Построить ориентированный граф, для которого матрица B является матрицей инцидентности. Найти матрицу смежности.
6. Определить функцию f x, y , полученную из функций g(x) 1 и h(x, y, z) xy по схеме примитивной рекурсии.
ВАРИАНТ 7
(для студентов, номера личных дел которых оканчиваются цифрой 7)
39
1. Даны множества чисел: |
A |
1, 2, 4, 5 , |
В |
4, 5, 6, 7 , |
|
С |
2, 3, 5, 7 и |
|||||||||
универсальное множество U |
1, 2, 3, 4, 5, 6, 7, 8 . |
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Найти множества чисел |
D |
А |
С |
С |
B , |
E |
B |
C |
A C \ B . |
|||||||
Являются ли множества Е и D равными? эквивалентными? включающими |
||||||||||||||||
одно в другое ( D E или E |
D )? пересекающимися, |
но не включающими |
||||||||||||||
одно в другое? непересекающимися ( D |
E |
)? |
|
|
|
|
|
|
|
|
|
|
||||
2.Чемпионат по футболу проводится по круговой системе. За победу в матче дается два очка, за ничью – одно, а за поражение нуль. Если две команды набирают одинаковое количество очков, то место определяется по разности забитых и пропущенных мячей. Чемпион набрал семь очков, второй призер – пять, третий – три. Сколько очков набрала команда, занявшая последнее место?
Задачу решить, используя теорию графов.
3.Установить вид формулы алгебры логики:
|
|
|
|
L A B C |
A B C . |
||
4. Упростить формулу:
A B B A .
Проверить результат, используя таблицу истинности.
5. |
|
|
|
|
|
|
|
|
|
|
|
2 |
e3 |
3 |
Для орграфа, представленного на |
||||
|
e1 |
|
|
|
рисунке, |
найти |
матрицу |
||
|
|
|
|
смежности |
|
и |
матрицу |
||
|
|
|
|
|
|
||||
|
e |
4 |
e5 |
e6 |
e7 инцидентности. |
Есть |
ли |
у |
|
|
1 |
|
|
|
данного графа циклы? Если есть, |
||||
|
e2 |
|
|
|
|||||
|
|
|
|
то приведите |
пример |
простого |
|||
|
|
|
|
|
|||||
|
|
5 |
e8 |
4 |
цикла. |
|
|
|
|
6. |
Определить функцию |
f x, y , |
полученную из функций g (x) |
0 и |
|||||
h(x, y, z) |
x2 z по схеме примитивной рекурсии. |
|
|
|
|
||||
ВАРИАНТ 8
(для студентов, номера личных дел которых оканчиваются цифрой 8)
40