Материал: Sb97309

УДК 004.421(07) ББК 3973.2-018я7

В 39

Ветчинкин А. С., Лукомская О. Ю., Шпекторов А. Г.

В39 Составление алгоритма и написание программ обработки массива данных: учеб.-метод. пособие к курсовому расчету. СПб.: Изд-во СПбГЭТУ

«ЛЭТИ», 2017. 32 с.

ISBN 978-5-7629-2381-1

Содержит описания основных разделов курсового расчета по дисциплине «Программирование и основы алгоритмизации». Рассмотрены принципы формирования математической модели по постановке задачи. Приведены основные алгоритмы решения задачи, встроенные конструкции и функции среды программирования MATLAB, типовые варианты заданий на курсовой расчет.

Предназначено для студентов бакалавриата, обучающихся по направлению 27.03.04 «Управление в технических системах».

УДК 004.421(07) ББК 3973.2-018я7

Рецензент: кафедра информационных систем и технологий (СПбГЛТУ им. С. М. Кирова)

Утверждено редакционно-издательским советом университета

в качестве учебно-методического пособия

2

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

Курсовая работа включает в себя следующие основные этапы:

1.Постановка задачи и формирование математической модели.

2.Выбор алгоритма поиска кратчайшего пути и его тестирование.

3.Разработка блок-схемы алгоритма решения задачи.

4.Написание и отладка программы на языке MATLAB.

5.Представление и анализ результатов работы программы.

1. ПОСТАНОВКА ЗАДАЧИ И ФОРМИРОВАНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ

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

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

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

3

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

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

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

Граф называется ориентированным, если его ребра имеют направление (рис. 1.1, а), и неориентированным, если направление не задано. Граф называется связным, если последовательность ребер соединяет его две любые вершины – такая последовательность представляет собой путь из одной вершины в другую [2]. Если хотя бы для одной пары вершин не существует пути, граф называется несвязным.

4

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

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

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

5