close

Вход

Забыли?

вход по аккаунту

?

Дискретная

код для вставкиСкачать
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Львівський національний університет імені Івана Франка
Економічний факультет Кафедра економічної кібернетики
“ЗАТВЕРДЖУЮ” Декан___________професор Панчишин С.М.
“_____” _____________200
7
р.
РОБОЧА НАВЧАЛЬНА ПРОГРАМА
ДИСКРЕТНИЙ АНАЛІЗ
Спеціальність - 6
.050100 “Економічна кібернетика”
ВИПИСКА З НАВЧАЛЬНОГО ПЛАНУ
Семестр
К-сть
В тому числі
Заліки
Іспити
Самостійна
ауд.год.
Лекц.
Практ.
Лаб.
робота
6
51
34
17
6
69
Всього
год.
3
2
1
Програму склалв доцент Баранкевич М.М.
_______________
Розглянуто на засіданні кафедри економічної кібернетики
Зав. кафедрою ___________проф. Вовк В.М.
“_____”_____________200
7
р. Рекомендовано Вченою Радою економічного факультету
“____”_________200
7
р.
Голова Ради економічного факультету професор Панчишин С.М. I
. АНОТАЦІЯ
“Дискретний аналіз” – це дисципліна, яка є основою курсів математичного
циклу, що вивчають сучасні прикладні економіко-математичні методи.
Крім того окремі розділи цієї дисципліни (теорія графів, теорія множин)
мають також самостійне широке застосування при дослідженні економічних
систем.
Метою вивчення даної дисципліни є ознайомлення студентів з
теоретичними основами дискретної математики, які складають фундамент ряду
математичних дисциплін, що застосовуються при кількісному економічному
аналізі.
ІІ .
ПЕРЕЛІК ТЕМ
Тема 1.
Основи теорії множин.
Тема 2.
Відношення. Тема 3.
Алгебра висловлень.
Тема 4.
Диз’юнктивні нормальні форми.
Тема 5.
Кон’юнктивні нормальні форми.
Тема 6.
Булеві функції.
Тема 7.
Алгебра Жигалкіна.
Тема 8. Повні системи булевих функцій.
Тема 9.
Властивості булевих функцій. Теорема Поста.
Тема 10.
Мінімальні диз’юнктивні нормальні форми.
Тема 11.
Контактні схеми.
Функціональні схеми. Побудова тестів.
Тема 12.
Логіка предикатів.
Тема 13.
Основи теорії графів.
Тема 14.
Задача про м
аксимальний потік.
Тема 15.
Задача про призначення.
Тема 16.
Алгоритм Літла про гамільтонів цикл.
Тема 17.
Елементи комбінаторики.
ІІІ.
ПЕРЕЛІК ТА ЗМІСТ ТЕМ
Тема 1.
Основи теорії множин.
( 2 год )
1
.
Предмет та зміст курсу .
2
.
Важливість теоретико-множинного підходу в дослідженнях
.
3.Поняття множини. Способи задання множин. Операції над множинами. Тотожності.
4.Метод рішення системи рівнянь відносно однієї невідомої множини.
Тема 2.
Відношення. 1
.Поняття відношення. Бінарні відношення. Способи завдання бінарних відношень.
2.Властивості бінарних відношень.
3.Складні відношення ( повне, нестрогого, строгого порядку, еквівалентність, домінування)
.
4.
Операції над відношеннями (об
’
єднання, перетин, доповнення, різниця, композиція відношень, обернене та двоїсте відношення)
.
Тема 3.
Алгебра висловлень.
1.
Поняття висловлень
.
Основні логічні операції
.
2
.
Логічні закони
.
3.
Логічні формули
. Рівносильні формули
.
4.
Тавтологія
. Теореми про тaвтологію
.
Тема 4.
Диз’юнктивні нормальні форми.
Тема 5.
Кон’юнктивні нормальні форми.
Тема 6.
Булеві функції.
1.Поняття булевих функцій. Булеві функції однієї та двох змінних.
2.
Диз’юнктивна та кон
’
юнктивна нормальні форми
.
3.
Досконалі нормальні форми
.
4.
Контактні схеми
.
Тема 7.
Алгебра Жигалкіна.
Тема 8
. Повні системи булевих функцій.
Тема 9.
Властивості булевих функцій. Теорема Поста.
Тема 10. Мінімальні диз’юнктивні нормальні форми.
Тема 11
. Контактні схеми.
Функціональні схеми. Побудова тестів.
Тема 12.
Логіка предикатів.
1.
Поняття предикату. Приклади. Операції логіки предикатів. Формули
логіки предикатів.
2.
Квантори. Правило внесення заперечення під знак квантора.
3.
Поняття рівносильних, приведених та нормальних формул. Теорема про
існування нормальної форми.
4.
Теоретико-множинний зміст предикатів та операції над ними.
Тема 13.
Основи теорії графів.
1.
Історія виникнення теорії графів.
2.
Поняття графа. Операції над графами.
3.
Ейлерів граф. Алгоритм знаходження ейлеревого циклу.
Тема 14.
Задача про м
аксимальний потік.
Тема 15
. Задача про призначення.
Тема 16.
Алгоритм Літла про гамільтонів цикл.
Тема 17.
Елементи комбінаторики.
IV
. ПЕРЕЛІК ПРАКТИЧНИХ ЗАНЯТЬ
Тема 1.
Доведення множинних тотожностей.
Тема 2.
Системи множинних рівнянь.
Тема 3.
Перетворення логічних виразів.
Тема 4.
Побудова досконалої диз’юнктивної нормальної форми.
Тема 5.
Побудова полінома Жигалкіна.
Тема 6.
Побудова мінімальної диз’юнктивної нормальної форми.
Тема 7.
Перетворення графів.
Тема 8.
Оптимальні задачі на графи.
Тема 9.
Алгоритм Літла.
ПЕРЕЛІК ТА ЗМІСТ ПРАКТИЧНИХ ЗАНЯТЬ
Практичне заняття №1.
Тема:
„
Доведення множинних тотожностей
”
.
Мета:
Розглянути операції над множинами, а також за допомогою них навчитись
доводити тотожності.
План заняття:
1.
Основні поняття теорії множин.
2.
Способи задання множин.
3.
Алгебра множин.
4.
Доведення множинних тотожностей.
Завдання для самостійного опрацювання.
Довести тотожність
:
1)
B
A
=
A
B
A
)
\
(
;
2)
)
(
\
\
B
A
A
B
A
=
;
3)
)
\
(
\
)
\
(
\
)
\
(
C
B
C
A
C
B
A
=
;
4)
)
\
(
)
\
(
)
(
\
C
A
B
A
C
B
A
=
;
5)
)
\
(
)
\
(
)
(
\
C
A
B
A
C
B
A
=
;
6)
B
A
B
A
A
=
)
\
(
\
;
7)
B
A
B
A
=
\
;
8)
C
B
A
C
B
A
\
)
(
)
\
(
=
;
9)
C
B
A
C
B
A
A
C
C
B
B
A
=
)
(
)
\
(
)
\
(
)
\
(
;
10)
)
(
)
\
(
)
\
(
\
C
A
B
A
C
B
A
=
.
Практичне заняття №2.
Тема:
„
Системи множинних рівнянь
”
.
Мета:
На основі відомих операцій над множинами та тотожностями з теорії
множин, навчитись розв’язувати системи множинних рівнянь.
Завдання для самостійного опрацювання.
Роз”язати систему множинних рівнянь 1)
î
í
ì
=
=
C
A
X
B
A
X
\
;
2)
î
í
ì
=
=
C
A
X
B
A
X
\
;
3)
î
í
ì
=
=
C
X
A
B
X
A
;
4)
î
í
ì
=
=
C
X
A
B
X
A
\
;
5)
î
í
ì
=
=
C
X
A
B
A
X
\
\
.
Практичне заняття №3.
Тема: „
Перетворення логічних виразів
”
Мета:
Ознайомитись з основними поняттями математичної логіки, навчитись
будувати таблиці істинності для логічних виразів.
План заняття:
1.
Поняття елементарної бульової функції.
2.
Побудова таблиць істинності.
3.
Перетворення логічних виразів.
Завдання для самостійного опрацювання.
Побудувати таблиці істинності:
1)
)
(
))
(
)
((
C
B
A
B
A
C
A
Ú
Ù
®
®
Å
¯
;
Практичне заняття №4.
Тема:
„
Побудова диз’юнктивної нормальної форми
”
.
Мета:
Навчитись будувати досконалу диз’юнктивну нормальну форму для
довільних бульових функцій.
Завдання для самостійного опрацювання.
1. Побудувати досконалу диз’юнктивну нормальну форму a)
A
(
Ù
B
)
Ù
(
)
C
B
®
;
b)
A
B
A
(
)
(
®
¯
Ù
C
)
;
c)
(
)
(
)
B
C
B
A
Å
®
®
;
d)
(
A
Ù
)
(
)
B
C
B
Å
®
.
2. Записати досконалу диз’юнктивну нормальну форму бульових функцій, які
приймають значення 1 тільки при таких значеннях аргументів:
a)
(0,0),(0,1),(1,0);
b)
(0,1,0),(1,0,0),(0,0,1);
c)
(1,1,1,0),(1,1,0,1),(1,0,1,1),(0,1,1,1),(1,0,0,0);
d)
(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1),(1,1,1,1);
e)
(1,1,0,0),(1,0,0,1),(1,0,1,0),(0,1,1,0),(0,1,0,1),(0,0,1,1),(1,1,1,1).
3.
Записати досконалу диз’юнктивну нормальну форму бульових функцій
f
1
(
x
1
,
x
2
,
x
3
), f
2
(
x
1
,
x
2
,
x
3
), f
3
(
x
1
,
x
2
,
x
3
) та f
4
(
x
1
,
x
2
,
x
3
) які задані таблично:
X
1
X
2
X
3
f
1
(x
1
,x
2
,x
3
)
f
2
(x
1
,x
2
,x
3
)
f
3
(x
1
,x
2
,x
3
)
f
4
(x
1
,x
2
,x
3
)
1
1
1
1
0
0
1
1
1
0
0
1
0
0
1
0
1
1
0
1
1
1
0
0
1
0
1
0
0
1
1
1
0
0
0
0
1
0
0
1
1
1
0
0
1
0
1
0
1
0
0
0
1
0
1
1
Практичне заняття №5.
Тема:
„
Побудова полінома Жигалкіна
”.
Мета:
н
авчитись будувати поліном по модулю 2.
Алгоритм побудови полінома Жигалкіна:
1)
Для довільної бульвої функції побудувати досконалу диз’юнктивну нормальну
форму.
2)
Операцію диз’юнкції замінюємо на операції кон’юнкції та заперечення за
допомогою формул де Моргана
: B
A
B
A
Ù
=
Ú
.
3)
Всі операції заперечення міняємо на операцію додавання по модулю 2, за
допомогою таких співвідношень: A
A
=
Å
1
та 0
=
Å
A
A
.
4)
Розкрити дужки та провести спрощення.
Типовий приклад
.
Побудувати поліном Жигалкіна для бульової функції заданої у вигляді досконалої
диз’юнктивної нормальної форми z
y
x
z
y
x
z
y
x
z
y
x
f
Ú
Ú
=
)
,
,
(
.
Замінюємо о
перацію диз’юнкції на операції кон’юнкції та заперечення.
z
y
x
z
y
x
z
y
x
z
y
x
f
Ú
Ú
=
)
,
,
(
;
1
)
(
)
,
,
(
Å
Ú
Ú
=
z
y
x
z
y
x
z
y
x
z
y
x
f
;
Завдання для самостійного опрацювання.
Для виразу побудувати поліном Жигалкіна:
1)
(
)
B
A
Å
Ù
(
)
C
B
¯
;
2)
(
)
B
A
¯
Ù
(
)
A
C
/
;
3)
(
)
B
C
A
(
¯
¥
Ù
С);
4)
(
)
)
((
C
B
B
A
Å
Ú
Ù
А)
.
Практичне заняття №6.
Тема:
„
Побудова мінімальної диз’юнктивної нормальної форми
”.
Мета:
н
авчитись будувати мінімальну диз’юнктивну нормальну форму методом
Квайна.
Алгоритм побудови мінімальної диз’юнктивної нормальної форми:
1)
Для заданої бульової функції побудувати досконалу диз’юнктивну нормальну
форму.
2)
Застосувати всіма можливими способами правило неповного склеювання
:
x
A
Ax
È
замінюємо на A
x
A
Ax
È
È
.
3)
Застосувати всіма можливими способами правило поглинання: вирази A
Ax
È
і
A
x
A
È
замінюємо на А.
Логічний вираз, який ми отримуємо носить назву
–
скорочена диз’юнктивна нормальна форма.
4)
Для скороченої диз’юнктивної нормальної форми будуємо таблицю Квайна, на
основі якої будуємо мінімальну диз’юнктивну нормальну форму. Таблицю Квайна
будують так: кількість рядків відповідає кількості кон’
юнкцій в скороченій
нормальній формі, а кількість стовпців – кількості наборів значень аргументів, при
яких задана логічна функція набуває значення 1(одиниці).
Для заповнення таблиці Квайна ставлять 1, там де на перехресті даного
рядка при певному неаборі значень аргументів логічна функція набуває значення
1.
Для знаходження мінімаль
ної диз’юнктивної нормальної форми необхідно в
таблиці Квайна вибрати найменшу кількість стрічок так, щоб в кожному
стовпчику вибраних була хоча б одна одиниця. Таких наборів може бути декілька,
кожен з яких предствляє собою певну мінімальну диз’юнктивну нормальну
форму.
Завдання для самостійного опрацювання.
Побудувати мінімальну диз’юнктивну нормальну форму таких бульових функцій:
1)
x
®
y;
2)
x
Å
y;
3)
x
Û
y;
4)
A
(
Ù
B
)
Ú
(
)
C
B
¯
;
5)
z
y
x
z
y
x
xyz
Ú
Ú
;
6)
z
y
x
z
y
x
z
y
x
xyz
Ú
Ú
Ú
;
7)
z
y
x
z
xy
xyz
Ú
Ú
;
8)
f
1
(x
1
,x
2
,x
3
, x
4
), де
Nf
1
={(0,0,0,0)
,(0,0,1,0),(0,0,1,1),(0,1,1,1),(1,0,0,0),(1,0,0,1),
(1,0,1,1),(1,1,1,1)
};
9)
f
2
(x
1
,x
2
,x
3
, x
4
), де
Nf
2
={(0,1,1,1)
,(1,0,1,1),(1,1,0,1),(1,1,1,0),(1,1,1,1)
};
10)
f
3
(x
1
,x
2
,x
3
, x
4
), де
Nf
3
={(0,0,1,1)
,(0,1,0,1),(1,0,0,1),(0,1,1,0),(1,0,1,0),
(1,1,0,0),(1,1,1,1)
}
Практичне заняття №7.
Тема:
„
Перетворення графів
”. Мета:
навчитись оперувати основними поняттями теорії графів, розглянути
операції над графами.
План заняття:
1.
Основні поняття з теорії графів.
2.
Спрособи запису графа.
3.
Операції над графами.
Завдання для самостійного опрацювання.
Побудувати графи:
1)
4
4
С
K
´
;
2)
4
5
K
С
+
.
Практичне заняття №8.
Тема:
„Оптимальні задачі на граф
и”.
Мета:
навчитись розраховувати сітьовий графік, розв’язувати задачу про
найкоротший шлях між двома вершинами графа, а також знаходити максимальний
потік у графі.
Завдання для самостійного опрацювання.
1.
Розрахувати сітьовий графік.
2.
Знайти найкоротший шлях між двома вершинами.
3.
Знайти максимальний потік у графі.
Практичне заняття №
9
.
Тема 9.
„
Алгоритм Літла
”
.
Мета: Завдання для самостійного опрацювання.
1.
2.
3.
VI
. ЗАВДАННЯ ДЛЯ САМОСТІЙНОЇ РОБОТИ
1.
Властивості бінарних відношень. Теорема про властивості відношень.
(9 год
)
2.
Логічні закони та їх доведення. Теореми тавтології.
(9 год
)
3.
Доведення властивостей булевих функцій (самодвоїстість, монотонність,
лінійність).
(9 год
)
4.
Застосування математичної логіки до побудови тестів.
(9 год
)
В. Г. Карпов. Математичная логика и дискретная математика Минск 1977.
1.
Операції над графами. (11 год.)
2.
Алгоритм побудови плоского зображення графа та його застосування. (11 год.)
А. Кофман Введения в прикладную комбинаторику 1975г.
1.
Поняття цикломатичного та хроматичного числа графа.
(11 год.)
А. Кофман Введения в прикладную комбинаторику 1975г.
VII
. ЛІТЕРАТУРА
1.
Баранкевич М.М. Розробка для самостійної роботи з „теорії графів”,1988. -16с.
2.
Баранкевич М.М. Розробка для самостійної роботи з курсу „Математична
логіка”, 1988. -16с.
3.
В.Г.Карпов. Математическая логика и дискретная математика, 1977. -250с.
4.
Ю.Л.Ершов. Математическая логика, 1987. -190с.
5.
П.С.Новиков Елементи математичної логіки, 1973. -350с.
6.
Андрійчук В.І. Вступ до дискретної математики. Підручник, 2004. -220с.
7.
Бардачов Ю.М. Дискретна математика. Підручник, 2004. -240с.
8.
Борисенко О.А. Лекції з дискретної математики, 2004. -180с.
Автор
belozierov
Документ
Категория
Без категории
Просмотров
1 666
Размер файла
187 Кб
Теги
дискретное
1/--страниц
Пожаловаться на содержимое документа