Алгоритмические языки программирования
Алгоритмический язык программирования – формальный язык, используемый для записи, реализации и изучения алгоритмов. Всякий язык программирования является алгоритмическим языком, но не всякий алгоритмический язык пригоден для использования в качестве языка программирования.
Алгоритмический язык образуют три его составляющие: алфавит, синтаксис и семантика.
Алфавит – фиксированный для данного языка набор символов (букв, цифр, специальных знаков и т.д.), которые могут быть использованы при написании программы.
Синтаксис – правила построения из символов алфавита специальных конструкций, с помощью которых составляется алгоритм.
Семантика – система правил толкования конструкций языка.
Таким образом, программа составляется с помощью соединения символов алфавита в соответствии с синтаксическими правилами и с учетом правил семантики.
Методы программирования
Существуют 3 основных принципа проектирования программных алгоритмов:
нисходящее программирование;
модульное программирование;
структурное программирование
Нисходящее программирование
Метод нисходящего программирования предполагает последовательное разложение общей функции обработки данных на простые функциональные элементы («сверху-вниз»).
В результате строится иерархическая схема, отражающая состав и взаимоподчиненность отдельных функций, которая носит название функциональная структура алгоритма (ФСА) приложения.
Последовательность действий по разработке функциональной структуры алгоритма приложения:
определяются цели автоматизации предметной области и их иерархия (цель-подцель);
устанавливается состав приложений (задач обработки), обеспечивающих реализацию поставленных целей;
уточняется характер взаимосвязи приложений и их основные характеристики (информация для решения задач, время и периодичность решения, условия выполнения и др.);
определяются необходимые для решения задач функции обработки данных;
выполняется декомпозиция функций обработки до необходимой структурной сложности, реализуемой предполагаемым инструментарием.
Подобная структура приложения отражает наиболее важное – состав и взаимосвязь функций обработки информации для реализации приложений, хотя и не раскрывает логику выполнения каждой отдельной функции, условия или периодичность их вызовов.
Разложение должно носить строго функциональный характер, т.е. отдельный элемент ФСА описывает законченную содержательную функцию обработки информации, которая предполагает определенный способ реализации на программном уровне.
Функции ввода-вывода информации рекомендуется отделять от функций вычислительной или логической обработки данных.
По частоте использования функции делятся на:
однократно выполняемые;
повторяющиеся.
Степень детализации функций может быть различной, но иерархическая схема должна давать представление о составе и структуре взаимосвязанных функций и общем алгоритме обработки данных. Широко используемые функции приобретают ранг стандартных (встроенных) функций при проектировании внутренней структуры программного продукта.
Пример. Некоторые функции, например Ф2, далее неразложимы на составляющие: они предполагают непосредственную программную реализацию.
Другие функции, например Ф1, Фm, могут быть представлены в виде структурного объединения более простых функций, например Ф11, Ф12 и т.д. Для всех функций-компонентов осуществляется самостоятельная программная реализация; составные функции (типа Ф1, Фm) реализуются как программные модули, управляющие функциями-компонентами, например, в виде программ-меню.
Функциональная структура приложения
Ц - цель; пЦ - подцель; П - приложение; Ф – функция
Модульное программирование
Модуль – логически взаимосвязанная совокупность функциональных элементов, оформленных в виде отдельных программных модулей.
Модуль характеризуют:
один вход и один выход – на входе программный модуль получает определенный набор исходных данных, выполняет содержательную обработку и возвращает один набор результатных данных, т.е. реализуется стандартный принцип IPO (Input - Process - Output) – вход-процесс-выход;
функциональная завершенность – модуль выполняет перечень регламентированных операций для реализации каждой отдельной функции в полном составе, достаточных для завершения начатой обработки;
логическая независимость – результат работы программного модуля зависит только от исходных данных, но не зависит от работы других модулей;
слабые информационные связи с другими программными модулями – обмен информацией между модулями должен быть по возможности минимизирован;
обозримый по размеру и сложности программный элемент.
Таким образом, модули содержат определение доступных для обработки данных, операции обработки данных, схемы взаимосвязи с другими модулями.
Каждый модуль состоит из спецификации и тела. Спецификации определяют правила использования модуля, а тело – способ реализации процесса обработки.
При модульном программировании сначала определяются состав и подчиненность функций, а затем – набор программных модулей, реализующих эти функции.
Однотипные функции реализуются одними и теми же модулями. Функция верхнего уровня обеспечивается главным модулем; он управляет выполнением нижестоящих функций, которым соответствуют подчиненные модули.
При определении набора модулей, реализующих функции конкретного алгоритма, необходимо учитывать следующее:
каждый модуль вызывается на выполнение вышестоящим модулем и, закончив работу, возвращает управление вызвавшему его модулю;
принятие основных решений в алгоритме выносится на максимально высокий по иерархии уровень;
для использования одной и той же функции в разных местах алгоритма создается один модуль, который вызывается на выполнение по мере необходимости. В результате дальнейшей детализации алгоритма создается функционально-модульная схема (ФМС) алгоритма приложения, которая является основой для программирования.
Функционально-модульная структура приложения
Некоторые функции могут выполняться с помощью одного и того же программного модуля (например, функции Ф1 и Ф2).
Функция Ф3 реализуется в виде последовательности выполнения программных модулей.
Функция Фm реализуется с помощью иерархии связанных модулей.
Модуль n управляет выбором на выполнение подчиненных модулей.
Функция Фx реализуется одним программным модулем.
Состав и вид программных модулей, их назначение и характер использования в программе в значительной степени определяются инструментальными средствами. Например, применительно к средствам СУБД отдельными модулями могут быть:
экранные формы ввода и/или редактирования информации;
отчеты генератора отчетов;
макросы;
стандартные процедуры обработки информации;
меню, обеспечивающее выбор функции обработки и др.
Алгоритмы большой сложности обычно представляются с помощью схем двух видов:
обобщенной схемы алгоритма – раскрывает общий принцип функционирования алгоритма и основные логические связи между отдельными модулями на уровне обработки информации (ввод и редактирование данных, вычисления, печать результатов и т.п.);
детальной схемы алгоритма – представляет содержание каждого элемента обобщенной схемы с использованием управляющих структур в блок-схемах алгоритма, псевдокода либо алгоритмических языков высокого уровня.
Наиболее часто детально проработанные алгоритмы изображаются в виде блок-схем согласно требованиям структурного программирования; при их разработке используются условные обозначения согласно ГОСТ 19.003-80 ЕСПД (Единая система программной документации). Обозначения условные графические, ГОСТ 19.002-80 ЕСПД. Схемы алгоритмов и программ. Правила обозначения.
Структурное программирование
Структурное программирование основано на модульной структуре программного продукта и типовых управляющих структурах алгоритмов обработки данных различных программных модулей.
В любой типовой структуре блок, кроме условного, имеет только один вход и выход, безусловный переход на блок с нарушением иерархии запрещен.
Различают три основных типа управляющих структур ( три класса алгоритмов): линейные, ветвящиеся и циклические.
Линейный алгоритм при каждом исполнении предписывает однократное выполнение всех действий алгоритма в определенной последовательности.
Ветвящийся алгоритм описывает несколько возможных последовательностей действий и при каждом исполнении предписывает выполнение одной из последовательностей действий в зависимости от определенных условий.
Циклический алгоритм при каждом исполнении предписывает многократное выполнение одной и той же последовательности действий.
Таблица Классы алгоритмов
Тип управляющей структуры |
Применение управляющей структуры |
Линейный алгоритм |
Последовательность включает фиксированный перечень блоков (операторов). Каждый очередной блок обрабатывается после завершения предыдущего без дополнительных условий. |
Ветвящийся алгоритм |
В блоке Условие содержится условие выбора альтернативы обработки. Каждая альтернатива выполняется 1 раз; выполнение одной из двух альтернатив - обязательно. Развитие данного типа структуры является множественная альтернатива, когда последовательно проверяются условия выполнения определенных альтернатив. Если очередное условие истинно, обрабатывается соответствующая ему альтернатива, после чего происходит выход. В противном случае - переход к проверке условия следующей альтернативы. Если ни одно из условий не выполнилось, происходит выход. |
Циклический алгоритм |
Цикл характеризуется условием выхода из цикла и телом цикла. В блоке Условие задается условие определенной обработки. Если условие выполняется, цикл прерывается и осуществляется выход. Условие может содержать счетчик повторений тела цикла либо логическое условие. Тело цикла – произвольная последовательность блоков (операторов) обработки |
Основные подходы к проектированию программных алгоритмов
Процесс последовательного построения алгоритма может выглядеть следующим образом: алгоритм сначала формулируется в самых «крупных» командах, при этом в записи алгоритма могут использоваться команды, выходящие за рамки возможностей исполнителя. Затем на каждом последующем этапе отдельные детали алгоритма уточняются, при этом недоступные исполнителю команды записываются как вызов вспомогательных алгоритмов. После этого строятся вспомогательные алгоритмы. Процесс продолжается до тех пор, пока все алгоритмы не будут состоять из команд, понятных исполнителю. Такой способ построения алгоритма называется методом последовательного уточнения алгоритма (пошаговой детализацией, нисходящей разработкой). Данный подход к проектированию алгоритмов позволяет повысить качество и надежность разрабатываемых программ. Кроме того, появляется возможность использовать отдельные модули программы при решении других задач.
На практике «чистую» нисходящую разработку осуществить практически невозможно, так как выбор более конкретизированных элементов на каждой стадии должен производиться на основе представления и понимания возможностей языка реализации. Однако даже в данном случае на более поздней стадии часто обнаруживается, что некоторый выбор, сделанный ранее, был неверным. Это приводит к необходимости разработки новых и корректировки уже имеющихся модулей.
Другой подход к созданию программ называется восходящей разработкой. При этом осуществляется последовательное построение программы из уже имеющихся элементов, начиная с примитивов, предоставляемых выбранным языком программирования. Этот процесс заканчивается получением требуемой готовой программы. На каждом этапе из имеющихся элементов строятся новые более мощные (в контексте разрабатываемой программы) элементы. Они в свою очередь используются на следующем этапе для построения еще более сложных элементов и так далее до тех пор, пока не будут получены элементы, из которых можно непосредственно составить требуемую программу. На практике восходящая разработка в чистом виде невозможна; построение каждого нового элемента должно сопровождаться «просмотром вперед» с целью проверки, выполняются ли все требования, предъявляемые к разрабатываемой программе. Но даже при таком подходе на более позднем этапе часто обнаруживается, что использованная ранее последовательность построения была выбрана неправильно и требует корректировки.
Таким образом, на практике при разработке алгоритмов обычно используется сочетание методов нисходящего и восходящего проектирования.
Использование вышеназванных подходов позволило создать огромное количество разнообразных алгоритмов, и пришлось обратить серьезное внимание на вопросы их эффективности. В значительной степени эффективность алгоритма зависит от его сложности — количественной характеристики, указывающей, сколько времени работает алгоритм (временная сложность) либо какой объем памяти необходим для его выполнения (емкостная сложность). Сложность рассматривается в основном для алгоритмических моделей, поскольку в них время и память присутствуют в явном виде.
Физическое время выполнения алгоритма – это величина, равная произведению n и t, где n число действий (элементарных шагов, команд); t –среднее время выполнения одного действия. Число шагов и определяется описанием алгоритма в данной алгоритмической модели и не зависит от физической реализации модели; t— величина физическая и зависит от скорости сигналов в элементах и узлах ЭВМ, Поэтому объективной математической характеристикой трудоемкости алгоритма (его временной сложности) в данной модели является число действий.
Емкостная сложность (трудоемкость) алгоритма определяется числом ячеек памяти, используемых в процессе его исполнения. Эта величина не может превосходить числа действий n, умноженного на определенную константу (число ячеек, используемых в данной модели на одном шаге). В свою очередь число шагов может сколь угодно сильно превосходить объем памяти (за счет циклов по одним и тем же ячейкам). Следует отметить, что проблемы памяти технически преодолеваются легче, чем проблемы быстродействия, которое имеет физический предел — скорость распространения физических сигналов (300 тыс. км/с). Поэтому трудоемкость (временная сложность) считается более существенной характеристикой алгоритма.
Трудоемкость алгоритма, как и другие виды сложности, не является постоянной величиной, а зависит от размерности задачи. Под размерностью задачи понимается либо объем памяти, необходимой для записи данных, либо характеристики задачи, от которых зависит этот объем. В задачах обработки графов размерностью может считаться число вершин или дуг графа, в задачах преобразования логических выражений — число букв в выражении и т. д.
Задачи большой размерности зачастую нецелесообразно решать последовательным перебором всех возможных вариантов решения, поэтому в таких случаях используют алгоритмы, повышающие скорость получения конечного результата.
Один из методов построения алгоритма состоит в том, чтобы решение исходной, сложной задачи свести к поочередному решению более простых подзадач. При этом мы исходим из двух предположений. Во-первых, совокупная трудоемкость решения подзадач оказывается заметно меньшей, чем для общей задачи. Во-вторых, частные решения подзадач удается объединить в решение общее. Этот механизм называют либо методом частных целей, либо методом декомпозиции задачи и композиции решений.
Метод (подъем) ветвей и границ также предназначен для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. По существу, метод является вариацией полного перебора с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений.
Общая идея метода может быть описана на примере поиска минимума и максимума функции f(x) на множестве допустимых значений x. Функция f и x могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).
Процедура ветвления состоит в разбиении области допустимых решений на подобласти меньших размеров. Процедуру можно рекурсивно применять к подобластям. Полученные подобласти образуют дерево, называемое деревом поиска или деревом ветвей и границ. Узлами этого дерева являются построенные подобласти.
Процедура нахождения оценок заключается в поиске верхних и нижних границ для оптимального значения на подобласти допустимых решений.
В основе метода ветвей и границ лежит следующая идея (для задачи минимизации): если нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения (правило отсева). Обычно, минимальную из полученных верхних оценок записывают в глобальную переменную m; любой узел дерева поиска, нижняя граница которого больше значения m, может быть исключен из дальнейшего рассмотрения.
Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является минимумом функции и достигается на соответствующей подобласти.
Эвристический алгоритм (эвристика) – алгоритм, который даёт приемлемое решение задачи в большинстве практически значимых случаев, однако при этом его правильность математически не доказана. В действительности может быть доказано обратное — то, что эвристический алгоритм формально неверен. При этом он может давать неверный результат только в отдельных (достаточно редких) случаях или же давать неточный, но всё же приемлемый результат.
Проще говоря, эвристика — это не полностью математически обоснованный (или даже «не совсем корректный»), но при этом практически полезный алгоритм.
Эвристические алгоритмы широко применяются для решения задач высокой вычислительной сложности (задачи, принадлежащие классу NP), то есть вместо полного перебора вариантов, занимающего существенное время, а иногда технически невозможного, применяется значительно более быстрый, но недостаточно обоснованный теоретически, алгоритм. В областях искусственного интеллекта, таких, как распознавание образов, эвристические алгоритмы широко применяются также и по причине отсутствия общего решения поставленной задачи. Различные эвристические подходы применяются в антивирусных программах, компьютерных играх и т.д.
Рекурсия – способ общего определения объекта или действия через себя, с использованием ранее заданных частных определений. Рекурсия используется, когда можно выделить самоподобие задачи. Применение рекурсивных алгоритмов позволяет во многих случаях более рационально использовать ресурсы вычислительной машины.
Итерация (метод последовательного приближения) – это организация обработки данных, при которой действия повторяются многократно, не приводя при этом к вызовам самих себя. Когда какое-то действие необходимо повторить большое количество раз, в программировании используются циклы. Количество повторений цикла определяется требуемой точностью решения поставленной задачи, которая увеличивается с каждым последующим циклом.