Програма Дисциплiни основи дискретної математики



Скачати 252.64 Kb.
Дата конвертації22.04.2017
Розмір252.64 Kb.
НАЦIОНАЛЬНИЙ ТЕХНIЧНИЙ УНIВЕРСИТЕТ УКРАЇНИ

"КИЇВСЬКИЙ ПОЛIТЕХНIЧНИЙ IНСТИТУТ"

Програма затверджена
Вченою Радою факультету інформатики та обчислювальної техніки
(протокол №___, __.__.2002)
Декан ФІОТ

___________________

ПАВЛОВ О.А.
“____”______________2002р.

РОБОЧА НАВЧАЛЬНА ПРОГРАМА ДИСЦИПЛIНИ

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

для напряму пiдготовки 0914 "Комп’ютеризовані системи, автоматика і управління"





Програму рекомендовано кафедрою

Автоматики і управління в технічних системах

(протоокол № __, від ))ол №, дата)
Зав.кафедрою

Теленик С.Ф.

“___” ________________2002р.


Київ 2002р.

I. ЗАГАЛЬНI ВIДОМОСТI
Зі створенням та широким запровадженням комп’ютерної техніки в наукові розрахунки, управління, проектування та інші сфери діяльності людини з’явилася потреба в математичних моделях опису структури та функціонування нових класів об’єктів та виникло прагнення максимально використовувати розумові здібності людини шляхом впровадження комп’ютерів в сам процес пізнання.

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

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

Дисципліна включається до циклу фундаментальних дисциплін ОПП.

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

Матеріал дисципліни буде використано для викладання дисциплін програмного та математичного циклів, циклів "Електроніка та мікропроцесорна техніка", "Проектування комп’ютеризованих систем керування”, “Передача даних і телекомунікації", "Теорія та системи керування".



II. РОЗПОДIЛ НАВЧАЛЬНОГО ЧАСУ

Семестр

Всього


Розподiл по видах занять

Сем. атест







Лекц

Практ

Семiн

Лабор


Iндив.

СРС




2

54/30

36







18




30

іспит

3

51/27

34







17




27

залік

Всього

105/57

70







35




57




III. МЕТА I ЗАВДАННЯ ДИСЦИПЛIНИ



    1. Мета вивчення дисципліни.

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



    1. Завдання вивчення дисципліни.

Навчити студентів методам і мисленню, характерним для дискретної математики. Повідомити необхідні для спеціаліста досягнення низки розділів дискретної математики. Ознайомити студентів з ключовими теоретичними і практичними задачами дисципліни і основними перспективними напрямками розвитку. Вказати конкретні проблеми приско­рення науково-технічного прогресу в державі, в розв’язанні яких методи і засоби дискретної математики визначають якісні зрушення у роботі інженерних кадрів, перехід до практики рішення всіх задач з вживанням сучасного математичного апарату.

Студенти повинні вміти:



  • формулювати прикладні проблеми у вигляді моделей дискретної математики;

  • застосовувати методи дискретної математики для розв’язання цих проблем;

  • досліджувати властивості моделей дискретної математики;

  • виконувати алгебраїчні перетворення формул, досліджувати нормальні форми;

  • описувати формально синтаксис мов;

  • будувати інтерпретації числень.

IY. ТЕМАТИЧНИЙ ПЛАН


IY.I РОЗПОДIЛ НАВЧАЛЬНОГО ЧАСУ ЗА ТЕМАМИ


Найменування роздiлiв, тем

Розподiл навчального часу




Всього

Лекц

Практ

Семiн.!

Лабор

Iндив

СРС

СЕМЕСТР 1 Роздiл 1 54 26 10 18

Проблематика і взаємозв'я­зок розділів курсу: передумови, рішення, перспективи

Тема 1.1. Загальний аналіз засобів моделювання дискрет­ної математики.

Тема 1.2. Лінгвістичні моделі дискретної математики.
Роздiл 2 22 10 4 8

Вступ до алгебраїчних систем


Тема 2.1. Загальне уявлення про алгебраїчний підхід.

Тема 2.2. Алгебри, підалгебри, базиси.



Разділ 3 28 14 4 10

Теорія графів і мереж


Тема 3.1. Загальні властивості графів.

Тема 3.2. Прикладні та комбінаторні проблеми теорії графів.


Тема 3.3. Алгоритми розв'язання проблем, сформульованих у термінах графів.

Ітого в 1 семестрі 54 36 18 30




Семестр 2


Роздiл 4 36 12 12 12

Теорія грама­тик та формальних мов


Тема 4.1. Формальні граматики і мови.

Тема 4.2. Алгебраїчні моделі формальних мов.


Роздiл 5 44 14 14 16

Теорія авто­матів

Тема 5.1. Скінчені автомати, їх аналіз і синтез.

Тема 5.2. Нескінчені автомати.

Тема 5.3. Автомати і граматики. Синтаксичний аналіз.



Роздiл 6 68 20 24 24

Вступ до математичної логіки


Тема 6.1. Логіка висловлювань.

Тема 6.2. Числення висловлювань.

Тема 6.3. Логіка предикатів.
Ітого в семестрі 2 51 34 17 27

Всього 105 70 35 57

IY.2 ЛЕКЦIЇ

Вступна лекція. Дискретна математика та її предмет. Кібернетичний підхід, сутність і функціонування, статика і динаміка. Роль дискретної математики при реалізації кібернетичного підходу. Роль систем штучного інтелекту. Нові вимоги до дискретної математики. Розділи дискретної математики, що включені до програми, та їх зміст. Рекомендована основна та додаткова література. Мета і завдання курсу.



Роздiл 1. Проблематика і взаємозв'я­зок розділів курсу: передумови, рішення, перспективи


Тема 1.1. Загальний аналіз засобів моделювання дискрет­ної математики.

Лекція 1. Множини та функції. Поняття множини, елементи множини. Способи описання множини і її елементів. Рівність множин. Підмножини. Універсальна множина, булеан множини. Операції над множинами: об'єднання, переріз, різниця, доповнення. Діаграми Ейлера. Властивості операцій над множинами, принцип двоїстості, тотожні перетворення виразів. Поняття вектора, компоненти вектора. Впорядковані пари, трійки, n-ки. Прямий (декартів) добуток множин. Поняття відображення і функції. Образ і прообраз функції. Типи функцій: ін'єктивна, сюр'єктивна, бієктивна. Часткові функції. Функції від n аргументів. Функції із множини S в множину S. Функціональний підхід в математиці і його значення.

Лекція 2. Бінарні відношення і їхні властивості. Визначення відношення, n-арного відношення. Властивості відношень. Бінарні відношення, область визначення та область значення відношення. Способи задання відношень. Композиція відно­шень, обернене відношення. Відношення: рефлексивні (антирефлексивні, іррефлексивні), симетричні (асиметричні, антисиметричні), транзитивні (не транзитивні). Відношення еквівалентності і порядку. Рівність і розбиття. Класи еквівалентності. Відношення еквівалентності і розбиття. Відношення порядку. Впорядкованість і відношення. Строгий та частковий порядок. Частково впорядковані множини. Повністю впорядковані множини. Найбільший і найменший елементи впорядкованоі множини, верхня і нижня межі.

Лекція 3. Ускладнення математичних обєктів. Розширення уявлень про функції. Функції слідування Пеано. Операції над функціями. Композиція функцій, підстановки. Обернені і оборотні функції. Теореми про існування обернених і оборотних функцій. Спеціальні класи функцій: підстановки, цикли, з’єднання, послідовності, функціонали.

Лекція 4. Ускладнення математичних об’єктів. Розширення уявле­нь про відношення. Решітки як частково впорядковані множини. Замикання відношень. Транзитивне замикання. Рефлексивне замикання.

Лекція 5. Відношення на базах даних і структури даних. Відношення і структури даних. Файли, записи, поля і відношення. Бази, таблиці, атрибути, домени, ключі. Нормальні форми: перша, друга, третя. Функціональна залежність атрибутів. Нормалізація. Приклади відношень як структур даних.
Тема 1.2. Лінгвістичні моделі дискретної математики.

Лекція 6. Уявлення про природні і формальні мови. Знаки і символи. Мова: формальне визначення. Поняття синтаксису і семантики. Алфавіти, множини слів та мови. Операції над словами та множинами слів. Конкатенація, об’єднання, ітерація.

Лекція 7. Загальне уявлення про способи визначення мов. Регулярні множини. Мовні засоби дискретної математики. Способи визначення мов. Породження мов. Уявлення про граматики. Розпізнавання мов. Уявлення про автомати. Алгебраїчний підхід та мови. Регулярні множини. Регулярні вирази. Приклади регулярних множин. Єдність засобів моделювання дискретної математики на прикладі формальних мов і засобів їх визначення: граматик, алгебраїчного підходу та автоматів.

Роздiл 2. Вступ до алгебраїчних систем


Тема 2.1. Загальне уявлення про алгебраїчний підхід.

Лекція 8. Поняття алгебри. Класи алгебр з однією і двома операціями Загальна характеристика алгебраїчного підходу і його роль в управлінні та проектуванні. Необхідність його виникнення на прикладі груп в історичному аспекті. Алгебра і прикладна алгебра. Поняття алгебри. Носій, сигнатура, алгебраїчна система, алгебра, модель. Роль властивостей операцій та аксіоматичне визначення. Вирази та спрощення. Аналіз властивостей операцій (комутативність, асоціативність, наявність одиниці і зворотних елементів) і встановлення типу алгебри. Алгебри з однією операцією: напівгрупа, моноїд, група. Алгебри з двома операціями: кільце, комутативне кільце, поле. Приклади алгебр з двома операціями. Аналіз власти­востей і встановлення типу алгебри. Абстрактні операції і алгебри.

Лекція 9. Розвиток уявлень про алгебраїчні системи. Решітка як алгебра. Еквівалентність двох визначень решітки. Ускладнення математичних об’єктів, морфізми: ендоморфізм, ізоморфізм. Розширення уявлень про решітки. Дистрибутивні і бульові решітки.

Лекція 10. Класи алгебр, що включають у носій більше одного класу мате­матичних об'єктів. Багатоосновні алгебри. Лінійний векторний простір. Векторні простори і лінійні перетворення (оператори). Лінійна алгебра. Матричне зображення лінійних алгебр.

Лекція 11. Алгебри Кантора і Буля. Алгебра Кантора, визначення і властивості. Алгебра Буля, визначення і властивості. Зв’язок алгебр Кантора і Буля. Функції алгебри логіки. Визначення. Функції від двох аргументів. Суперпозиція. Функції та формули. Таблиці і зображення формулами функцій. Мінімізація зображень.

Лекція 12. Алгебра відношень та реляційна алгебра. Теоретико-множинні та додаткові операції на відношеннях. Алгебра відношень. Селекція, проекція, зєднання. Їх властивості. Реляційна алгебра. Приклади застосування операцій. Мови типу SQL.

Лекція 13. Числові системи як алгебраїчні системи. Напівгрупа натуральних чисел. Числові кільця і поля. Доведення властивостей. Єдність засобів моделювання дискретної математики. Метод дискретної математики та структуризація. Проблема визначення підмножин структур. Алгебраїчний підхід.
Тема 2.2. Алгебри, підалгебри, базиси.

Лекція 14. Підалгебри і системи твірних. Універсальні алгебри, підалгебри і проблема породження. Замикання множини за операцією. Властивості теоретико-множинних операцій над замкненими множинами. Аналіз власти­востей і встановлення типу алгебри. Приклади алгебраїчних систем і систем твірних.

Лекція 15. Максимальні підалгебри та їх властивості. Максимальні підалгебри. Приклади максимальних під алгебр. Співвідношення між максимальними підалгебрами. Властивості максимальних під алгебр. Результати Поста про повноту. Базиси.

Лекція 16. Повнота систем функцій алгебри логіки. Функції алгебри логіки. Функціонально-замкнені класи функцій алгебри логіки. Передповні функціонально-замкнені класи функцій алгебри логіки. Монотонні, лінійні функції, інші цікаві класи функцій. Властивості булевих функцій та їх класів. Теорема Поста і встановлення повноти деяких систем функцій алгебри логіки.
Разділ 3. Теорія графів і мереж

Тема 3.1. Загальні властивості графів.

Лекція 3.1. Графи. Основні поняття і визначення. Закономірність виникнення теорії графів в історичному аспекті. Визначення графу і відповідна термінологія. Способи завдання графів (геометричний, аналітичний, матричний (матриці суміжності і інцидентності)). Часто вживані види графів: прості, ізольовані, мультиграфи тощо. Позначені і непозначені графи, оцінки їх кількості. Ступені вершин графів і їх властивості. Загальні властивості неорієнтованих графів.

Лекція 3.2. Підграфи і маршрути в графах. Графи і підграфи. Власні і кістякові підграфи. Повні графи. Доповнення. Маршрути, ланцюги, шляхи, цикли, компоненти зв’язності в графах. Ексцентриситет, діаметр, радіус, центр графа. Шляхи, ланцюги, цикли, маршрути у графах, зв’язані графи, підграфи тощо як необхідна термінологія для вирішення задач управління. Приклади графів для моделювання різних об'єктів.

Лекція 3.3. Графи. Операції над графами і спеціальні графи. Операції над графами: об’єднання, перетин, вилучення ребер і вершин, стягування тощо. Властивості операцій над шляхами, циклами, компонентами. Спеціальні види графів: однорідні, двочасткові і їх властивості. Розпізнавання двочасткових графів. Спеціальні ребра і вершини графів: точки зчленування, мости тощо.

Лекція 3.4. Дерева, розрізи, Ейлерові і Гамільтонові графи. Неорієнтовані дерева: визначення, властивості, ліс, теорема Келі про перерахування. Ейлерові і гамільтонові неорієнтовані графи: визначення і властивості. Умови ейлеровості і гамільтоновості графів. Спеціальні властивості графів, що використовуються теорією надійності. Проблеми прикладної теорії надійності і графи. Визначення і основні властивості розрізу і розділяючої множини. Співвідношення розрізу і розділяючої множини.

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

Лекція 3.6. Орієнтовані дерева і їхні властивості. Орієнтовані (кореневі) дерева. Корінь, зв’язність, квазисильна зв’язність та інші властиво­сті орієнтованих дерев. Символьне зображення орієнтованих дерев. Рівень, глибина, листя та інші поняття орієнтованих дерев. Лівий і правий польський запис. Особливості виконання операцій над графами, заданими різними способами.

Лекція 3.7. Мережі і задачі на мережах. Потоки у мережах. Визначення мережі, потоку і розрізу. Теорема Форда-Фалкерсона. Найпростіші алгоритми вирішення задачі про максимальний потік. Практичні задачі і мережі. Мережі Петрі. Практична необхідність і виконання мереж Петрі. Визначення і основні властивості.

Тема 3.2. Прикладні та комбінаторні проблеми теорії графів.

Лекція 3.8. Розширення уявлень про графи. Теорія графів та її зв’язок з теорією відношень. Графи і відношення. Особливості графів, які відповідають відношенням з певними властивостями. Гіперграфи, особливості завдання, властивості. Нескінчені графи і їх властивості. Приклади застосування графів і відношень, гіперграфів та нескінчених графів.

Лекція 3.9. Укладання графів і проблема планарності. Спеціальні властивості графів, що використовуються в інформаційних технологіях управління та проектування. Укладання графа у просторі. Визначення плоского і планарного графів. Встановлення планарності графів. Існування планарних графів і теореми про непланарність деяких графів. Теорема Куратовського. Планарність і стягування. Планарність та двоїстість.

Лекція 3.8. Комбінаторні аспекти теорії графів. Оцінки характеристик графів. Грані і ступені графів. Теорема Ейлера і теореми про властивості ступенів планарних графів. Комбінаторні властивості двоїстих графів.

Лекція 3.9. Розфарбування графів. Задачі розведення друкованих плат, розфарбування мап і проблема розфарбування графів. Функція розфарбування, хроматичне число, вершинне і реберне розфарбування. Результати розв’язання проблеми розфарбування для графів загального вигляду. Результати розв’язання проблеми розфарбування для планарних графів.

Лекція 3.10. Розвиток комбінаторних уявлень про графи. Задача про весілля. Вершинне паро сполучення і задача про весілля в графовій інтерпретації. Необхідні і достатні умови вирішення, теорема Холла. Теорія трансверсалей. Трансверсаль, часткова трансверсаль. Необхідні і достатні умови існування трансверсалі. Застосування теореми Холла: латинські квадрати, (0,1)-матриці, реберне розфарбування, загальні трансверсалі.

Лекція 3.11. Зв’язок між шляхами та розрізами і поділами в графах. Реберно неперетинні та вершинно-неперетинні шляхи в графах. Поділяючі і розрізаючі множини в графах. Реберна форма теореми Менгера: зв’язок ре­берно неперетинних простих ланцюгів і поділяючих множин. Теорема Менгера: зв’язок вершинно неперетинних простих ланцюгів і розрізаючих множин. Аналоги основних результатів для орграфів. Зв’язок теорем Менгера і Холла.
Роздiл 4. Теорія грама­тик та формальних мов

Тема 4.1. Формальні граматики і мови.

Лекція 4.1 Граматики породження: визначення і класифікація. Алфавіти і мови: основні поняття і формальні визначення (слово, мова, операції над словами і мовами, їх властивості). Визначення граматик породження: термінальний і не термінальний алфавіти, правила породження, породжувані слова і мова. Класифікація граматик за Хомським: автоматні, контекстно-вільні, контекстно-залежні граматики та граматики без обмежень. Приклади граматик типів 0-3.

Лекція 4.2. Інші моделі граматик. Трансформаційні граматики. Програмні гаматики. Індексні граматики. Приклади програмних та індексних граматик, аналіз їх­ніх властивостей.

Лекція 4.3. Властивості контекстно-вільних мов як базис теорії трансляції. Контекстно-вільні граматики і мови. Дерева виведення. Виведення і дерева виведення. Проблема порожнечі мови. Властивості контекстно-вільних мов. Нормальні форми Хомського та Грейбах контекстно-вільних граматик та алгоритми зведення до них. Проблеми дослідження контекстно-вільних граматик та відповідні алгоритми.

Лекція 4.4. Контекстно-залежні граматики і граматики без обмежень. Властивості граматик без обмежень і контекстно-залежних граматик. Загальне уявлення про завдання алгоритмічних мов програмування граматиками. Форма Бекуса-Наура і розширена фор­ма Бекуса-Наура. Уявлення про граматику мови програмування Паскаль.

Тема 4.2. Алгебраїчні моделі формальних мов.

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

Лекція 4.6. Алгебраїчні властивості мов. Алгебраїчні властивості регулярних мов. Операції над регулярними мовами і їх властивості. Алгебра подій. Алгебраїчні властивості контекстно-вільних мов. Операції над контекстно-вільними мовами і їх властивості. Алгебра контекстно-вільних мов.

Лекція 4.7. Алгебраїчні властивості контекстно-залежних мов і мов без обмежень.

Роздiл 5. Теорія авто­матів

Автомати як засоби моделювання динаміки об’єктів. Основні поняття теорії автоматів. Стани та їх зміна у просторі. Функціонування як переходи автомата. Застосування автоматів.


Тема 5.1. Скінчені автомати, їх аналіз і синтез.

Лекція 5.1. Скінчені автомати: визначення і загальна арактеристика. Основні поняття скінчених автоматів: стан, перехід, вихід, конфігурація і ситуація, такт. Скінчений автомат як математичний об’єкт і пристрій. Тривіальні і нетривіальні, детерміновані і недетерміновані автомати. Деякі властивості автоматів. Способи задання скінчених автоматів. Перерахування скінчених автоматів.
Лекція 5.2. Задача аналізу скінченних автоматів. Проблеми дослідження скінчених автоматів: аналіз, синтез, розпізнавання. Скінчені автомати і регулярні мови. Скінчений розпізнавач. Задача аналізу скінченого автомата і властивості графів і матриць переходів автомата.

Лекція 5.3. Функціонування автомата і формальні засоби його аналізу. Переходи в автоматі і необхідність їх дослідження. Дослідження маршрутів на основі операцій над матрицями переходів. Найкоротші шляхи. Замкнені шляхи. Кістякові матриці і їх застосування для аналізу автоматів.

Лекція 5.4. Еквівалентність станів скінченних автоматів. Еквівалентні і розрізнені стани. Умови еквівалентності і розрізненості станів. k-еквівалентні і k-розрізнені стани. Умови k-еквівалентності і k-розрізненості станів. Властивості відношення k-еквівалентності і k-розрізненості станів. k-еквівалентне розбиття та його властивості.

Лекція 5.5. Еквівалентне розбиття і матричний метод його визначення. Еквівалентне розбиття та його властивості. Розбиття та k-еквівалентне розбиття. Матричний метод визначення еквівалентного розбиття. Побудова початкової матриці і опис ітерації перетворень матриці автомата. Еквівалентність автоматів: визначення і властивості.

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

Лекція 5.7. Експерименти по розпізнаванню станів. Класифікація експериментів: безумовні і умовні, прості і кратні, діагностичні і установочні експерименти. Діагностична і установочна задачі. Діагностичні експерименти для двох станів. Діагностична послідовність. Алгоритм побудови мінімальної діагностичної послідовності.
Лекція 5.7. Експерименти по розпізнаванню автоматів. Загальна задача розпізнавання автомата. Умови розпізнаваності і нерозпізнаваності автомата. Розпізнавання автоматів відомого класу. Умови розпізнаваності і нерозпізнаваності автомата відомого класу. Алгоритм побудови мінімальної діагностичної послідовності розпізнавання автоматів відомого класу.

Лекція 5.8. Задача синтезу скінченого автомата. Алгоритм синтезу скінченого автомата за регулярним виразом. Приклади скінчених автоматів для моделювання реальних об'єктів.
Тема 5.2. Нескінчені автомати.

Загальна характеристика нескінчених автоматів.



Лекція 5.9. Автомати з магазинною пам'яттю. Автомат з магазинною пам'яттю. Визначення МП-автомата і його властивості. Детермінований і недетермінований МП-автомати. Приклади детермінованих і недетермінованих МП-автоматів.

Лекція 5.10. Розширений МП-автомат. Мови, що допускаються МП-автоматами. МП-автомати і контекстно-вільні мови.

Лекція 5.11. Лінійно-обмежені автомати і машина Т’юрінга. Машина Т’юрінга. Визначення і властивості, функціонування. Машина Т’юрінга і мови без обмежень. Лінійно-обмежений автомат. Його визначення на базі машини Т’юрінга.

Лекція 5.12. Лінійно-обмежені автомати і контекстно-залежні мови. Зв'язок машини Т’юрінга з алгоритмами. Приклади машини Т’юрінга і лінійно-обмежених автоматів, аналіз мов, що допускаються ними.
Роздiл 6. Вступ до математичної логіки

Загальна характеристика логічного підходу. Логіка та її проблеми. Необхідність формалізації. Алгебраїчний метод спрощень. Формальні аксіоматичні теорії.



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

Лекція 6.1. Висловлювання, зв’язки, істинність. Висловлювання. Істинність та хибність висловлювань. Прості та складні висловлювання. Логічні зв’язки та істинність. Табличний метод встановлення істинності.

Лекція 6.2. Вдосконалення методу таблиць істинності та загальна характеристика інших підходів до вирішення проблеми встановлення істинності. Корисні властивості таблиць істинності. Основи алгебраїчного методу встановлення істинності. Відношення логічного слідування та аксіоматичний підхід.

Лекція 6.3. Булева алгебра висловлювань та алгебраїчний метод встановлення істинності. Булева алгебра висловлювань. Носій, операції, виділені елементи, властивості операцій, тотожність висловлювань. Тотожність і еквівалентність. Застосування алгебраїчного методу встановлення істинності.

Лекція 6.4. Нормальні форми алгебри висловлювань та встановлення абсолютної істинності і абсолютної хибності. Елементарні диз’юнкція і кон’юнкція та їх властивості. Диз’юнктивна і кон’юнктивна нормальні форми та їх властивості. Зведення до нормальних форм.

Лекція 6.5. Двоїстість в алгебрі висловлювань. Двоїсті висловлювання та їх зв’язок з вихідними. Двоїстість алгебр. Арифметичні операції в алгебрі логіки. Поліноми Жегалкіна.
Тема 6.2. Числення висловлювань.

Лекція 6.6. Означення числення висловлювань і аналіз його дедуктивних властивостей. Числення висловлювань. Означення та аналіз дедуктивних властивостей. Теорема дедукції, її значення і наслідки.

Лекція 6.7. Аналіз виведення з гіпотезами. Звичайне виведення у прямому та зворотному напрямах та теорема дедукції. Виводи з гіпотезами. Гіпотези і аксіоми. Властивості виводів з гіпотезами.


Лекція 6.8. Модельні властивості числення висловлювань. Повнота: сутність, значення і встановлення повноти числення висловлювань. Несу­пе­реч­ливість: сутність, значення і встановлення несперечливості числення вислов­лювань. Розв’язуваність: сутність, значення і встановлення розв’язуваності числення висловлювань.

Лекція 6.9. Незалежність аксіом. Вибір аксіом та інші аксіоматизації. Незалежність аксіом. Вибір аксіом. Інші аксіо­метизації числення висловлювань. Застосування засо­бів математичної логіки на практиці. Вентильні схеми, їхній аналіз і проектування.
Тема 6.3. Логіка предикатів.

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

Лекція 6.11. Нормальні форми логіки предикатів. Зведені, зведені нормальні, скулемівські нормальна та стандартна форми. Зведення до нормальних форм.

Лекція 6.12. Числення предикатів та теорії першого порядку. Означення та аналіз дедуктивних властивостей. Теорема дедукції. Виведення з гіпотезами та його властивості. Приклади теорій першого порядку.

Лекція 6.12. Модельні властивості числення предикатів. Повнота числення предикатів. Несу­пе­реч­ливість числення предикатів. Розв’язуваність числення предикатів. Проблема характеризації і підходи до її розв’язання.

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

IY.3 ПРАКТИЧНI ЗАНЯТТЯ


IY.4 СЕМIНАРСЬКI ЗАНЯТТЯ

IY.5 ЛАБОРАТОРНI РОБОТИ



  1. Множини і відношення. Способи визначення, операції над множинами: об'єднання, переріз, різниця, доповнення, декартів добуток. Рівнопотужні множини. Функції. Композиція і типи. Відношення, n-нарні відношення. Властивості відношень. Способи задання відношень. Відношення еквіва­лентності, порядку. Впорядковані множини. Злічені та незлічені множини.

  2. Впорядковані множини. Універсальні границі. Мінімальні і максимальні елементи. Найбільший і найменший елементи, межі. Частково впорядковані множини як решітки.

  3. Регулярні множини.

  4. Перестановки, розміщення, сполуки елементів. Рекурентні співвідношення. Розбиття множини.

  5. Алгебри з однією операцією: напівгрупа, моноїд, група. Алгебри з двома операціями.

  6. Алгебра відношень. Приклади алгебр з двома операціями. Аналіз власти­востей і встановлення типу алгебри.

  7. Проблема породження. Підалгебра і система твірних. Аналіз власти­востей і встановлення типу алгебри.

  8. Способи завдання графів. Спеціальні види графів. Дерева, підграфи. Шляхи, ланцюги, маршрути у графах Операції над графами. Ейлерові і гамільтонові графи. Турніри.

  9. Розріз і розрізаюча множина. Встановлення планарності графів. Грані і ступені графів. Планарність і двоїстість.

  10. Потоки у мережах. Найпростіші алгоритми розв'язання задачі про максимальний потік. Мережі Петрі.

  11. Граматики, породження, загальні властивості. Визначення мов граматиками. Регулярні множини і автоматні граматики.

  12. Контекстно-вільні мови та їхні властивості. Нормальні форми граматик. Контекстно-залежні граматики і граматики без обмежень. Властивості граматик без обмежень і контекстно-залежних граматик.

  13. Загальне уявлення про задання алгоритмічних мов програмування граматиками. Форма Бекуса-Наура і розширена фор­ма Бекуса-Наура.

  14. Скінчені автомати і їхні властивості. Скінчені автомати і регулярні мови.

  15. Аналіз і синтез скінчених автоматів. Еквівалентність станів і еквівалентність скінчених автоматів. Еквівалентне розбит­тя. Приклади скінчених автоматів для моделювання реальних об'єктів.

  16. Автомати з магазинною пам’яттю. Мови, що допускаються МП-автоматами. МП-автомати і контекстно-вільні мови. Загальна проблема розпізнавання і пробле­ма трансляції.

  17. Лінійно-обмежені автомати і машина Т’юрінга. Машина Т’юрінга. Машина Т’юрінга і мови без обмежень. Лінійно-обмежені автомати і контекстно-залежні мови. Зв'язок машини Т’юрінга з алгоритмами.

  18. Прості і складні висловлювання. Дослідження можливостей табличного методу встановлення істинності. Закріплення вміння формалізувати знання, що представлені у природно мовній формі.

  19. Функції алгебри логіки. Перевірка повноти, визначення базису.

  20. Алгебраїчний метод. Дослідження можливостей алгебраїчного методу. Нормальні форми. Двоїсті висловлювання.

  21. Дедуктивні властивості числення висловлювань. Виведення в численні висловлювань.

  22. Особливості використання аксіом та правил виведення, виведення з гіпотезами, використання дедукції.

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

  24. Закріплення вміння формалізувати знання мовою логіки предикатів, що представлені у природно мовній формі.Виведення в численні предикатів.

IY.6 IНДИВIДУАЛЬНI ЗАВДАННЯ

Викладені в методичних вказівках.

IY.7 КОНТРОЛЬНI РОБОТИ

Завдання на контрольні роботи вибираються із вправ методичних вказівок.

Y. МЕТОДИЧНI ВКАЗIВКИ


YI. НАВЧАЛЬНО-МЕТОДИЧНI МАТЕРIАЛИ

Основна література.

1. Печурін М.К. та ін. Основи дискретної математики: Учб. посібник для студ. вузів. - К: Вища школа.-212с.

2. Горбатов В.А. Основы дискретной математики.-М.:Высш.шк.,1986.-311 с.

3. Кук Г., Бейз Д. Компьютерная математика. - М.: Наука, 1990. - 400 с.

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

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

5. Мендельсон 3. Введение в математическую логику.-М.:Наука,1984.-320с.

6. Свами М., Тхуласираман К. Графы, сети, алгоритмы.-М.:Мир,1984.-455 с.

7. Биркгоф Г. Теория решеток. - М.: Наука, 1984. - 566 с.

8. Гетманова А.Д. Логика. - М.: Высш.шк., 1986. - 288 с.

9. Джордж Ф. Основы кибернетики. - М.: Радио и связь, 1984. - 520с.

10. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность.- М.: Мир, 1985. - 510 с.

11.Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. - М.: Мир, 1966. - 260с.

12. Глушков В.М, Цейтлин Г.Е., Ющенко Е.Л. Алгебра, языки, программирование. – К.: Наукова думка, 1989. - 328 с.

13. Кудрявцев В.Б. и др. Введение в теорию автоматов. - М.: Наука, 1985.-320 с.

14. Яблонский С.В. Введение в дискретную математику.- М.: Наука, 1970.-277 с.

15. Перминов О.Н. Язык программирования Паскаль. - М.: Радио и связь, 1989. - 120 с.


Методична література.

  1. Методичні вказівки до самостійної роботи з дисципліни “Основи дискретної математики”. Частина 1. Укладач С.Ф.Теленик.

  2. Методичні вказівки до самостійної роботи з дисципліни “Основи дискретної математики”. Частина 2. Укладач С.Ф.Теленик



Програму розробив д.т.н. Теленик С.Ф.


База даних захищена авторським правом ©lecture.in.ua 2016
звернутися до адміністрації

    Головна сторінка