Основи дискретної математики
Федеральне агентство з освіти
Новомосковський інститут (філія)
Державної освітньої установи вищої професійної освіти
„Український хіміко-технологічний університет імені Д.І. Менделєєва»
T.П. Тюріна, В.І. Ємельянов
Практикум з дискретної математики
Практична робота №1 Вивчення методів сортування даних. 6
1.1 Теоретична частина. 6
1.2 Методи, що використовуються при пошуку та сортуванні. 9
1.2.1 Основні поняття. 9
1.2.3. Оцінки часу виконання. 18
1.2.4 Сортування. 19
1.3. Практична частина. 40
1.3.1 Зміст звіту з практичної роботи. 40
1.3.2 Додаток на Delphi, в якому представлено роботу деяких методів сортування та пошуку. 40
1.3.3 Приклад виконання. 51
1.3.4 Варіанти завдань. 53
1.4 Запитання для самоперевірки. 62
Практична робота № 2 Подання множин у комп'ютері. 64
2.1 Теоретична частина. 64
2.1.1 Безліч та операції з них. 64
2.1.2 Подання множин та відносин у програмах. 67
2.1.4 Подання множин у додатках на Delphi. 82
2.1.5 Характеристичний вектор множини. 83
2.2. Практична частина. 85
2.2.1 Завдання на роботу. 85
2.2.2 Приклади виконання. 86
2.2.3 Варіанти завдань. 90
2.3 Запитання для самоперевірки. 92
Практична робота №3 Елементи теорії графів. 94
3.1 Теоретична частина. 94
3.2. Практична частина. 111
3.2.1 Завдання на роботу. 111
3.2.2 Приклади виконання. 111
3.2.3 Варіант завдань. 117
Практична робота №4 Елементи теоріїмножин та алгебри логіки 122
4.1 Вказівка до виконання. 122
4.2 Завдання на роботу. 122
4.3. Практична частина. 122
4.4 Запитання для самоперевірки. 133
Практична робота №5 Дослідження логічних функцій. 135
5.1 Завдання на роботу. 135
5.2. Практична частина. 135
5.2.1 Приклад виконання. 135
5.2.2 Варіанти завдань. 138
5.3 Запитання для самоперевірки. 140
Практична робота №6 Вивчення методів мінімізації логічних функцій. 142
6.1 Короткі теоретичні відомості. 142
6.2. Практична частина. 144
6.2.1 Завдання на роботу. 144
6.2.2 Приклади виконання. 144
6.3 Запитання для самоперевірки. 147
Практична робота № 7 Моделювання вузлів комп'ютера за допомогою Еxcel. 149
7.1 Теоретична частина. 149
7.2. Практична частина. 152
7.2.1 Схеми порівняння кодів. 153
7.2.2 Дешифратори. 158
7.3 Завдання на роботу. 160
7.4 Запитання для самоперевірки. 164
Список літератури. 165
Практична частина дисципліни адаптована для навчання майбутніх спеціалістів із обробки інформації. Практикум містить додаткові відомості з теорії множин, теорії графів і логіки алгебри, опис практичних робіт, запланованих для виконання студентами в процесі вивчення предмета із залученням засобів Excel, Delphi.
Зміст посібника повністю відповідає вимогам програми дисципліни та належить до практичної частини. Підготовка рукопису викликана необхідністю створення навчального посібника для студентів, оскільки подібні практикуми з дискретної математики відсутні. Практикум містить короткий виклад теорії, яка стосується безпосередньо виконання робіт, варіанти завдань, прикладивиконання. Наприкінці кожного розділу наведено контрольні питання. Студенту пропонується виконати індивідуальні завдання.
Мета роботи: вивчення найвідоміших методів сортування даних та їх використання на прикладах конкретних завдань.
1.1 Теоретична частина
Для дискретного аналізу характерно, що найпростіші, начебто, нічим не примітні завдання може бути предметом серйозного наукового дослідження. Тут ми розглядаємо одне з таких простих завдань, яке часто зустрічається в додатках, називається завданням сортування і досі залишається цікавим.
При розгляді даного кола завдань необхідно заздалегідь вивчити тему «Множини та відносини». Рефлексивне, транзитивне, але антисиметричне відношенняRна множиніAназивається частковим порядком. Частковий порядок важливий у тих ситуаціях, коли хочемо якось охарактеризувати старшинство. Іншими словами, вирішити за яких умов вважатимуться, що один елемент множини перевершує інший.
Приклади часткових систем.
«£» на множині дійсних чисел;
«Ì» на підмножинах універсальної множини;
«…ділить…» на багатьох натуральних чисел.
Безліч із частковим порядком прийнято називати частково впорядкованими множинами (ч. у. м.).
ЯкщоR- відношення часткового порядку на множиніA, то прих