Методичні вказівки до самостійного вивчення курсу Основи дискретної математики затверджено icon

Методичні вказівки до самостійного вивчення курсу Основи дискретної математики затверджено




Скачати 291.92 Kb.
НазваМетодичні вказівки до самостійного вивчення курсу Основи дискретної математики затверджено
Дата14.09.2012
Розмір291.92 Kb.
ТипМетодичні вказівки

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ


Вінницький національний технічний університет

Інститут автоматики, електроніки та комп’ютерних систем управління


С.Д.Штовба


МЕТОДИЧНІ ВКАЗІВКИ


до самостійного вивчення курсу


Основи дискретної математики


ЗАТВЕРДЖЕНО


на засіданні кафедри комп'ютерних систем управління


Протокол №1 від 1 вересня 2009 р.


Вінниця ВНТУ 2009




ВСТУП

Дисципліна “Основи дискретної математики” надає студентам базові теоретичні знання та сприяє набуттю практичних навичок із теорії множин, теорії алгоритмів, формальних систем, графів та дискретних екстремальних задач, які необхідних для розуміння студентами місця та ролі дискретної математики в майбутній фаховій діяльності.

Знання, набуті студентами, будуть витребуванні під час професійної діяльності в галузі створення та експлуатації систем управління і автоматики.

При вивченні дисципліни студентам знадобляться знання з “Вищої математики” та “Алгоритмічних мов та програмування”. Отримані знання використовуватимуться при вивченні дисциплін “Методи оптимізації”, “Дослідження операцій”, “Теорія автоматичного управління”, “Теорія інформації та кодування”, “Автоматизовані системи управління технологічними процесами”, “Штучний інтелект та розпізнавання образів” в дипломному проектуванні та при підготовці магістрів.

В результаті вивчення дисципліни студенти знатимуть:

  • місце і роль дискретної математики в сучасній фаховій діяльності інженерів-електриків;

  • термінологію дискретної математики;

  • основи теорії алгоритмів;

  • базові понятті теорії графів;

  • популярні задачі дискретної оптимізації.

На основі набутих знань студенти вмітимуть:

  • застосовувати апарат дискретної математики розв’язанні практичних задач.
^

ПЕРЕЛІК ОСНОВНИХ ТЕМ ТЕОРЕТИЧНОГО МАТЕРІАЛУ



Вступ

Мета і задача курсу. Структура дисципліни. Неперервність та дискретність математики. Історичні передумови сучасної дискретної математики. Видатні науковці. Місце і роль дискретної математики в інженерній діяльності. Книжки, журнали та інтернет-ресурси з дискретної математики.

Література: основна [1 С.7-13, 3 С. 4-9]; додаткова [2 С. 12-27].


^ Множини та операції над ними

Множини та підмножини. Потужність множини. Способи завдання множин. Теоретико-множини операції: об’єднання, перетин, доповнення. Добуток множин. Характеристична функція.

Література: основна [1 С.14-20, 3 С. 9–17; 5 С. 12–16].


^ Нечіткі множини.

Визначення нечіткої множини. Ступінь належності. Функція належності. Зв’язок функції належності та характеристичної функції. Теоретико-множини операції об’єднання, перетину та доповнення над нечіткими множинами.

Література: основна [1 С.23-27], додаткова [1 С. 11–17, 4 С. 9–17, 5 С. 7–9, 7 С. 4–26].


^ Відображення і функції

Відображення. Образ. Прообраз. Функціональне відображення. Функції. Багатомісні функції. Способи завдання функцій.

Література: основна [1 С.89-93, 3 С.19–29, 5 С.39–45].


Відношення

Визначення. Способи завдання відношень. Бінарне відношення. Приклади. Властивості відношень: рефлексивність, симетричність, транзитивність. Операції над відношеннями: об’єднання, перетин, доповнення, композиція, транзитивне замикання.

Література: основна [1 С.81–88, 3 С.29–36].


^ Основи теорії графів

Поняття графу. Основні терміни і визначення. Неорієнтовані і орієнтовані графи. графи. Поняття вершин, ребер і дуг графа. Суміжні вершини і ребра. Графічне і матричне представлення графів. Матриця суміжності і матриці інцидентності.

Література: основна [1 С.234–239, 3 С.88-98, 5 С.178–180].

^ Основи теорії алгоритмів

Основні поняття і властивості алгоритмів. Основні вимоги до алгоритмів. Формалізація алгоритму рекурсивними функціями та машиною Тюрінга.

Література: основна [1 С.108–141, 3 С.144–215, 5 С.159–162].


^ Основи теорії формальних систем

Визначення формальної системи. Вимоги до формальних систем: інтерпретуємість, несуперечність, повнота, аксіоматизуємість. Принципи побудови формальних систем. Формальні граматики.

Література: основна [1 С.147–182, 3 С.217–281].


^ Складність алгоритмів

Поняття складності алгоритму. Етапи визначення складності алгоритму: точний опис алгоритму; визначення розмірності задачі; визначення кількості операцій. Класифікація алгоритмів за складністю: P- та NP-алгоритми.

Література: основна [3 С. 350–398, 4 С.352-369, 5 С.168–177].
^

Задача про Кенігсбергські мости


Обходи графа. Маршрути, ланцюги, шляхи і цикли. Властивості зв'язних графів. Вершинна і реброва зв'язність. Дерева. Ліси. Цикли і дерева. Остов дерева. Властивості дерев. Задача про Кенігсбергські мости. Ейлерові та гамільтонові цикли.

Література: основна [1 С.243-253, 3 С. 99–105].
^

Задача про найкоротший шлях на орієнтованому графі


Орієнтовані графи. Орієнтовані маршрути, ланцюги, шляхи і цикли. Способи завдання орієнтованих графів. Знаходження найкоротшого шляху на графі: постановка задачі, алгоритм розв’язання, приклад.

Література: основна [3 С.124–130]


^ Задача про розфарбування графу

Розбиття вершин графу на класи. Помічені вершини. Задача розфарбування вершин графу. Проблема чотирьох фарб.

Література: основна [1 С.254–255, 3 С.131–135].


^ Задача про комівояжера

Змістовна та формалізована постановки задачі. Розв’язання задачі методом динамічного програмування. Приклад. Бібліотека тестових задач TSPLIB.

Література: основна [12 С.102–109].


^ Популярні екстремальні задачі дискретної оптимізації

Задача маршрутизації вантажівок. Квадратична задача про призначення. Задача про рюкзак. Задача про мінімальне остовне дерева. Задача про максимальний потік. Складність задач. Огляд евристичних алгоритмів їх розв’язання.

Література: основна [4 С.112–165].


^ Мурашині алгоритми розв’язання задач дискретної оптимізації

Основні принципи функціонування колонії мурах: додатній та від’ємний зворотній зв’язки, випадковість та багатократність дій. Стигмержі та феромони. Мурашиний алгоритм оптимізації маршруту комівояжера. Порівняння з іншими метаевристичними алгоритмами оптимізації.

Література: додаткова [6 C.1–16].


^
КОНТРОЛЬНІ ЗАПИТАННЯ ТА ЗАВДАННЯ ДЛЯ
САМОСТІЙНОГО ВИКОНАННЯ

Електроні бази даних статей та підручників з дискретної математики.

Література: основна [1 С.7-13, 3 С. 4-9]; додаткова [2 С. 12-27].


Алгебра множин.

Література: основна [1 С.14-20, 3 С. 9–17; 5 С. 12–16].


Синглтоні нечіткі множини.

Література: основна [1 С.23-27], додаткова [1 С. 11–17, 4 С. 9–17, 5 С. 7–9, 7 С. 4–26].


13-та проблема Гільберта.

Література: основна [1 С.89-93, 3 С.19–29, 5 С.39–45].


Відношення еквівалентності. Відношення порядку.

Література: основна [1 С.81–88, 3 С.29–36].


Представлення відображення графом.

Література: основна [1 С.234–239, 3 С.88-98, 5 С.178–180].


Операції над машиною Тюрінга.

Література: основна [1 С.108–141, 3 С.144–215, 5 С.159–162].


Контексно-вільна граматика.

Література: основна [1 С.147–182, 3 С.217–281].


Розрахунок складності алгоритмів сортування.

Література: основна [3 С. 350–398, 4 С.352-369, 5 С.168–177].


Алгоритми знаходження ейлерового циклу.

Література: основна [1 С.243-253, 3 С. 99–105].


Експериментальні дослідження часу розв’язання тестових задач TSPLIB.

Література: основна [12 С.102–109].


Розв’язання означених задач методом гілок та меж.

Література: основна [4 С.112–165].


Алгоритм мурашиної колонії.

Література: додаткова [6 C.1–16].


^ Завдання для самостійної роботи


Варіант №1

Завдання 1. Намалювати граф за стрічковою матрицею, яку наведено на рисунку. Обґрунтувати переваги на недоліки представлення графа матрицею суміжності та стрічковою матрицею.

7

5

5

2

4

4

3

6

5

6

6

3

5

1

4

1

Рисунок. Стрічкова матриця графа

Завдання 2. Розробити алгоритм перетворення довільної стрічкової матриці графа в матрицю cуміжності. Проілюструвати роботу алгоритму на матриці з завдання 1.

Завдання 3. Матриця відстаней між вершинами графа наведена в таблиці. Знайти маршрути мінімальної довжини для кожної пари вершин. Визначити ребра графа, збільшення довжини яких не відобразиться на мінімальних маршрутах.
^

Таблиця. Відстані між вершинами графа





A

B

C

D

E

F

A

0



10

30



25

B



0





8



C

10



0

11



3

D

30



11

0

22

11

E



8



22

0

10

F

25



3

11

10

0



^

Варіант №2


Завдання 1. Намалювати граф за матрицею cуміжності, яку наведено в таблиці 1. Обґрунтувати переваги на недоліки представлення графа матрицею суміжності та стрічковою матрицею.
^

Таблиця. Матриця суміжності графа





1

2

3

4

5

6

1

1

0

1

0

0

1

2

0

1

0

0

1

0

3

0

0

0

0

1

0

4

1

0

0

0

0

0

5

0

1

1

0

0

0

6

0

0

0

1

1

0

Завдання 2. Розробити алгоритм перетворення довільної матриці суміжності графа в стрічкову матрицю. Проілюструвати роботу алгоритму на матриці з завдання 1.

Завдання 3. Матриця відстаней між вершинами графа наведена в таблиці 2. Знайти маршрути мінімальної довжини для кожної пари вершин. Визначити ребра графа, збільшення довжини яких не відобразиться на мінімальних маршрутах.
^

Таблиця. Відстані між вершинами графа





A

B

C

D

E

F

A

0



10

30



25

B



0





8



C

10



0

11



3

D

30



11

0

22

11

E



8



22

0

10

F

25



3

11

10

0
^

Варіант №3


Завдання 1. Намалювати граф за стрічковою матрицею, яку наведено на рисунку. Обґрунтувати переваги на недоліки представлення графа матрицею суміжності та стрічковою матрицею.

7

5

2

2

4

4

3

6

5

6

6

3

5

1

7

1

Рисунок. Стрічкова матриця графа

Завдання 2. Розробити алгоритм перетворення довільної стрічкової матриці графа в матрицю cуміжності. Проілюструвати роботу алгоритму на матриці з завдання 1.

Завдання 3. Матриця відстаней між вершинами графа наведена в таблиці. Знайти маршрути мінімальної довжини для кожної пари вершин. Визначити ребра графа, збільшення довжини яких не відобразиться на мінімальних маршрутах.
^

Таблиця. Відстані між вершинами графа





A

B

C

D

E

F

A

0





20



25

B



0





8



C

10



0

10



3

D

20



11

0

22

11

E



8



5

0

10

F

25



3

11

10

0
^

Варіант №4


Завдання 1. Намалювати граф за матрицею cуміжності, яку наведено в таблиці 1. Обґрунтувати переваги на недоліки представлення графа матрицею суміжності та стрічковою матрицею.
^

Таблиця. Матриця суміжності графа





1

2

3

4

5

6

1

1

0

0

0

0

1

2

0

1

0

0

1

0

3

0

0

1

0

1

0

4

1

0

0

0

0

0

5

0

1

1

0

0

0

6

0

0

0

1

1

0

Завдання 2. Розробити алгоритм перетворення довільної матриці суміжності графа в стрічкову матрицю. Проілюструвати роботу алгоритму на матриці з завдання 1.

Завдання 3. Матриця відстаней між вершинами графа наведена в таблиці 2. Знайти маршрути мінімальної довжини для кожної пари вершин. Визначити ребра графа, збільшення довжини яких не відобразиться на мінімальних маршрутах.
^

Таблиця. Відстані між вершинами графа





A

B

C

D

E

F

A

0



10

30



25

B



0





8



C

20



0

11



3

D

3



11

0



11

E



8



22

0

10

F

5



3

11

10

0


^ Варіанти №№5-24

Задача 1. Розв’язати задачу комівояжера методом динамічного програмування. Матрицю відстаней для усіх варіантів наведено в табл. 1. Звіт має містити усі проміжні результати. За зразок оформлення можна взяти С.103-104 з книги [2].

Задача 2. Побудувати мінімальне остовне (кістякове) дерево для графу з задачі 1. Граф зробити неорієнтованим, без кратних ребер. Розв’язання задачі здійснити за пожадливим алгоритмом. За зразок оформлення можна взяти С.225–228 з книги [6].

Задача 3. Знайти мінімальні відстані між кожною парою вершин графа з задачі 1. Розв’язання задачі здійснити за алгоритмом Флойда. За зразок оформлення можна взяти С.238–241 з книги [6].

^

Відстані між пунктами

























0

29

13

18

6

18

14

23

24

12




7

0

26

27

11

2

28

24

20

23




16

13

0

20

24

18

9

18

26

17




17

27

28

0

23

25

23

18

20

13




18

15

25

19

0

26

5

3

14

21




22

23

24

19

21

0

21

27

12

26




6

29

17

9

18

27

0

17

30

23




11

5

13

18

14

17

17

0

6

30




19

27

13

28

8

22

23

22

0

29




7

10

14

10

25

25

18

21

20

0



^

Варіанти завдань


Варіант

Початковий та кінцевий пункт

Проміжні пункти

A

B C D E

B

J C F G

C

B I H J

D

J F G I

E

G H I A

F

E D B C

G

F J B C

H

A B C D

I

E F G H

J

D F G A

A

E C F G

B

I E H J

C

A B G I

D

C H I A

E

I A B C

F

D J B C

G

A H C D

H

E F G A

I

D J G B

J

B D F I



^ ВКАЗІВКИ ДО ПІДГОТОВКИ ДО ПРАКТИЧНИХ РОБІТ


Множини та операції над ними

Множини та підмножини. Потужність множини. Характеристична функція Теоретико-множини операції: об’єднання, перетин, доповнення.

Література: основна [1 С.14-20, 3 С. 9–17; 5 С. 12–16].


^ Нечіткі множини.

Представлення невизначеної інформації нечіткими множинами. Параметричні функції належності. Теоретико-множини операції об’єднання, перетину та доповнення над нечіткими множинами.

Література: основна [1 С.23-27], додаткова [1 С. 11–17, 4 С. 9–17, 5 С. 7–9, 7 С. 4–26].


Відношення

Бінарне відношення. Перевірка рефлексивності, симетричності, транзитивності відношення. Операції над відношеннями: об’єднання, перетин, доповнення, композиція, транзитивне замикання.

Література: основна [1 С.81–88, 3 С.29–36].


^ Основи теорії графів

Неорієнтовані і орієнтовані графи. графи. Знаходження суміжних вершин і ребер графу. Графічне і матричне представлення графів. Матриця суміжності і матриця інцидентності.

Література: основна [1 С.234–239, 3 С.88-98, 5 С.178–180].


^ Основи теорії алгоритмів

Перевірка основних властивостей алгоритмів. Запис алгоритма блок-схемою та псевдокодом. Формалізація алгоритму машиною Тюрінга.

Література: основна [1 С.108–141, 3 С.144–215, 5 С.159–162].


^ Формальні граматики

Розробка формальної породжувальної граматики: алфавіту термінальних символів; алфавіту нетермінальних символів; аксіом; множини правил виведення.

Література: основна [1 С.147–182, 3 С.217–281].


^ Складність алгоритмів

Визначення складності алгоритмів з невеликою кількістю операторів та логічних умов. Класифікація алгоритмів за складністю: P- та NP-алгоритми. Профілювання програм.

Література: основна [3 С. 350–398, 4 С.352-369, 5 С.168–177].
^

Задача про Кенігсбергські мости


Знаходження маршрутів, ланцюгів, шляхів і циклів графу. Розв’язання задачі про Кенігсбергські мости: постановка задачі; алгоритм; контрольний приклад.

Література: основна [1 С.243-253, 3 С. 99–105].


^ Задача про розфарбування графу

Розбиття вершин графу на класи. Розв’язання задачі розфарбування вершин графу: постановка задачі; алгоритм; контрольний приклад. Проблема чотирьох фарб.

Література: основна [1 С.254–255, 3 С.131–135].


^ Задача про комівояжера

Розв’язання задачі про комівояжера різними методами Порівняння складності алгоритмів розв’язання задачі про комівояжера

Література: основна [12 С.102–109].


^ Задача про рюкзак

Змістовна та формалізована постановки задачі. Алгоритм розв’язання. Контрольний приклад. Розрахунок складності алгоритму.

Література: основна [4 С.112–165].


^ Квадратична задача про призначення

Змістовна та формалізована постановки задачі. Алгоритм розв’язання. Контрольний приклад. Розрахунок складності алгоритму.

Література: основна [4 С.112–165].
^ ОРГАНІЗАЦІЯ ВИВЧЕННЯ ДИСЦИПЛІНИ ЗА КМС


Трудомісткість дисципліни 3*36*51= 540.

Трудомісткість модулів 1.5*36*51= 270.


Таблиця 1 – Відповідність оцінок

% балів

Оцінка

Абс. бальна за 1-й модуль

Абс. бальна за 2-й модуль

Абс. бальна з дисципліни

за нац. шкалою

за 12-бальною шкалою

за шкалою ECTS

[100, 97)

відмінно

5+

A

262-270

262-270

524-540

[94, 97)

5

254-261

254-261

508-523

[91, 94)

5-

246-253

246-253

492-507

[85, 91)

добре

4+

B

230-245

230-245

459-491

[80, 85)

4

C

216-229

216-229

432-458

[75, 80)

4-

203-215

203-215

405-431

[71, 75)

задовільно

3+

D

195-202

195-202

384-404

[68, 71)

3

E

184-194

184-194

368-383

[65, 68)

3-

176-183

176-183

351-367

[40, 65)

незадовільно

*

FX

108-175

108-175

216-350

[27, 40)

2+

F

73-107

73-107

146-215

[14, 27)

2

36-73

36-73

76-145

[0, 14)

2-

0-35

0-35

0-75



Таблиця 2 – Кількість і зміст модулів

Модуль

Кредити

Лекції, год.

Практичні заняття, год.

Колоквіум.

І

1.5

16

8

1

ІІ

1.5

16

8

1



Таблиця 3 – Оцінюванння знань, умінь навичок студентів з окремих видів робіт та в цілому по модулях (в балах)

Вид роботи

Модуль


І

ІІ

1. Відповіді на практичних занняттях

40

40

2. Виконання завдань з СРС

30

30

3. Колоквіум

200

200

Всього


270

270



ЛІТЕРАТУРА
Основна література

  1. Бардачов Ю.М., Соколова Н.А., Ходаков В.Є. Дискретна математика. – К.: Вища школа, 2002. – 287с.

  2. Глушков В.М. Введение в АСУ. К.: Техніка – 1974.

  3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988.– 480 с.

  4. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – М.: Мир, 1985. – 512 с.

  5. Biggs N. L. Discrete Mathematics. – Oxford: Oxford University Press, 2nd eds., 2002. – 425p.

  6. Таха Х. Введение в исследование операций. – М.: Издательский дом «Вильямс», 2001. – 911 с.


Додаткова література

  1. Заде Л. Понятие лингвистической переменной и его применение к принятию приближенных решений. – М.: Мир, 1976. – 165 с.

  2. Коршунов Ю.М. Математические основы кибернетики. – М.: Энергия, 1972.

  3. Новиков Ф.А. Дискретная математика для программистов. – СПб: Питер, 2001.

  4. Ротштейн А.П. Интеллектуальные технологии идентификации: нечеткая логика, генетические алгоритмы, нейронные сети. – Винница: УНІВЕРСУМ–Вінниця, 1999. – 320 с.

  5. Орловский С.А. Проблемы принятия решений при нечеткой исходной информации. М.: Радио и связь.- 1981.- 286с.

  6. Штовба С.Д. Муравьиные алгоритмы: теория и применение // Программирование. – 2005. – №4.– C. 1–16.

  7. Zimmerman H.-J. Fuzzy Sets Theory and Its Applications.3rd ed. – Kluwer Academic Publisher, 1996. – 435 p.




Схожі:

Методичні вказівки до самостійного вивчення курсу Основи дискретної математики затверджено iconМетодичні вказівки з дискретної математики
Методичні вказівки з дискретної математики для практичних занять та самостійної роботи студентів 1 курсу денної та заочної форми...
Методичні вказівки до самостійного вивчення курсу Основи дискретної математики затверджено iconМетодичні вказівки до практичних занять з курсу Основи дискретної математики затверджено
Знання, набуті студентами, будуть витребуванні під час професійної діяльності в галузі створення та експлуатації систем управління...
Методичні вказівки до самостійного вивчення курсу Основи дискретної математики затверджено iconМетодичні вказівки до самостійного вивчення курсу "Споживачі електроенергії "
Методичні вказівки до самостійного вивчення курсу "Споживачі електроенергії" (для студентів 4 курсу денної І 5 курсу заочної форм...
Методичні вказівки до самостійного вивчення курсу Основи дискретної математики затверджено iconМетодичні вказівки до самостійного вивчення курсу “Фінансовий ринок”
Методичні вказівки до самостійного вивчення курсу “Фінансовий ринок” І проведення практичних занять (для студентів 5 курсу спеціальності...
Методичні вказівки до самостійного вивчення курсу Основи дискретної математики затверджено iconМетодичні вказівки до самостійного вивчення курсу «фінансова статистика»
Методичні вказівки до самостійного вивчення курсу «Фінансова статистика» (для студентів 3 курсу заочної форми навчання спец. 050100...
Методичні вказівки до самостійного вивчення курсу Основи дискретної математики затверджено iconХарківська національна академія міського господарства методичні вказівки
Методичні вказівки до самостійного вивчення курсу “Основи екології” (для студентів 2 курсу денної форми навчання спеціальності 120100...
Методичні вказівки до самостійного вивчення курсу Основи дискретної математики затверджено iconХарківська національна академія міського господарства с. С. Родченко методичні вказівки до самостійного вивчення курсу
Методичні вказівки до самостійного вивчення курсу «Система національних рахунків» (для студентів заочної форми навчання за напрямом...
Методичні вказівки до самостійного вивчення курсу Основи дискретної математики затверджено iconМетодичні вказівки для самостійного вивчення теми «гроші» з курсу «Основи економічної теорії» для студентів усіх форм навчання
Методичні вказівки для самостійного вивчення теми «Гроші» з курсу «Основи економічної теорії» для студентів усіх форм навчання /...
Методичні вказівки до самостійного вивчення курсу Основи дискретної математики затверджено iconХарківська національна академія міського господарства методичні вказівки
Методичні вказівки до самостійного вивчення курсу “Основи утилізації відходів”(для студентів 4 курсу денної І 5 курсу заочної форм...
Методичні вказівки до самостійного вивчення курсу Основи дискретної математики затверджено iconХарківська національна академія міського господарства методичні вказівки
Методичні вказівки до самостійного вивчення курсу “Основи екології” (для студентів 2 курсу денної форми навчання спеціальності 070900...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи