Файл: Дискретная мат-ка_УМП.pdf

Министерство образования и науки Российской Федерации 

Федеральное государственное бюджетное образовательное  

учреждение высшего профессионального образования 

ТОМСКИЙ  ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ  СИСТЕМ 

УПРАВЛЕНИЯ  И  РАДИОЭЛЕКТРОНИКИ 

Кафедра компьютерных систем в управлении 

и проектировании (КСУП)

Е. Ф. Жигалова  

ÑàëäêÖíçÄü åÄíÖåÄíàäÄ 

Учебное

методическое

пособие

2014

 
 
 
Корректор: Осипова Е. А. 
 
 
 
 
 
 
 
 
Жигалова Е. Ф. 
Дискретная математика: учебное методическое пособие. — Томск: 
Факультет дистанционного обучения, ТУСУР, 2014. — 82 с. 
 
 

 
Учебное  методическое  пособие  содержит  требования  по  выполне-

нию лабораторных работ, задания на лабораторные работы,  варианты ис-
ходных данных к ним. В качестве теоретической базы при выполнении ла-
бораторных работ следует  использовать  учебное  пособие Жигалова  Е.  Ф. 
Дискретная математика : учебное пособие / Е. Ф. Жигалова. — Томск : Эль 
Контент, 2014.

© Жигалова Е. Ф., 2014 

                                                              © Факультет дистанционного 

                     обучения, ТУСУР, 2014 

3 

ëÓ‰ÂðʇÌË 

Введение............................................................................................................4 

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

Лабораторная работа № 1.................................................................................7 

Лабораторная работа № 2.................................................................................9 

Приложение А Пример оформления титульного листа ...............................11 

Приложение Б Варианты исходных данных для выполнения                                

пп. 1—7 лабораторной работы № 1 .........................................................12 

Приложение В Значения элементов матрицы смежности R(r[i,j]) ..............52 

Приложение Г Задача нахождения кратчайших маршрутах в графе. 

Алгоритм Дейкстры..................................................................................58 

Приложение Д Исходные данные к задаче нахождения                       

гамильтонова цикла в графе (задача коммивояжера) .............................63 

Приложение Е Задача о максимальном потоке на сети.                               

Алгоритм Форда—Фалкерсона................................................................72 

Приложение Ж Варианты булевой функции ................................................77 

Приложение З Логические функции двух переменных ...............................80 

Приложение И Законы булевой алгебры ......................................................81

4 

ǂ‰ÂÌË 

Дисциплина  «Дискретная математика»  изучается на протяжении од-

ного семестра. В процессе освоения дисциплины  помимо изучения  теоре-

тического материала студент должен выполнить две лабораторные работы. 

Отчет  по  каждой  лабораторной  работе  студент  отправляет  на  про-

верку.  Рецензент  проверяет  правильность  выполнения  всех  пунктов  зада-

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

торой преподавателем приводится описание ошибок в тех или иных пунк-

тах заданий (в случае их наличия).  

Выбор варианта лабораторных работ осуществляется по общим пра-

вилам с использованием следующей формулы:  

V = (N*K) div 100, 

где V — искомый номер варианта, 

N — общее количество вариантов, 

div — целочисленное  деление  (после  деления  дробная  часть  отбра-

сывается), при V= 0 выбирается максимальный вариант, 

K — значение 2-х последних цифр пароля. 

Количество  вариантов  в  лабораторных  работах  не  совпадает,  поэто-

му номера вариантов для двух лабораторных работ будут различаться. 

5 

åÂÚӉ˘ÂÒÍË Û͇Á‡ÌËfl ÔÓ ‚˚ÔÓÎÌÂÌ˲ 

··Óð‡ÚÓðÌ˚ı ð‡·ÓÚ 

鷢ˠÛ͇Á‡ÌËfl 
Целью  лабораторного  практикума  является  закрепление  теоретиче-

ских знаний по дисциплине «Дискретная математика», приобретение прак-

тических  навыков  по  моделированию  дискретных  объектов,  изучаемых  в 

данном курсе, и операций над ними.  

íð·ӂ‡ÌËfl Í ÒÓ‰ÂðʇÌ˲ Ë ÓÙÓðÏÎÂÌ˲ ÓÚ˜fiÚ‡  
Отчеты по лабораторным работам должны быть выполнены с помо-

щью  текстового  редактора Word. Требования  к  оформлению:  шрифт  ос-

новного текста Times New Roman, 12—14 пунктов, через 1,5—2 межстроч-

ных интервала. 

Отчет к лабораторной работе должен содержать: 

1.  Титульный  лист.  Пример  оформления  титульного  листа  пред-

ставлен в Приложении А. 

2.  Задание  —  включает  задание  на  лабораторную  работу,  перечень 

вопросов  для  изучения,  исходные  данные  для  выполнения  лабораторной 

работы в соответствии с выбранным вариантом. 

3.  Введение  —  содержит  общую  информацию  по  изучаемой  теме: 

краткую  характеристику  решаемой  задачи,  описание  метода,  алгоритма 

решения поставленной задачи. 

4. Основная часть отчёта — включает: математическую постановку 

задачи;  описание  алгоритма  решения  задачи;  результат  решения  каждого 

шага применяемого алгоритма или итерации (если применялся итерацион-

ный алгоритм).