Слово «алгоритм» появилось в результате искаженного перевода с арабского на европейские языки имени узбекского ученого IX века Аль Хорезми, который изложил правила арифметических действий над числами в позиционной десятичной системе счисления. Эти правила и назвали алгоритмами.
Алгоритм – это система точно сформулированных правил, определяющих процесс преобразования доступных исходных данных (входной информации) в желаемый результат (выходную информацию) за конечное число шагов.
Алгоритм имеет ряд обязательных свойств (атрибутов):
- дискретность – предусматривает разбиение процесса обработки информации на более простые этапы (шаги выполнения);
- определенность (или детерминированность) – характеризует однозначность выполнения каждого отдельного шага преобразования информации;
- результативность (или конечность) – предполагает завершение работы алгоритма в целом за конечное число шагов;
- массовость – характеризует пригодность алгоритма для решения определенного класса задач.
Процесс сведения задачи к последовательности этапов, выполняемых друг за другом так, что результаты предыдущих этапов используются при выполнении последующих, называется алгоритмизацией. В процессе алгоритмизации осуществляется выбор метода решения задачи с указанием необходимых расчетных формул, логических условий, соотношений для контроля достоверности выходных результатов, а также формы представления исходной информации с учетом специфики ЭВМ.
Программа– это алгоритм, записанный на специальном алгоритмическом языке программирования, который может восприниматься ЭВМ.
Исполнитель алгоритма – это автоматическое устройство (ЭВМ, робот, станок с ЧПУ) или человек, выполняющие определенный набор команд.
Оформить (представить) алгоритм можно несколькими способами: словесным, формульно-словесным, графическим (в виде блок схемы), операторным, в виде таблицы решений и на алгоритмическом языке.
Словесный способ предполагает словесное (без формул и таблиц) описание алгоритма, в принципе, с любой степенью детализации.
Формульно-словесный способ более компактный. В нем словесные описания сочетаются с формулами.
Графический способ получил наибольшее распространение. В этом способе алгоритм представляется в виде схемы, состоящей из элементов символов, отражающих отдельные операции технологического процесса обработки данных и отдельные вычислительные операции.
Операторный способ предполагает представлять алгоритм в виде последовательности операторов. Каждое элементарное предписание можно считать оператором. Из этого следует из того, что дискретный алгоритм, являющийся совокупностью элементарных предписаний (инструкций), можно рассматривать как совокупность элементарных операторов. Для элементарных операторов вводятся обозначения, например, арифметический оператор - АV.
Табличный способ предполагает представление алгоритмов в виде таблицы решений и, в основном, носит вспомогательный характер.
Основные структуры алгоритмов– это ограниченный набор блоков и стандартных способов их соединения для выполнения типичных последовательных действий. Описание этих структур приведено ниже.
Следование (рисунок 7.2).Структура предполагаетпоследовательное расположение блоков и групп блоков операторов.
Рисунок 7.2. - Структура «Следование».
Цикл «До»(рисунок 7.3). Применяется при необходимости выполнить какие-либо вычисления несколько раз до выполнения некоторого условия.
Цикл «Пока» (рисунок 7.4).Структура этого цикла отличается от цикла «До» тем, что проверка условия производится до выполнения тела цикла.
Разветвление (рисунок 7.5). Структура применяется, когда в зависимости от условия нужно выполнить либо одно, либо другое действие.
Рисунок 7.3. - Структура цикла «До».
Рисунок 7.4. - Структура цикла «Пока».
Рисунок 7.5. - Структура «Разветвление».
Обход. Эточастный случай разветвления, когда одна из ветвей не содержит никакого действия.
Множественный выбор (рисунок 7.6) является обобщением разветвления, когда в зависимости от значения переменной (I) выполняется одно из нескольких действий (S1, S2, Sn).
Рисунок 7.6. - Множественный выбор.
7.4. Технологии программирования
Технология программирования – это методы и средства создания программ. Эффективная технология программирования предполагает использование стандартов, прогрессивных инструментальных средств разработки, а также специальных методов и приёмов организации работ. Различают две технологии: структурное программирование;объектно-ориентированное программирование.
Структурное программирование является классической технологией разработки алгоритмов и программ. К его основным принципам относятся:
- разработка программ «сверху вниз»методом пошаговой детализации;
- модульное программирование;
- структурное кодирование.
Метод пошаговой детализациипредполагает последовательное разложение общей функции обработки данных на простые функциональные элементы («сверху - вниз»).
Первоначально продумывается общая структура алгоритма без детальной проработки отдельных его частей, но при этом используются лишь основные структуры алгоритмов (следования, ветвления, цикла). Далее прорабатываются (детализируются) отдельные блоки. Этот процесс производится до тех пор, пока не будут получены блоки описанных выше трёх типов, которые детализируются до элементарных команд или операторов языка программирования. Эта технология называется методом последовательной (пошаговой) детализации или методом «сверху - вниз».
Модульное программирование основано на понятии модуля – это самостоятельная часть программы, имеющая определенное назначение и обеспечивающая выполнение одной функции обработки автономно от других программных модулей. Модуль характеризуется:
- наличием логической структуры (алгоритма);
- функциональной завершённостью (модуль выполняет, как правило, одну функцию);
- независимостью (результат работы программного модуля зависит только от исходных данных и не зависит от работы других модулей);
- использованием в одном или более контекстах;
- обозримым по размеру и сложности программным элементом.
Каждый модуль состоит из спецификации и тела. Спецификация определяет правила использования модуля, а тело – способ реализации процесса обработки. Состав и вид программных модулей, их назначение и характер использования в программе определяются инструментальными средствами.
Среди множества модулей различают:
- головной модуль - управляет запуском программного продукта;
- управляющий модуль - обеспечивает вызов модулей на обработку;
Структурное кодирование состоит в получении правильной программы из некоторых простых логических структур. Оно базируется на строго доказанной теореме о структурировании, которая утверждает, что любую правильную программу (с одним входом, одним выходом, без зацикливания и недостижимых команд) можно написать с использованием только следующих основных логических структур: линейной (следование); нелинейной (развилка) и циклической (цикл или повторение). Допустимые элементы структурного программирования изображены на рисунках выше.
Объектно-ориентированное программирование представляет собой новый этап развития концепции построения языков программирования. Здесь получили дальнейшее развитие принципы структурного программирования – структуризация программ и данных, модульность и т. д.
Базовымипонятиями объектно-ориентированного подхода являются: объект, свойство объекта, метод обработки, событие, класс объектов.
Объект – это совокупность свойств (параметров) определённых сущностей (отношений) и методов их обработки (программных средств).
Свойство – это характеристика объекта и его параметров. Все объекты наделены определёнными свойствами, которые в совокупности выделяют объект из множества других объектов.
Метод – это программа действий над объектом или его свойствами.
Событие – это характеристика изменения состояния объекта.
Класс – это совокупность объектов, характеризующихся общностью применяемых методов обработки или свойств.
Один объект может выступать объединением вложенных в него по иерархии других объектов. Программируя объект, его состояние можно хранить в наборе переменных, а методы реализовать в форме процедур. Объект представляет собой единство состояния и методов.
Попадая в среду развитого алгоритмического языка, понятия объектно-ориентированного программирования оформляются в системе этого языка. Например, в Turbo Pascal объект – это особый тип данных, а экземпляры этого объекта – переменные этого типа. Состояние характеризуется значениями полей объекта. Методами объекта являются ассоциированные с ним функции и процедуры, которым доступны поля. Передача сообщений объекту происходит в виде вызовов его методов с заданными параметрами.
Существуют различные методики, которые должны обеспечить выполнение важнейших принципов объектного подхода: инкапсуляция (замыкание) свойств данных и программ в объекте, наследование и полиморфизм.
Инкапсуляция означает сочетание структур данных с методами их обработки в абстрактных типах данных – классах объектов.
Класс может иметь образованные от него подклассы. При построении подклассов осуществляется наследование данных и методов обработки объектов исходного класса. Механизм наследования позволяет переопределить или добавить новые данные и методы их обработки, создать иерархию классов.
Подполиморфизмом подразумевается способность объекта реагировать на запрос (вызов метода) сообразно своему типу, при этом одно и то же имя метода может использоваться для различных классов объектов.
