Список використаної літератури

1. Бондаренко М.Ф. Комп’ютерна дискретна математика.—Харків: «Компанія СМІТ», 2004.— 464с.

2. Горбатов В.А. Основи дискретної математики.— К.: «Наукова думка», 2000. — 312с.

3. Новиков Ф.А. Дискретна математика для програмістів.— Харків: «Ранок», 1998.— 304с.

4. Слєсарєв В.В. Методичні вказівки до виконання курсової роботи з дисципліни «Основи дискретної математики».— Дніпропетровськ: НГУ, 1998.—26 с.

6.

7.

8.

9.

10.

Міністерство освіти і науки України

Дніпропетровський національний гірничий університет

Кафедра системного аналізу і управління

Пояснювальна записка

до курсового проекту

з дисципліни «Дискретна математика»

Виконав

екстерн

Новицький М.О.

Перевірив

проф. Слєсарєв В.В.

м. Дніпропетровськ

2013 Зміст

Вступ……………………………………………………………………....3

Розділ І. Дослідження методів дискретної математики для вирішення

задач, математичні моделі яких представлені в вигляді графів...…4

1.1. Метод Дейкстри для визначення найкоротшого шляху…………..4

1.2. Використання метода Форда-Фалкерсона для обчислення максимальної пропускної здатності графа………………..………...8

1.3. Мережеве планування ……………………………...……………...12

Розділ ІІ. Виконання операцій мінімізації логічних функцій. Розробка скінчених автоматів………………………………………….………17

2.1. Мінімізація логічних функцій……………………………………...17

2.2. Синтез скінченого автомата………………………………………..19

Розділ ІІІ. Дослідження методик представлення операторів інтегрованого середовища Turbo Pascal за допомогою КВ-граматики та нормальної форми Бєкуса…………………………………………26

3.1. Представлення оператора циклу case за допомогою КВ-граматики…………………………………………………….………..26

3.2. Представлення оператора циклу case за допомогою нормальної форми Бєкуса ……………………………….………………………...28

Розділ ІV. Розробка програми формування матриці відношень типу aRb (R≡≤) на мові Turbo Pascal…………………………………….....30

Висновки……………………..……………………………………………37

Список використаної літератури………………….………………….…38

Вступ

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

Основні розділи дискретної математики:

1). Основи теорії множин;

2). Основи теорії графів;

3). Алгебра логіки та кінцеві автомати;

4). Математична логіка і формальні системи;

5). Комбінаторика.

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

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

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

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

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

Розділ І.

Дослідження методів дискретної математики для вирішення задач, математичні моделі яких представлені в вигляді графів.

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

1. Метод Дейкстри для визначення найкоротшого шляху.

Алгоритм Дейкстри – алгоритм на графах, винайдений Едсгером Дейкстрою в 1959 році. Алгоритм полягає у знаходженні найкоротшої відстані від початкової вершини графу до кінцевої. Алгоритм широко застосовується в програмуванні і технологіях, наприклад, його використовує протокол OSPF для усунення кільцевих маршрутів.

Формальний опис алгоритму Дейкстри

Розглянемо алгоритм Дейкстри для визначення найкоротшого шляху (ланцюга) з джерела мережі (початкова вершина) в стік (кінцева вершина).

Крок 1. В алгоритмі Дейкстри вершинам графа присвоюються тимчасові або ж постійні помітки. Починаючи застосовувати алгоритм до конкретної математичної моделі, вважатимемо, що джерелу графа {S} надано постійної помітки (δs=0), а всім іншим вершинам присвоєно тимчасові мітки (d1÷t = ∞).

Крок 2. Переглядаються всі вершини графа, у які входять дуги, що вийшли з вершини, що помічена постійною поміткою {δi}. При цьому нові тимчасові помітки цих вершин розраховуються за формулою:

Із множини отриманих тимчасових поміток обираємо найменшу за величиною і відповідній вершині присвоюємо постійну помітку

Крок 3. Якщо остання зафарбована вершина є стоком, розрахунок припиняється. У протилежному випадку виконується шаг 2-ий і фіксується мінімальна відстань від джерела до стоку.

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

Цей вираз треба досліджувати рекурсивно: рухаючись від стоку до джерела графа.