Методичні вказівки до самостійної роботи з курсу "Основи дискретної математики" для студентів бакалаврату "Комп’ютеризовані системи, автоматика і управління" денної та заочної форм навчання. Частина 1: Зміст курсу, рекомендації і вправи до вивчення алгебраїчних систем і теорії графів та мереж / Укладачі С.Ф.Теленик, Я.Ю.Дорогий. - К.: НТУУ «КПІ», 2003. - 50 с.

Укладачі: С.Ф.Теленик, докт.техн.наук

Я.Ю.Дорогий.

Відповідальний редактор О.А.Павлов. Рецензент: В.П.Полторак

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

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

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

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

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

Звідси й випливає важливість проблеми організації самостій­ної роботи студентів. У цих методичних вказівках розглянуто організацію і зміст само­стійної роботи студентів з дисципліни "Основи дискретної математики", яка разом з дисциплінами "Математичні основи штучного інтелекту”, “Алгоритміка" та іншими дисциплінами математич­ного циклу покликана формувати основу математичного апарату бакалавра за напрямком "Комп’ютеризовані системи, автоматика і управління". В усіх спеціальних дисциплі­нах використовуються методи й засоби цих дисциплін.

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

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

І. Зміст дисципліни

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

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

Завданнями викладання дисципліни є:

• навчити студентів методам і схемам міркувань, характерним для дискретної математики;

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

• ознайомити студентів з ключовими теоретичними і практичними задачами дисципліни і основними перспек­тивними напрямками розвитку її окремих розділів;

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

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

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

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

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

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

• виконувати алгебраїчні перетворення конструкцій, застосовувати типові об’єкти дискретної математики;

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

• описувати, обробляти формальні мови;

• будувати інтерпретації об’єкти дискретної математики.

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

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

До того ж, у кібернетиці й теорії керування усе більш рішуче заявляє про свої права новий напрямок – штуч­ний інтелект (ШІ). Створюються комп'ютери, моделі і програмні сис­теми, що імітують мислення людини, її логічну діяльність. Виявилося, що для реалізації систем ШІ необхідно мати засоби подання, накопичення і оброблення знань. У системах ШІ традиційний алгоритмічний підхід доповнюють методи виведення розв’язків проблем. Область досліджень дискретної математики істотно розширилася, у ній з'явилися відповідні засоби – теорія виведення, граматики із семантикою тощо.

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

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

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

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

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

5. Теорія автоматів.

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

У розділі І розглянуто основні проблеми дискретної математики й необхідні для їхнього розв’язання засоби. Зокрема, велика увага при­діляється низці проблем, які виникають при проектуванні й експлуа­тації сучасних систем керування складними об’єктами. Насамперед виділено перелік розділів дискретної математики, необхідних для спеціалістів, які розв’язують ці проблеми; введені поняття, засоби й методи різних розділів, що використовуються для розв’язання зазначених проблем. При цьому одне з головних завдань полягало у встановленні чітких зв’язків між матеріалом різних розділів як на підставі, спільнос­ті розв’язуваних проблем, так і на підставі внутрішніх особли­востей самого матеріалу.

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

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

Матеріал розділу 2 служить вступом до курсів “Математичні основи штучного інтелекту”, “Алгоритміка”, використовується для моделювання структури й функціонування бага­тьох об’єктів керування, формує математичний апарат для низки дисциплін циклів “Електроніка та мікропроцесорна техніка”, “Програмування”, “Проектування комп’ютеризованих систем керування” то­що. У ньому розглянуті уявлення про алгебраїчний підхід і понят­тя алгебри та алгебраїчної системи, досліджені властивості деяких типів ал­гебраїчних систем, зокрема, алгебр з однією операцією, бульових алгебр, алгебри Кантора, алгебр з двома операціями та числових систем.

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

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

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

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

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

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

Матеріал розділу використовується в дисциплінах математичного та програмного циклів, продовженням розділу 4 служить дисципліна “Комп’ютерна лінгвістика”, де розгля­даються модифікації граматик та їх застосування для розв’язання багатьох мовних проблем систем керування.

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

Матеріал розділу використовується в дисциплінах практично усіх циклів підготовки бакалаврів зазначеного напрямку, насамперед: "Електроніка та мікропроцесорна техніка", "Проектування комп’ютеризованих систем керування”, "Теорія та системи керування". Визначення машини Т’юрінга - зручний засіб для формального визначення алгоритму, що широко викорис­товується в курсі "Алгоритміка".

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

Матеріал розділу служить вступом до курсу "Математичні основи штучного інтелекту”, широко застосо­вується в дисциплінах циклів "Програмування", "Проектування комп’ютеризованих систем керування" .

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

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

Найменування роздiлiв, тем	Розподiл навчального часу
	Всього	Лекції	Практичні заняття	Семiнари	Лабораторні роботи	Iндивід. заняття	С Р С
СЕМЕСТР 1
Роздiл 1	20	10			10
Проблематика і взаємозв'я­зок розділів курсу: передумови, рішення, перспективи Тема 1.1. Загальний аналіз засобів моделювання дискрет­ної математики. Тема 1.2. Лінгвістичні моделі дискретної математики.
Роздiл 2	20	10			10
Вступ до алгебраїчних систем Тема 2.1. Загальне уявлення про алгебраїчний підхід. Тема 2.2. Алгебри, підалгебри, базиси.
Роздiл 3	32	16			16
Теорія графів і мереж Тема 3.1. Загальні властивості графів. Тема 3.2. Прикладні та комбінаторні проблеми теорії графів. Тема 3.3. Алгоритми розв'язання проблем, сформульованих у термінах графів.
Ітого в 1 семестрі	72	36			36
СЕМЕСТР 2
Роздiл 4	20	10			10
Теорія грама­тик та формальних мов Тема 4.1. Формальні граматики і мови. Тема 4.2. Алгебраїчні моделі формальних мов.
Роздiл 5	24	12			12
Теорія авто­матів Тема 5.1. Скінчені автомати, їх аналіз і синтез. Тема 5.2. Нескінчені автомати. Тема 5.3. Автомати і граматики. Синтаксичний аналіз.
Роздiл 6	24	12			12
Вступ до математичної логіки Тема 6.1. Логіка висловлювань. Тема 6.2. Числення висловлювань. Тема 6.3. Логіка предикатів.
Ітого в 2 семестрі	68	34			34
Всього	140	70			70

А тепер розглянемо зміст лекційних занять по кожній темі.

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