Реферати

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

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

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

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

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

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

Міністерство Вищого і Середнього професійного освіти

Державна освітня установа вищої професійної освіти

“ Хабаровский Державний Технічний Університет”

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

Спеціальність 351400 Прикладна інформатика в економіці

Хабаровськ-2003

РЕФЕРАТ

КР містить пояснювальну записку на 23 листах формату А4, що включає 13 малюнків, 10 таблиць, 5 літературних джерел.

БУЛЕВА АЛГЕБРА, БУЛЕВА ФУНКЦІЯ, ТАБЛИЦІ ІСТИННОСТІ, ДИЗЪЮНКТИВНАЯ НОРМАЛЬНА ФОРМА, КОНЪЮНКТИВНАЯ НОРМАЛЬНА ФОРМА, ПОЛІНОМ ЖЕГАЛКИНА, ПОХІДНА ЛОГІЧНІЙ ФУНКЦІЇ, ГРАФ, АЛГОРИТМ, НЕЧІТКА БЕЗЛІЧ

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

При складанні роботи використовувалися дані з різних джерел, а саме були використані різні методичні рекомендації по дискретної математики і роботи різних авторів (Комірів А. П., Новіков Ф. А., Логинов Б. М., Яблонський С. В.), а також при рішенні задач виборі альтернатив на основі нечіткого відношення переваги використовувалися дані з журналу Hard’n’Soft.

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

ЗМІСТ

Введення 4

1 Математична логіка 5

1.1 Застосування математичної логіки в інформатиці 5

1.2 Застосування математичної логіки 12

2 Графи 16

2.1 Алгоритм Дейкстра 16

2.2 Жадібний алгоритм 18

2.3 Побудова мінімального кістяка 19

2.4 Задача Комівояжера 20

3 Нечіткі множини 22

Висновок 27

Список використаних джерел 28

вВЕДЕНИЕ

Курсова робота являє собою комплекс задач по наступних темах дисципліни: “ Дискретна математика і дискретний аналіз”: “ Способи завдання булевских функцій”, “ Теорія графів”, “ Стратегія знаходження мінімального кістяка”, “ Жадібний алгоритм”, “ Алгоритм Дейкстра”, “ Задача Комівояжера”, “ Многокритериальний вибір альтернатив на основі нечіткого відношення переваги”. Курсова робота містить три частини: математична логіка, графи, нечіткі множини. Перша частина розглядає застосування дискретної математики в інформатиці, а також розглянуті застосування математичної логіки на практичних прикладах: складена таблиця істинності, знаходження двох похідних, конъюнктивная і дизъюнктивная нормальна функція, а також метод невизначених коефіцієнтів для побудови полінома Жегалкина. У другій частині розглядається застосування теорії графів в економічних задачах, які поділяються на: алгоритм побудови мінімального кістяка, який складається у визначенні мінімальних витрат на проїзд від будинку до супермаркету; Жадібний алгоритм – рішення задачі про максимальну завантаженість ліній, які з'єднують нафтопереробні заводи з новим родовищем нафти; Алгоритм Дейкстра – задача про знаходження оптимального шляху, отже мінімальних витрат на забезпечення відпочинку своїм співробітникам; Задача Комівояжера – максимізація прибутку і зменшення витрат часу. У третій частині розглянутий спосіб знаходження більш переважно товару за допомогою методу многокритериального вибору альтернатив на основі нечіткого відношення переваги.

1 Математична логіка

1.1 Застосування математичної логіки в інформатиці

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

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

Інформатика – це наука, яка вивчає комп'ютер, а також взаємодію комп'ютера з людиною.

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

Ідея логічних машин з'явилася в 13 віці у іспанських схоластик Раймунда Луллія, розглядалася потім Лейбніцем і отримало новий розвиток в 19 віці, після виникнення математичної логіки. У 1870 році англійський філософ і економіст Вільям Стенлі Джевонс побудував в Манчестере “ логічне піаніно”, яке витягувало з алгебраїчно записаних посилок слідства, виділяючи допустимі комбінації термінів. Це називають також розкладанням висловлювання на конституанти. Важливо відмітити можливість практичного застосування логічної машини для рішення складних логічних задач.

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

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

Проблема штучного розуму складна і багатогранна. Ймовірно, не помилимося, якщо скажемо, що остаточні межі механізації думки можна встановити лише експериментальним шляхом. Помітимо ще, що в сучасної кібернетики обговорюється можливість моделювання не тільки формальних, але і змістовних мислительних процесів. 1.1.1 Математична логіка в техніці. Роль логічної обробки бінарних даних на сучасному етапі розвитку обчислювальної техніки істотно зросла. Це пов'язано, насамперед, з створенням технічно систем. реалізуючий в тому або інакшому вигляді технології отримання і накопичення знань, моделюванням окремих інтелектуальних функцій людини. Ядром таких систем є могутні ЕОМ і обчислювальні комплекси. Крім того, існує великий клас прикладних задач, які можна звести до рішення логічних задач, наприклад, обробка і синтез зображень, транспортні задачі. Необхідна продуктивність обчислювальних коштів досягається шляхом распараллеливания і конвейеризації обчислювальних процесів. Це реалізовується, як правило, на основі сверхбольших інтегральних, схем (СБИС). Однак технологія СБИС і їх структура пред'являє ряд специфічних вимог до алгоритмів, а саме: регулярність, паралельно— потокова організація обчислень, сверхлинейная операційна складність (багаторазове використання кожного елемента вхідних даних), локальність зв'язків обчислень, двумерность простору реалізації обчислень. Ці вимоги зумовлюють необхідність розв'язання проблеми ефективного “ занурення” алгоритму в обчислювальну середу, або, як ще прийнято говорити, — відображення алгоритму в архітектуру обчислювальних коштів. У цей час доведена помилковість раніше широко поширених поглядів, що полягають в тому, що перехід на паралельно— конвейєрні архітектури ЕОМ зажадають лише невеликій модифікації відомих алгоритмів. Виявилося, що параллелилизм і конвейеризация обчислювальних процесів вимагає розробки нових алгоритмів навіть для тих задач, для яких існували добре вивчені і випробувані методи і алгоритми рішення, але орієнтовані на послідовний принцип реалізації. По прогнозах фахівців, в найближче десятиріччя потрібно чекати появи нових концепцій побудови обчислювальних коштів. Основою для прогнозів є результати перспективних досліджень, що проводяться в цей час, зокрема, в області биочипов і органічних перемикаючих елементів. Деякі напрями ставлять своєю метою створення схем у вигляді шарів органічних молекул і плівок з високорозвинений структурою. Це дозволить, на думку дослідників, “ вирощувати” комп'ютери на основі генной інженерії і посилити аналогію між елементами технічних систем і клітками мозку. Тим самим реальні контури придбавають нейрокомпьютери, які імітують інтелектуальні функції біологічних об'єктів, в тому числі людини. Мабуть, молекулярна електроніка стане основою для створення ЕОМ шостого покоління. Все це об'єктивно зумовлює інтенсивні роботи по методах синтезів алгоритмів обробки логічних даних і їх ефективному зануренні в операційну середу бінарних елементів. Очевидно, що бінарні елементи і бінарні дані найбільш повно відповідають один одному в плані представлення і обробки останніх на таких елементах, якщо розглядати їх окремо. Дійсно, покладемо, алгебра логіки над числами (0,1) реалізовується на бінарному елементі повному використанні його операційного ресурсу. Іншими словами, ставиться питання про ефективність, а іноді взагалі можливості реалізації даного алгоритму на такій мережі (структурі). У цьому складається суть занурення алгоритму в структуру.

1.1.2 Математична логіка в криптографії. Криптографія вивчає методи пересилки повідомлень в замаскованому вигляді, при яких тільки намічені відправником одержувачі можуть видалити маскування і прочитати повідомлення. Загальна схема захисту інформації представлена на малюнку 2. Етап кодування від помилок заснований на внесенні в повідомлення надлишку інформації, що передається, достатнього для подолання перешкод на лінії зв'язку. Наприклад, допустимо, передається послідовність символів типу “0” і “1”. При цьому в мережі зв'язку з деякою імовірністю можуть відбуватися помилки прийому сигналу “0 “ замість сигналу “1” або навпаки, тоді кодер на кожний символ aiсообщения передає п'ятьма імпульсами 00000, якщо ai-0 і навпаки. На приймальному кінці послідовність імпульсів, що приймається розбивається по п'ять імпульсів, звана блоками. Якщо в прийнятому блоці міститься 2 і менше за імпульс 0, то приймається рішення про те, що передавався символ ai-1. Таким чином, початкова імовірність помилки буде значно знижена. Більш елегантні методи кодування, які при достатній надійності дозволяють вносити не такий великий надлишок інформації. Для вираження в інформації потрібно ввести деякий алфавіт, з якого буде перебувати повідомлення (кінцеві впорядковані множини з цих символів). Визначимо через А – потужність вибраного алфавіта. Будемо також вважати, що всі множини інформації або, що те ж саме, безліч всіляких повідомлень кінцева. Як міра інформації в повідомленні даної довжини можна взяти Log2от числа всіляких повідомлень звісно. Тоді обсяг інформації, падаючий на один символ алфавіта X=log2a. Далі мається справа зі словами довгої S, тоді усього таких слів буде N=AS (декартова S- міра алфавіта), а отже, кількість інформації в слові Y=Log2N=Log2As=SX.

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

Загальна схема криптосистеми з секретним ключем зображена на малюнку 3. Тут Х – відкритий текст, Y- шифр тексту, K – ключ шифру, R – рандомизирующая послідовність.

Малюнок 1 – Загальна схема криптосистеми

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

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

Приклад 1. Нехай початковий текст має наступний набір символів х=x1, x2. . Нехай d=5 і k=(23154), тоді х=x1x2x3x4x5¦ x6x7x8x9x10; у=x2x3x3x5x4¦x7x6x8x10x9...

Прикладом такої ж простої перестановки є шифр маршрут, що отримав назву Гальмітона.

1.1.3 Математична логіка в програмуванні. Функція одного аргументу - це правило, що ставить відповідність будь-якому значенню, лежачому в області зміни цього аргументу (яка буде і областю визначення цієї функції), іншу величину, лежачу в області значень функції.

Поняття функції було перенесене в мови програмування. У мові програмування, як правило, передбачений ряд вбудованих функцій, наприклад sin, cos, sqrt і т. д. Крім того, програміст має можливість визначати свої власні функції. Вони можуть працювати не тільки з дійсними числами, але і з різними типами даних, що включають звичайне integer (ціле), real (вещест­ венное), boolean (булевское), character (рядкове). Вони можуть також працювати зі структурами. У мовах Паськаль, Алгол=68 і ПЛ/1 є, наприклад, типи records (записи), arrays (масиви), lists (списки), files of records (файли, що складаються із записів), а значеннями функцій можуть бути покажчики цих структур. Все це узгоджене з поняттям області визначення, поза якою функція не визначена. У мовах програмування ця область задана звичайно вказівкою типу даних, який є деякою безліччю величин. Так, в Паськале компілятор повинен стежити за тим, щоб ніяка функція не застосовувалася до величини невідповідного типу, яка могла б вийти за межі області визначення функції.

Функція багатьох аргументів. Тепер треба узагальнити визначення, щоб охопити функції багатьох аргументів. Для цього зберемо n аргументів у впорядкований набір, який будемо розглядати як один аргумент. Візьмемо функцію віднімання diff(x.y). Трактується її як відображення пар < х, у > в цілі числа. У вигляді безлічі впорядкованих пар її можна записати таким чином:

diff = {«5,3 >, 2 >. «6,3 >, 3 >, «4,5 >, -1 >. ..}

Якби замість цього у нас була функція чотирьох аргументів h(х, у, z, w), то використали б відображення, визначене на четвірках < х, у, z, w >. Цей прийом використовується і в програмуванні. Якщо необхідно зменшити кількість аргументів процедури або функції (причому всі вони мають один і той же тип), то в Фортране можна записати ці значення в масив і передати як пара­ метра цей масив, а не окремі значення. У більш загальному випадку (наприклад, в Паськале), коли аргументам дозволяється мати различ­ ние типи, можна передати як параметр запис і зберігати значення у вигляді окремих компонент цього запису. У действительнос­ ти набір, той, що складається з n елементів в математиці відповідає запису в програмуванні. Кожна з її компонент береться з своєї окремої області, як і у разі запису. Єдина відмінність складається в тому, що компонента визначається своїм розташуванням (позицією), а не ім'ям. Реляційна модель даних працює з множинами впорядкованих наборів, які відповідають файлам записів, що зберігаються в машині. Також математична логіка використовується і в інших областях інформатики – це в розробці в області моделювання і автоматизації інтелектуальних процедур – напрям так званого штучного інтелекту.

1. 2 застосування математичної логіки

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

(1)

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

1.2.1 Побудова таблиці істинності. Всяка логічна функцияnпеременних може бути задана таблицею, в лівій частині якій перераховані все2nнаборов значень змінних (тобто всіляких наборів двійкових векторів длиниn), а в правій частині приведені значення функції на цих наборах. Функцію (1) можна представляти через таблицю істинності, причому всі операції над змінними х і у, а саме – це конъюнкция, дизъюнкция, пряма сума, импликация можна замінити готовими значеннями булевой функції./2/ Приклад перетворення функції до чисел 0 і 1 представлений в таблиці 1.

Таблиця 1- Таблиця істинності для функції (1)

х

у

0

0

1

1

1

0

1

0

0

0

1

0

0

0

1

1

0

0

1

0

1

0

0

1

1

0

0

1

1

0

0

1

1

0

1

1

1.2.2 Кон'юнктівная і дизъюнктивная нормальні форми (КНФ і ДНФ)

Діз'юнктівной нормальною формою називається формула, що має вигляд дизъюнкції елементарних конъюнкций.

Конъюнктивной нормальною формою (КНФ) називається формула, що має вигляд конъюнкції елементарних дизъюнкций./2/

f(e1, e2,...,en)= x1e1x2e2.. xnen(.2)

Для приведення функції від двох переменнихf(х, у) до ДНФ потрібно скористатися формулою 2 і таблицею 1.

Кожна булева функція f(x1, x2,...,xn), яка не ідентична нулю, може бути записана у вигляді всіляких булевих виразів типу

f(х, у)=(3)

Кожну булеву функцію f(x1, x2,...,xn), яка не рівна тотожно одиниці, можна представити у вигляді твору всіляких булевих виразів вигляду:

f( 'e1,'e2,...,'e3) = x1e1Ú x2e2Ú ... Ú xnen(4)

Для приведення функції від двох змінних f(х, у) до КНФ потрібно скористатися теоремою 2 і таблицею 1. Отже ДНФ=х&у.

1.2.1 П остроение поліноми Жегалкина. Поліном Жегалкина визначається по формулі:,

гдеki() попарно різні монотонні елементарні конъюнкції./2/

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

Р(х, у) = B0ÅB1xÅB2yÅB3xy (3)

Метод невизначених коефіцієнтів полягає в тому, що послідовної подстановкойх, уи відповідно значень функцій при них в даний поліном, знаходимо коефіцієнтиβ0, β1, β2, β3, β4,β5,β6,β7. Значення переменнихх, уи значення функції представлені в таблиці 4:

Таблиця 2 – значення функції

х

Y

f (х, у)

0

0

0

0

1

0

1

0

0

1

1

1

На основі таблиці 2 складаємо систему рівнянь і знаходимо послідовно коефіцієнти:

f(00)=B0=0

f(01)=B0ÅB2=0; B2=0

f(10)=B0ÅB1=0; B1=0

f(11)=B0ÅB1ÅB2ÅB3=1; B3=1

отже, отримали поліном Жегалкина:

Р(х, у)=х*у (5)

1.2.3 Знаходження похідною від двох змінних. Знаходимо дві похідних.

і;

(5)

(6)

Використовуючи формулу 6 можна побудувати таблицю істинності (таблиця 6) для функції (6), а також таблицю (таблица7) значень похідної (5)

Таблиця 3 – Таблиця істинності для функції (6)

х

у

0

0

1

1

1

1

0

1

0

0

0

1

1

0

0

0

1

1

0

0

1

0

0

1

0

0

1

1

0

0

1

1

0

0

0

1

1

0

1

1

Таблиця 4 – Значення похідної (5)

f(х, у)

f(

0

1

1

0

0

0

1

0

1

Знайдемо похідну по х, у

- (6)

- (7)

Для знаходження диференціала функції (1) спочатку побудуємо таблицю істинності для функції (7) (таблиця 8) і остаточним результатом буде таблиця 9 для функції 6.

Таблиця 5 - Таблиця Істинності для функції (7)

х

у

х&у

0

0

0

1

1

0

1

1

0

1

0

1

0

1

0

0

1

0

0

0

0

1

0

0

1

1

1

0

1

1

0

0

Таблиця 6 – Значення похідної

f(х, у)

f( f(х, у)Å f(0

0

0

0

0

1

0

1

2 ГРАФИ

2.1 Алгоритм Дейкстра

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

Якщо задачу перекласти на мову математики, то вийде, є n вершин і число ребер не менше n-1. Якщо дві вершини сполучені, то вони сполучені тільки одним ребром.

Малюнок 2 – Початковий граф

Вершині А привласнюємо постійний ярлик 0. Далі приписується вершинам суміжні до А (В і I) тимчасові ярлики. Тимчасовий ярлик вершини В рівний 5; тимчасовий ярлик вершини I рівний 4. Вибираємо найменший – це буде I, і робимо його постійним. На малюнку він виділяється жирним шрифтом.

Малюнок 3 – Знаходження першого приєднаного ребра

L(w)=4 далі призначаємо тимчасові ярлики Н і F і вони відповідно будемо рівні 11 і 10, вибираємо мінімальний – це буде F, виділяємо його і робимо його постійним і так далі, поки не дійдемо до G.

Малюнок 4-Резулітірующий граф

В результаті виходить, що найкоротший шлях буде рівний 13 і буде пролягати через А, I, F, 2.2 Жадібний алгоритм

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

Вирішити – цю задачу можна за допомогою Жадібного алгоритму.

Рішенням задачі буде наступний алгоритм. /6/

a. знаходиться ребро з максимальною вагою, з нього складається подграф. Ясно, що таким є ребро з вагою рівним 14, що з'єднує вершини D і би. подальшим кроком знаходиться наступне ребро з максимальною вагою. Це ребро, що з'єднує Е і F (з вагою 13)

в. приєднується ребро, зв'язуюче Е і З (з вагою 12)

м. приєднується ребро, зв'язуюче Е і G (з вагою 11)

д. приєднується ребро, зв'язуюче I і Н (з вагою 8)

е. приєднується ребро, зв'язуюче I і F (з вагою 8)

же. приєднується ребро, зв'язуюче А і В (з вагою 6)

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

Малюнок 5 – Максимальне дерево покриття

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

Вага = 10+7+8+6+6+7=44

2.3 Побудова мінімального кістяка

В одному великому місті є один великий супермаркет (F) і існує безліч доріг до нього. Відомі витрати на проїзд. Потрібно знайти шлях з мінімальними витратами.

Для рішення цієї задачі можна застосувати алгоритм мінімального кістяка./6/

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

Десять міст поставимо у відповідність десяти вершинам графаа, b, з, d, е, f, g, h, i, j,. Мету визначимо F, а початок шляху визначимо

1 етап (H-J), 2 етап: (I-g), 3 етап: (h-i), 4 етап: (I-f), 5 етап: (g-d), 6 етап: (d-b), 7 етап: (b-a), 8 етап: (b-e). Виконання алгоритму завішене, оскільки додавання ребер без утворення петель неможливе. Залишилося скласти ваги ребер, що становлять подграф графа G, який утворить мінімальний кістяк. Ця сума буде наступна: 2+7+4+6+5+7+6+6+4=47. У результаті отримуємо, що існує один шлях до F – це AIF і він рівний = 10. Побудувавши граф (малюнок 6), можна побачити, що існує тільки єдиний шлях від початку нашого шляху до вказаної мети..

Малюнок 6 – Результуючий граф

2.4 Задача Комівояжера

Підприємства (А) в цілях збільшити свій прибуток вирішила відкрити свої філіали в 10 містах (В, З, D, Е, F, G, I, Н, J) і, щоб мінімізувати витрати і зекономити час економістам була поставлена задача знайти мінімальний шлях і так щоб всі міста були пройдені по одному разу.

Оскільки цей граф є Гальмітонов, то одним з способів рішення буде рішення за допомогою Комівояжера./6/

а) В матриці визначаємо мінімальний елемент рядка і віднімаємо його з елементів відповідного рядка. Таким чином, отримуємо нульовий елемент в кожному рядку. Далі визначуваний мінімальний елемент стовпця (не включаючи і нулі) і віднімаємо його з елементів відповідного стовпця (малюнок 2).

A1=

Підраховуємо Kпр=1+1+1+1+1+1=6.

б) Для кожного нульового елемента визначаються коефіцієнти Кi, jпо формулі 2.

(4)

К15=3; К26=3; К34=2; К43=2; К51=3; К62=3; К15=3

Вибираємо найбільший з коефіцієнтів (К1,5=3). Отже, в наш гамильтонов граф буде включено ребро, що з'єднує 1 і 5 вершини з вагою 13. Далі викреслюється рядок і стовпець, відповідні індексу

A2=

Повторюємо крок під буквою а і отримуємо:

K пр=6+3 =9.

A3=

Далі повторюваний крок би:

К21=1; K26=2; K34=2; K43=1; K53=0; K54=0; K62=3.

Наступним ребром, яке буде включене в граф – це K62=3

Повторюємо крок а

A4= A5=

Отримуємо Kпр=11

Повторюємо крок би:

K21=2; K34=0; K36=3; K43=3; K53=0; K54=0

Отримуємо, що буде включене ребро K36=3

A6=

Додаємо до графа ребро K21=2

A7=

В ході рішення задачі були виділені елементи матриці:

К1,5, К6,2, К3,6, К2,1, К5,4, К4,3, яким відповідають ребра (1-5), (6-2), (3-6), (2-1), (5-4), (4-3) з вагою 3, 3, 3, 2.

Довжина маршруту рівна 11, що співпадає з сумою всіх коефіцієнтів приведення: 6 + 3 + 2 = 11. Побудуємо граф (малюнок 8) і, якщо всі вершини сполучилися, отже, задача було вирішена правильно.

Малюнок 8- Результуючий граф

3 Нечіткі множини

Аналізу підлягають ряд сучасних моделей принтерів, що відносяться до класу що не дорого коштують, для цього скористаємося многокритериальним вибором альтернатив на основі нечіткого відношення переваги. /6/

Моделі принтерів, які будуть підлягати аналізу.

A1 – Canon S900; A2 – EPSON Stylus Photo 830; A3 – Hewlett Packard DeskJet 6122; A4 – Lexmark Z65; A5 – Lexmark Z90.

F1 - якість друку (8-10) – чим краще якість друку, тим більше бал. Також визначаються F2, F3, F4, F5, F6, F7, F8.

F2 – швидкість друку (6-10)

F3 – зручність у використанні (8-10)

F4 – аксесуари (7-9)

F5 – виправданість ціни (6-10)

F6 – дизайн (7-10)

F7 – підтримка USB 2.0 (0-1)

F8 – шумность при роботі (6-9)

F9, F10 – чим менше ціна тим більше попит

F9 - вартість картриджів (600-1103)

F10 - вартість принтера (3600-4700)

Розглянемо характеристики кожного принтера по критеріях в задачі.

A1:F1=8, F2=7, F3=8, F4=8, F5=7, F6=9, F7=0, F8=9, F9=600, F10=4700

A2:F1=9, F2=6, F3=8, F4=9, F5=8, F6=7, F7=1, F8=7, F9=900, F10=4700

A3:F1=8, F2=9, F3=10, F4=10, F5=9, F6=9, F7=1, F8=9, F9=1103, F10=3900

A4:F1=8, F2=8, F3=9, F4=7, F5=7, F6=8, F7=1, F8=6, F9=1103, F10=5000

A5:F1=8, F2=6, F3=8, F4=7, F5=8, F6=7, F7=8, F8=6, F9=1100, F10=4700

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

Малюнок 6 – Якість друку Малюнок 7 – Швидкість друку

Малюнок 8 – Зручність у використанні Малюнок 9 – Аксесуари

Малюнок 10 – виправданість ціни Малюнок 11 - Дизайн

Малюнок 12 – Підтримка USB2.0 Малюнок 13 – рівень шуму

Малюнок 14 – Вартість картриджу Малюнок 15 – Вартість принтера

На основі малюнків можна скласти µFn

µF1 = {1/10; 0,8/9; 0,6/8; 0,6/8; 0,6/8}.

µF2 = {0,4/7; 0,2/6; 0,8/9; 0,6/8; 0,2/6}

µF3 = {0,6/8; 0,6/8; 1/10; 0,8/9; 0,6/8}

µF4 = {0,6/8, 0,8/9; 1/10; 0,4/7; 0,4/7}

µF5 = {0,4/7; 0,6/8; 0,8/9; 0,4/7; 0,6/8}

µF6 = {0,8/9; 0,4/7; 0,8/9; 0,6/8; 0,4/7}

µF7 = {0,8/0; 1/1; 1/1; 1/1; 1/1; 0,8 }

µF8 = {0,8/9; 0,6/7; 1/9; 0,4/6; 0,4/6}

µF9 = {1/600; 0,6/900; 0,8/800; 0,2/1103; 0,2/1100}

µF10 = {1/3600; 0,4/4700; 0,6/3900; 0,2/5000, 0,4/4700}

За цими даними складемо матриці нечітких відносин переваги R1,. .., Rn(R5).

1

1,02

0,4

0,4

0,4

0

1

0,2

0,2

0,2

0

0

1

0

0

0

0

0

1

0

0

0

0

0

1

1

0,2

0

0

0,2

0

1

0

0

0

0,4

0,6

1

0,2

0,6

0,2

0,4

0

1

0,4

0

0

0

0

1

R2=

R1=

1

0

0

0

0

0

1

0

0

0

0,4

0,4

1

0,2

0,4

0,2

0,2

0

1

0,2

0

0

0

0

1

1

0

0

0,2

0,2

0,2

1

0

0,4

0,4

0,4

0,2

1

0,6

0,6

0

0

0

1

0

0

0

0

0

1

R3=

R4=

1

0,4

0

0,2

0,4

R5=

0

1

0

0

0

0

0,4

1

0,2

0,4

0

0,2

0

1

0,2

0

0

0

0

1

1

0

0

0

0

R6=

0,2

1

0

0

0,2

0,2

0

1

0

0,2

0,2

0

0

1

0,2

0

0

0

0

1

1

0

0

0

0

R7=

0,2

1

0

0

0,2

0,2

0

1

0

0,2

0,2

0

0

1

0,2

0

0

0

0

1

1

0,2

0

0,4

0,4

R8=

0

1

0

0,2

0,2

0,2

0,4

1

0,6

0,6

0

0

0

1

0

0

0

0

0

1

1

0,6

0,4

0,8

0,6

0

1

0

0,2

0

0

0,2

1

0,4

0,2

0

0

0

1

0

0

0

0

0,2

1

1

0,4

0,2

0,8

0,8

0

1

0

0,4

0,4

0

0,2

1

0,6

0,6

0

0

0

1

0

0

0

0

0

1

R10=

R9=

Будуємо нечітке відношення Q1:

Q1=F1F2... F5, отримуємо матрицю

За експертною оцінкою була визначена міра важливості всіх критеріїв:

W1=0,25; W2=0,19; W3=0,03; W4=0,06; W5=0,095; W6=0,02; W7=0,02; W8=0,015

W9=0,15; W10=0,1

µQ2=1-max{0;0.11;-0.001;0.26;0.337}=0.663

µQ2=1-max{0;-0.11;-0.171;0.09;0.155} =0.845

µQ2=1-max{0;0.001;0.171;0.261;0.326}=0.674

µQ2=1-max{0;-0.26;-0.09;-0.261;0.065}=0.935

µQ2=1-max{0;-0.337;-0.155;-0.326;-0.065}=1

Результуюча безліч недоминируемих альтернатив є перетин множин μQ1н. д. і μQ2н. д.:

μQ1н. д.Ç μQ2н. д.=¦¦(1 1 1 1) Ç ()¦¦=¦¦¦¦

Отже, раціональним потрібно вважати вибір альтернативи ai, що має максимальну міру недоминируемости.

Таким чином, з урахуванням всіх перерахованих критеріїв і їх відносної важливості, найкращим буде вибір принтера Lexmark Z90.

ВИСНОВОК

У курсовій роботі було розглянуто три частини дискретної математики, а саме застосування її на практиці. Розглянуті такі теми як математична логіка, графи, нечіткі множини. У першій частині було розглянуте застосування дискретної математики в інформатиці, а саме застосування її в програмуванні, в побудові схем і в криптографії. Також були розглянуті застосування математичної логіки на практичному прикладі: складена таблиця істинності, знаходження двох похідних, конъюнктивная і дизъюнктивная нормальна функція, а також метод невизначених коефіцієнтів для побудови полінома Жегалкина. У другій частині розглядається застосування теорії графів в економічних задачах, які поділяються на: алгоритм побудови мінімального кістяка, внаслідок чого були визначені мінімальні витрат на проїзд від будинку до супермаркету; Жадібний алгоритм, де була вирішена задача про максимальну завантаженість ліній, які з'єднують нафтопереробні заводи з новим родовищем нафти; Алгоритм Дейкстра – задача про знаходження оптимального шляху, знаходження мінімальних витрат на забезпечення відпочинку своїм співробітникам; Задача Комівояжера – максимізація прибутку і зменшення витрат часу. У третій частині розглянутий метод многокритериального вибору альтернатив на основі нечіткого відношення переваги. Серед 5 принтерів (, що аналізуються Canon S900; EPSON Stylus Photo 830; Hewlett Packard DeskJet 6122; Lexmark Z65; Lexmark Z90) були визначені більш переважний принтер з п'яти запропонованих принтерів, шляхом побудови математичної моделі на основі методу многокритериального вибору. Внаслідок чого був знайдений найбільш переважний принтер (Lexmark Z90).

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ:

1. Комірів А. П., Практикум по введенню в математичну логику.- СПб., 1986 – 300с.

2. Новиков Ф. А., Дискретна математика для програмістів. – СПб., 2002 – 302с.

3. Новиков Ф. А., Введення в крипторафию. – СПб, 1993 – 190 з.

4. Логинов Б. М., Лекції по дискретній математиці. – Калуга, 1993 – 140с.

5. Яблонский С. В., Введення в дискретну математику. - M.: Наука, 1996 – 200с.

6. Методичні вказівки по дискретній математиці – 30с.