46749 (571861)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Алгоритмизация задач

На первом этапе разработки комплексов программ АСУ определяют требования, выполнение которых обеспечивает решение поставленных задач. Основными характеристиками являются время и стоимость обработки информации, вероятность ошибки, допустимые объемы памяти, неизбежность выполнения основных функций и т.п. Требования к системе содержатся в системных спецификациях, которые отображают предполагаемую реализацию системы с помощью ЭВМ. Спецификации являются основополагающим документом в процессе разработки системы. Точность и подробность составления спецификаций определяют вероятность возникновения ошибки на дальнейших этапах разработки. Большинство современных методов создания программного обеспечения допускает появление ошибок в спецификациях проекта, однако цена обнаружения и корректировки ошибок возрастает по мере приближения разработки к завершению. В большинстве случаев ошибки в системе – результат неполных или противоречивых спецификаций (60–70% ошибок). В связи с этим возникает необходимость разработки и использования языков и формализованных методов разработки спецификаций, их анализа и контроля.

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

Эффективным средством формализации процесса определения спецификаций является система PSL/PSA, которая включает язык определения задач (PSL) и анализатор определения задач (PSA).

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

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

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

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

Система SREM, используемая для автоматизации анализа требований, включает язы к определения требований RSL для установления связи между объектами. Проверка последовательности предложений на языке RSL осуществляется с помощью процессора REVS. Система выполняет следующие операции: разработку требований, включающую описатели данных и этапы их разработки; разработку подробных проектов; моделирование отдельных аспектов проектных решений с учетом принятых допущений; проверку пользователем требований, предъявляемых к системе.

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

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

Вторым этапом процесса разработки программного обеспечения является составление алгоритма решения поставленной задачи.

При разработке алгоритма решения задачи прежде всего решаются следующие вопросы:

а) следует ли использовать имитационное моделирование или какой-либо из методов оптимизации;

б) следует ли учитывать случайный характер переменных или процессов или использовать детерминированный подход;

в) следует ли учитывать нелинейность некоторых соотношений или достаточно ограничиться их линейной аппроксимацией;

г) можно ли использовать существующие методы решения или требуется разработать новый алгоритм;

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

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

Предел временной сложности при увеличении размера задачи называется асимптотической временной сложностью. Аналогично определяется емкостная сложность и асимптотическая емкостная сложность. Именно асимптотическая сложность алгоритма определяет в итоге размер задач, которые можно решить этим алгоритмом. Если алгоритм обрабатывает входы размера п за время сn², где с - некоторая постоянная, то говорят, что временная сложность этого алгоритма есть О(п²) (читается "порядка n²"). Точнее, говорят, что неотрицательная функция g(n) есть O(f(n)), если существует такая постоянная с, что g(n) ≤ cf(n) для всех, кроме конечного (возможно пустого) множества неотрицательных значений п.

Пусть дано пять алгоритмов А₁ – A₅ (табл. 1). Под временной сложностью здесь понимается число единиц времени, требуемого для обработки входа размера п. В табл. 5.1 приведены размеры задач, которые можно решить за 1 с, 1 мин и 1 ч каждым из этих пяти алгоритмов. Если в качестве основы для сравнения взять 1 мин, то, заменяя алгоритм А₄ алгоритмом А₃, можно решить задачу в 6 раз большую, а заменяя А₄ на А₂, можно решить задачу, большую в 125 раз. Если в качестве основы для сравнения взять 1 ч, то различие алгоритмов становится еще значительнее. Отсюда можно заключить, что асимптотическая сложность алгоритма служит важной мерой его качества, причем такой мерой, которая приобретает все большее значение с увеличением размера вычислений.

Таблица 1

Сложность алгоритма определяет также то увеличение размера задачи, которого можно достичь с увеличением скорости машины. Увеличение скорости вычислений в 10 раз увеличивает размер задачи, которую можно решить, для алгоритма А₅ только на 3, тогда как для алгоритма А₃ – более чем втрое. Однако алгоритм с быстро растущей сложностью может оказаться предпочтительнее для задач с малым размером. Например, если временные сложности алгоритмов А₁ – A₅ равны соответственно 1000n, 100n, logn, 10n², n³ и 2ⁿ, то алгоритм А₅ будет наилучшим для задач размера 2 ≤ п ≤ 9, А₃ – для задач размера 10 ≤ п ≤ 58, А₂ – при 59 ≤ n ≤ 1024, a A₁ – n > 1024.

Для того чтобы показать, что не существует алгоритма, выполняющего решение задачи менее чем за определенное время, необходимо точное определение того, что есть алгоритм. Уточнение понятий алгоритма и его сложности требует привязки к некоторой конкретной схеме вычислений. Обычно в качестве такой схемы рассматривается машина Тьюринга или так называемая адресная машина. Однако можно принять модель, более близкую к реальному ходу вычислений в оперативной памяти машины с одним процессором, и считать, что вычисления реализуются программой, написанной на некотором упрощении (подмножестве) языка АЛГОЛ.

На первоначальных этапах развития теории сложности в ней чаще всего рассматривались задачи, на которые можно дать лишь один из двух ответов: ДА или НЕТ. Например, классическая "сложностная" постановка известной задачи о ранце (с ограничением в виде равенства) будет заключаться в выяснении того, существуют ли для заданных чисел a_j, j = 1,2, ..., n и b значения булевых переменных x_j, удовлетворяющие ограничению

(1)

Обычная же формулировка задачи о ранце состоит в максимизации суммы

(2)

при условии (1). Однако легко заметить, что ответы на последовательность задач типа "существует ли набор булевых переменных x_j, удовлетворяющих (1), такой, что z = k при k = 0, 1,2, ..." дадут решение задачи о ранце в привычной формулировке. При этом под задачей понимается весь класс однотипных вопросов, различающихся входными данными. Например, в задаче (1), (2) вход представляет собой набор {k, {а_j}, {с_j}, b}, так что задача о ранце сводится к решению вопроса "существует ли значение целевой функции, равное k, в ситуации, описываемой остальными входными данными". Конкретный набор исходных данных определяет реализацию задачи.

Обозначим задачу через П, ее реализацию – через π. Под размером реализации будем понимать число символов, необходимых для записи входных данных этой реализации. Размер реализации π будет обозначаться . Под временем решения t_π реализации π понимается сумма времен выполнения всех команд программы.

Введем понятие класса задач Р, разрешимых за полиномиальное время. Этот класс состоит из всех задач П, обладающих следующим свойством: для любой существует АЛГОЛ-программа u_П и полином f_П (·), такие, что любая реализация u_П за время t_π (u_П) ≤ f_П ( ). Примерами задач из класса Р являются задачи нахождения кратчайшего пути между двумя вершинами графа, минимального разреза в сети, минимального дерева.

Общепринято, что если задачу нельзя решить быстрее, чем за экспоненциальное время, то ее следует рассматривать как трудно разрешимую. Такие задачи образуют класс задач, недетерминированным образом разрешимых за полиномиальное время (NP-класс). Для определения NP класса необходимо расширить язык, добавив к нему новую команду CHOOSE(x). Эта команда придает недетерминированным образом переменной х значение О или 1. Расширенный за счет этой команды язык назовем N-АЛГОЛ. Будем говорить, что программа на N-АЛГОЛе (N-программа) выдает на некоторую реализацию задачи ответ ДА, если N-программа выдает ответ ДА при некоторой комбинации значений, реализовавшихся при выполнении команд CHOOSE(x). В этом случае под временем выполнения N-программы будем понимать минимальное время для всех детерминированных программ, полученных путем замены CHOOSE(x) нулями или единицами, которые выдают ответ ДА. Если N-программа дает ответ НЕТ, то время ее выполнения для данной реализации не определяется.

Отметим, что приведенное определение времени для реализации с ответом ДА является в значительной мере условным, так как любая реальная схема вычислений является детерминированной и для нее необходимо просмотреть все последовательности реализации CHOOSE(x), чтобы определить, выдает ли хоть одна из них ответ ДА. Это потребует времени, равного сумме времен, необходимых для каждого набора реализаций.

Определим класс NP как подкласс всех таких задач П, для которых существует N-программа и_П и полином f_π (·), такие, что для любой реализации π задачи П, для которой имеется ответ ДА, программа и_П выдает ответ ДА за время t_π (u_П) ≤ f_П ( ). Так как любая программа является N-программой, то, очевидно, .

Дадим определение: множество А полиномиально сводимо к В (обозначается А < В), если существует функция φ, вычислимая за полиномиальное время и такая, что при

Если то А и В полиномиально эквивалентны.

Множество Е называется NP-полным (или универсальной переборной задачей), если и для любого имеем . Множество NP-полных задач обозначается NPC, .

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

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

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

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

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

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

Список файлов ответов (шпаргалок)