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

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

направления 230100.62- Информатика и вычислительная техника

очной и заочной форм обучения

Нижневартовск

УДК 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-16 и рис. 1.1б для вариантов 17-32) с помощью алгоритма Прима найти стягивающее дерево минимального веса (в таблице 1.1 указаны веса некоторых дуг).

а) б)

Рис. 1. 1

Задача 2.

В графе (см. рис. 1.2а для вариантов 1-16 и рис. 1.26 для вариантов 17-32) с помощью алгоритма Дейкстры найти, кратчайший путь от i -й вершины-до всех остальных (в таблице 1.2 указаны номер i и веса некоторых дуг).

а) б)

Рис. 1.2

Задача 3.

Пусть проект описывается взвешенным графом (см. рис. 1.3а для вари­антов 1-16 и рис. 1.3б для вариантов 17-32), где дуги соответствуют опера­циям (этапам) проекта, а вес дуги обозначает время выполнения соответ­ствующей операции.

а)

б)

Рис. 1.3

Найти наименьшее время выполнения проекта, критические пути и резерв времени для выполнения операции u_i®u_j (в таблице 1.3 указаны номера i и j и веса некоторых дуг).

Задача 4.

Найти максимальный поток в транспортной сети (см. рис. 1.4а для вариантов 1-16 и рис. 1.4б для вариантов 17-32). Число рядом с дугой есть ее пропускная способность.

б)

Рис. 1.4

В таблице 1.4 указаны пропускные способности некоторых дуг.

Не нашли, что искали? Воспользуйтесь поиском: