Файл: Алгоритмизация как обязательный этап разработки программы (Разработка программ).pdf

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

Оформление программ должно соответствовать определенным требованиям. В настоящее время действует единая система программной документации (ЕСПД), которая устанавливает правила разработки, оформления программ и программной документации. В ЕСПД определены и правила оформления блок-схем алгоритмов (ГОСТ 10.002-80 ЕСПД, ГОСТ 10.003-80 ЕСПД).

Операции обработки данных и носители информации изображаются на схеме соответствующими блоками. Большая часть блоков по построению условно вписана в прямоугольник со сторонами а и b. Минимальное значение а = 10 мм, увеличение а производится на число, кратное 5 мм. Размер b=1,5a. Для от дельных блоков допускается соотношение между а и b, равное 1:2. В пределах одной схемы рекомендуется изображать блоки одинаковых размеров. Все блоки нумеруются. Виды и назначение основных блоков приведены в табл. 1.

Наименование	Обозначение	Функции
Процесс		Выполнение операции или группы операций, в результате которых изменяется значение, форма представления или расположение данных.
Ввод-вывод		Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод).
Решение		Выбор направления выполнения алгоритма в зависимости от некоторых переменных условий.
Предопределенный процесс		Использование ранее созданных и отдельно написанных программ (подпрограмм).
Документ		Вывод данных на бумажный носитель.
Магнитный диск		Ввод-вывод данных, носителем которых служит магнитный диск.
Пуск-останов		Начало, конец, прерывание процесса обработки данных.
Соединитель		Указание связи между прерванными линиями, соединяющими блоки.
Межстраничный соединитель		Указание связи между прерванными линиями, соединяющими блоки, расположенные на разных листах.
Комментарий		Связь между элементом схемы и пояснением.

---

Таблица 1. Условные обозначения блоков схем алгоритмов

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

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

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

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

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

Подходы к созданию алгоритмов

Одним из наиболее важных аспектов алгоритма является его скорость. Часто бывает легко придумать алгоритм решающий задачу, но если алгоритм слишком медленный, то он возвращается на доработку. Поскольку точная скорость алгоритма зависит от того где запускается алгоритм, а также деталей реализации, компьютерные специалисты обычно говорят о времени выполнения относительно входных данных. Например, если вход состоит из N целых чисел, то алгоритм может иметь время выполнения пропорциональное N², что представляется как O(N²). Это означает, что если вы запустите реализацию алгоритма на компьютере с входом размером в N, то это займет C*N² секунд, где C-некоторая константа, которая не меняется с изменением размера входа.

---

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

Сортировка. Сортировка является хорошим примером алгоритма, который часто используется программистами. Самый простой способ отсортировать группу элементов это начать с удаления наименьшего элемента из группы, и поставить его первым. Затем удаляется второй по величине элемент и ставится вторым и т.д. К сожалению, время работы этого алгоритма составляет O(N²), а это означает, что потребуется количество времени пропорциональное количеству элементов в квадрате. Если бы нам пришлось сортировать млрд. элементов, то этот алгоритмы бы потребовал 10¹⁸ операций. Если считать что обычные настольные ПК делают примерно 10⁹ операций в секунду, то потребуются годы чтобы закончить сортировку этого млрд. элементов.

К счастью существует ряд более совершенных алгоритмов, например, быстрая сортировка (quicksort), пирамидальная сортировка (heapsort) и сортировка слияния(mergesort). Эти алгоритмы имеют время выполнения O(N * Log(N)). Таким образом, число операций необходимых для сортировки млрд. элементов сокращается до таких разумных пределов, что даже самый дешевый настольный ПК способен провести такую сортировку. Вместо млрд. в квадрате операций (10¹⁸) эти алгоритмы требуют только 10 млрд. операций (10¹⁰), т.е. в 100 млн. раз быстрее.

Кратчайший путь. Алгоритмы поиска кратчайшего пути из одной точки в другую исследуются уже на протяжении многих лет. Примеров прикладного применения этих алгоритмов предостаточно, однако для простоты изложения будем придерживаться следующей постановки: требуется найти кратчайший путь из точки А в точку Б в городе с несколькими улицами и перекрестками. Существует много разных алгоритмов для решения этой задачи и все они со своими преимуществами и недостатками. Прежде чем мы углубимся в их изучение, давайте рассмотрим время выполнения простого алгоритма перебором. Если алгоритм рассматривает каждый возможный путь от А до Б (который не образует циклов) он вряд ли закончится при нашей жизни, даже если А и Б находятся в маленьком городке. Время выполнения этого алгоритма является экспоненциальным, что обозначается как O(C^N) для некоторого C. Даже для малых значений C, C^N становится астрономическим числом, когда N принимает умеренно большое значение.

---

Один из самых быстрых алгоритмов для решения этой задачи имеет время выполнения O(E+V*Log(V)), где E число дорожных сегментов, а V число пересечений. Алгоритм займет около 2 секунд времени, для поиска кратчайшего пути в городе из 10000 пересечений и 20000 дорожных сегментов (обычно бывает около 2 дорожных сегментов на одно пересечение). Этот алгоритм известен как алгоритм Дейкстры, он является довольно таки сложным и требует использования структуры данных очередь с приоритетом (priority queue). Однако в некоторых случаях даже такое время выполнения является слишком медленным (взять например нахождение кратчайшего пути от Нью-Йорка до Сан-Франциско - в США есть миллионы пересечений), в таких случаях программисты пытаются улучшить время выполнения с помощью так называемой эвристики. Эвристика - это приближенное значение чего-то, что имеет отношение к задаче. В задаче поиска кратчайшего пути, например, может оказаться полезным знать, как далеко находится точка от пункта назначения. Зная это можно разработать более быстрый алгоритм (например алгоритм поиска А* в некоторых случаях работает значительно быстрее чем алгоритм Дейкстры). Такой подход не всегда улучшает время выполнения алгоритма в наихудшем случае, но в большинстве реальных приложений алгоритм начинает работать быстрее.

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

На самом деле есть немало важных задач, для которых известные на сегодня алгоритмы выдают оптимальный результат слишком медленно. Наиболее известная группа из этих задач называется NP (non-deterministic polynomial). Если задача называется NP-полной или NP-трудной, то это означает, что никто не знает достаточно хорошего способа для получения оптимального решения. Кроме того, если кто-то разработает эффективный алгоритм для решения одной NP-трудной задачи, то этот алгоритм можно будет применить ко всем NP-трудным задачам.

Хорошим примером NP-трудной задачи является задача коммивояжёра. Продавец хочет посетить N городов, и он знает, сколько времени занимает перемещение из одного города в другой. Вопрос в том насколько быстро он сможет посетить все города? Самый быстрый из известных алгоритмов для решения этой задачи является слишком медленным - и многие считают, что так будет всегда - поэтому программисты ищут достаточно быстрые алгоритмы, дающие хорошее решение, но часто не оптимальное.

---

Случайные алгоритмы. Еще один подход, применяемый для решения некоторых задач, заключается в том, чтобы сделать алгоритм случайным. Данный подход не улучшает время алгоритма в худшем случае, но довольно часто хорошо работает в среднем случае. Алгоритм быстрой сортировки является хорошим примером использования рандомизации. В худшем случае, алгоритм быстрой сортировки сортирует группу элементов за O(N²), где N количество элементов. Если в этом алгоритме использовать рандомизацию, то шансы на худший случай становятся незначительно малыми, и в среднем случае алгоритм быстрой сортировки работает за время O(N*Log(N)). Другие алгоритмы даже в худшем случае гарантируют время работы O(N*Log(N)), однако они медленнее в среднем случае. Хотя оба алгоритма имеют время работы пропорциональное N*Log(N), алгоритм быстрой сортировки имеет более меньший постоянный коэффициент (constant factor) - т.е. он требует C*N*Log(N), в то время как другие алгоритмы требуют более 2*C*N*Log(N) операций.

Другой алгоритм, использующий случайные числа ищет медиану для группы чисел и его время работы в среднем случае составляет O(N). Это намного быстрее по сравнению с алгоритмом, который сортирует числа и выбирает среднее, и работает за O(N*Log(N)). Существуют детерминированные алгоритмы (не случайные) которые позволяют найти медиану за время O(N), однако случайный алгоритм проще для понимания и часто работает быстрее этих детерминированных алгоритмов.

Основная идея алгоритма поиска медианы это выбрать среди чисел случайное, и посчитать, сколько чисел в группе меньше чем выбранное число. Допустим, есть N чисел, K из них меньше или равно выбранному числу. Если K меньше чем половина N, тогда мы знаем что медиана это (N/2-K)-е число которое больше чем случайно выбранное число, так что мы отбрасываем K чисел меньших или равных случайному числу. Теперь допустим мы хотим найти (N/2-K)-е наименьшее число, вместо медианы. Алгоритм такой же, мы просто случайно выбираем число и повторяем описанные шаги.

Сжатие. Еще один класс алгоритмов предназначен для сжатия данных. Этот алгоритм не имеет ожидаемого результата (как например, алгоритм сортировки), но вместо этого делается оптимизация по некоторым критериям. В случае сжатия данных, алгоритм (например, LZW) пытается сделать так чтобы данные занимали как можно меньше байтов, но в то же время, чтобы можно было распаковывать их до первоначальной формы. В некоторых случаях этот тип алгоритмов использует те же методы что и другие алгоритмы, что приводит к хорошему результату, но неоптимальному. Например, JPG и MP3 сжимают данные таким образом, что конечный результат получается более низкого качества, чем оригинал, однако и размер меньше. MP3 сжатие не сохраняет каждую особенность оригинального аудио файла, но пытается сохранить достаточно деталей, чтобы обеспечить приемлемое качество и в то же время значительно сократить размер файла. Формат JPG следует тому же принципу, но детали существенно отличаются, т.к. целью является сжатие изображения, а не аудио.

---