ДЕРЖАВНА ПОДАТКОВА СЛУЖБА УКРАЇНИ

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ДЕРЖАВНОЇ   ПОДАТКОВОЇ СЛУЖБИ УКРАЇНИ

КАФЕДРА ЕКОНОМІЧНОЇ КІБЕРНЕТИКИ

Розглянуто і схвалено

на засіданні Вченої ради університету

Протокол №___ від “___”_______ 2011р.

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

«ОСНОВИ ДИСКРЕТНОЇ МАТЕМАТИКИ»

для підготовки бакалаврів

в галузі знань 0305 «Економіка і підприємництво»

за напрямом підготовки:

6.030502 «Економічна кібернетика» 

денної  форми навчання

статус дисципліни:  вибіркова

Ірпінь – 2011

Робоча навчальна програма курсу "ОСНОВИ ДИСКРЕТНОЇ МАТЕМАТИКИ" складена навчального плану підготовки бакалаврів в галузі знань 0305 «Економіка і підприємництво» за напрямом підготовки  6.030502 «Економічна кібернетика», затвердженого  у 2010 році.

Автори: Мамченко С.Д., к.т.н., доцент, Антоненко В.М., к.т.н., доцент.

Рецензент: О.В.Поденежко, к.ф.-м.н., доцент.

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

економічної кібернетики

Протокол № ___ від «_____» ______________ 2011 р.

Зав. кафедри: В.М. Антоненко.

 

ЗМІСТ

ПЕРЕДМОВА

ОПИС  НАВЧАЛЬНОЇ ДИСЦИПЛІНИ

СТРУКТУРА НАВЧАЛЬНОЇ ДИСЦИПЛІНИ

ЗМІСТ НАВЧАЛЬНОЇ ДИСЦИПЛІНИ ЗА ЗМІСТОВИМИ МОДУЛЯМИ

Змістовий модуль 1. ОСНОВИ  ТЕОРІЇ МНОЖИН

Змістовий модуль 2. ЕЛЕМЕНТИ МАТЕМАТИЧНОЇ ЛОГІКИ

Змістовий модуль 3. ЕЛЕМЕНТИ ТЕОРІЇ АЛГОРИТМІВ

Змістовий модуль 4. ОСНОВИ ТЕОРІЇ ГРАФІВ

МЕТОДИ ОЦІНЮВАННЯ  ТА РОЗПОДІЛ БАЛІВ

ЗА РЕЙТИНГОВОЮ СИСТЕМОЮ

КОНТРОЛЬНІ ПИТАННЯ З ДИСЦИПЛІНИ

РЕКОМЕНДОВАНА ЛІТЕРАТУРА

 

ПЕРЕДМОВА

„ОСНОВИ ДИСКРЕТНОЇ МАТЕМАТИКИ” – нормативна дисципліна циклу професійної підготовки бакалаврів у галузі знань „Економіка і підприємництво за напрямом «Економічна кібернетика».

Дискретна математика є основою сучасної  кібернетики і важливим ланцюжком у математичній освіті, тому найважливіші її розділи включені у даний курс „ОСНОВИ ДИСКРЕТНОЇ МАТЕМАТИКИ” для підготовки фахівців з економічної кібернетики.

У кібернетичних системах визначальними є інформаційно- логічні, принципово дискретні процеси,  інформаційними. Такі системи містять функції управління, контролю, прогнозу, аналізу і синтезу динамічних систем різного призначення. Класична вища математика націлена в першу чергу на моделювання, аналіз та синтез систем у просторово - часовому середовищі. Натомість, на відміну від класичної вищої математики, дискретна математика орієнтована на  опис і дослідження систем, які функціонують у мовному (інформаційному) середовищі. Різні середовища потребують і різних принципів моделювання. Класичної вищої математики недостатньо для моделювання кібернетичних систем. Тому на сучасному етапі розвитку суспільства  знання з дискретної математики є необхідними для підготовки фахівців за напрямом «Економічна кібернетика». Задачі дискретної математики пов’язані з з проблемами управління та організації у складних системах.

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

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

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

4. Зміст дисципліни розкривається у таких  змістових модулях:

5. Міжпредметні зв’язки: вивчення дисципліни передбачає міжпредметні зв’язки з такими дисциплінами як „Інформатика”, „Користування базами та сховищами даних”, „Економіка підприємства”, „Менеджмент”,  “Макроекономіка”, “Мікроекономіка”, «Введення в спеціальність». Дисципліна є базовою для вивчення  дисциплін «Економічна кібернетика», «Моделювання економіки».

Розроблена та наведена авторами навчальна програма дисципліни охоплює всі теми, визначені анотацією для мінімальної кількості навчальних годин, передбачених освітнім стандартом. Її складено відповідно до місця та значення дисципліни за структурно-логічною схемою програми підготовки бакалаврів за напрямом 6.030502 «Економічна кібернетика». Під час вивчення дисципліни передбачається систематична самостійна робота студентів, яка становить 46 % від загального обсягу часу, відведеного на вивчення даного курсу. Загальний обсяг навчальної дисципліни 72 години, з них 16 годин відведено на лекції, 20 годин – на лабораторні роботи, 3 години - на індивідуально-консультаційні заняття студентів під керівництвом викладача та 33 години на самостійну роботу студентів. В процесі вивчення дисципліни студенти виконують одну контрольну роботу, форма підсумкового контролю – ПМК.

ОПИС  НАВЧАЛЬНОЇ ДИСЦИПЛІНИ

«ОСНОВИ ДИСКРЕТНОЇ МАТЕМАТИКИ»

 для підготовки бакалаврів

на 2010/2011 н.р. та 2011/2012 навчальні роки

в галузі знань 0305 «Економіка і підприємництво»

за напрямом підготовки:

6.030502 «Економічна кібернетика»

 (денна форма навчання)

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

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

 

 СТРУКТУРА НАВЧАЛЬНОЇ ДИСЦИПЛІНИ

«ОСНОВИ ДИСКРЕТНОЇ МАТЕМАТИКИ»

 для підготовки бакалаврів

на 2010/2011 навчальний рік

в галузі знань 0305 «Економіка і підприємництво»

за напрямом підготовки

6.030502 «Економічна кібернетика»

 (денна форма навчання)

 

 

 ЗМІСТ НАВЧАЛЬНОЇ ДИСЦИПЛІНИ ЗА ЗМІСТОВИМИ МОДУЛЯМИ

 Змістовий модуль 1. ОСНОВИ  ТЕОРІЇ МНОЖИН

 Тема 1.1. Множини: способи визначення, різновиди, співвідношення,  операції та їх властивості.

1. Поняття множини. Приклади множин.

2. Скінчені і нескінчені множини. Поняття кортежу.

3. Способи визначення множин.

4. Співвідношення між множинами.

5. Операції над множинами та їх властивості.

6. Еквівалентність множин.

7. Потужність множин. Теорема Кантора.
   

Самостійна робота

1. Лінійні точкові множини.

2. Доведення теореми Кантора.

Література: 1, 3-7.

 

Лабораторна робота (2 год.)

Тема: «Способи визначення множин, операції над множинами та їх властивості»

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

 

Тема 1.2. Поняття відображення. Ізоморфізм множин.

1. Поняття відповідності. Способи задання відповідності.

2. Поняття відображення. Ін’єктивні, сюр’єктивні та бієктивні відображення.

3. Взаємнооднозначне відображення.

4. Ізоморфізм множин.

Самостійна робота

1. Поняття функції. Способи задання функції.

2. Одномісні, двомісні та багатомісні функції.

Література: 1, 3, 5

 

Тема 1.3. Відношення  та їх властивості

1. Відношення еквівалентності.

2. Відношення порядку та лінійного порядку.

3. «Решітки» як частково впорядковані множини.

Самостійна робота

1. Способи зображення частково впорядкованих множин.

Література: 1, 3-7.

 

Лабораторна робота (2 год.)

Тема: «Відображення. Відношення та їх властивості»

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

  

Змістовий модуль 2. ЕЛЕМЕНТИ МАТЕМАТИЧНОЇ ЛОГІКИ

Тема 2.1. Алгебра висловлювань

1. Поняття висловлювання. Атомарні висловлювання. Зв’язки між висловлюваннями.

2. Операції над висловлюваннями..

3. Штрих Шеффера. Стрілка Пірса.

4. Основні закони логіки висловлювань.

5. Формули (вирази) в алгебрі висловлювань.

Самостійна робота

1. Алфавіт найбільш поширеної формальної мови алгебри висловлень.

2. Тавтології, суперечності та нейтральні вирази.

3. Перетворення складених виразів.

Література: 1, 3-7.

 

Тема 2.2. Еквівалентність висловлювань та взаємозамінність основних зв’язків. Функція істинності складеного висловлювання (виразу).

1. Еквівалентність висловлювань.

2. Взаємозамінність основних зв’язків.

3. Функція істинності логічного виразу.

Самостійна робота

1. Алгебра та поліном Жегалкіна.

Література: 1, 3-7.

 

Лабораторна робота (2 год.)

Тема: «Основні закони логіки висловлювань та взаємозамінність звязків»

Мета роботи: набути знань  та практичних навичок застосування законів логіки висловлювань.

 

Тема 1.3. Нормальна форма логічного виразу. Завжди істинні і завжди хибні висловлювання. Поняття предикату. Операції навішування кванторів

1. Кон’юнктивна та диз’юнктивна нормальна форма логічного виразу.

2. Поняття предикату (логічної функції).

3. Операції навішування кванторів у численні предикатів.

Самостійна робота

1. Завжди істинні і завжди хибні висловлювання.

2. Приклади зведення логічного виразу до нормальної форми.

Література: 1, 3-7.

 

Лабораторна робота (2 год.)

Тема: «Зведення логічного виразу до диз’юнктивної нормальної форми та конюнктивної нормальної форми»

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

 

Змістовий модуль 3. ЕЛЕМЕНТИ ТЕОРІЇ АЛГОРИТМІВ

 Тема 3.1. Алгоритм як різновид множин. Емпіричні властивості алгоритму.

1. Алгоритм як різновид множин.

2. Емпіричні властивості алгоритмів.

3. Складність алгоритму.

4. Дискретна математика як наука про багатосортні множини.

5. Поняття про нечіткі множини.

Самостійна робота

1. Системи числення як алгоритми.

2. Адитивні та мультиплікативні системи числення.

3. Визначення формальної алгебри.

Література: 1, 3-7.

 

Тема 3.2. Алфавітні оператори та алгоритми. Слова в асоціативному численні. Нормальний алгоритм Маркова

1. Алфавітні оператори та алгоритми.

2. Слова в асоціативному численні.

3. Еквівалентні алгоритми.

4. Машина Тюринга.

5. Нормальний алгоритм Маркова.

Самостійна робота

1. Визначення формальної алгебри.
2. Асоціативне числення.

Література: 1, 3-7.

 

Лабораторна робота (2 год.)

Тема: «Побудова нормального алгоритму  Маркова»

Мета роботи: набути знань  та практичних навичок побудови нормального алгоритму Маркова

 

Тема 3.3. Зведення будь-якого алгоритму до числового алгоритму

1. Алгоритмічно нерозв’язні проблеми.

2. Метод Геделя.

3. Зведення будь-якого алгоритму до числового алгоритму.

4. Приклад застосування метода Геделя.

Самостійна робота

1. Класифікація алгоритмів.

2. Числові та логічні алгоритми.

Література: 3, 5.

 

Лабораторна робота (2 год.)

Тема: «Зведення логічного алгоритму до числового алгоритму»

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

 

Змістовий модуль 4. ОСНОВИ ТЕОРІЇ ГРАФІВ

 Тема 4.1. Поняття графа. Маршрут графа

1. Поняття графа. Скінчені і нескінчені графи.

2. Способи задання графа.

3. Матриця суміжності та матриця інцидентності.

4. Підграфи. Ізоморфізм графів.

5. Алгебра графів.

6. Поняття маршруту графа. Довжина маршруту.

Самостійна робота

1.Становлення та розвиток теорії графів.

2. Задача про кенігзберські мости як перша задача теорії графів.

Література: 1, 3-7.

 

Лабораторна робота (2 год.)

Тема: «Розвязування задач теорії графів»

Мета роботи: набути знань  та практичних навичок розв’язування задач теорії графів.

 

Тема 4.2. Цикли та ланцюги. Зв’язні та незв’язні графи. Орієнтовані та неорієнтовані графи. Дерева.

1. Ланцюги та цикли.

2. Зв’язність графу. Зв’язні та незв’язні графи.

3. Теорема Ейлера.

4. Орієнтовані та неорієнтовані графи. Дерева.

5. Однодольні та дводольні графи.

6. Поняття індуктивного графу та бази.

Самостійна робота

1. Метричні характеристики графів, відстань вершин у графі, радіус та діаметр графа.

Література: 1, 3-7.

 

Лабораторна робота (2 год.)

Тема: «Розвязування економічних задач шляхом побудови дерев рішень»

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

Тема 4.3. Приклади застосування теорії графів до розв’язання економічних задач

1. Мережа як різновид графу.

2. Задача про лінії зв’язку.

3. Задача про максимальний потік в мережі.

4. Застосування теорії графів для розробки моделі систем масового обслуговування.

5. Мережі Петрі як різновид графу.

6. Застосування мереж Петрі  для розробки моделей. 

Література: 1, 2, 3, 5

Самостійна робота

1. Поняття про марківський процес.

2. Застосування теорії графів для розробки моделі систем масового обслуговування.

 

Лабораторна робота (2 год.)

Тема: «Застосування теорії  графів для розв’язання економічних задач»

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

МЕТОДИ ОЦІНЮВАННЯ ТА РОЗПОДІЛ БАЛІВ ЗА РЕЙТИНГОВОЮ СИСТЕМОЮ

на 2011/2012 навчальний рік

При визначенні підсумкової оцінки  за кредитно – модульною системою при  заключному контролі враховується загальна кількість балів, отриманих студентом при поточному контролі у процесі виконання навчального плану дисципліни. Передбачено один підсумкових контроль: 3-й семестр – ПМК.

Максимальна сумарна кількість балів підсумкового модульного  контролю становить 100 балів.

На підставі отриманої кількості балів за кредитно – модульної системи згідно до вимог Болонської декларації застосовується наступна шкала оцінки знань: 

Поточний контроль засвоєння матеріалу з кожної  теми здійснюється у відповідності з навчальним планом дисципліни і включає:

• оцінювання виконання та захисту кожної лабораторної  роботи;

• оцінювання виконання та захисту індивідуальної роботи студента.

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

Враховується  науково- дослідницька робота студента та участь у науково-практичних конференціях та наукових семінарах (максимальна кількість балів у семестрі - 20).

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