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

Київський національний університет

Імені Тараса Шевченка

Механіко-математичний факультет

Кафедра алгебри та математичної логіки

Укладач: проф. .

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

РОБОЧА НАВЧАЛЬНА ПРОГРАМА

Для студентів спеціальності 6.080101 «Математика»

Затверджено

на засіданні кафедри

Протокол №10 від 29.05.2007

Зав. кафедрою

_______________________

Погоджено

з науково-методичною комісією

„_____”____________2007

____________________

Підпис голови НМК факультету

Декан факультету

__________ _____________

КИЇВ -2007

Методичні рекомендації по вивченню дисципліни

Дисципліна «Дискретна математика» є базовою нормативною дисципліною для спеціальності «математика», що читається в II семестрі в обсязі 2 кредитів (за Європейською Кредитно-Трансферною Системою ECTS), в тому числі 68 годин аудиторних занять, з них 34 годин лекцій, 34 годин практичних занять і 46 годин самостійної роботи і закінчується заліком та іспитом в II семестрі.

Мета і завдання навчальної дисципліни «Дискретна математика»:

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

Предмет навчальної дисципліни «Дискретна математика»:

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

Вимоги до знань та вмінь.

Знати: основні поняття комбінаторики, математичної логіки та теорії графів, зокрема такі, як біноміальні коефіцієнти, сполучення, розміщення, перестановки, степеневі ряди та ряди Діріхле, твірні функції, рекурентні послідовності, числа Стірлінга, Фібоначчі, Каталана, числа та многочлени Бернуллі, булеві функції, логічні сполучники, диз'юнктивна та кон’юнктивна нормальні форми, булеві многочлени, повні системи булевих функцій, відношення еквівалентності та порядку, орієнтовані та неорієнтовані графи, числові характеристики графів, ойлерові та гамільтонові графи, дерева, дводольні графи, парування.

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

Місце в структурно-логічній схемі спеціальності.

Нормативна навчальна дисципліна «Дискретна математика» є складовою циклу професійної підготовки фахівців освітньо-кваліфікаційного рівня «бакалавр», є базовою для вивчення таких спеціальних дисциплін як «Алгебра і теорія чисел», «Теорія ймовірностей», «Математична логіка».

Система контролю знань та умови складання іспиту.

Навчальна дисципліна "Дискретна математика" оцінюється за модульно-рейтинговою системою. Вона складається з 2 модулів, до першого входять 1-2 теми, до другого 3-4 теми.

Результати навчальної діяльності студентів в семестрі оцінюються за 100–бальною шкалою.

Модульний контроль за семестр:

1-й змістовий модуль: 0-30 балів

· модульна контрольна робота – 0-20 балів

· виконання домашніх робіт і робота на практичних заняттях - 0- 10 балів

2-й змістовий модуль: 0-30 балів

· модульна контрольна робота – 0-20 балів

· виконання домашніх робіт і робота на практичних заняттях - 0-10 балів

Якщо контрольна робота або колоквіум пропущені з поважної причини, то вони можуть бути написані без зменшення кількості балів за них.

Підсумковий контроль за семестр складається з суми балів, які отримав студент за роботу протягом семестру. Максимально студент може отримати 60 балів протягом кожного семестру. Студент не допускається до іспиту, якщо за результатами роботи в семестрі він отримав менше 20 балів.

При складанні іспиту студент може отримати до 40 балів. За сумою S балів за роботу в семестрі і за відповідь на іспиті виставляється оцінка студенту:

· S<60 відповідає оцінці «незадовільно»;

· 60 ≤S<75 відповідає оцінці «задовільно»;

· 75≤S<90 відповідає оцінці «добре»;

· 90≤S відповідає оцінці «відмінно».

Шкала відповідності

За 100-бальною шкалою	Оцінка за національною шкалою
90-100	5	відмінно	зараховано
85-89	4	добре
75-84
65-74	3	задовільно
60-64
35-59	2	незадовільно	Не зараховано
1-34

ТЕМАТИЧНИЙ План ЛЕКЦІЙ І ПРАКТИЧНИХ ЗАНЯТЬ

теми	Назва теми	Кількість годин
лекції	практичні заняття	самостійна робота	контрольна модульна робота	інші форми контролю
Змістовний модуль 1. Комбінаторика
1	Біноміальні коефіцієнти і комбінаторні формули	6	8	14
2	Твірні функції та рекурентні послідовності	8	8	16	2
Змістовний модуль 2. Елементи математичної логіки та теорії графів
3	Елементи математичної логіки	8	8	16
4	Теорія графів	12	10	22	2
Всього годин за семестр	34	34	68

Теми лекцій, практичних занять та завдання для самостійної роботи

Змістовий модуль 1. Комбінаторика.

Тема 1. Біноміальні коефіцієнти і комбінаторні задачі.

Лекція 1. Біноміальні коефіцієнти та їх властивості. – 2 год.

Лекція 2. Множини та дії над ними. Правило включення та вилучення. – 2 год.

Лекція 3. Сполучення, розміщення, перестановки, сюр'єкції. Числа Стірлінга. – 2 год.

Лабораторна робота 1. Приклади комбінаторних задач. Принцип математичної індукції та його застосування. – 2год.

Лабораторна робота 2. Біноміальні коефіцієнти, їх властивості. – 2 год.

Лабораторна робота 3. Сполучення, розміщення, перестановки. Числа Стірлінга. – 2 год.

Завдання для самостійної роботи (опрацювання лекційного матеріалу і виконання домашніх завдань)

До лекції 1 і лабораторної роботи 1 (4 год)

а) Приклади комбінаторних задач

б) Принцип математичної індукції

До лекції 2 і лабораторної роботи 2 (4 год)

а) Властивості біноміальних коефіцієнтів.

б) Застосування біноміальних коефіцієнтів.

До лекції 3 і лабораторної роботи 3 (4 год.)

а) Сполучення і розміщення

б) Числа Стірлінга

Література [2, 3, 5]

Контрольні питання і завдання:

1. Біноміальні коефіцієнти, їх властивості та зв'язок з цілозначними многочленами.

2. Дії над множинами, їх властивості.

3. Правило включення та вилучення.

4. Формули для числа сполучень, розміщень, сюр'єкцій.

5. Числа Стірлінга, їх властивості.

Тема 2. Твірні функції та рекурентні послідовності.

Лекція 4. Степеневі ряди. Твірні функції, їх властивості та застосування. – 2 год.

Лекція 5. Рекурентні послідовності. Числа Фібоначчі. – 2 год.

Лекція 6. Ряди Діріхле та їх застосування. Функція Мебіуса, мебіусова формула обертання. – 2 год.

Лекція 7. Числа Каталана. Числа та многочлени Бернуллі. – 2 год.

Лабораторна робота 4. Степеневі ряди. Твірні функції та їх застосування. – 2 год.

Лабораторна робота 5. Рекурентні послідовності. Числа Фібоначчі. – 2 год.

Лабораторна робота 6. Ряди Діріхле. Мебіусова формула обертання та її застосування. – 2 год.

Лабораторна робота 7. Числа Каталана, їх застосування. Числа і многочлени Бернуллі. – 2 год.

Завдання для самостійної роботи (опрацювання лекційного матеріалу і виконання домашніх завдань)

До лекції 4 і лабораторної роботи 4 (4 год)

а) Степеневі ряди

б) Твірні функції та їх застосування

До лекції 5 і лабораторної роботи 5 (4 год)

а) Рекурентні послідовності.

б) Числа Фібоначчі.

До лекції 6 і лабораторної роботи 6 (4 год.)

а) Ряди Діріхле

б) Формула обертання Мьобіуса

До лекції 7 і лабораторної роботи 7 (4 год.)

а) Числа Каталана

б) Числа Бернуллі

Література [1- 3, 5]

Контрольні питання і завдання:

1. Степеневі ряди та твірні функції. Композиції послідовностей.

2. Рекурентні послідовності. Застосування твірних функцій до рекурентних послідовностей.

3. Числа Фібоначчі, формула для них.

4. Ряди Діріхле. Мультиплікативна композиція послідовностей.

5. Функція Мебіуса. Мебіусова формула обертання.

6. Числа Каталана. Комбінаторні задачі, в яких вони виникають.

7. Числа та многочлени Бернуллі, їх властивості.

Типове завдання модульної контрольної роботи № 1

Довести, що обєднання скінченої або зліченної сімї множин потужності континуум є множиною потужності континуум. Довести, що . У місті проживає 25000 жителів. Чи правильно, що принаймні двоє з них мають однакові ініціали. Довести, що для чисел Фібоначчі виконується рівність

5. Нехай для . Довести, що.

Змістовий модуль 2. Елементи математичної логіки та теорії графів.

Тема 2. Елементи математичної логіки.

Лекція 8. Логічні висловлювання, булеві функції та логічні сполучники. – 2 год.

Лекція 9. Диз'юнктивна і кон'юнктивна нормальні форми. Булеві многочлени. – 2 год.

Лекція 10. Повні системи булевих функцій. Критерій Поста повноти. – 2 год.

Лекція 11. Відношення та дії над ними. Відношення еквівалентності. Відношення порядку. – 2 год.

Лабораторна робота 8. Обчислення булевих функцій. Аналіз логічних міркувань. – 2 год.

Лабораторна робота 9. Диз'юнктивна та кон'юнктивна нормальні форми. Зображення булевих функцій булевими многочленами. – 2 год.

Лабораторна робота 10. Перевірка повноти системи булевих функцій. Побудова повних систем. – 2 год.

Лабораторна робота 11. Дії над відношеннями. Відношення еквівалентності та порядку. – 2 год.

Завдання для самостійної роботи (опрацювання лекційного матеріалу і виконання домашніх завдань)

До лекції 8 і лабораторної роботи 8 (4 год)

а) Логічні сполучники

б) Булеві функції

До лекції 9 і лабораторної роботи 9 (4 год)

а) Нормальні форми.

б) Булеві многочлени

До лекції 10 і лабораторної роботигод.)

а) Повні системи мулевих функцій

б) Теорема Поста

До лекції 11 і лабораторної роботигод.)

а) Дії над відношення

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

Література [1, 2, 4]

Контрольні питання і завдання:

1. Поняття логічного висловлювання.

2. Булеві функції та логічні сполучники.

3. Поняття повної системи булевих функцій.

4. Диз'юнктивна та кон'юнктивна нормальні форми.

5. Булеві многочлени. Зображення булевих функцій булевими многочленами.

6. Критерій Поста повноти системи булевих функцій.

7. Відношення та дії над ними.

8. Відношення еквівалентності, їх зв'язок з розбиттями множини.

9. Відношення порядку.

Тема 3. Теорія графів.

Лекція 12. Основні означення теорії графів. – 2 год.

Лекція 13. Числові характеристики графів, зв'язки між ними. – 2 год.

Лекція 14. Ойлерові графи. Критерій ойлеровості. Гамільтонові графи, ознаки гамільтоновості. – 2 год.

Лекція 15. Дерева. Центри дерев. Перелік дерев. – 2 год.

Лекція 16. Дводольні графи. Парування. Критерій існування парувань. Системи різних представників. – 2 год.

Лекція 17. Приклади застосування графів у комбінаториці. – 2 год.

Лабораторна робота 12. Числові характеристики графів, зв'язки між ними.

Лабораторна робота 13. Ойлерові та гамільтонові графи.

Лабораторна робота 14. Дерева та циклові числа.

Лабораторна робота 15. Дводольні графи. Парування.

Лабораторна робота 16. Системи різних представників.

Лабораторна робота 17. Застосування графів у комбінаториці

Завдання для самостійної роботи (опрацювання лекційного матеріалу і виконання домашніх завдань)

До лекції 12 і лабораторної роботигод)

а) Означення графа

б) Основні поняття теорії графів

До лекції 13 і лабораторної роботигод)

а) Числові характеристики графів.

б) Зв’язки між числовими характеристиками.

До лекції 14 і лабораторної роботигод.)

а) Ойлерові графи

б) Гамільтонові графи

До лекції 15 і лабораторної роботигод.)

а) Дерева

б) Перелік дерев

До лекції 16 і лабораторної роботигод.)

а) Дводольні графи

б) Критерій існування парувань

До лекції 17 і лабораторної роботигод.)

а) Застосування графів

б) Графи і комбінаторика

Література [1, 3, 5]

Контрольні питання і завдання:

1. Поняття орієнтованого і неорієнтованого графів. Зв'язки графів з бінарними відношеннями.

2. Підграфи, повні підграфи. Доповнення підграфа.

3. Гомоморфізми та ізоморфізми графів.

4. Шляхи та цикли в графі. Зв'язні компоненти графа.

5. Степінь вершини. Степінь графа.

6. Відстань між вершинами у графі. Радіус і діаметр графа.

7. Зв'язки між числовими характеристиками графа.

8. Означення ойлерового графа. Критерій ойлеровості.

9. Означення гамільтонова графа. Ознаки гамільтоновості.

10. Циклове число графа, його властивості.

11. Центри графа. Властивості центрів дерева.

12. Дводольні графи. Парування у дводольному графі.

13. Критерій існування парування для заданої множини вершин.

14. Системи різних представників. Критерій їх існування.

Типове завдання модульної контрольної роботи № 2.

Знайти ДДНФ і ДКНФ для булевої функції . Чи буде тавтологєю формула ю Довести повноту системи функцій де . Довести, що кількість вершин непарного степеня будь-якого графа є парним числом. Побудувати граф, який відповідає частково впорядкованій множині підмножин множини з 3 елементів.

Перелік питань до іспиту

Біноміальні коефіцієнти та їх властивості. Множини та дії над ними. Правило включення та вилучення.. Сполучення, розміщення, перестановки, сюр'єкції. Числа Стірлінга. Степеневі ряди. Твірні функції, їх властивості та застосування. Рекурентні послідовності. Числа Фібоначчі. Ряди Діріхле та їх застосування. Функція Мебіуса, мебіусова формула обертання. Числа Каталана. Числа та многочлени Бернуллі Логічні висловлювання, булеві функції та логічні сполучники. Диз'юнктивна і кон'юнктивна нормальні форми. Булеві многочлени. Повні системи булевих функцій. Критерій Поста повноти. Відношення та дії над ними. Відношення еквівалентності. Відношення порядку Основні означення теорії графів. Числові характеристики графів, зв'язки між ними. Ойлерові графи. Критерій ойлеровості. Гамільтонові графи, ознаки гамільтоновості.. Дерева. Центри дерев. Перелік дерев. Дводольні графи. Парування. Критерій існування парувань. Системи різних представників. Приклади застосування графів у комбінаториці.

ЛІТЕРАТУРА

1. М. Й. Ядренко. Дискретна математика. – Київ: Експрес, 2003.

2. А. Я. Оленко, М. Й. Ядренко. Дискретна математика. – Київ: Видавничий центр Київського університету, 1997.

3. Ю. А. Дрозд. Дискретна математика (електронний конспект лекцій). – Київ, 2006.

4. М. Холл. Комбинаторика. – Москва: Мир, 1970.

5. О. Оре. Теория графов. – Москва: Мир, 1965.