Вимоги до виконання та оформлення контрольних робіт

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

ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ БІЗНЕС-КОЛЕДЖ

О.О. ДЕМЧЕНКО

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

Методичні рекомендації

Для студентів заочної форми навчання

ЧЕРКАСИ - 2006
Видання здійснено за фінансової підтримки громадської організації „Рада батьків Черкащини”

УДК 681.3.06

Рекомендовано до друку рішенням Розповсюдження та

методичної ради Черкаського тиражування

державного бізнес-коледжу без офіційного дозволу Протокол № 2 від 30 листопада 2006 р. ЧДБК заборонено

Укладач: Демченко О.О.

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

Методичні рекомендації

для студентів заочної форми навчання

Черкаси, 2006. – 42 с.

Методичні рекомендації містять навчальну програму з дисципліни ”Дискретна математика”, вимоги до виконання та оформлення контрольних робіт, варіанти контрольних робіт, приклади розв’язання типових задач та питання до іспиту.

Розраховано на студентів заочної форми навчання вищих навчальних закладів І-ІІ рівнів акредитації.

Затверджено на засіданні циклової

комісії фундаментальних дисциплін

Протокол № 4 від 01 листопада 2006 р. © О.О. Демченко, 2006

Зміст

Вступ...................................................................................................4

Тематичний план...............................................................................6

Навчальна програма.........................................................................7

Вимоги до виконання та оформлення контрольних робіт............9

Варіанти контрольних робіт..........................................................11

Приклад розв’язання контрольної роботи....................................31

Питання до заліку...........................................................................35

Питання до екзамену......................................................................37

Список рекомендованої літератури..............................................40

Вступ

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

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

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

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

Вивчення предмета включає в себе наступні теми:

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

Елементи теорії множин. Відношення.

Алгебраїчні структури.

Цілі числа. Теорія конгруенцій.

Елементи комбінаторного аналізу.

Елементи теорії графів.

Робота над курсом передбачає послідовне, систематичне вивчення рекомендованої навчальної та наукової літератури.

Курс передбачає аудиторні заняття, індивідуальну та самостійну роботу студентів. Вивчення курсу завершується підсумковим екзаменом.

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

Тематичний план

з дисципліни „Дискретна математика”

№ з/п	Назва теми	Кількість годин
Всього	Аудиторні	Індивідуальна робота	Самостійна робота
1.	Елементи математичної логіки
2.	Елементи теорії множин
3.	Відношення. Алгебраїчні структури
4.	Булеві функції
5.	Цілі числа. Теорія конгруенцій
6.	Метод математичної індукції
7.	Елементи комбінаторного аналізу
8.	Елементи теорії графів
Разом

Навчальна програма

з дисципліни „Дискретна математика”

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

Булеві функції: основні поняття та означення; способи задання; область визначення. Елементарні функції алгебри логіки, їхні властивості. Реалізація булевих функцій формулами: поняття формули, принцип суперпозиції, рівносильність формул. Основні тотожності. Принцип двоїстості. Предикати. Квантори. Формули логіки предикатів. Рівносильність формул. Числення предикатів.

Тема 2. Елементи теорії множин

Множина: основні поняття та означення. Способи задання множин. Порожня та універсальна множина. Алгебра множин. Потужність множини. Поняття та основні властивості відношень. Відношення еквівалентності, порядку, рівнопотужності.

Тема 3. Відношення

Поняття та основні властивості відношень. Відношення еквівалентності. Відношення порядку. Відношення рівно потужності. Впорядкованість множин. Властивості бінарних відношень. Відношення нестрогого і строгого порядків.

Тема 4. Алгебраїчні структури

Основні поняття, означення і властивості. Гомоморфізм та ізоморфізм алгебр. Види алгебр: алгебри з однією алгебраїчної операцією (півгрупа, група), алгебри з двома алгебраїчними операціями (кільце, поле).

Тема 5. Булеві функції

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

Тема 6. Цілі числа. Теорія конгруенцій

Властивості подільності в кільці цілих чисел. Теорема про ділення з остачею. Найбільший спільний дільник, найменше спільне кратне. Взаємнопрості числа. Конгруенції та її властивості. Класи лишків. Функція Ейлера. Теорема Ейлера. Теорема Ферма.

Тема 7. Метод математичної індукції

Сутність методу математичної індукції. Доведення тотожностей за допомогою математичної індукції. Доведення методу математичної індукції. Сфери застосування методу математичної індукції.

Тема 8. Елементи комбінаторного аналізу

Метод математичної індукції. Основні закони комбінаторики (правило суми і добутку). Основні формули комбінаторики: розміщення, сполуки, перестановки з повторенням та без повторення. Трикутник Паскаля. Біном Ньютона.

Тема 9. Елементи теорії графів

Основні поняття теорії графів. Задання графа за допомогою матриць інцедентності та суміжності. Локальні степені вершин і ребер графа. Маршрути, ланцюги та цикли. Зв’язність графа. Дерева. Ейлерові та Гамільтонові графи.

Вимоги до виконання та оформлення контрольних робіт

Контрольна робота повинна бути виконана на аркушах формату А4 або в зошиті.

Титульна сторінка оформлюється наступним чином:

Умови завдань потрібно записувати повністю, без скорочень. Кожне завдання виконувати на новій сторінці.

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

Робота, виконана не за своїм варіантом, не перевіряється і повертається студенту без оцінки. Студенти, які не отримали залікову оцінку з контрольної роботи, до екзамену не допускаються.

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

Дата добавления: 2015-10-26