Международная
«Лига развития науки и образования» (Россия)
Международная ассоциация развития науки,
образования и культуры России (Италия)
НОУ ВПО «Институт управления»
(г. Архангельск)
ЯРОСЛАВСКИЙ ФИЛИАЛ
Учебно-методические материалы для студентов
по дисциплине «Дискретная математика»
для студентов направления:
320700.62 Прикладная информатика
профиль подготовки:
«Прикладная информатика в экономике»
Квалификация (степень) выпускника: бакалавр
Ярославль
филиал «Института управления»
2012
СОДЕРЖАНИЕ:
1. Самостоятельная работа студентов…………………………………. | 3 |
2. Методические рекомендации для студентов……………………….. | 4 |
3. Рекомендуемая литература…………………………………………… | 5 |
4. Примерная тематика контрольных работ……………………………. | 6 |
5. Условия прикладных задач…………………………………………… | 6 |
6. Программные вопросы для подготовки к зачету…………………… | 8 |
7. Примерные варианты тестов по дисциплине……………………….. | 10 |
1. Самостоятельная работа студентов
Самостоятельная работа студентов является важнейшей составной частью учебного процесса. В соответствии с учебным планом на самостоятельную работу отводится 85,6 % учебного времени.
Самостоятельная работа представляет собой внеаудиторную учебную деятельность студента, предполагает изучение программного учебного материала и направлена на подготовку к лекционным и семинарским занятиям, выполнение рефератов, анализа литературы по установленной тематике, а также иных учебных заданий. Самостоятельная работа включает также подготовку студента к зачету, тестированию и др.
Самостоятельная работа студентов способствует развитию ответственности и организованности, творческого подхода к решению проблем учебного и профессионального уровня.
Самостоятельная работа студента предполагает различные формы индивидуальной учебной деятельности: аннотирование научной литературы; сбор и анализ практического материала в периодике, средствах СМИ или Интернете; выполнение тематических творческих заданий, рефератов. Выбор форм и видов самостоятельной работы определяются индивидуально-личностным подходом к обучению самого студента.
Применяемые формы организации самостоятельной работы.
1. Фронтальная самостоятельная работа – основными особенностями являются: общее для всех студентов задание; общий инструктаж преподавателя по выполнению задания; использование общих приемов организации и руководства дальнейшими действиями студентов.
Фронтальная форма целесообразна, когда студенты приступают к изучению темы, когда важно вызвать интерес к новой теме, а также на начальном этапе формирования умений, когда студенты овладевают способами выполнения заданий по образцу.
2. Индивидуальная самостоятельная работа – основными особенностями являются: возрастание роли студента в определении содержания работы, выборе способа ее выполнения; появление возможности сотрудничества студента с преподавателем, особенно при выполнении трудоемких заданий. Индивидуальные задания вызывают личностное отношение к материалу, стимулируют активность.
3. Групповая самостоятельная работа – эта форма работы используется для совместной проработке материала учебника, документа и др.; подготовке к семинарским занятиям с использованием элементов игрового метода, когда студенты готовятся в составе групп (ролевых групп, оппонентных групп, обсуждение гипотетических сценариев развития ситуации и др.).
Самостоятельная работа студентов направлена на решение задач, определенных преподавателем.
В ходе самостоятельной работы студент решает следующие задачи:
– самостоятельно применяет в процессе самообразования учебно-методические материалы, разработанные профессорско-преподавательским составом филиала (Института) в помощь студенту;
– изучает учебную и научную литературу, углубляет и расширяет знания, полученные на аудиторных занятиях;
– осуществляет поиск ответов на поставленные преподавателем вопросы и решает задачи;
– самостоятельно изучает отдельные темы (разделы) дисциплины, определенные для самостоятельной работы студентов;
– самостоятельно планирует процесс освоения материала в сроки, предусмотренные графиком учебного процесса;
– совершенствует умение анализировать и обобщать полученную информацию;
– развивает навыки научно-исследовательской работы.
Самостоятельная работа студента включает виды занятий и перечень вопросов для самостоятельного изучения, отраженные в пункте 4.
В качестве видов самостоятельной внеаудиторной работы студентов предусмотрены:
· подготовка к лекциям и другим видам занятий;
· самостоятельная работа студентов по изучению тем (разделов) дисциплины, определенные для самостоятельной работы студентов;
· подготовка к сдаче экзамена.
2. Методические рекомендации для студентов
Учебная дисциплина «дискретная математика» обеспечивает приобретение студентами знаний об основных дискретных математических моделях, умения применять математические методы в приложениях к задачам экономики и информатики, навыков применения их в практической работе.
Для усвоения теоретической части курса необходимо изучить вопросы, рассматриваемые на лекциях.
Прежде чем приступить к выполнению заданий, необходимо изучить материал лекций и сопоставить его с трактовками, предлагаемыми в источниках списка рекомендованной (основной и дополнительной) литературы. Следует учитывать тот факт, что время, отводимое на лекционный курс, не позволяет охватить весь учебный курс дисциплины «дискретная математика». Поэтому в процессе освоения дисциплины для лучшего усвоения материала необходимо регулярно обращаться к литературным источникам, предлагаемым в библиографическом списке и, кроме этого, пользоваться через компьютерную сеть филиала института и при самостоятельной подготовке в домашних условиях образовательными ресурсами, а также общедоступными Интернет-порталами, содержащими большое количество как научно-популярных, так и узкоспециализированных статей, посвященных различным аспектам учебной дисциплины.
После изучения материала по определенной теме студентам предлагается выполнить задания и подготовиться к практическому занятию. При возникновении затруднений в подготовке к занятиям рекомендуется после изучения лекционного материала и рекомендованной литературы обратиться по проблемным вопросам за консультацией к преподавателю и затем самостоятельно выполнить задания.
3. Рекомендуемая литература
а) основная литература
1. Шапорев математика. Курс лекции и практических занятий. СПБ.: БХВ-Петербург, 2006. – 400 с.
2. Новиков математика для программистов: учебное пособие. – СПБ.: Питер, 2007. – 416 с.
б) дополнительная литература:
1. Тишин математика в примерах и задачах. СПБ.: БХВ-Петербург, 2008. – 352 с.
в) базы данных, информационно-справочные и поисковые системы
1. Справочно-информационная система Гарант, Консультант.
4. Примерная тематика контрольных работ:
1.Алгебра множеств.
2.Алгебра отношений.
3.Элементы комбинаторики и комбинаторного анализа.
4.Алгебра логики.
5.Логика предикатов.
6.Теория графов.
7.Теория кодирования.
8.Теория алгоритмов.
9.Теория автоматов.
5. Условия прикладных задач
1.Даны множества 
,
, 
.
Найдите а) 
, б) 
,
в) 
, г) 
.
2.Даны множества
, 
, 
, 
, 
.
Найдите прямые (Декартовы) произведения следующих множеств и изобразите их на плоскости. а) 
, б) 
, в) 
, г) 
, д) 
.
, 
- множества натуральных и целых чисел соответственно.
3.Докажите, что для любых множеств 
, 
, 
верны равенства
, 
.
4. Построив таблицы функций, выяснить эквивалентны ли формулы 
и 
.
; 
.
5. Для функции 
найти все импликанты, указать среди них простые, записать сокращенную ДНФ.
6. Построив таблицу функции 
, построить для неё совершенную дизъюнктивную нормальную форму (СДНФ) и совершенную конъюнктивную нормальную форму (СКНФ), найти сокращенную ДНФ с помощью минимизирующей карты Карно.
7. Для функции 
построить таблицу истинности, записать СДНФ, СКНФ, найти сокращенную ДНФ с помощью минимизирующей карты Карно.
8. Для функции построить полином Жегалкина. Сделать проверку.
9. Построить матрицы смежности и инцидентности для графа представляющего собой прямоугольник с одной диагональю. Найти диаметр и радиус графа.
10. Дана матрица весов 
графа.
.
Найти: а) величину минимального пути и сам путь от вершины 
до вершины 
по алгоритму Дейкстры;
б) по алгоритму Фалкерсона упорядочить вершины графа и найти величину максимального пути и сам путь от вершины до вершины .
11. Для графа, заданного матрицей весов , построить минимальный по весу остов и найти его вес.
12. Выяснить является ли алфавитное кодирование, с кодирующим алфавитом 
, заданное схемой 
однозначно декодируемым, если
: 
13. Дан набор вероятностей 
.
а) построить двоичные коды Фано и Хаффмана для данного набора вероятностей. Найти средние длины, кодов.
б) построить оптимальный 
код.
14. Построить код Хэмминга, содержащий 3 информационных символа.
15. По каналу связи передавалось кодовое слово, построенное по методу Хэмминга. После передачи по каналу связи, искажающему слово не более чем в одном разряде, было получено слово 
. Восстановить исходное сообщение.
Тему контрольной работы и задачу студент выбирает в соответствии с последней цифрой шифра зачетной книжки.
6. Программные вопросы для подготовки к экзамену:
1.Множества и основные операции над ними. Диаграммы Эйлера-Венна.
2.Отношение включения. Конечные множества: формула включений и исключений, подсчет количества элементов в конечных множествах.
3.Булеан. Булев куб и координаты подмножеств.
4.Геометрия Булева куба, расстояние Хэмминга.
5.Декартовы (прямые) произведения. Понятие об n-арном отношении.
6.Бинарные отношения и их свойства.
7.Эквивалентности и разбиения множеств.
8.Фактор множество.
9.Отношение порядка: линейный и лексико-графический.
10.Метод математической индукции.
11.Основные формулы комбинаторики.
12.Реккурентные соотношения и треугольник Паскаля.
13.Отображения и их свойства.
14.Подсчет числа отображений.
15.Метод производящих функций.
16.Булевы переменные и булевы функции.
17.Теорема о числе булевых функций от n переменных.
18.Представление функций формулами.
19.Функции от 1-й и 2-х переменных.
20.Приложения булевых функций к алгебре логики и релейно-контактным схемам.
21.Принцип двойственности.
22.СДНФ и СКНФ.
23.Минимизация в классе ДНФ.
24.Полиномы Жегалкина.
25.Полнота и замкнутость.
26.Основные классы булевых функций.
27.Теорема Поста.
28.Понятие предиката: теоретико-множественный и логический подходы.
29.Область истинности предиката.
30.Операции над предикатами.
31.Кванторы.
32.Формулы логики предикатов.
33.Логический вывод.
34.Графы, орграфы и их основные характеристики.
35.Представление графов матрицами.
36.Геометрические графы и планарность.
37.Части графа, связность и сильная связность.
38.Пути, цепи, контуры и циклы в графе.
39.Эйлеровость и квазиэйлеровость.
40.Деревья и леса. Помеченные деревья.
41.Основная теорема о деревьях.
42.Теорема Кэли.
43.Алфовитное кодирование.
44.Критерий однозначности декодирования.
45.Канальное кодирование.
46.Линейные коды.
47.Групповые коды.
48.Понятие об алгоритме.
49.Тьюренгов подход к понятию алгоритма.
50.Машины Тьюринга, их сочетания.
51.Алгоритмически неразрешимые проблемы, проблема самоприменимости.
52.Нормальные алгоритмы Маркова.
53.Разрешимость и вычислимость.
54.Рекурсивные функции.
55.Понятие о конечных автоматах.
56.Автоматы Мура.
57.Автоматы Мили.
58.Граф автомата.
59.Сети из автоматов.
7. Примерные варианты тестов по дисциплине
Вариант 1
1.Дано универсальное множество U={1,2,3,4,5,6,7} и в нем подмножества A={x| x < 5}, B={2,4,5,6}, C={1,3,5,6}.
Найти 
(Указать правильные варианты ответов).
a. {1,2,2,3,4,4,5,6}
b. {1,2,3,4,5,6}
c. {x| x < 7, 
}
d. {1,3}
e. {3,4,2,5,1,6}
2.Дано универсальное множество U={1,2,3,4,5,6,7} и в нем подмножества A={x| x < 4}, B={2,4,5,7}, C={1,2,5,6}.
Найти 
(Указать правильные варианты ответов).
a. {1,1,2,2,3,5,6}
b. {1,2,3,5,6}
c. {x| x < 7}
d. {3,2,6,1,5}
e. {1,2}
3.Дано универсальное множество U={1,2,3,4,5,6,7} и в нем подмножества A={x| x > 4}, B={3,5,7}, C={1,2,4,6}.
Найти 
(Указать правильные варианты ответов).
a. U
b. {3,5,7}
c. 
d. {3,5,7,1,2,4,6}
e. {1,2,3,4,5,6,7}
4.Дано универсальное множество U={1,2,3,4,5,6,7} и в нем подмножества A={x| x < 5}, B={2,4,5,6}, C={1,3,5,6}.
Найти 
(Указать правильные варианты ответов).
a. {1,2,3,4,5,5,6,6}
b. {6,5}
c. {1,2,3,4,5,6}
d. {x| x < 7}
e. {5,6}
5.Дано универсальное множество U={1,2,3,4,5,6,7} и в нем подмножества A={x| x < 4}, B={2,4,5,7}, C={1,2,5,6}. Найти 
(Указать правильные варианты ответов).
a. {1,2,3,4,5,7}
b. {1,2,2,3,4,5,7}
c. {2}
d. {5,6}
e. {x| x=2}
6.Дано универсальное множество U={1,2,3,4,5,6,7} и в нем подмножества A={x| x > 4}, B={3,5,7}, C={1,2,4,6}.
Найти 
(Указать правильные варианты ответов).
a. {7,5}
b. {3,5,6,7}
c. {5,7,5,7}
d. {5,7}
e. {x| 2 < x < 8}
7.Дано универсальное множество U={1,2,3,4,5,6,7} и в нем подмножества A={x| x < 5}, B={2,4,5,6}, C={1,3,5,6}.
Найти декартово (прямое) произведение 
, где 
(Указать правильные варианты ответов).
a. {1,3,5,6}
b. {(1,1), (3,1), (1,3), (3,3), (1,5), (3,5), (1,6), (3,6)}
c. {(1,1), (1,3), (3,3), (1,5), (3,5), (1,6), (3,6)}
d. { (1,3), (1,5), (3,5), (1,6), (3,6)}
e. { (3,3), (1,5), (3,5), (1,6), (3,6), (1,1), (3,1), (1,3)}
f. {1,1,3,3,5,6}
8.Дано универсальное множество U={1,2,3,4,5,6,7} и в нем подмножества A={x| x < 4}, B={2,4,5,7}, C={1,2,5,6}.
Найти декартово (прямое) произведение 
, где 
(Указать правильные варианты ответов).
a. {1,2,3,6}
b. {(1,1), (6,1), (1,2), (6,2), (1,3), (6,3)}
c. { (1,1), (1,6), (1,2), (2,6), (1,3), (3,6)}
d. {1}
e. {(1,1), (1,2), (1,3), (6,1), (6,2), (6,3)}
f. {(6,3), (1,1), (1,3), (6,1), (6,2), (1,2)}
9.Дано универсальное множество U={1,2,3,4,5,6,7} и в нем подмножества A={x| x > 4}, B={3,5,7}, C={1,2,4,6}.
Найти декартово (прямое) произведение 
, где 
(Указать правильные варианты ответов).
Варианты ответов:
a. {1,2,3,4,5,7}
b. {(3,1),(5,1),(7,1),(3,2),(5,2),(7,2),(3,4),(5,4),(7,4)}
c. U - {4}
d. {(1,3),(2,3),(3,4),(1,5),(2,5),(4,5),(1,7),(2,7),(4,7)}
e. {(3,1),(3,2),(3,4),(5,1),(5,2),(5,4),(7,1),(7,2),(7,4)}
f.
10.Справедлив ли дистрибутивный закон?
a. да
b. нет
11.Справедлив ли дистрибутивный закон?
a. да
b. нет
12.Справедлив ли дистрибутивный закон?
a. да
b. нет
13.Справедлив ли дистрибутивный закон?
a. да
b. нет
14.Справедлив ли дистрибутивный закон?
a. да
b. нет
15.Справедлив ли дистрибутивный закон?
a. да
b. нет
16.Справедлив ли дистрибутивный закон?
a. да
b. нет
17.Справедлив ли дистрибутивный закон?
a. да
b. нет
18.Справедлив ли дистрибутивный закон?
a. да
b. нет
19.Сколькими способами можно выбрать 3 различных карандаша из имеющихся 5 карандашей разных цветов? (Ввести ответ в виде числа)
20.Сколькими способами можно разделить 5 различных карандашей между двумя школьниками так, чтобы у каждого был хотя бы один карандаш? (Ввести ответ в виде числа)
21.Сколькими способами можно разделить 8 шахматистов на две команды по 4 человека? (Ввести ответ в виде числа)
22.Граф G задан следующей матрицей смежности:
Найти радиус r(G) графа.
23.Граф G задан следующей матрицей смежности:
Найти диаметр d(G) графа.
24.Граф G задан следующей матрицей смежности:
Найти радиус r(G) графа.
25.Граф G задан следующей матрицей смежности:
Найти диаметр d(G) графа.
26.Граф G задан следующей матрицей смежности:
Найти радиус r(G) графа.
27.Граф G задан следующей матрицей смежности:
Найти диаметр d(G) графа.
28.Сколько существует неизоморфных деревьев с 6 вершинами?
29.Сколько существует неизоморфных связных графов с 5 вершинами и 4 ребрами?
30.Сколько существует неизоморфных связных графов с 5 вершинами и 5 ребрами?
ВАРИАНТ 2
1.Пусть граф G с n вершинами является деревом. Тогда: (Выберите для G верные утверждения)
a. число ребер m = n - 1
b. граф связный
c. граф не содержит циклов
d. граф планарный
e. граф не эйлеров
f. есть вершина степени 1
g. есть вершина степени больше 1
2.Пусть граф G с n вершинами является несвязным. Тогда: (Выберите для G верные утверждения.)
a. число компонент связности всегда равно 2
b. число компонент связности может быть равно 2
c. степень каждой вершины не превосходит n - 2
d. число компонент связности больше 1
e. граф не может быть двудольным
f. граф планарный
g. граф не может быть деревом
3.Пусть граф G с n вершинами является двудольным. Тогда: (Выберите для G верные утверждения.)
a. в нем нет циклов четной длины
b. в нем могут быть циклы четной длины (+7 баллов)
c. в нем все циклы имеют четную длину (+7 баллов)
d. граф связный
e. степень каждой вершины не превосходит n - 2
f. граф содержит цикл, если каждая доля содержит не менее двух вершин
g. граф планарный
4.Является ли планарным следующий граф:
a. да
b. нет
5.Является ли планарным следующий граф:
a. да
b. нет
6.Является ли планарным следующий граф:
a. да
b. нет
7.Является ли планарным следующий граф:
a. да
b. нет
8.Является ли планарным следующий граф:
a. да
b. нет
9.Является ли планарным следующий граф:
a. да
b. нет
10.Сколько граней у плоского графа:
11.Сколько граней у плоского графа:
12.Сколько граней у плоского графа:
13.Сколько граней у плоского графа:
14.Сколько граней у плоского графа:
15.Сколько граней у плоского графа:
16.По дереву найти соответствующий ему код Прюфера P(t) (Указать его вариант).
a. P(t) =3)
b. P(t) =4)
c. P(t) =3)
17.По дереву найти соответствующий ему код Прюфера P(t) (Указать его вариант).
a. P(t) =7)
b. P(t) =7)
c. P(t) =7)
18.По дереву найти соответствующий ему код Прюфера P(t) (Указать его вариант).
a. P(t) =3)
b. P(t) =2)
c. P(t) =2 )
19.Для функции f, заданной вектором 
, определить, является ли она:
a. линейной
b. монотонной
c. самодвойственной
d. функцией из класса 
e. функцией из класса 
20.Для функции f, заданной вектором 
, определить, является ли она:
a. линейной
b. монотонной
c. самодвойственной
d. функцией из класса
e. функцией из класса
21.Для функции f, заданной вектором 
, определить, является ли она:
a. нелинейной
b. монотонной
c. самодвойственной
d. функцией из класса
e. функцией из класса
22.Для функции 
определить, является ли она:
a. линейной
b. монотонной
c. самодвойственной
d. функцией из класса
e. функцией из класса
23.Для функции 
определить, является ли она:
a. линейной
b. немонотонной
c. самодвойственной
d. функцией из класса
e. функцией из класса
24. Для функции 
определить, является ли она:
a. линейной
b. монотонной
c. несамодвойственной
d. функцией из класса
e. функцией из класса
25.Полна ли система функций {f, g, h} (принадлежность функций классам 
отображена в таблице).
a. да
b. нет
26.Полна ли система функций {F, G, H} (принадлежность функций классам отображена в таблице).
a. да
b. нет
27.Полна ли система функций {f, g, h} (принадлежность функций классам отображена в таблице).
a. да
b. нет
28.Верно ли, что:
a. да
b. нет
29.Верно ли, что:
a. да
b. нет
30.Верно ли, что:
a. да
b. нет
