asyan.org
добавить свой файл
1 2 ... 6 7
Конспект лекцій
Основи дискретної математики
Розділ 1

Тема 1




Зміст


Вступна лекція 2

РОЗДІЛ 1. ПРОБЛЕМАТИКА І ВЗАЄМОЗВ’ЗОК РОЗДІЛІВ КУРСУ: ПЕРЕДУМОВИ, РІШЕННЯ, ПЕРСПЕКТИВИ. 11

ТЕМА 1. Загальний аналіз засобів моделювання дискретної математики 11

Лекція 1. Множини і функції 11

Лекція 2. Бінарні відношення і їхні властивості 20

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

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

Лекція 5. Відношення на базах даних і структури даних 40



Вступна лекція


Курс лекцій, що вам пропонується, носить назву “Основи дискретної математики”. Що приховує ця назва, тобто що Ви будете вивчати і задля якої мети?

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

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

Звідки ж випливає необхідність вивчення дискретної математики інженерами з комп’ютеризованих систем зі спеціальності “Системи управління і автоматики”?

Відомо, що з комп'ютеризованими системами в керуванні, проектуванні й інших сферах діяльності людини, зокрема, автоматизованими системами керування технологічними процесами (АСКТП), автоматизованими системами керування (АСК), автоматизованими системами обробки інформації і керування (АСОІК), системами автоматизації проектування (САПР), інформаційно-керуючими системами (ІКС), інформаційно-пошуковими системами (ІПС), автоматизованими інформаційними системами (АІС) тощо, пов'язана реалізація кібернетичного підходу до керування з використанням комп'ютерів. Кібернетика – наука, що вивчає задачі керування і зв'язку в різних об'єктах як живих, так і неживих. Фундатор кібернетики Норберт Вінер увів нову категорію “керування”. Сутність принципу керування полягає в тому, що рух і дія великих мас чи передача і перетворення великих кількостей енергії направляються і контролюються за допомогою невеликих кількостей енергії, що несуть інформацію.

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

Реалізація зазначених принципів пов'язана з реалізацією за допомогою комп'ютерної техніки виниклого в кібернетиці представлення про схему керування зі зворотним зв'язком:






І кібернетика, і інформатика мають як теоретичну, так і практичну спрямованість. Їхня практична сторона – методи побудови систем керування (СК), що забезпечують найкраще, в якомусь сенсі, керування. Їхня теоретична сторона – вивчення закономірностей побудови СК і процесів керування, щонайменше це Ляпунов відносить до кібернетики.

Сформувалися наступних два підходи до вивчення СК:

  • макропідхід, коли система розглядається як “чорний ящик”, і дослідник визначає як залежить вихід від входу; це дозволяє підібрати відповідний вхід для досягнення необхідного чи найкращого виходу;

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

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



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

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

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

По-перше, необхідно мати модель системи перевезень. Найпростіший вихід – використання плану магістралей на місцевості. Але план містить безліч непотрібних деталей. Щоб позбутися їх, треба залишити тільки факт наявності пункту (підприємства) і магістралі. Виникає об'єкт, який можна представити графічно, у вигляді, наведеному на рис.2 (будемо вважати, що він відповідає конкретним вхідним даним нашої проблеми).

Тут підприємствам відповідають позначені літерами A, B, C, D та E точки площини. Причому ми їх позначаємо, щоб не втратити зв'язок з реальними підприємствами. А наявності транспортної магістралі між парою підприємств відповідає лінія між точками, що відповідають цим підприємствам.



Цей об'єкт називають графом, заданим геометричним способом. Tочки і лінії називають відповідно вершинами і ребрами. Тоді граф – модель системи перевезень. Розглянемо докладніше граф з цієї точки зору. У графі збережена лише наявність магістралі (у вигляді ребра) між парою вершин, але не її форма. Форма магістралі на плані з урахуванням масштабу давала можливість зберегти деякі характеристики магістралей, наприклад, відстань. З іншого боку, на плані вже не можна установити пропускну здатність магістралі, якщо не вказати це явно. Таким чином, задати цю характеристику магістралей можна на графі в явному вигляді. Тоді ми одержимо об'єкт, який вже не називають графом. Це вже інший об'єкт дискретного аналізу – мережа. Відстань на графі також потрібно вказувати явно. Тоді ми також одержимо новий об'єкт дискретного аналізу, який звичайно називають зваженим графом. Приклад зваженого графа наведений на рис.3. Кожне ребро характеризується вагою – довжиною відповідної магістралі (відстанню між відповідними підприємствами). Отже, зважений граф на рис.3 зберігає потрібні для розв’язання сформульованої проблеми дані і можна прийняти його за потрібну нам модель.



Потім варто створити модель поведінки, тобто модель вибору найкоротшого маршруту. Будемо позначати ребро, що зв'язує вершини X і Y, парою літер XY. Маршрутом у графі називають послідовність ребер, у якій позначення попереднього ребра закінчується, а позначення наступного ребра починається з тієї ж літери (природно, жодних дві точки не повинні бути позначені тією ж літерою). Модель поведінки змістовно можна сформулювати в такий спосіб: знайти маршрут з вершини X у вершину Y, сума ваг ребер якого мінімальна серед усіх маршрутів з вершини X у вершину Y.

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



Де – маршрут i між заданою парою вершин;

– множина усіх маршрутів між заданою парою вершин;

– вага ребра XY маршруту

Друга стадія полягає в створенні методу розв’язання поставленої задачі. Застосування методу розв’язання до вхідних даних (наведеного зваженого графа) і реалізація результатів і забезпечать найкращу поведінку. Нехай потрібно визначити найкоротший маршрут з вершини А в вершину Е. Можна було б перебрати всі маршрути, визначити суми їхніх ваг і вибрати маршрут, якому відповідає найменша сума, визначена вище. Наприклад, з маршрутів АВ, ВЕ й АD, DC, CE вигідніший другий маршрут. Однак вже в нашому прикладі потрібно порівняти п'ять маршрутів, а в більш складних випадках число маршрутів різко зростає. Тому дискретний аналіз ставить не просто проблему визначення методу розв’язання, але проблему створення методу, що працює краще, звичайно швидше інших. Будемо записувати метод розв’язання у вигляді послідовності дій, що повинні бути виконані тим, хто розв’язує задачу. Така послідовність дій звичайно називається алгоритмом. Більш зручним у цьому відношенні буде наступний алгоритм:

Крок 1. Вершині, що відповідає пункту відправлення, приписуємо вагу 0.

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

Крок 3. Вибираємо зі списку перегляду чергову вершину Z. Визначаємо вершини, з якими вершина Z зв'язана ребрами, приписуємо до списку перегляду ті з них, що у списку не містяться (вершину, що відповідає пункту призначення, у список не включаємо). Для кожної знайденої вершини визначаємо відстань, додаючи вагу відповідного ребра до відстані вершини Z. Якщо для вершини відстань вже визначалася раніше, і нова відстань менше, то приписуємо їй нову відстань і позначаємо її літерою Z. Якщо нова відстань не менше, то залишаємо вершину без змін. Якщо вершині раніше відстань не приписувалася, то приписуємо їй визначеним чином відстань і позначаємо її літерою Z. Викреслюємо Z зі списку перегляду.

Крок 4. Якщо список перегляду не порожній, то переходимо до кроку 3, інакше – до кроку 5.

Крок 5. Відновлюємо маршрут по оцінках відстаней, рухаючись по ребрах графа від вершини, що відповідає пункту призначення, до вершини, що відповідає пункту відправлення, використовуючи позначки відстаней, приписаних вершинам. Робота алгоритму для визначення найкоротшого маршруту з пункту А в пункт Е моделі показана на рис 4 – 8.










Легко відновити найкоротший маршрут: AD, DC, CE.

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

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

Отже, основна наша мета – оволодіння набором засобів і методів дискретного аналізу, достатніх для реалізації кібернетичного підходу при створенні АСК для різноманітних об'єктів керування, реалізації ефективних систем збору, передачі, оброблення, відображення, збереження, розподілення і захисту інформації.

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

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

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

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

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

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

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

  4. Теорія граматик.

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

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

Матеріал зазначених розділів дозволяє відібрати набір засобів і методів математичного моделювання дискретних систем і процесів. Зокрема, засоби моделювання розглядаються в розділах 1-3,5. Засоби для розв’язання мовних проблем розглядаються в розділах 4,5.

Засоби реалізації алгоритмічного підходу будуть розглядатися в курсі “Алгоритміка”, що читається в 4-му семестрі. Теорія алгоритмів виникла після того, як з'явилося поняття нерозв'язуваності проблем, коли численні невдалі спроби рішення відомих масових проблем зміцнили математиків у прагненні довести, що відповідних алгоритмів для рішення цих проблем узагалі не існує. Уся множина проблем розділяється на розв'язувані і нерозв'язувані, тобто на ті, котрі мають алгоритм і ті, котрі алгоритмів не мають. Для доведення нерозв'язуваності проблеми необхідне точне визначення алгоритму, оскільки неможливо довести існування чи не існування того, що не визначено.

Точне визначення алгоритму було першою проблемою теорії алгоритмів. У 30 - 40-х роках А.Т'юрінгом, Е.Постом, А.Черчем, а пізніше А.А.Марковим і С.Кліні були запропоновані уточнення до визначення алгоритму і розроблені перші методи доведення нерозв'язуваності масових проблем.

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

На основі теорії алгоритмів сформувалися теорія складності, теорія NP-повноти і теорія зведення, метою яких була оцінка алгоритмів і проблем, розбиття множини розв'язуваних проблем на “гарні” і “погані” і побудова ієрархії “поганих” проблем. Подальший розвиток теорії алгоритмів пов'язаний з автоматизацією конструювання алгоритмів. У теорії алгоритмів з'явився напрямок “Прикладна теорія алгоритмів” чи “Алгоритміка”.

Усе це обумовлює включення теорії алгоритмів у окремий курс лекцій. Необхідні для розвитку систем ШІ методи і засоби розглядаються в розділі 6 і, крім того, складуть предмет згаданого вище курсу “Алгоритміка”.

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

  • по-перше, покажемо, які прикладні проблеми формалізації реальних об'єктів обумовили появу тих чи інших засобів дискретної математики;

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

  • по-третє, продемонструємо на прикладі дискретної математики спільність багатьох проблем логіки, лінгвістики, кібернетики;

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

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

Насамкінець, варто зазначити, що матеріал нашого курсу пов'язаний фактично з усіма загальноосвітніми дисциплінами навчального плану підготовки бакалаврів «Комп'ютеризовані системи, керування і автоматика».




следующая страница >>