Методика применение теории графов к решению олимпиадных задач по информатике
| дипломные работы, Программирование Объем работы: 59 стр. Год сдачи: 2014 Стоимость: 50 бел рублей (1613 рф рублей, 25 долларов) Просмотров: 716 | Не подходит работа? |
Оглавление
Введение
Заключение
Заказать работу
Введение 4
1. Теоретическая часть 8
1.1 История возникновения теории графов 8
1.2 Основные понятия теории графов 11
1.3 Основные теоремы теории графов 15
1.4 Способы предоставления графов в компьютере 19
1.4.1 Требования к предоставлению графов 19
1.4.2 Матрица смежности 19
1.4.3 Матрица инциденций 20
1.4.4 Списки смежности 21
1.4.5 Массив дуг 21
1.5 Обзор задач теории графов 22
1.6 Определения кратчайшего пути в графах 24
1.6.1 Метод Шимбелла 24
1.6.2 Обзор существующих методов нахожд. кратчайших путей 26
2. Практическая часть 29
2.1 Pascal как язык программирования 29
2.2 Система Pascal ABC 31
2.3 Скрытые графы в олимпиадных задачах 33
2.4 Задача о восьми ферзях 39
2.4.1 Описание алгоритма программы 44
2.4.2 Реализация программы 45
Заключение 49
Список использованных источников 50
Приложение 1 51
Приложение 2 59
1. Теоретическая часть 8
1.1 История возникновения теории графов 8
1.2 Основные понятия теории графов 11
1.3 Основные теоремы теории графов 15
1.4 Способы предоставления графов в компьютере 19
1.4.1 Требования к предоставлению графов 19
1.4.2 Матрица смежности 19
1.4.3 Матрица инциденций 20
1.4.4 Списки смежности 21
1.4.5 Массив дуг 21
1.5 Обзор задач теории графов 22
1.6 Определения кратчайшего пути в графах 24
1.6.1 Метод Шимбелла 24
1.6.2 Обзор существующих методов нахожд. кратчайших путей 26
2. Практическая часть 29
2.1 Pascal как язык программирования 29
2.2 Система Pascal ABC 31
2.3 Скрытые графы в олимпиадных задачах 33
2.4 Задача о восьми ферзях 39
2.4.1 Описание алгоритма программы 44
2.4.2 Реализация программы 45
Заключение 49
Список использованных источников 50
Приложение 1 51
Приложение 2 59
Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждении о Кенигсбергских мостах. Однако эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины прошлого столетия и был сосредоточен главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это благодаря исследованиям электрических цепей, моделей кристаллов и структур молекул. Развитие формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок подавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса. Наиболее знаменитая среди этих задач–проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 года. Никакая проблема не вызывала столь многочисленных и остроумных работ в области теории графов...
В работе были рассмотрены задачи из теории графов, которые уже стали классическими. Особенно часто в практическом программировании возникают вопросы о построении кратчайшего остова графа и нахождении максимального паросочетания. Таким образом, задачи теории графов актуальны, так как могут принести экономию времени и средств на производстве и в быту.
В дипломной работе были рассмотрены основные понятия теории графов, области их применения, определение кратчайшего пути методом Шимбелла, реализованное в Pascal ABC.
В ходе работы были выполнены все поставленные ранее задачи:
1. Изучена история возникновения теории графов.
2. Ознакомлены с основными понятиями и теоремами теории графов.
3. Исследованы способы представления графов в компьютере.
4. Решена задача о восьми ферзях в среде программирования Pascal ABC с использованием теории графов.
Таким образом, можно сказать, что проведенная работа была выполнена в соответствии с поставленными в начале целями и задачами.
В дипломной работе были рассмотрены основные понятия теории графов, области их применения, определение кратчайшего пути методом Шимбелла, реализованное в Pascal ABC.
В ходе работы были выполнены все поставленные ранее задачи:
1. Изучена история возникновения теории графов.
2. Ознакомлены с основными понятиями и теоремами теории графов.
3. Исследованы способы представления графов в компьютере.
4. Решена задача о восьми ферзях в среде программирования Pascal ABC с использованием теории графов.
Таким образом, можно сказать, что проведенная работа была выполнена в соответствии с поставленными в начале целями и задачами.
После офорления заказа Вам будут доступны содержание, введение, список литературы*
*- если автор дал согласие и выложил это описание.