Программа определения достижимости населенного пункта в системе односторонних дорог - Программирование, компьютеры и кибернетика курсовая работа

Главная

Программирование, компьютеры и кибернетика
Программа определения достижимости населенного пункта в системе односторонних дорог

Функциональное и эксплуатационное назначение изделия, методологические ограничения. Требования к составу и параметрам технических средств. Описание алгоритма, входные и выходные данные. Стадии и этапы разработки, технико-экономическое обоснование.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.


Программа определения достижимости населенного пункта в системе односторонних дорог. Описание: даны несколько населенных пунктов, соединенных между собой (произвольным образом) односторонними дорогами некоторой длины. Определить, есть ли населенный пункт, из которого можно добраться до каждого из остальных пунктов, проезжая не более 100 км. Отобразить решение графически, выделив цветом найденный результат.
Основанием для разработки программы является задание к курсовому проекту по предмету «Программирование».
оптимальность при использовании физических ресурсов компьютера.
Часто попадаются задачи, в условиях которых заданы некоторые объекты и между некоторыми их парами имеются определенные связи. Если объекты изобразить точками (вершинами), а связи - линиями (ребрами), соединяющими соответствующие пары точек, то получится рисунок, называемый графом. Историю теории графов принято исчислять с 1736 г., когда Эйлер исследовал «задачу о кенигсбергских мостах»: построить в графе циклический путь, проходящий по одному разу через каждое ребро. В середине 19-го века Гамильтон заинтересовался задачей построения циклического пути, проходящего по одному разу через каждую вершину графа. В это же время графы использовали для анализа электрических цепей (Кирхгоф) и химических молекул (Кэли). Развитие современной теории графов относится к 30-м годам 20-го столетия. Они нашли многочисленные применения в электротехнике, электронике, биологии, экономике, программировании и в других областях.
Граф G (рис. 1.1) задается множеством точек (вершин) х 1 , х 2 ,…, х n . (которое обозначается через Х) и множеством линий (ребер) а 1 , а 2 ,…, а m . (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (Х, А). Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом.
Рис. 1.2 Пути и последовательности дуг
Например, если дорога имеет не двух-, а одностороннее движение то направление этого движения будет показано стрелкой.
Если ребра не имеют ориентации, то граф называется неориентированным, (двухстороннее движение).
В ориентированном графе дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин, ее направление предполагается заданным от первой вершины ко второй. Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Так, на рис. 1.2 путями являются последовательности дуг:
а 1 , а 6 , а 5 , а 9 , а 10 , а 6 , а 4 . (3)
Ориентированной цепью (орцепью) называется такой путь, в котором каждая дуга используется не больше одного раза.
Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза. Например, путь (2).
Маршрут есть неориентированный «двойник» пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Таким образом, маршрут есть последовательность ребер a 1 , a 2 ,…, a q , в которой каждое ребро а i , за исключением первого и последнего ребер, связано с ребрами а i-1 и а i+1 своими концевыми вершинами.
В графе, изображенном на рис. 1.2, являются маршрутами; две точки над символом дуги означают, что ее ориентацией пренебрегают, т.е. дуга рассматривается как неориентированное ребро. Также путь или маршрут можно изображать последовательностью вершин. Например, путь (1) будет выглядеть следующем образом: х 2 , х 5 , х 4 , х 3 , х 5 , х 6 . Иногда дугам графа приписываются числа, называемые весом, стоимостью, или длиной этой дуги. В этом случае граф называется графом с взвешенными дугами. А если вес приписывается вершинам графа, то тогда получается граф с взвешенными вершинами. Если в графе веса приписаны и дугам и вершинам, то он называется просто взвешенным.
При рассмотрении пути µ представленного последовательностью дуг (a 1 , a 2 ,…, a q ), за его вес принимается число l(µ), равное сумме весов всех дуг , входящих в µ, т.е.
На этом шаге приводится описание алгоритма Дейкстры.
Напомним, что алгоритм Дейкстры разработан для нахождения кратчайшего пути между заданным исходным узлом и любым другим узлом сети.
В процессе выполнения этого алгоритма при переходе от узла i к следующему узлу j используется специальная процедура пометки ребер. Обозначается через u i  кратчайшее расстояние от исходного узла 1 до узла i, через d ij  - длину ребра (i, j). Тогда для узла j определим метку [u j , следующим образом:
[u j , i] = [u i + d ij , i], d ij >= 0
Метки узлов в алгоритме Дейкстры могут быть двух типов: временные и постоянные. Временная метка впоследствии может быть заменена на другую временную, если будет найден более короткий путь к данному узлу. Когда же станет очевидным, что не существует более короткого пути от исходного узла к данному, статус временной метки изменяется на постоянный.
Вычислительная схема алгоритма состоит из следующих шагов.
Шаг 0 .  Исходному узлу (узел 1) присваивается метка [0, -]. Полагаем i = 1.
Шаг i .  а) Вычисляются временные метки [u i  + d ij , i] для всех узлов j, которые можно достичь непосредственно из узла i и которые не имеют постоянных меток. Если узел j уже имеет метку [u j , k], полученную от другого узла k, и если u i  + d ij  < u j , тогда метка [u j , k] заменяется на [u i  + d ij , i].
b) Если все узлы имеют постоянные метки, процесс вычислений заканчивается. В противном случае выбирается метка [u r , s] с наименьшим значением расстояния u r  среди всех временных меток (если таких меток несколько, то выбор произволен). Полагаем i = r и повторяем шаг i.


Пример. На рисунке 2 показана транспортная сеть, состоящая из пяти городов (расстояния между городами (в километрах) приведены возле соответствующих дуг сети). Необходимо найти кратчайшие расстояния от города 1 (узел 1) до всех остальных четырех городов.
Шаг 0 .  Назначаем узлу 1 постоянную метку [0, -].
Шаг 1 .  Из узла 1 можно достичь узлов 2 и 3. Вычисляем метки для этих узлов, в результате получаем следующую таблицу меток:
2 [0 + 100, 1] = [100, 1] Временная
3 [0 + 30, 1] = [30, 1] <-Временная
Среди узлов 2 и 3 узел 3 имеет наименьшее значение расстояния (u 3  = 30). Поэтому статус метки этого узла изменяется на «постоянная».
Шаг 2 .  Из узла 3 (последнего узла с постоянной меткой) можно попасть в узлы 4 и 5. Получаем следующий список узлов:
4 [30 + 10, 3] = [40, 3] <-Временная
Временный статус метки [40, 3] узла 4 заменяется на постоянный (u 4  = 40).
Шаг 3 . Из узла 4 можно достичь узлов 2 и 5. После вычисления меток получим следующий их список:
2 [40 + 15, 4] = [55, 4] <-Временная
5 [90, 3] или [40 + 50, 4] = [90, 4] Временная
Временная метка [100, 1], полученная узлом 2 на втором шаге, изменена на [55, 4]. Это указывает на то, что найден более короткий путь к этому узлу (проходящий через узел 4). На третьем шаге узел 5 получает две метки с одинаковым значением расстояния u 5  = 90.
Шаг 4 .  Из узла 2 можно перейти только в узел 3, но он уже имеет постоянную метку, которую нельзя изменить. Поэтому на данном шаге получаем такой же список меток, как и на предыдущем шаге, но с единственным изменением: метка узла 2 получает статус постоянной. С временной меткой остается только узел 5, но так как из этого узла нельзя попасть ни в какой другой, процесс вычислений заканчивается.
Алгоритм позволяет проводить вычисления непосредственно по схеме сети, как показано на рисунке 3.
Рис. 3 Вычисления по схеме (в скобках указан номер шага)
Кратчайший маршрут между узлом 1 и любым другим узлом определяется начиная с узла назначения путем прохождения их в обратном направлении с помощью информации, представленной в постоянных метках. Например, для определения кратчайшего маршрута между узлами 1 и 2 получаем такую обратную последовательность узлов: (2) -> [55, 4] -> (4) -> [40, 3] -> (3) -> [30, 1] -> (1).
Таким образом, получаем путь 1->3->4->2 общей длиной 55 километров.
Входными данными для моделируемых устройств, будут являться данные, вводимые пользователем с помощью мыши. Входными данными будет являться:
Программа не является секретной. Предназначена для всех лиц. Используется в качестве решение поставленной задачи.
Для копирования программы с диска или flash-USB на компьютер необходимо:
1. Распаковать RAR-архив, расположенный на диске (flash-USB), в какую-либо папку на жёстком диске компьютера.
На стадии «Техническое задание» проводится постановка задачи, разработка требований к программному изделию, изучение литературы по задаче и оформление документа «Техническое задание».
На стадии «Пояснительная записка» проводится разработка схем алгоритмов для каждого из функциональных модулей, физическое проектирование программного изделия. В заключение данного этапа оформляется документ «Пояснительная записка».
2.9 Технико-экономические показатели разработки
Программное изделие разрабатывается в качестве курсовой работы, поэтому технико-экономические показатели не рассчитываются.
Данный программный продукт должен успешно пройти следующие тесты:
Тест 1. Пользователь рисует на image вершины и рёбра
Тест 2. Вводим данные в таблицу смежности
Тест 3. Выполнение задания, определение достижимости пункта
Программа обладает следующими характеристиками:
оптимальность при использовании физических ресурсов компьютера.
Функциональное и эксплуатационное назначение данного изделия. Требования к составу и параметрам технических средств. Описание алгоритма ГОСТ 28147-89 в режиме гаммирования. Технико-экономические показатели разработки. Интерфейс программного продукта. курсовая работа [1,7 M], добавлен 27.02.2015
Требования к функциональным характеристикам, составу и параметрам технических средств, информационной и программной совместимости. Описание программы: общие сведения, логическая структура. Средства и порядок испытаний. Входные и выходные данные. курсовая работа [6,3 M], добавлен 12.01.2015
Функциональное и эксплуатационное назначение изделия. Перечень требований пользователя к программному изделию. Программные ограничения, совместимость. Требования к параметрам технических средств. Безопасность и секретность, требования к надежности. курсовая работа [574,6 K], добавлен 27.04.2011
Требования к программе, составу и параметрам технических средств. Основные элементы языка программирования. Инструкция на выполнение программы учета клиентов: вызов и загрузка, входные и выходные данные. Расчет себестоимости программного продукта. дипломная работа [3,9 M], добавлен 29.06.2012
Функциональное и эксплуатационное назначение генератора. Требования к составу и параметрам технических средств. Информационная и программная совместимость. Результирующие компоненты изделия. Безопасность и секретность. Удобства эксплуатации, мобильность. курсовая работа [2,1 M], добавлен 07.03.2013
Требования к программному изделию, составу и параметрам технических средств (аппаратные ограничения). Технико-экономическое обоснование целесообразности разработки. Функция, реализующая метод "Северо-западного угла". Модуль Sz, Nst, Venger-m, М1. дипломная работа [1,6 M], добавлен 30.09.2013
Анализ использования разработки, обзор средств программирования и описание языков. Требования к составу и параметрам технических средств. Построение алгоритма и требования к его функциональности. Описание рабочего места на вычислительном центре. дипломная работа [2,6 M], добавлен 19.06.2017
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Программа определения достижимости населенного пункта в системе односторонних дорог курсовая работа. Программирование, компьютеры и кибернетика.
Реферат по теме Понятие, предмет и метод регулирования финансового права
Сроки Контрольных Работ В Школе
Дипломная работа по теме Значение инвестиций в финансовой деятельности предприятия
Арбитражные суды их задачи и место в судебной системе
Реферат: Бустрем, Владимир Владимирович
Реферат На Тему Аномалии Формирования И Прорезывания Зубов
Практическая Работа Маркированные Списки
Реферат На Тему Бронхоэктатическая Болезнь
Реферат: Японский опыт государственного регулирования экономики
Реферат по теме Потенциал Центрального федерального округа РФ
Реферат Профессионально Значимые Качества Педагога Дефектолога
Реферат: The Development Of Constitutional Monarchy In England
Реферат: The Media THe Social Construction Of Gendered
Реферат Про Word
Реферат На Тему Макіавеллі
Реферат: Анодное устройство электролизёра
Доклад: Циолковский Константин Эдуардович
Отчет по практике по теме Анализ деятельности муниципального казенного учреждения 'Координационный центр Активный город'
Күз Кереметі Эссе
Банк Клише Для Оформления Цели Курсового Исследования
Влияние социальных целей и политических ориентиров на деятельность организации - Менеджмент и трудовые отношения контрольная работа
Изменения учетной политики в проекте нового Положения о бухгалтерском учете - Бухгалтерский учет и аудит реферат
Управління діяльністю лізингових установ - Менеджмент и трудовые отношения контрольная работа