Отчет по лабораторной работе по дисциплине \"Технологии программирования\" на тему \" icon

Отчет по лабораторной работе по дисциплине "Технологии программирования" на тему "


1 чел. помогло.

Смотрите также:
Методические указания по проведению экзамена по 5423 «Учет в непроизводственной сфере» Обсуждены...
Тема: Мультимедиа технологии...
Программа курса ( Syllabus ) по дисциплине «технологии программирования» для студентов...
Методические указания к лабораторной работе №3 по дисциплине «Сетевые информационные технологии»...
Программа обучения студентов ( Syllabus ) по дисциплине Языки и технологии программирования...
Выявление и анализ требований. Требования к программному обеспечению...
Отчет должен состоять из следующих пунктов: Заголовок лабораторной работы (название и цель...
Методические указания к курсовому проекту по дисциплине «Технологии программирования»...
Программа юбилейной конференции «новые технологии в лабораторной медицине»...
Отчет по лабораторной работе №...
Отчет по лабораторной работе №...
Отчет по лабораторной работе №2 По дисциплине...



страницы:   1   2
скачать


Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«Самарский государственный
аэрокосмический университет
имени академика С.П. Королева
(национальный исследовательский университет)»

Факультет информатики

Кафедра программных систем

ОТЧЕТ
по лабораторной работе по дисциплине
"Технологии программирования" на тему
" Автоматизированная система поиска
оптимального пути по заданному критерию "


Выполнили:
студенты гр.6401.
Артамонов Ю. С.,
Ульбеков А. Д.
Руководитель проекта:
доцент каф. ПС Зеленко Л.С.

Дата сдачи:

Оценка:

Самара 2011

РЕФЕРАТ

Пояснительная записка: 58 страниц, 22 рисунка, 17 таблиц, 11. источников, 2 приложения.

^ ТРАНСПОРТНАЯ СЕТЬ, ПЕРЕКРЁСТОК, ДОРОГА, КРИТЕРИЙ ОПТИМАЛЬНОСТИ, ПУТЬ, АЛГОРИТМ ПОИСКА, ГРАФ

Разработан алгоритм, составлена и отлажена программа конструирования участка транспортной сети. Сохранение производится сразу в базу данных, при любом действии с участком ГТС.

Реализованы функции добавления узла, дуги, сотрудника ДПС, дорожных знаков, работа со словарями, удаление составляющих ГТС.

Программа реализована на языке Java в среде Intellij Idea 10 и функционирует под управлением операционных систем Windows или Linux, с установленной платформой Java6.

СОДЕРЖАНИЕ

Введение 5

1 Системотехническая часть 6

i. Описание и анализ предметной области 6

1.1.1 Определение городской транспортной сети 6

1.1.2 Элементы городской транспортной сети 7

1.1.3 Правила дорожного движения 14

1.1.4 Формализация задачи. Теория графов 15

1.1.5 Алгоритм Дейкстры 16

1.1.6 Описание систем – аналогов 17

ii. Постановка задачи 18

iii. Построение структурной схемы программной системы 20

iv. Функциональная спецификация 20

1.4.1 Перечень функций, выполняемых системой 22

1.4.2 Перечень исключительных ситуаций и информационных сообщений 22

v. Разработка структур данных и классов объектов 22

vi. Выбор и обоснование алгоритмов обработки данных 31

vii. Выбор и обоснование комплекса программных средств 32

1.7.1 Выбор операционной системы 32

1.7.2 Выбор языка программирования 34

1.7.3 Выбор СУБД 34

2 Конструкторско-технологическая часть 36

2.1 Разработка и описание интерфейса пользователя 36

2.2 Разработка и описание пользовательского меню 36

2.2.1 Разработка панели инструментов 37

2.2.2 Описание контрольного примера 38

2.3 Реализация классов и структур данных 40

2.4 Разработка и описание модулей 41

2.5 Выбор и обоснование комплексно-технических средств 41

2.5.1 Расчет требуемых ресурсов 41

ЗАКЛЮЧЕНИЕ 45

^ СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 46

Приложение А 47

Приложение Б 49

Б.1 Введение 49

Б.2 Необходимые условия применения 49

Б.3 Подготовка к работе 49

Б.4 Описание операций 49

Введение


Вследствие растущей загруженности автомагистралей, возрастающей интенсивности автомобильных перевозок в условиях современных мегаполисов остро ощущается необходимость регулирования транспортных потоков. Для обеспечения комфорта участникам дорожного движения и их информирования о текущем состоянии транспортной сети, для снижения материальных и финансовых издержек были созданы системы управления дорожным движением, получившие название Intelligent Transportation Systems (Интеллектуальные Транспортные Системы - ИТС), которые уже долгое время успешно функционируют во всем мире.

В системе управления городской транспортной сетью также широко применяются ГИС. В настоящее время существуют ГИС, такие как OpenStreetMap, Marble, 2Gis, Navitel. Хотя приведённые системы более функциональны, разработка данной системы полезна для образовательной деятельности.

Для решения задач оптимизации в геоинформационных системах (ГИС) находит активное применение теория графов. Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.

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

Проектирование системы производится по технологии быстрой разработки приложений (RAD), которая поддерживается методологией структурного проектирования и включает элементы объектно-ориентированного проектирования и анализа предметной области [1].
^

1Системотехническая часть

      1. Описание и анализ предметной области


Проектирование любой программной системы начинается с описания и анализа предметной области.

Интенсивное развитие информационных технологий с каждым годом делает разработку информационных систем (ИС) одним из определяющих факторов успеха в каждой области бизнеса, промышленности, также и в сфере научных исследований. Основной компонентой любой информационной системы является предметная область. Под предметной областью понимают ту часть реального мира, которая имеет существенное значение или непосредственное отношение к процессу функционирования программы. Предметная область включает в себя только те объекты и взаимосвязи между ними, которые необходимы для описания требований и условий решения некоторой задачи [2].
      1. ^

        Определение городской транспортной сети


Транспортной сетью (ТС) называется совокупность транспортных связей, в системе которых осуществляются городские пассажирские и грузовые перевозки. Городскую транспортную сеть (ГТС) образует совокупность улиц и транспортных проездов, обслуживаемых различными видами городского транспорта, а также подземные, наземные и надземные транспортные линии, связанные с уличной сетью лишь частично или не связанные с ней вообще (городские железные дороги, эстакадные автомагистрали, метрополитен, монорельсовые дроги). Транспортная сеть неразрывно связана с обслуживаемым городом, его населением, застройкой, рельефом местности, климатическими условиями. В общем, виде ТС - это некоторая неявная функция планировочных, социально-экономических, демографических, климатических и других характеристик города. В общем виде данная функция может быть предоставлена имитационной моделью ТС. Особенности формирования ТС многих городов связаны с их историческим развитием. ТС городов современной застройки проектируется с учетом комплексного решения градостроительных и транспортных проблем [3].
      1. ^

        Элементы городской транспортной сети


В состав ГТС входят множество элементов, притом они могут быть одушевлёнными и неодушевлёнными.

Дороги

Основным элементом ГТС являются дороги, которые служат в качестве транспортных связей. Дорога - путь сообщения для передвижения людей и транспорта, составная часть дорожной инфраструктуры. Согласно Федеральному закону от 10.12.1995 № 196-ФЗ «О безопасности дорожного движения», дорога — обустроенная или приспособленная и используемая для движения транспортных средств полоса земли либо поверхность искусственного сооружения. Дорога включает в себя одну или несколько проезжих частей, а также трамвайные пути, тротуары, обочины и разделительные полосы при их наличии [4].

По направлению движения различают дороги с односторонним движением и дороги с двусторонним движением. Также различаются по ограничению скоростного режима в зависимости от знаков и местонахождения (город, загород, автомагистраль). Существует множество типов покрытия дорог, такие как асфальт, грунтовка и т.д. Пример дороги приведён на рисунке 1.



Рисунок 1 – Пример городской автодороги

Перекрёстки

Перекрёсток — пересечение дорог или полос движения на одном уровне. В соответствии с Правилами дорожного движения Российской Федерации перекрёсток определяется как «место пересечения, примыкания или разветвления дорог на одном уровне, ограниченное воображаемыми линиями, соединяющими соответственно противоположные, наиболее удаленные от центра перекрёстка начала закруглений проезжих частей». Встречаются равнозначные и неравнозначные перекрёстки, с круговым движением и с примыкающей дорогой, управляемые (регулируемые) и неуправляемые (нерегулируемые) [3]. Виды перекрёстков приведены на рисунке 2. На рисунке 3 приведён пример кругового перекрёстка.



Рисунок 2 – Виды перекрёстков



Рисунок 3 – Пример перекрёстка

^ Транспортные средства

Транспорт — совокупность средств, предназначенных для перемещения людей, грузов из одного места в другое. Транспорт делится на три категории: транспорт общего пользования, транспорт специального пользования и личный или индивидуальный транспорт. Транспорт общего пользования обслуживает торговлю (перевозит товары) и население (пассажирские перевозки). Транспорт специального пользования — внутрипроизводственный и внутриведомственный транспорт. Наконец, личный транспорт — это легковые автомобили, велосипеды, яхты, частные самолёты. Персональный автоматический транспорт образует новую категорию, так как соединяет в себе черты городского общественного транспорта и личного автотранспорта [3].

Автомобильный транспорт сейчас самый распространённый вид транспорта. Автомобильный транспорт моложе железнодорожного и водного, первые автомобили появились в самом конце XIX века. После Второй мировой войны автомобильный транспорт начал составлять конкуренцию железной дороге. Преимущества автомобильного транспорта - маневренность, гибкость, скорость. Грузовые автомобили перевозят ныне практически все виды грузов, но даже на больших расстояниях (до 5 и более тыс. км) автопоезда (грузовик-тягач и прицеп или полуприцеп) успешно конкурируют с железной дорогой при перевозке ценных грузов, для которых критична скорость доставки, например, скоропортящихся продуктов [3].

Абсолютное большинство ныне существующих автомобилей — автомобили индивидуального пользования (легковые). Их используют, как правило, для поездок на расстояния до двухсот километров. На рисунке 4 изображены средства передвижения, различающиеся по типу, массе и назначению.



Рисунок 4 – Средства передвижения

^ Дорожные знаки

Дорожный знак — техническое средство безопасности дорожного движения, стандартизированный графический рисунок, устанавливаемый у дороги для сообщения определённой информации участникам дорожного движения. С 1 января 2006 года в России вступили в силу новые стандарты на дорожные знаки, светофоры и разметку. На дорогах, в связи с этим, появились 24 новых и 18 изменённых знаков. Все они соответствуют конвенции ООН о дорожных знаках и сигналах, а также последним европейским стандартам [9]. Некоторые дорожные знаки приведены на рисунке 5.

В данной работе особое значение будет иметь знак ограничения скорости, используемый для контроля скоростного режима, изображение приведено на рисунке 6.

Светофоры

Светофор — устройство оптической сигнализации, предназначенное для регулирования движения людей, велосипедов, автомобилей и иных участников дорожного движения, поездов железной дороги и метрополитена, речных и морских судов [3].

^ Виды светофоров

Существует несколько типов светофоров, рассмотрим некоторые из них.




Рисунок 5 - Дорожные знаки



Рисунок 6 – Знак ограничения скорости

^ Автомобильные светофоры. Наиболее распространены светофоры с сигналами (обычно круглыми) трёх цветов: красного, жёлтого и зелёного. В некоторых странах в том числе и в России вместо жёлтого используется оранжевый цвет. Сигналы могут быть расположены как вертикально (при этом красный сигнал всегда располагается сверху, а зелёный — снизу), так и горизонтально (при этом красный сигнал всегда располагается слева, а зелёный — справа). При отсутствии других, специальных светофоров они регулируют движение всех видов транспортных средств и пешеходов (но на перекрёстке может быть бессветофорное движение последних). Иногда сигналы светофора дополняют специальным табло обратного отсчёта времени, которое показывает сколько времени ещё будет гореть сигнал. Чаще всего табло обратного отсчёта делают для зелёного сигнала светофора, но в ряде случаев табло отображает и оставшееся время красного сигнала. Практически повсеместно красный сигнал светофора запрещает движение, жёлтый запрещает выезд на охраняемый светофором участок, но допускает завершение его проезда, а зелёный — разрешает движение. Распространено, но не повсеместно использование сочетания красного и жёлтого сигналов, обозначающее предстоящее включение зелёного сигнала. Иногда зелёный сигнал включается сразу после красного без промежуточного жёлтого, но не наоборот. Детали применения сигналов различаются в зависимости от принятых в той или иной стране Правил дорожного движения. Существуют светофоры из двух секций — красной и зелёной. Такие светофоры обычно устанавливаются на пунктах, где пропуск автомобилей производится в индивидуальном порядке, например, на пограничных переходах, при въезде или выезде с автостоянки, охраняемой территории и т. п. Пример светофора на рисунке 7.



Рисунок 7 – Светофор

^ Стрелки и стрелочные секции. На светофорах могут быть дополнительные секции в виде стрелок или контуров стрелок, регулирующие движение в том или ином направлении. Правила (в странах бывшего СССР) таковы:

Контурные стрелки на красном (жёлтом, зелёном) фоне — это обычный светофор, действующий только в заданном направлении.

Сплошная зелёная стрелка на чёрном фоне разрешает проезд, но не даёт преимущества при разъезде.

Светофор с мигающим красным сигналом. Красный мигающий сигнал (как правило, на светофорах с мигающей одной или попеременно мигающими двумя красными секциями) используется для ограждения пересечений с трамвайными линиями при приближении трамвая, мостов при разводке, участков дорог вблизи взлётно-посадочных полос аэропортов при взлёте и посадке самолётов на опасной высоте. Эти светофоры аналогичны тем, что используются на железнодорожных переездах.

^ Светофор, устанавливаемый на железнодорожных переездах.

Реверсивный светофор. Для регулирования движения по полосам проезжей части (особенно там, где возможно реверсивное движение), применяют специальные светофоры контроля полосы (реверсивные) [5].

^ Светофоры для маршрутных транспортных средств. Для регулирования движения маршрутных транспортных средств (трамваев, автобусов, троллейбусов) используют специальные светофоры, вид которых отличается от страны к стране.

  • Светофор для пешеходов.

  • Светофор для велосипедов.

  • Трамвайный светофор.

Субъекты

Водитель — человек, управляющий своим транспортным средством.

Пешеход — участник дорожного движения, находящийся вне транспортного средства. К пешеходам приравниваются лица, передвигающиеся в инвалидных колясках без двигателя, ведущие велосипед, мопед, мотоцикл, везущие санки, тележку, детскую или инвалидную коляску. Правилами дорожного движения определяются права и обязанности пешеходов. В дорожной инфраструктуре для пешеходов предназначены пешеходные дорожки (тротуары), регулируемые и нерегулируемые наземные пешеходные переходы, а также надземные и подземные пешеходные переходы. Пешеходы должны двигаться по тротуарам или пешеходным дорожкам, а при их отсутствии — по обочинам. Пешеходы, перевозящие или переносящие громоздкие предметы, а также лица, передвигающиеся в инвалидных колясках без двигателя, могут двигаться по краю проезжей части, если их движение по тротуарам или обочинам создаёт помехи для других пешеходов. При отсутствии тротуаров, пешеходных дорожек или обочин, а также в случае невозможности двигаться по ним пешеходы могут двигаться по велосипедной дорожке или идти в один ряд по краю проезжей части (на дорогах с разделительной полосой — по внешнему краю проезжей части) [3].

^ Сотрудник Дорожно-патрульной службы (ДПС). Дорожно-патрульная служба — структурное подразделение Государственной инспекции безопасности дорожного движения Министерства внутренних дел Российской Федерации, входящее в состав полиции Российской Федерации. Появилось в 1918 году. Основными задачами ДПС являются: сохранение жизни, здоровья и имущества участников дорожного движения, защита их законных прав и интересов, а также интересов общества и государства; обеспечение безопасного и бесперебойного движения транспортных средств; предупреждение и пресечение преступлений и административных правонарушений в области дорожного движения. Выполнение других обязанностей, возложенных на подразделения милиции общественной безопасности [6]. На рисунке 9 изображён контроль дорожного движения сотрудником ДПС.



Рисунок 9 – Сотрудник ДПС
      1. ^

        Правила дорожного движения


Правила дорожного движения (сокращенно ПДД) — свод правил, регулирующих обязанности водителей транспортных средств и пешеходов, а также технические требования, предъявляемые к транспортным средствам для обеспечения безопасности дорожного движения.

История современных правил дорожного движения берёт своё начало в Лондоне. 10 декабря 1868 года на площади перед Парламентом был установлен механический железнодорожный семафор с цветным диском. Его изобретатель — Дж. П. Найт — был специалистом по железнодорожным семафорам. Устройство управлялось вручную и имело два семафорных крыла. Крылья могли занимать разные положения: горизонтальное — сигнал «стоп»; и опущенные под углом 45 градусов — можно двигаться с осторожностью. С наступлением темноты включали вращающийся газовый фонарь, который подавал сигналы красным и зелёным светом. К семафору был приставлен слуга в ливрее, в обязанности которого входило поднимать и опускать стрелу и поворачивать фонарь. Однако техническая реализация устройства оказалась неудачной: скрежет цепи подъёмного механизма был настолько сильным, что проезжавшие лошади шарахались и вставали на дыбы. Не проработав и месяца, 2 января 1869 года семафор взорвался, находившийся при нём полицейский был ранен.

Прототипами современных дорожных знаков можно считать таблички, на которых указывалось направление движения к населённому пункту и расстояние до него. Решение о создании единых европейских правил дорожного движения было принято в 1909 году на всемирной конференции в Париже, ввиду увеличения числа автомобилей, роста скоростей и интенсивности движения на городских улицах. Следующим важным шагом стало принятие «Конвенции о введении единообразия в сигнализацию на дорогах» в 1931 году в Женеве, на Конференции по дорожному движению, в которой среди прочих стран принял участие и Советский Союз [3].
      1. ^

        Формализация задачи. Теория графов


Для решения задачи можно представить участок ГТС как граф, узлами которого являются перекрёстки, а дугами — улицы (рисунок 10).



Рисунок 10 – Представление участка в виде графа

^ Теория графов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V,E), где V есть подмножество любого счётного множества, а E - подмножество V×V. Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, перекрёстки, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов [7].

^ Основные термины теории графов

Граф — базовое понятие. Включает множество вершин и множество рёбер, являющееся подмножеством декартова квадрата множества вершин (то есть каждое ребро соединяет ровно две вершины). Участок ГТС будет представлен в виде графа.

^ Вершина, Узел — базовое понятие: точка, где могут сходиться/выходить рёбра и/или дуги. Множество вершин графа G обозначается V(G). Перекрёсток - вершина.

^ Ребро графа — базовое понятие. Ребро соединяет две вершины графа. Дорога – ребро.

Дуга — это ориентированное ребро.

Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра).

^ Вес ребра — значение, поставленное в соответствие данному ребру взвешенного графа. Обычно, вес - вещественное число, в таком случае его можно интерпретировать как «длину» ребра. Длина дороги — вес ребра [7].
      1. ^

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


Алгоритм Дейкстры (Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях.

Каждой вершине из V сопоставим метку - минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово - на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противно случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма [8].
      1. ^

        Описание систем – аналогов


В настоящее время существует немало систем, реализующих процесс нахождения пути и навигации, такие как 2Gis, Navitel, Open Street Map. Интерфейс программы Open Street Map приведён на рисунке 11, программы 2ГИС – на рисунке 12.

Программа имеет множество функций: масштабирование, специализированные слои, метки, пути, отображение погоды, улиц, зданий, поиск объектов, навигация и т.д.



Рисунок 11 - Интерфейс Open Street Map


Рисунок 12 – Интерфейс программы 2ГИС
      1. ^

        Постановка задачи


В рамках поставленной задачи необходимо разработать программную систему, позволяющую моделировать нахождение оптимального пути на участке ГТС.

Пользователь должен иметь возможность загрузить уже имеющийся участок ГТС, или составить новый с помощью специального редактора, встроенного в разрабатываемую систему. При составлении участка ГТС пользователь должен использовать следующие шаблоны: узлы (перекрестки), дуги (дороги), знаки запрещения движения (не более одного на дугу), знаки ограничения скорости (в соответствии с правилами дорожного движения ПДД), сотрудников ДПС, светофоры. При этом данным объектам необходимо задавать некоторые характеристики.

Каждый инструмент должен иметь свои характеристики:

Ребро: тип покрытия, длина (положительное число) и имя, наличие сотрудника ДПС, поставить на дугу знак ограничения скорости, знак запрещения движения.

^ Сотрудник ДПС: необходимо задать коэффициент строгости (положительное число).

Узел: К узлу можно привязать не более одного светофора и сотрудника ДПС. Также узлу необходимо задать время его прохождения. Пользователю необходимо задать начальную фазу светофора (красный, зеленый), длительность зеленой и красной фазы (положительное число).

После выбора участка ГТС пользователь должен выбрать объекты, участвующие в движении (автомобиль и водитель), а также выбрать критерии нахождения оптимального пути.

К характеристикам автомобиля относятся: максимальная скорость движения (натуральное число), объем бака (натуральное число), расход топлива на условную единицу пути (положительное число), тип топлива. Пользователь может указать также марку и модель автомобиля.

К характеристикам водителя относятся: имя, тип (нарушитель, добропорядочный).

Все данные и настройки при составлении участка ГТС должны храниться в базе данных (БД). В системе должны вестись следующие справочники: типов топлива, названий улиц, типов сотрудника ДПС, названий улиц, типов дорожного покрытия, типов дорожных знаков. Необходимо предусмотреть целостность таблиц БД.

При возникновении вопросов у пользователя должна иметься возможность обратиться к справочной информации по системе.

Таким образом, система моделирования должна выполнять следующие функции:

  1. настройка параметров системы;

  2. составление участка ГТС;

  3. сохранение участка ГТС в базу данных;

  4. загрузка участка ГТС из базы данных;

  5. работа с редактором участка ГТС:

  6. добавление узла, дуги, знака, сотрудника ДПС, светофора;

  7. удаление узла, дуги, знака, сотрудника ДПС, светофора;

  8. изменение характеристик узла, дуги, знака, сотрудника ДПС, светофора;

  9. ведение справочников БД:

  • добавление;

  • редактирование;

  • удаление;

  1. ведение таблиц БД;

  2. проверка целостности БД.

  3. выдача справочной информации.
      1. ^

        Построение структурной схемы программной системы


На основании проведенного выше анализа предметной области формируются общие требования к функциям, которые должна выполнять система. Проектируемую систему разобьем на подсистемы и определим взаимосвязи между ними.

Система – это совокупность объектов, компонентов или элементов произвольной природы, образующих некоторую целостность. Структура системы – это устойчивая во времени совокупность взаимосвязей между ее элементами или компонентами. Структура системы предполагает вложенность элементов одной системы в другую. Более мелкая система – это подсистема. Проектируемую систему разобьем на подсистемы и определим взаимосвязи между ними.

В проектируемую систему входят пять подсистем:

  1. ^ Модуль графического интерфейса — обеспечивает взаимодействие пользователя с системой, отображение данных и визуализацию процессов.

  2. Подсистема моделирования — служит для вычисления оптимального пути по заданному критерию.

  3. Ядро — служит для коммуникации с БД.

  4. Сущности БД — набор объектов и метаинформации для ORM.

  5. Справочная подсистема, которая предназначена для вывода справочной информации о системе, разработчиках, а также руководства пользователя системой.

Структурная схема автоматизированной системы поиска оптимального пути по заданному критерию приведена на рисунке 13.
      1. ^

        Функциональная спецификация


Разработка П/С начинается с формулировки требований, в которой, исходя из пожеланий к ней, должен быть получен документ, в котором должно быть достаточно точно определены требования к разработчикам. Этот документ называется спецификацией требований. Он играет роль точной постановки задачи и включает две составные части:

  1. спецификация качества на П/С

  2. функциональная спецификация

Разработка спецификации качества предшествует функциональной спецификации. В нее включаются требования к технологическим процессам, перечисляющиеся основными показателями качества П/С (надежность, функциональность, эффективность).




Рисунок 13 – Структурная схема системы

^ Функциональная спецификация включает в себя описание всех функций, которые должна выполнять П/С с указанием обрабатываемых результирующих данных. Она строится на естественном языке, но может включать в себя и математические модели, записанные на формализованном языке и диаграммы, выполненные в том или ином стандарте.

Функциональная спецификация:

  1. описание внешней информационной среды

  2. определение функций, определенных на множестве состояний этой информационной среды.

  3. описание исключительных ситуаций, которые могут возникнуть при выполнении функций П/С и реакции на эти ситуации.

^ Функциональная спецификация служит уточнением структурной схемы, где определяются все функции, которые выполняет система (с разбивкой на подсистемы), исключительные ситуации, возникающие в каждой из подсистем, а также и информационная среда (входные и выходные параметры) каждой из функций всех подсистем.
      1. ^

        Перечень функций, выполняемых системой


При детальном проектировании вводятся обозначения для всех функций, специфицируются все входные данные и результаты каждой определенной функции, включая указание их типов и задания всех ограничений, которые должны удовлетворять эти данные и результаты. В таблице 1 приведен перечень функций, выполняемых системой.
      1. ^

        Перечень исключительных ситуаций и информационных сообщений


В рамках функциональной спецификации необходимо указать исключительные ситуации, возникновение которых возможно в процессе работы программы.

Исключительная ситуация - это наиболее существенная с точки зрения пользователя ситуация, при которой П/С не может нормально выполнить ту или иную функцию.

Перечень исключительных ситуаций представлен в таблице 2.
      1. ^

        Разработка структур данных и классов объектов


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

Структура данных «класс», представляющая собой объектный тип данных, внешне похожа на типы данных процедурно-ориентированных языков. При этом есть возможность сокрытия внутреннего устройства объекта и его поведения. Такая возможность называется инкапсуляцией. Инкапсуляция — свойство языка программирования, позволяющее пользователю не задумываться о сложности реализации используемого программного компонента (то, что у него внутри), а взаимодействовать с ним посредством предоставляемого интерфейса (публичных методов и членов), а также объединить и защитить жизненно важные для компонента данные. При этом

Название
подсистемы

Название
функции

Информационная среда

Входные данные

Выходные данные

Назначение
(наименование)

Тип,
ограничения

Назначение
(наименование)

Тип,
ограничения

1 Справочная

1.1 Выдать сведения о разработчиках

Сведения о разработчиках системы (ФИО, номер группы)

Текст
(МЕМО)

Визуальное отображение информации

 

1.2 Выдать сведения о системе

Файл справки

Текстовый
(*.HTML)

Код ошибки

целое

1.3 Выдать руководство пользователя

Файл руководства

Текстовый
(*.HTML)

2 Модуль графического интерфейса

2.1 Загрузить участок ГТС из БД

Наименование участка ГТС

Строка

Модель участка ГТС

Структура объектов

Код ошибки:

Целое

2.2 Сохранить участок ГТС в БД

Модель участка ГТС

Структура объектов

Карта ГТС

Структура определяется в ходе проектирования

Код ошибки

Целое

2.3 Добавить перекресток

Координаты перекрестка

Целые числа

Объект «Узел»

Структура определяется в ходе проектирования

Код ошибки

Целое

2.4 Добавить улицу

Начальный и конечный перекрестки

Координаты узлов

Объект «Ребро»

Структура определяется в ходе проектирования

Код ошибки

Целое

2.5 Добавить дорожный знак на улицу

Тип дорожного знака

Объект из библиотеки

Объект «Ребро»

Структура определяется в ходе проектирования

Сотрудник ДПС

Объект

2.6 Добавить сотрудника ГАИ на перекресток

Координаты перекрестка

Целые числа

Код ошибки

Целое

2.7 Удалить перекресток

Выбранный перекресток

Объект

ГТС

Структура определяется в ходе проектирования

Код ошибки

Целое

2.8 Изменение названия улицы

Название улицы

Строка

Улица

Объект

Код ошибки

Целое

2.9 Удалить улицу

Выбранная улица

Объект

ГТС

Структура определяется в ходе проектирования

Код ошибки

Целое

2.10 Удалить дорожный знак с улицы

Улица, дорожный знак

Объекты

ГТС

Структура определяется в ходе проектирования

2.11 Удалить сотрудника ДПС с перекрестка

Перекресток

Объект

Код ошибки

Целое

3 Подсистема моделирования

3.1 Начать поиск маршрута

Критерий поиска

  • по времени;

  • по стоимости;

  • по длине.

Оптимальный путь

Список вершин графа

3.2 Выбрать критерий поиска

Список критериев

  • по времени;

  • по стоимости;

  • по длине.

Критерий поиска

Перечислимый тип

3.3 Выбрать начальную точку пути

ГТС

Объект

Начальный узел

Объект

3.4 Выбрать конечную точку пути

Конечный узел

Объект

3.5 Выбор типа водителя

Список водителей

Таблица водителей из БД

Водитель

Объект

3.6 Выбор автомобиля

Список автомобилей из БД

Таблица автомобилей из БД

Автомобиль

Объект

4 Ядро

4.1 Поиск по справочникам в БД

Список критериев поиска

  • по имени;

  • по id;

  • по типу

Данные об объекте

Объект

Код ошибки

Целое

5 Сущности БД

5.1 Обновить данные об объекте в БД

Данные об объекте

Строка, числовые данные

Измененный объект в БД

Объект

5.2 Создать объект в БД

Данные об объекте

Строки, числовые данные

Объект в БД

Объект

5.3 Удалить объект из БД

Id объекта

Ключ

Измененная таблица в БД

Структура БД

Название
подсистемы

Название
исключительной ситуации

Реакция системы

1 Справочная

1.1 Отсутствует файл справки

Выдача сообщения

2 Модуль графического интерфейса

2.1 Запись в БД с заданным именем не существует

Выдача сообщения

2.2 Запись в БД с заданным именем уже существует

Выдача сообщения

2.3 Некорректные координаты для нового перекрестка

Выдача сообщения

2.4 Не выбран начальный или конечный перекресток для новой улицы

Выдача сообщения

3 Подсистема моделирования

3.1 Не выбран критерий поиска пути

Выдача сообщения

3.2 Не выбрана начальная точка пути

Выдача сообщения

3.3 Не выбрана конечная точка пути

Выдача сообщения

3.4 Не выбран водитель

Выдача сообщения

3.5 Не выбран автомобиль

Выдача сообщения

4.Ядро

4.1 Не найден выбранный тип справочника

Выдача сообщения, запись в лог

5. Сущности БД

5.1 Не найден объект в БД

Выдача сообщения

5.2 Такой объект в БД уже есть

Выдача сообщения

5.3 Нарушение целостности, удаление сущности, на которую ссылаются другие

Выдача сообщения, запись в лог

Продолжение таблицы 2




5.4 Дублирующиеся записи для поля с уникальным ключом

Выдача сообщения, запись в лог

пользователю предоставляется только спецификация объекта.

Наличие инкапсуляции не означает объектной ориентированности языка программирования — для этого требуется наличие наследования. Наследование — механизм объектно-ориентированного программирования (наряду с инкапсуляцией, полиморфизмом и абстракцией), позволяющий описать новый класс на основе уже существующего (родительского), при этом свойства и функциональность родительского класса заимствуются новым классом. В нашей системе выделяются классы BaseEntity и PersonEntity как базовые, BaseEntity – базовый класс всех сущностей, PersonEntity – сущности хранящие информацию о людях.

UML (англ.Unified Modeling Language– унифицированный язык моделирования) – язык графического описания для объектного моделирования в области разработки программного обеспечения. UML является языком широкого профиля, это открытый стандарт, использующий графические обозначения для создания абстрактной модели системы, называемой UML-моделью. UML был создан для определения, визуализации, проектирования и документирования в основном программных систем. UML не является языком программирования, но в средствах выполнения UML-моделей как интерпретируемого кода возможна кодогенерация.

В UML диаграмма классов описывает структуру системы, показывая её классы, их атрибуты и операторы, а также взаимосвязи этих классов. На рисунке 14 представлена UML-диаграмма классов.

Таблица 3 – Описание класса «Базовая сущность»

Имя поля

Тип

Описание

идентификатор

Длинное целое

Идентификатор

версия

Длинное целое

Номер версии

Таблица 4 – Описание класса «Карта ГТС»

Имя поля

Тип

Описание

название

Строка




перекрестки

Набор объектов типа «Узел»




ширина

Целое




высота

Целое




Таблица 5 – Описание класса «Узел»

Имя поля

Тип

Описание

координата по вертикали

Целое

Координата узла на карте

координата по горизонтали

Целое

Координата узла на карте

карта

Объект «Карта ГИС»




светофор

Объект «Светофор»




полицейский

Объект «Полицейский»




начала улиц

Набор объектов "Ребро"




окончания улиц

Набор объектов "Ребро"




Таблица 6 – Описание класса «Ребро»

Имя поля

Тип

Описание

улица

Объект «Улица»

Улица

покрытие

Объект «Покрытие»

Покрытие

длина

Действительное




цвет

Строка




полицейский

Объект «Полицейский»




начальный узел

Объект «Узел»




конечный узел

Объект «Узел»




список дорожных знаков

Набор объектов типа «Знак»




Таблица 7 – Описание класса «Топливо»

Имя поля

Тип

Описание

марка

Строка




цена

Денежный




Таблица 8 – Описание класса «Улица»

Имя поля

Тип

Описание

название

Строка




Таблица 9 – Описание класса «Машина»

Имя поля

Тип

Описание

топливо

Строка




марка

Строка




модель

Строка




расход топлива

Действительное




максимальная скорость

Целое





Рисунок 14 – UML-диаграмма классов

Таблица 10 – Описание класса «Покрытие»

Имя поля

Тип

Описание

название

Строка




коэффициент сопротивления

Действительное




Таблица 11 – Описание класса «Дорожный знак»

Имя поля

Тип

Описание

название

Строка




ребро

Объект «Ребро»




направление

Целое




тип знака

Целое




значение знака

Целое




Таблица 12 – Описание класса «Светофор»

Имя поля

Тип

Описание

метка

Строка




длительность красного

Целое




длительность зеленого

Целое




Таблица 13 – Описание класса «Водитель»

Имя поля

Тип

Описание

вероятность нарушения ПДД

Действительное




Таблица 14 – Описание класса «Сущность для описания человека»

Имя поля

Тип

Описание

Фамилия

Строка




Отчество

Строка




Имя

Строка




отображаемое имя

Строка




Таблица 15 – Описание класса «Полицейский»

Имя поля

Тип

Описание

коэффициент жадности

Действительное



      1. ^

        Выбор и обоснование алгоритмов обработки данных


Алгоритм Дейкстры (Dijkstra) - предназначен для решения задачи Поиск кратчайших путей в графе [8].

Ниже представлен алгоритм нахождения пути минимального веса в графе G = (V, E) заданном весовой матрицей W у которой элемент wij  равен весу ребра соединяющего i-ую и j-ую вершины. При этом предполагается, что все элементы wij  неотрицательны. Путь ищется из вершины номер u к вершине номер u. Здесь использует алгоритм Дейкстры. Для представления веса, равного бесконечности, используется число GM, передаваемое в алгоритм. Это число можно задавать в зависимости от конкретной задачи.

Алгоритм по которому происходит поиск заключается в следующем:

  1. всем веpшинам пpиписывается вес - вещественное число, d(i) := GM для всех вершин кроме вершины с номером u, а d(u) := 0

  2. всем веpшинам пpиписывается метка m(i) := 0

  3. вершина u объявляется текущей: t := u

  4. для всех вершин у которых m(i) равно 0, пересчитываем вес по формуле: d(i) := min{d(i), d(t)+W[t,i]}

  5. среди вершин для которых выполнено m(i) = 0 ищем ту для которой d(i) минимальна, если минимум не найден, т.е. вес всех не "помеченных" вершин равен бесконечности (GM), то путь не существует, покидаем алгоритм

    иначе найденную вершину c минимальным весом полагаем текущей и помечаем (m(t) := 1)

  1. если t = u, то найден путь веса d(t), покидаем алгоритм

  2. переходим на шаг 4.

На выходе имеем переменную Length, которая определяет длину пути (length равно null если пути не существует, length равно 0, если u равно u), переменную Weight - вес пути и массив Path содержащий последовательность номеров вершин определяющих путь.

Схема алгоритма представлена на рисунке 15.
      1. ^

        Выбор и обоснование комплекса программных средств

      1. Выбор операционной системы


В качестве операционной системы мы не выбираем конкретную ОС поскольку используем кросплатформенные средства разработки, такие как: Java 1.6, MySQL 5.1. Эти программные инструменты позволяют вести разработку под ряд современнных ОС:



Рисунок 15 – Блок схема алгоритма

семейство Linux 2.6, Unix (FreeBSD), Microsoft Windows. Кроме того, в качестве среды разработки АС «поиска оптимального пути по заданному критерию» была выбрана IntelliJ Idea, позволяющая быстро и гибко разрабатывать приложения для бизнеса на платформе Java.
      1. ^

        Выбор языка программирования


Java — это язык программирования, в котором, по замыслу создателей, должны сочетаться выразительность и простота. Его цель — позволить программисту создавать сложные высокопроизводительные программы. Java позволяет исполнять программы на множестве аппаратных платформ и ОС: PC, Android, мобильные устройства (Java ME). При этом окружение разработчика Java позволяет использовать современные БД и серверные решения.

Java является полностью объектно-ориентированным языком, где даже типы, встроенные в язык, представлены классами.

Java является мощным объектным языком с возможностями наследования и универсализации.

Для платформы Java существует целый набор языков программирования с различными парадигмами: Java – объектно-ориентированное программирование; Scala – функциональное программирование; Groovy, Jython, JRuby – динамическое окружение. В одном проекте возможно комбинировать различные языки и парадигмы для достижения гибкости и необходимого уровня абстракции. В своём проекте мы используем Groovy для быстрой разработки пользовательских интерфейсов.

В Java приняты стандарты для различных подсистем приложений. Основа JCP — так называемые JSR (Java Specification Request/Запрос на Спецификацию Java), формальные документы, описывающие спецификации и технологии, которые предлагается добавить к Java платформе. Основа JCP — так называемые JSR (Java Specification Request/Запрос на Спецификацию Java), формальные документы, описывающие спецификации и технологии, которые предлагается добавить к Java платформе.
      1. ^

        Выбор СУБД


В качестве средства проектирования базы данных, была выбрана MySQL 5.1., она является широко распространённой СУБД, используется как на Linux, так и Windows

серверах. Для коммуникации с сервером БД на базе MySQL имеется набор

библиотек для многих языков программирования и программных платформ.

СУБД MySQL имеет ряд преимуществ. Главным из них является то, что она обеспечивает создание информационных систем с архитектурой "клиент-сервер", в которой он играет роль сервера баз данных. Также можно сказать, что он удовлетворяет требованиям, предъявляемым к системам распределенной обработки информации. Эта СУБД поддерживает: тиражирование данных, параллельную обработку, создание и обработку больших баз данных на недорогих аппаратных платформах, отличается простотой управления и использования.




оставить комментарий
страница1/2
Артамонов Ю. С
Дата04.03.2012
Размер0,49 Mb.
ТипОтчет, Образовательные материалы
Добавить документ в свой блог или на сайт

страницы:   1   2
отлично
  2
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Документы

наверх