|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ЮЖНО-УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ,
ФИЛИАЛ В Г.НИЖНЕВАРТОВСКЕ
КАФЕДРА «ИНФОРМАТИКА»
|
Дискретная математика
Методические указания для самостоятельной работы студента
направления 230100.62- Информатика и вычислительная техника
очной и заочной форм обучения
Нижневартовск
2014
УДК 519.2
© Зверева Е.А.
Одобрено
редакционно-издательским советом филиала
(протокол № 2 от 16.10.2014)
Дискретная математика: методические указания для самостоятельной работы студента направления 230100.62 «Информатика и вычислительная техника» очной и заочной форм обучения / Е.А. Зверева – Нижневартовск, 2014. – 21 с.
Задания составлены в соответствии с ФГОС-3 по направлению обучения 230100.62- Информатика и вычислительная техника и предназначены для формирования общекультурных компетенций по дисциплине «Дискретная математика». Данное методическое руководство содержит задания к РГР, методику их решения, а также примерный перечень вопросов для подготовки к экзамену.
Рецензент:
доцент кафедры естественнонаучных и гуманитарных дисциплин, к.ф.-м.н., О.Р. Нурисламов;
Утверждено на заседании кафедры
Протокол №2
«9» октября 2014 год
ВВЕДЕНИЕ
Методические указания для самостоятельной работы студентов предназначены для студентов очной и заочной форм обучения, обучающихся по направлению 230100.62 Информатика и вычислительная техника. Методические указания составлены в соответствии:
- требованиями ФГОС-3 по направлению подготовки 230100.62 Информатика и вычислительная техника;
- с рабочей программой по дисциплине "Дискретная математика»
В рамках изучение данной дисциплины предусматривается:
- чтение лекций, в которых даются фундаментальные понятия дискретной математики — о логике, множествах, графах, отношениях и булевых функциях, теории графов;
- проведение практических занятий, которые предполагают конкретизацию и углубленную проработку лекционного материала, акцентирование практической направленности полученных знаний, освоение и закрепление изучаемых вопросов посредством решения как теоретических, так и практических задач.
Самостоятельная работа студентов по дисциплине «Дискретная математика» состоит из подготовки к экзамену, включающей дополнительное изучение специальной литературы, а также подготовку и выполнение РГР.
Данное методическое руководство содержит задания к РГР, методику их решения, а также примерный перечень вопросов для подготовки к экзамену.
РГР предусматривает решение каждым студентом четырех задач Выбор задания определяется номером варианта, который соответствует порядковому номеру в журнале. РГР выполняется в тетради. На обложку тетради наклеивается титульный лист со всеми данными автора работы. Условия каждой задачи записываются полностью. Решение сопровождается подробными объяснениями. В условии задачи и ее решении не допускаются никакие сокращения слов. Отчет сдается на кафедру за 10 дней до защиты РГР.
1 Задание на работу
Задача 1
В графе (см. рис. 1.1а для вариантов 1-16 и рис. 1.1б для вариантов 17-32) с помощью алгоритма Прима найти стягивающее дерево минимального веса (в таблице 1.1 указаны веса некоторых дуг).
2
1
2
d
c
2
a
b
1
1
1
1
2
6
5
3
4
7
2
1
2
3
d
c
2
a
b
3
1
2
6
5
8
3
4
7
1
1
1
а) б)
Рис. 1. 1
Таблица 1.1
|
№ варианта
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
а
|
1
|
1
|
1
|
2
|
2
|
4
|
6
|
5
|
1
|
1
|
1
|
2
|
2
|
4
|
6
|
5
|
b
|
2
|
4
|
6
|
5
|
3
|
5
|
7
|
7
|
2
|
4
|
6
|
5
|
3
|
5
|
7
|
7
|
c
|
1
|
7
|
1
|
1
|
1
|
8
|
1
|
1
|
8
|
8
|
1
|
1
|
1
|
9
|
8
|
8
|
d
|
2
|
2
|
7
|
2
|
2
|
9
|
8
|
2
|
2
|
2
|
8
|
2
|
9
|
2
|
9
|
9
|
№ варианта
|
17
|
18
|
19
|
20
|
21
|
22
|
23
|
24
|
25
|
26
|
27
|
28
|
29
|
30
|
31
|
32
|
а
|
4
|
1
|
1
|
2
|
2
|
4
|
6
|
5
|
1
|
1
|
1
|
2
|
2
|
4
|
6
|
5
|
b
|
2
|
4
|
6
|
5
|
3
|
5
|
7
|
7
|
2
|
4
|
6
|
5
|
3
|
5
|
7
|
7
|
c
|
2
|
6
|
9
|
9
|
9
|
9
|
9
|
9
|
7
|
7
|
7
|
7
|
7
|
7
|
4
|
4
|
d
|
1
|
4
|
7
|
7
|
4
|
4
|
1
|
1
|
9
|
9
|
4
|
4
|
1
|
1
|
9
|
9
| |
