Преподаватель который помогает студентам и школьникам в учёбе.

Алгоритмизация как обязательный этап разработки программы (Подходы к разработке программных систем)

Содержание:

Введение

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

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

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

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

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

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

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

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

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

Объект исследования – разработка программ.

Предмет исследования – алгоритмизация.

Целью данной работы является изучение алгоритмизации программ.

В соответствии с целью была определена необходимость постановки и решения следующих задач:

– изучить подходы к разработке программных систем;

– описать средства разработки программных систем;

– описать процессы алгоритмизации программ;

– разработать и описать программную систему.

1. Подходы к разработке программных систем

1.1. Методологии разработки программных систем

Существует широкий спектр методологий, которые придерживаются принципами и ценностями, заявленными в Agile Manifesto, к основным можно отнести следующие:

– Agile Modeling представляет собой набор понятий, приёмов и принципов, которые позволяю просто и быстро выполнять документирование и моделирование в реализуемых проектах разработки прикладного программного обеспечения. Методология Agile Modeling не включает в себя детальные инструкции по проектированию, не содержит подробных описаний, каким образом необходимо разрабатывать диаграммы на языке моделирования UML. Основной целью данной методологии является эффективное документирование и моделирование; но не охватывает последующие операции программирования и тестирования, не включает различные вопросы по управлению проектом разработки, развёртывания и послепроектного сопровождения программной системы [4].

– Agile Unified Process представляет собой упрощенную версию IBM Rational Unified Process (RUP), которая была разработана Скоттом Амблером, позволяющая описывать понятное и простое приближение определенной модели для разработки программной системы в рамках необходимого бизнес-приложения;

– Agile Data Method представляет собой группу итеративных методов разработки программных систем, в которых требования и решения могут быть достигнуты в рамках сотрудничества различных кросс-функциональных команд разработчиков;

– DSDM представляет собой методологию, которая основана на концепциях быстрой разработки программных систем (Rapid Application Development, RAD). Позволяет реализовать инкрементный и итеративный подход, придающий особое значение длительному участию в процессе разработки пользователя совместно с потребителем разрабатываемой программной системы;

– Feature driven development представляет собой функционально- ориентированную методологию разработки программных систем. Используемое в методологии FDD понятие свойства или функции программной системы является достаточно близким к понятию прецедента использования, которое используется в методологии IBM Rational Unified Process, существенным отличием является наличие дополнительных ограничений, которое заключается в том, что все функции по отдельности должны допускать свою реализацию не более, чем за две недели. То есть если принятый сценарий использования будет достаточно невелик, его можно считать функцией. Если же он будет достаточно большой, то его нужно будет разделить на несколько независимых функций [10];

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

– OpenUP представляет собой итеративно-инкрементальную методологию разработки программных систем, который позиционируется как гибкий и лёгкий вариант методологии IBM Rational Unified Process. В рамках использования методологии OpenUP жизненный цикл программного проекта может быть разделен на следующие фазы: начальная фаза, фазы уточнения, конструирования и передачи. Жизненный цикл реализуемого проекта обеспечивает предоставление членам коллектива и заинтересованным лицам точек принятия решений и ознакомления на протяжении практической реализации всего проекта программной системы [15]. Это позволяет эффективно контролировать процесс разработки и вовремя принимать необходимые решения о приемлемости получаемых результатов. План реализации проекта в полной мере определяет жизненный цикл программной системы, а конечным результатом работы над программным проектом является окончательная программная система;

– Scrum представляет собой методологию, которая позволяет устанавливать необходимые правила по управлению процессами разработки программной системы и позволяет использовать уже существующие практики практического кодирования, корректируя необходимые требования или внося тактические изменения в процессы разработки. Использование данной методологии предоставляет возможности выявления и устранения возникающих отклонений от желаемого результата на ранних этапах разработки программной системы [14].

Таким образом, перечисленные методологии базируются на принципах и ценностях методологии Agile позволяя разработчикам выбрать наиболее подходящий инструмент разработки программных систем. Разработка программной системы на базе использования методологии Agile является передовым подходом в разработке, который позволяет обеспечить наиболее эффективный процесс разработки.

1.2. Методология Agile

Гибкая методология разработки (англ. Agile software development, agile-методы) представляет собой серию подходов к разработке программного обеспечения, которые ориентированы на использование принципов итеративной разработки, динамического формирования требований и обеспечение их практической реализации в результате постоянного взаимодействия внутри самоорганизующихся рабочих групп, которые состоят из специалистов разного профиля [3].

Методология Agile используется как эффективная практика организации труда небольших групп (которые работают над однородной творческой работой) в объединении с управлением ими комбинированным (демократическим и либеральным) методом [7].

Большая часть гибких методологий направлены на сокращение возможных рисков за счет сведения процесса разработки к серии небольших циклов, которые называются итерациями, протекающие по две-три недели. Каждая отдельная итерация представляет собой небольшой программный проект и включает все задачи, которые необходимы для выдачи небольшого прироста функциональности базового проекта: планирование; анализ требований; проектирование; программирование; тестирование; документирование.

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

Использование Agile-методов дает возможность сделать упор на непосредственное общение лицом к лицу разработчика и заказчика программной системы. Большая часть agile-команд могут быть расположены в одном офисе, иногда такие офисы называют bullpen. Офис может включать дизайнеров интерфейса, тестировщиков, технических писателей.

Основной метрикой agile-методов является рабочий продукт. Отдавая предпочтение непосредственному общению, agile-методы позволяют значительно уменьшить объём письменной документации в сравнении с использованием других методов разработки. Это привело к некоторой критике такого рода методов как недисциплинированных.

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

Agile Manifesto разработан и принят 11-13 февраля 2001 года на лыжном курорте The Lodge at Snowbird в горах Юты. Agile Manifesto содержит четыре основные идеи и двенадцать принципов. Примечательным является то, что Agile Manifesto не включает практических советов по разработке [2].

Основные идеи, представленные в Agile Manifesto: люди и возникающее взаимодействие являются важнее протекающих процессов и используемых инструментов; работающий продукт является важнее любой исчерпывающей документации на него; сотрудничество с заказчиком намного важнее предварительного согласования различного рода условий контракта на разработку программной системы; готовность к возможным изменениям намного важнее следования первоначальному плану разработки программы [5].

Принципы, разъясняемые в Agile Manifesto: удовлетворение клиента обеспечивается бесперебойной и ранней поставкой ценной программной системы; приветствие вносимых в рабочий проект изменений требований даже на конечных стадиях разработки программной системы; частая поставка рабочей программной системы (каждый месяц, неделю или ещё чаще); тесное, в некоторых случаях даже ежедневное общение команды разработчиков и заказчика на протяжении всего срока практической реализации программной системы; над проектом работают сильно мотивированные люди, обеспеченные всеми необходимыми условиями работы, поддержкой и должным доверием, как со стороны заказчика, так и со стороны участников команды [13];

– рекомендуемым методом передачи рабочей информации является личный разговор; работающая программная система является лучшим измерителем прогресса практической реализации проекта; разработчики, спонсоры и пользователи должны иметь возможности поддержания постоянного темпа на неопределённом сроке проекта; постоянное внимание улучшению удобного дизайна и технического мастерства; простота заключается в искусстве не делать лишней работы проекта программной системы; лучшие технические решения, архитектура и дизайн могут быть получены только у самоорганизованной команды; адаптация к постоянно изменяющимся обстоятельствам процесса реализации проекта реализации программной системы. Команда должна систематически выполнять анализ возможных способов улучшения эффективности и соответственно выполнять корректировку стиль своей практической работы над проектом разработки [6].

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

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

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

2. Средства разработки программных систем

2.1. Характеристика языка программирования С++

Среди устоявшихся и популярных языков программирования выделяется язык С++, который представляет собой компилируемый, статически типизированный язык программирования общего назначения. Изучение технологии алгоритмизации данный язык подходит в полной мере, в связи с тем, что реализованные технологии в языке программирования С++ представлены в линейке современных языков программирования, например, С#, Java, php.

Язык программирования С++ в полной мере поддерживает такие парадигмы программирования, как объектно-ориентированное программирование, процедурное программирование, обобщённое программирование. Язык программирования С++ имеет достаточно богатую стандартную библиотеку, включающая в себя специализированные алгоритмы и распространённые контейнеры, функции ввода-вывода, регулярные выражения, есть поддержка многопоточности и другие уникальные возможности. Язык программирования C++ сочетает в себе специализированные свойства как высокоуровневых, так и низкоуровневых языков программирования. В сравнении с его прямым предшественником – языком программирования C, – наибольшее внимание в языке программирования С++ было уделено поддержке концепций объектно-ориентированного и обобщённого программирования [11].

Язык программирования C++ широко используется для непосредственной разработки прикладного программного обеспечения, являясь одним из наиболее популярных языков. Область его практического применения включает создание ОС, различного спектра прикладных программ, драйверов устройств, прикладных программных приложений для встраиваемых систем, серверов, а также развлекательных прикладных программных приложений.

Существует большое количество практических реализаций языка программирования C++, как бесплатных, так и на коммерческой основе и для различных операционных систем. Например, на платформе x86 это GCC, Visual C++, Intel C++ Compiler, Embarcadero (Borland) C++ Builder и другие. Язык программирования C++ оказал большое влияние на другие языки программирования, в первую очередь на языки программирования Java и C#.

Синтаксис языка программирования C++ унаследован от языка программирования C. Одним из базовых принципов непосредственной разработки было сохранение полной совместимости с языком программирования C. Тем не менее, язык программирования C++ не является в строгом смысле надмножеством языка программирования C; множество прикладных программ, которые могут одинаково успешно быть транслированы как компиляторами языка программирования C, так и компиляторами языка программирования C++, довольно велико, но не включает все возможные прикладные программы на языке программирования C.

Стандартная библиотека языка программирования C++ включает в себя достаточно большой набор специализированных средств, которые должны быть доступны для любой реализации языка программирования, чтобы обеспечить программистам удобное пользование языковыми средствами и возможности создания баз данных для практической разработки, как прикладных программных приложений самого широкого спектра, так и специализированных программных библиотек [9].

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

Доступ к возможностям стандартной библиотеки языка программирования C++ обеспечивается при помощи включения в прикладную программу (посредством использования директивы #include) необходимых стандартных заголовочных файлов. Всего в стандарте языка программирования C++11 определено 79 таких файлов. Средства стандартной библиотеки объявляются как входящие в пространство имён std [1]. Стандартные функции библиотеки C также находятся в пространстве имён std.

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

Таким образом, язык программирования С++ имеет необходимый комплекс возможностей для разработки программ любой сложности и эффективной алгоритмизации программных систем.

2.2. Массивы в языке программирования

Алгоритмизация представляет собой описание очередности выполнения различных операций, необходимых для решения той или иной задачи в форме алгоритма. Использование массивов в программах является достаточно частым и необходимым условием получение необходимого результата.

Массив представляет собой конечную последовательность упорядоченных элементов одного типа, доступ ко всем элементам в которой выполняется по средствам использования его индекса [14]. Массив представляет собой специализированную структуру данных, которая представлена в виде группы ячеек одного типа, объединенных под одним единым именем. Массивы используются для непосредственной обработки большого количества однотипных данных.

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

Отдельная ячейка данных массива называется элементом массива. Элементами массива могут быть данные любого доступного типа. Массивы могут иметь как одно, так и более одного измерений. В зависимости от количества таких измерений массивы можно поделить на одномерные массивы, двумерные массивы, трёхмерные массивы и так далее до n-мерного массива.

Чаще всего в процессе программирования используются одномерные и двумерные массивы, поэтому можно рассмотреть только эти виды массивов для понимания данной темы.

Индекс начального элемента будет равен 0, следующего за ним будет равен 1 и т.д. Индекс последнего элемента в массиве – будет на единицу меньше, чем размер исходного массива. Графическое представление массива можно представить в виде следующей схемы, представленной на рис. 1.

Рисунок 1 – Графическое представление массива

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

Для объявления одномерного массива в языке программирования С++ необходимо выполнить следующую инструкцию:

int a[16];

где, int представляет собой целочисленный тип данных;

а является именем создаваемого одномерного массива;

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

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

Также, еще есть один способ для объявления одномерного массива

int m[10], a[16];

В представленном примере были объявлены два одномерных массива m и а размерностью 10 и 16. Причём при использовании такого способа объявления все созданные массивы будут иметь одинаковые типы данных, в представленном случае - int.

Массивы в языке программирования С++ могут быть инициализированы при их непосредственном объявлении следующим образом:

int m[16] = { 5, -13, -13, 9, 13, 0, -9, -13, -1, 23, 61, 63, 13, 43, 33, -14 };

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

Инициализации массива без определения его размера может быть выполнена следующим образом

int m[]={ 5, -11, -11, 9, 11, 0, -9, -11, -1, 21, 61, 61, 11, 41, 31, -11 };

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

2.3. Резервирование памяти для массива и его инициализация

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

Для объявленного myFirstArrays, зарезервируем память при помощи практического использования ключевого слова new.

int[] myFirstArrays; // объявляем массив

myFirstArrays = new int[20]; // резервируем память

В данном примере будет создан массив из 20 элементов типа int и присвоено ему ранее объявленной переменной myFirstArrays.

Объявить имя массива и выполнить резервирование для него памяти также можно выполнить одной строкой.

int[] myArrays = new int[15];

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

myFirstArrays[0] = 11; // выполнение инициализации первого элемента

myFirstArrays[1] = 21; // выполнение инициализации второго элемента

myFirstArrays[2] = 31; // и т.д.

так и в программном цикле, при помощи индекса элемента массива проходя все элементы обрабатываемого массива и присваивая им необходимые числовые значения [3].

for(int i = 0; i < 20; i++){

myFirstArrays[i] = 11; // присваиваем всем элементам массива 11

}

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

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

3. Программная разработка

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

Алгоритм Форда–Беллмана представляет собой специализированный алгоритм для нахождения кратчайшего пути в рамках обработки взвешенного графа. За отведенное время O(|V| × |E|) алгоритм Форда–Беллмана позволяет выполнить необходимый поиск кратчайшего пути от определенной вершины графа ко всем остальным.

Алгоритм Беллмана–Форда, в отличие от алгоритма Дейкстры допускает оперативную обработку рёбер обрабатываемого объекта, которые имеют отрицательный вес. Данный алгоритм был предложен независимо Ричардом Беллманом и Лестером Фордом.

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

Следует построить матрицу A_ij, элементы которой обозначают следующее: A_ij представляет собой длину наименьшего пути из s в i, который содержит не более j рёбер исследуемого графа.

Можно предположить, что граф содержащий 0 рёбер, может существовать только до вершины s. Таким образом, A_i0 является равным 0 при i = s, и +∞ в противном случае.

Теперь следует рассмотреть все возможные пути из s в i, содержащие ровно j рёбер исследуемого графа. Каждый такой путь является путем из j-1 ребра, к которому будет добавлено последнее ребро данного графа. Если на пути длины j-1 все данные уже будут подсчитаны, то определить j-й столбец матрицы не будет составлять особого труда.

Так выглядит алгоритм оперативного поиска длин кратчайшего пути в анализируемом графе без наличия отрицательных циклов:

for v V

do d[v] +

d[s] 0

for i 1 to |V| - 1

do for (u, v) E

if d[v] > d[u] + w(u, v)

then d[v] d[u] + w(u, v)

return d

В представленном алгоритме переменная V представляет собой специальное множество вершин исследуемого графа, переменная E представляет собой множество его рёбер, а переменная w является весовой функцией, которая задается на ребрах исследуемого графа (используется для возвращения длины полученной дуги, которая ведет из вершины u в вершину v), переменная d представляет собой массив, который содержит расстояния от вершины s до любой другой вершины исследуемого графа.

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

Вместо массива d можно хранить всю анализируемую матрицу A, но это требует O(V²) достаточно большого количества вычислительной памяти. Зато при этом можно будет выполнить вычисление и самих кратчайших путей, а не только их непосредственной длины. Для этого необходимо завести дополнительную матрицу в виде массива P_ij.

Если элемент матрицы A_ij будет включать длину наименьшего по длине пути из s в i, который содержит j рёбер исследуемого графа, то P_ij будет включать предыдущую вершину до i в одном из таких кратчайших путей (ведь кратчайших путей в исследуемом графе может быть и несколько).

Теперь изучаемый алгоритм Форда-Беллмана будет выглядеть следующим образом:

for v V

for i 0 to |V| - 1

do A_vi +

A_s0 0

for i 1 to |V| - 1

do for (u, v) E

if A_vi > A_{u, i-1} + w(u, v)

then A_vi A_{u, i-1} + w(u, v)

P_vi u

После непосредственного исполнение представленного алгоритма элементы матрицы A_i,j будет включать длины кратчайших путей исследуемого графа от s до i с количеством ребер j, и из всех таких путей необходим будет выполнить выбор самого короткого пути. А сам кратчайший путь до вершины i с j ребрами может быть восстановлен следующим образом:

while j > 0

p[j] i

i P_ij

j j - 1

return p

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

После непосредственного запуска программа предлагает пользователю ввести имя файла с параметрами графа и необходимые вершины графа, между которыми будет вычисляться кратчайший путь. Графическое представление файла data.txt представлено на рис. 2.

Рисунок 2 – Граф

Например, пользователь вводит data.txt 1 7, это значит, что параметры графа будут взяты с заранее созданного информационного файла data.txt. Содержание файла data.txt

7 11

1 2 5

1 6 7

2 3 1

2 4 3

2 6 1

3 4 1

3 5 2

3 7 4

4 6 2

5 7 2

6 5 1

Значения 1 7 представляют собой вершины графа, между которыми и будет найден кратчайший путь.

3.2. Разработка алгоритма программы

Для практической реализации поставленной задачи необходимо выполнить следующие действия:

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

Приведем реализацию алгоритма Форда-Беллмана.

for (h=1 ; h<=N ;h++) {

i=0;

for (j=2 ; j<=N ; j++) {

for (k=1 ; k<=N ; k++) {

if (D[k] > D[j]+m[j][k])

D[k]=D[j]+m[j][k] ;

i++;

// преобразуем полученный информационный массив расстояний

// в матрицу значений

for (l=2 ; l<=N ; l++) {

// (i-ая строка информационной матрицы является массивом

// расстояний на i-ом шаге)

W[i][l]=D[l];

// выполняем отслеживание улучшений полученного пути

// исследуемого графа

if (W[i][l]<W[i-1][l])

// выполняем запоминание вершины, через которую

// будет проходить данный путь

G[k][2]=j ;

}

Реализация функции для непосредственного нахождения возможных путей между данными вершинами в исследуемом графе не пересекающиеся по ребрам выглядит следующим образом

void PYTU () {

// пока путь будет существовать ...

while (D[F]<MAX) {

// выполняем вызов функции нахождения наименьшего

// расстояния для исследуемого графа

// без учета весов рёбер (все ребра будут иметь вес равный единице)

GRAF(v);

for (j=0 ; j<M ; j++)

// пройденные ребра будут удалены

v[Z[j+1]][Z[j]]=MAX;

}

// завершение функции

return;

}

Для выполнения присваивания элементам обоих матриц максимальных значений можно представить в виде реализации следующего программного кода

for ( i=1 ; i<=N ; i++)

for ( j=1 ; j<=N ; j++) {

m[i][j]=MAX;

v[i][j]=MAX;

}

Исходный программный код разработанной программы представлен в Приложении.

3.3. Порядок работы с программой

После выполнения запуска программы необходимо будет ввести имя файла, которое содержит информацию о графе (имя файла txt.txt). Затем ввести необходимые узлы графа, для определения кратчайшего пути (например, вводим вершины 1 и 7). Результат работы программы представлен на рис. 3.

Рисунок 3 – Результат работы программы

Результат выполнения разработанной программы для нахождения кратчайшего пути с введенными вершинами 2 и 6 имеет следующий вид, представленный на рис. 4.

Рисунок 4 – Результат работы программы

Результат выполнения программы с введенными вершинами 1 и 5 имеет следующий вид, представленный на рис. 5.

Рисунок 5 – Результат работы программы

Таким образом, был представлен процесс алгоритмизации и описание хода работы с программной системой, реализующей алгоритм Форда–Беллмана для нахождения кратчайшего пути в рамках взвешенного графа.

Заключение

В процессе выполнения данной работы были получены следующие результаты. Установлено, что существует широкий спектр методологий, которые придерживаются принципами и ценностями, заявленными в Agile Manifesto, к основным можно отнести следующие: Agile Modeling; Agile Unified Process; Agile Data Method; DSDM; Feature driven development; Getting Real; OpenUP; Scrum. Описанные методологии базируются на принципах и ценностях методологии Agile позволяя разработчикам выбрать наиболее подходящий инструмент разработки программных систем.

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

Процесс оказания услуг по разработке программной системы в рамках методологии Agile включает следующие стадии: определение проблемы практической реализации программной системы; определение различных вариантов решения выявленных проблем клиента; проверка рынка существующих программных систем, которые могут быть использованы в качестве альтернативных или основных вариантов решения проблем; разработка программного решения.

Установлено, что язык программирования С++ представляет собой компилируемый, статически типизированный язык программирования общего назначения. Поддерживает такие парадигмы программирования, как процедурное программирование, объектно-ориентированное программирование, обобщённое программирование.

Массив представляет собой конечную последовательность упорядоченных элементов одного типа, доступ ко всем элементам в которой выполняется по средствам практического использования его индекса. Массив представляет собой специализированную структуру данных, которая представлена в виде группы ячеек одного типа, объединенных под одним единым именем. Массивы используются для непосредственной обработки большого количества однотипных данных.

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

В языках программирования существуют следующие циклические операторы: for; while; do while.

В качестве практической разработки была разработана программа, работающая по алгоритму Форда–Беллмана для нахождения кратчайшего пути в рамках взвешенного графа.

Алгоритм Беллмана–Форда, в отличие от алгоритма Дейкстры допускает обработку рёбер, которые имеют отрицательный вес. Данный алгоритм был предложен независимо Ричардом Беллманом и Лестером Фордом.

Список использованной литературы

Гаврилов М.В. Информатика и информационные технологии: Учебник / М.В. Гаврилов, В.А. Климов. - Люберцы: Юрайт, 2016. – 383 c.
Гома Х. UML. Проектирование систем реального времени, распределенных и параллельных приложений / Х. Гома. - М.: ДМК, 2016. – 700 c.
Дарков А.В. Информационные технологии: теоретические основы: Учебное пособие / А.В. Дарков, Н.Н. Шапошников. - СПб.: Лань, 2016. – 448 c.
Довек Ж. Введение в теорию языков программирования / Ж. Довек, Ж.-Ж. Леви. - М.: ДМК, 2016. – 134 c.
Ерохин В.В. Безопасность информационных систем: учеб пособие / В.В. Ерохин, Д.А. Погонышева, И.Г. Степченко. - М.: Флинта, 2016. – 184 c.
Информационные технологии: Учебное пособие / Л.Г. Гагарина, Я.О. Теплова, Е.Л. Румянцева и др.; Под ред. Л.Г. Гагариной - М.: ИД ФОРУМ: НИЦ ИНФРА-М, 2015. – 320 c.
Информационные системы и технологии: Научное издание. / Под ред. Ю.Ф. Тельнова. - М.: ЮНИТИ, 2016. – 303 c.
Корнеев И.К. Информационные технологии в работе с документами: Учебник / И.К. Корнеев. - М.: Проспект, 2016. – 304 c.
Косиненко Н.С. Информационные системы и технологии в экономике: Учебное пособие для бакалавров / Н.С. Косиненко, И.Г. Фризен. - М.: Дашков и К, 2015. – 304 c.
Кулямин В.В. Технологии программирования. Компонентный подход / В.В. Кулямин. - М.: Интуит, 2014. – 463 c.
Куроуз Д. Компьютерные сети. Нисходящий подход / Д. Куроуз, К. Росс. - М.: Эксмо, 2016. – 912 c.
Лукин В.Н. Введение в проектирование баз данных / В.Н. Лукин. - М.: Вузовская книга, 2015. – 144 c.
Романова Ю.Д. Информационные технологии в управлении персоналом: Учебник и практикум / Ю.Д. Романова, Т.А. Винтова, П.Е. Коваль. - Люберцы: Юрайт, 2016. – 291 c.
Сальникова Л.С. Современные коммуникационные технологии в бизнесе: Учебник / Л.С. Сальникова. - М.: Аспект-Пресс, 2015. – 296 c.
Советов Б.Я. Информационные технологии: теоретические основы: Учебное пособие / Б.Я. Советов, В.В. Цехановский. - СПб.: Лань, 2016. – 448 c.

Приложение

Исходный код программы

#include <stdio.h>

#include <stdlib.h>

#define P 60

#define MAXX 1000

int mm[PP][PP];

int vv[PP][PP];

int DD[PP], GG[PP][PP], WW[PP][PP],ZZ[PP];

int N,M,S,F;

int a,b,c;

int i,j,k,l,h,f;

void GRAF (int mm[PP][PP]) {

for (i=1 ; i<=N ; i++ )

DD[i] = mm[S][i];

DD[S] = 0 ;

for (j=1; j<=2 ; j++) {

GG[j][1]=S;

GG[S][j]=0;

}

for (h=1 ; h<=N ;h++) {

i=0;

for (j=2 ; j<=N ; j++) {

for (k=1 ; k<=N ; k++) {

if (DD[k] > DD[j]+mm[j][k])

DD[k]=DD[j]+mm[j][k] ;

i++;

for (l=2 ; l<=N ; l++) {

WW[i][l]=DD[l];

if (WW[i][l]<WW[i-1][l])

GG[k][2]=j ;

}

printf("\n");

if (DD[FF]<MAXX) {

printf("\ndlinna puti ot %d uzla do %d uzla = ",S,F);

printf("%d \n",DD[FF]);

printf("put' megdu %d u %d vershinami : ",S,F);

i=1;

ZZ[0]=F;

while ( GG[FF][2] !=0 ) {

ZZ[i]=GG[FF][2];

i++;

GG[FF][2]=GG[GG[FF][2]][2];

}

ZZ[i]=S;

for (j=i ; j>=0 ;j--)

printf(" %d",ZZ[j]);

}

else {

printf("\nputi net\n\n\n");

return;

}

return;

}

void PYTU () {

while (DD[FF]<MAXX) {

GRAF(v);

for (j=0 ; j<M ; j++)

vv[ZZ[j+1]][ZZ[j]]=MAXX;

}

return;

}

int main () {

char fileName[256];

FILE *inp;

printf("Vvedite imya faila : ");

scanf("%s", fileName);

printf("\n");

inp=fopen(fileName, "r");

fscanf (inp,"%d %d",&N,&M);

for ( i=1 ; i<=N ; i++)

for ( j=1 ; j<=N ; j++) {

mm[i][j]=MAXX;

vv[i][j]=MAXX;

}

for (i=1 ;i<=M ;i++ ) {

fscanf(inp,"%d %d %d",&a,&b,&c);

mm[a][b]=c;

vv[a][b]=1;

}

fclose(inp);

printf("\n");

printf("Vvedite nachalo i konec puti : ");

scanf ("%d %d",&S,&F);

printf("\nVse puti ne perecekautcya po rebram : \n");

PYTU();

printf("Min put' i ego dlinna : ");

GRAF(m);

system("pause");

return 0 ;

}