Вятський Державний Гуманітарний Університет

Кафедра прикладної математики

Курсова робота з інформатики

Тема: Розробка системи вправ і завдань (алгоритми-програми) з дискретної математики .

Виконав: Студент 4 курсу факультету інформатики

Лепешкін Антон Геннад'евіч

Проверила: Ашихміна Тетяна Вікторівна

Кіров 2004

Зміст.

Зміст. 2

Введення. 3

Глава 1 Теоретичний матеріал. 4

Перебір з поверненням. 4
Пошук даних. 5

Логарифмічний (бінарний) пошук 5
Методи сортування. 6

Сортування злиттями. 6

Швидке сортування Хоар. 6
Графи. 6

Представлення графа в пам'яті комп'ютера 6

досяжність 7
Найкоротші шляху. 8

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

Алгоритм Флойда (найкоротші шляхи між всіма парами вершин). 9

Глава 2 Система завдань і вправ. 9

Класифікація задач. 9

Кімнати музею. 12

Пірат в підземеллі. 13

Диспетчер і міліція. 14

Задача про футболістів. 15

Задача про сім'ї. 16

Метро. 16

Роботи. 17

Вожатий у таборі 20

Єгер. 21

Гра «Знайди друга». 22
Додаток. 22

1 22

2 25

3 27

4 30

5 32

6 32

7 34

8 39

9 41

10 43

Висновок. 45

Література 45

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

1) Розробити власну систему завдань і вправ з дискретної математики.

2) Визначити способи вирішення даних завдань, використовуючи теоретичний матеріал курсу дискретної математики.

3) Скласти алгоритм - програму для кожного завдання, що реалізує вибраний способи рішення.

4) Розробити систему критеріїв класифікації даної системи завдань.
Глава 1 Теоретичний матеріал.

Перебір з поверненням.

Загальна схема
Дано N впорядкованих множин U1 U2 ,..., Un (N - відомо), і потрібнопобудувати вектор А = (а1 а2, ..., аn), де a1 ? U1, a2 ? U2, ..., an ? Un,задовольняє заданому безлічі умов і обмежень.
В алгоритмі перебору вектор А будується покомпонентний ліворуч

направо. Припустимо, що вже знайдені значення першому (до-1)

компонент, A = (a1, a2, ..., a (k-1)),?, ...,?), Тоді заданий безліч

умов обмежує вибір наступного компоненти Аk деяким

безліччю SkCUk. Якщо Sk [] (нічого), ми маємо право вибрати в

як акнайменший елемент Sk іперейти до вибору ^/^ "^ вибори п« я »,
(до 1) компоненти ітак далі. Однак/[+ Д Jfcv при цьому а,якщо умови умови а,, ^ іазтакі, що Sk виявилося порожнім, то ми повертаємося до вибору
(к-1) компоненти, відкидаємоа (k-1) і вибираємо як новий a (k-1) той елемент S (ki), якийбезпосередньо випливає за щойно відкинутим. Може виявитися, що длянового a (k-1) умови завдання допускають непорожній Sk, і тоді ми намагаємосязнову вибрати елемент ак. Якщо неможливо вибрати a (k-1), ми повертаємосяще на крок назад і вибираємо новий елемент а (к-2) і так далі.

Графічне зображення - дерево пошуку. Корінь дерева (0 рівень)є порожній вектор. Його сини суть безліч кандидатів для вибору а1 і,в загальному випадку, вузли k-го рівня є кандидатами на вибір ак приумови, що а1, а2, ..., a (k-1) вибрані так, як вказують предки цихвузлів. Питання про те, чи має завдання рішення, рівносильний питання, єЧи є які-небудь вузли дерева рішеннями. Розшукуючи всі рішення, ми хочемоотримати всі такі вузли.
Рекурсивна схема реалізації алгоритму,procedure Backtrack (Beктop, i);beginif then else begin; for a ? Si do Васкtrаск (вектор | | a, i + l); (| | - додавання довектору компоненти)end; end;
Оцінка тимчасової складності алгоритму. Дана схема реалізації переборупризводить до експоненціальним алгоритмам. Дійсно, Нехай всі рішеннямають довжину N, тоді досліджувати потрібно близько | Si | * | S2 | *...*| SN |вузлів дерева. Якщо значення S; обмежена деякою константою С, тоотримуємо порядку CN вузлів.

Пошук даних.

Логарифмічний (бінарний) пошук

Логарифмічний (бінарний або метод ділення навпіл) пошук даних застосуємодо сортованого безлічі елементів а1 <а2 <... <Ап, розміщенняякого виконано на суміжній пам'яті. Для більшої ефективності пошукуелементів треба, щоб шляху доступу до них стали коротшими, ніж простопослідовний перебір. Найбільш очевидний метод: почати пошук зсереднього елемента, тобто виконати порівняння з елементом а. Результатпорівняння дозволить визначити, в якій половині послідовності а (,а2 ,..., а, 1 + ",,..., ап продовжити пошук,застосовуючи до неї ту ж процедуру, і т.д. Основна ідея бінарного пошукудосить проста, проте «для багатьох хороших програмістів не одна спробанаписати правильну програму закінчилася невдачею ». Щоб доскональнорозібратися в алгоритмі, найкраще представити дані ах <а2 <... <Апу вигляді двійкового дерева порівнянь, яке відповідає бінарного пошуку.
Двійкове дерево називається деревом порівнянь, якщо для будь-якої його вершини
(кореня дерева або кореня піддереві) виконується умова:

(Вершини лівого піддереві)