Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ЛЕКЦИЯ

ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ

ПЛАН

Введение

1. Основы алгоритмизации

1.1 Понятие алгоритма и его свойства

1.2 Способы представления алгоритмов

2. Эволюция технологий программирования

Приложения

Выводы

ВВЕДЕНИЕ

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

ЭВМ (computer) - это комплекс технических средств, предназначенных для автоматической обработки информации в процессе решения задач, представленных программами и данными в цифровой форме.

На лекции 5 мы рассмотрели понятие программного обеспечения и его классификацию.

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

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

Инструментальное программное обеспечение служит для создания программ и включает специализированные программные продукты, которые являются инструментальными средствами разработчика. Программные продукты данного класса поддерживают все технологические этапы процесса проектирования, программирования (кодирования), отладки и тестирования создаваемых программ. Пользователями инструментального программного обеспечения являются системные и прикладные программисты.

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

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

Целью данной лекции является изучение основ алгоритмизации, уяснение понятия и этапов эволюции технологии программирования.

1. ОСНОВЫ АЛГОРИТМИЗАЦИИ

1.1 Понятие алгоритма и его свойства

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

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

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

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

Понятие алгоритма, раскрывающее его сущность на интуитивном уровне, следующее:

Алгоритм - точно определенное правило действий, для которого задано указание, как и в какой последовательности это правило необходимо применять к исходным данным задачи, чтобы получить ее решение за конечное число шагов^** Название «алгоритм» произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в 783-850 гг. В своей книге «Об индийском счете» он изложил правила записи натуральных чисел с помощью арабских цифр и правила действий над ними «столбиком». В XII веке эта книга была переведена на латынь и получила широкое распространение в Европе..

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

Формула для нахождения корней квадратного уравнения

также является своеобразной формой записи алгоритма.

Следует иметь в виду, что не для всякой задачи существует алгоритм ее решения, например, в криптографии на этом основано построение криптосистем с открытым ключом.

Вполне очевидно, что с практической точки зрения особую ценность составляют алгоритмы, приводящие к решению задачи наиболее кратким путем. До появления ЭВМ алгоритмы, для осуществления которых необходимо было выполнить сотни тысяч элементарных операций, представляли лишь теоретический интерес. С появлением ЭВМ исследования алгоритмической разрешимости различных классов задач приобрели непосредственное практическое значение.

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

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

Основные свойства алгоритмов следующие:

1. Детерминированность (определенность) -- однозначность результата процесса при заданных исходных данных. Благодаря этому свойству выполнение алгоритма носит механический хаpактеp и не требует никаких дополнительных указаний или сведений о решаемой задаче.

2. Дискретность (прерывность) -- алгоритм должен представлять процесс решения задачи как последовательное выполнение элементарных шагов, возможность выполнения которых человеком или машиной не вызывает сомнения.

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

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

1.2 Способы представления алгоритмов

На практике наиболее распространены следующие формы представления алгоритмов:

· словесная - запись алгоритма на естественном языке;

· графическая - изображение алгоритма в виде схемы, состоящей из графических символов;

· аналитическая - запись алгоритма в виде последовательности формул;

· псевдокодом - полуформализованное описание алгоритма на условном алгоритмическом языке, включающем как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.;

· программная - запись алгоритма в виде текста на одном из языков программирования.

Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных в произвольном изложении на естественном языке.

Пример 1. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Эвклида).

Алгоритм можно описать так:

1. Задать два числа.

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

3. Определить большее из чисел.

4. Заменить большее из чисел разностью большего и меньшего из чисел.

5. Повторить алгоритм с шага 2.

Этот алгоритм применим к любым натуральным числам и должен приводить к решению поставленной задачи.

Словесный способ не имеет широкого распространения, так как такие описания:

· строго не формализуемы;

· страдают многословностью записей;

· допускают неоднозначность толкования отдельных предписаний.

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

Такое представление называется схемой алгоритма (иногда называют блок-схемой).

Схема алгоритма - графическое изображение его структуры, в котором каждый этап процесса обработки данных представляется в виде различных геометрических фигур (примитивов).

В таблице 1.1 приведены часто употребляемые графические примитивы в схемах алгоритмов.

Таблица 1.1. Графические примитивы схем алгоритмов

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

Основные правила составления схемы алгоритма сводятся к следующему:

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

2. Внутри примитива дается краткое описание соответствующего шага.

3. Любой шаг или поток можно сопроводить пояснением с помощью примитива «Комментарий».

4. Примитивам присваиваются порядковые номера, проставляемые в разрыве линии контура в левом верхнем углу изображения.

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

6. Расстояние между параллельными линиями потока должно быть не менее 3 мм, а между другими символами - не менее 5 мм.

7. Линию потока можно обрывать, используя на месте обрыва примитив «Узел» в пределах одной страницы или примитив «Ссылка на другую страницу», если надо указать переход на другую страницу.

8. Размеры примитивов фиксированы. Если через b обозначить ширину элемента, а через а его высоту, то размер b = 1,5а, причем а должно принимать значения 10, 15, 20 мм. Допускается увеличивать размер а на величину, кратную 5.

Составление схем алгоритмов регламентируется двумя ГОСТами:

· ГОСТ 19.002-80 соответствует международному стандарту ИСО 2636-73 и определяет правила составления схем алгоритмов;

· ГОСТ 19.003-80 соответствует международному стандарту ИСО 1028-73 и регламентирует использование графических примитивов.

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

Пример 2. Необходимо составить алгоритм вычисления суммы элементов вектора , т.е.

.

Для определения суммы применим алгоритм ее накопления, используя рекуррентное соотношение

S_i := S_i-1 + a_i; S₀ = 0; i := 1, 2, ..., n,

где S_i -- текущее значение суммы;

S_i-1 -- предыдущее ее значение;

S₀ -- начальное значение суммы;

a_i -- значение текущего элемента вектора.

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

Схема алгоритма приведена на рис. 1.1. Поясним ее.

1. Схема начинается с символа «Пуск-останов». Каждый вычислительный процесс имеет начало, и это отображается на схеме.

2. Начальные данные вводятся в память компьютера. Для обозначение этой операции используется символ «Ввода-вывода», внутри которого указываются, какие элементы вводятся.

3. Сумме присваивается начальное значение, равное нулю (S:=0). Это означает пересылку 0 в область памяти, предназначенную для накопления суммы. Операция на схеме отображается символом «Процесс». Принятое обозначение суммы S расшифровывается символом «Комментарий».

4. Индексу i, определяющему порядковый номер элемента, присваивается значение 1. При i = 1 происходит обращение к первому элемента вектора, т.е. а₁.

5. К сумме S (на первом шаге i = 1, S = 0 и a_i = а₁) прибавляется значение элемента вектора a_i (S := S + a_i). В области памяти S записывается новое значение суммы.

6. С увеличением значения i на 1 (i = i + 1) определяется порядковый номер следующего элемента вектора.

7. Количество элементов вектора равно n. Отсюда, операция суммирования S := S + a_i должна повторяться n раз, для чего осуществляется проверка: продолжать вычисление суммы или нет. Для выбора направления вычислений применяется символ «Решение». Внутри него указывается проверка условия i <= n. Если значение i не превысило своего максимального значения n, то операция вычисления суммы повторяется (переход к шагу 5), в противном случае осуществляется переход к шагу 8.

8. Осуществляется вывод полученной суммы S. Эта операция отображается на схеме символом «Ввода-вывода», внутри которой указывается, что именно выводится.

9. Схема заканчивается символом «Пуск-останов».

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

Пример 3. Рассмотрим алгоритм вычисления корней квадратного уравнения .

1. Ввести исходные данные a, b, c.

2. Вычислить .

3. Если d 0, то

§ ;

§ ;

§ ;

§ Вывести результаты на печать;

§ Конец вычислений.

иначе

§ Вывести сообщение «Действительных корней нет»;

§ Конец вычислений.

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

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

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

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

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

алг название алгоритма (аргументы и результаты) дано условия применимости алгоритма надо цель выполнения алгоритма нач описание промежуточных величин последовательность команд (тело алгоритма) кон

Рис. 1.3. Общий вид алгоритма на псевдокоде

Часть алгоритма от слова алг до слова нач называется заголовком, а часть, заключенная между словами нач и кон -- телом алгоритма.

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

Пример 4. Запись на псевдокоде алгоритма вычисления суммы квадратов целых чисел от 1 до n.

алг Сумма квадратов (арг цел n, рез цел S)

дано | n > 0

надо | S = 1*1 + 2*2 + 3*3 + ... + n*n

нач цел i

ввод n; S:=0

нц для i от 1 до n

S:=S+i*i

кц

вывод "S = ", S

кон

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

Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык принято называть языком программирования, а запись алгоритма на этом языке -- программой для компьютера.

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

По этому критерию можно выделить следующие уровни алгоритмических языков (языков программирования):

· машинные;

· машинно-оpиентиpованные (ассемблеpы);

· машинно-независимые (языки высокого уровня).

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

Языки высокого уровня делятся на:

· процедурные (алгоритмические) (Basic, Pascal, C и др.), предназначенные для однозначного описания алгоритмов (для решения задачи процедурные языки требуют в той или иной форме явно записать процедуру ее решения);

· логические (Prolog, Lisp и др.), ориентированные не на разработку алгоритма решения задачи, а на систематическое и формализованное описание задачи с тем, чтобы решение следовало из составленного описания;

· объектно-ориентированные (Object Pascal, C++, Java и др.), в основе которых лежит понятие объекта, сочетающего в себе данные и действия над нами. Программа на объектно-ориентированном языке, решая некоторую задачу, по сути описывает часть мира, относящуюся к этой задаче. Описание действительности в форме системы взаимодействующих объектов естественнее, чем в форме взаимодействующих процедур.

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

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

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

Пример 5. Программа на языке ассемблера для IBM PC, вычисляющая значение a = b + c для целых a, b и c:

Программа	Пояснение
MODEL SMALL DATA b DW 5 c DW 3 a DW ? CODE begin MOV AX,@DATA MOV DS,AX MOV AX,B ADD AX,C MOV A,AX MOV AH,4CH INT 21H END begin	Директива задает механизм распределения памяти под данные и команды. Директива определяет начало участка программы с данными. Директивы DW задают типы переменных и их значения. Директива CODE определяет начало участка программы с командами. Команды MOV AX,@DATA и MOV DS,AX записывают адрес сегмента данных в регистр DS (Data Segment). Для вычисления a используются команды MOV AX,B, ADD AX,C и MOV A,AX. В директиве END задана метка первой выполняемой программы программы begin.

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

Основные преимущества алгоритмических языков перед машинными:

· алфавит алгоритмического языка значительно шире алфавита машинного языка, что существенно повы шает наглядность текста программы;

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

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

· требуемые операции задаются с помощью общепринятых математических обозначений;

· данным в алгоритмических языках присваиваются индивидуальные имена, выбираемые программистом;

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

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

Алгоритмический язык определяется заданием алфавита исходных символов, точным описанием его синтаксиса (грамматики) и семантики.

· Алфавит -- это фиксированный для данного языка набор основных символов, т.е. «букв алфавита», из которых должен состоять любой текст на этом языке -- никакие другие символы в тексте не допускаются.

· Синтаксис -- это набор правил, устанавливающих, какие комбинации символов являются осмысленными и правильными предложениями на этом языке.

· Семантика определяет смысловое значение предложений языка. Она устанавливает, какие последовательности действий описываются теми или иными фразами языка и, в конечном итоге, какой алгоритм определен данным текстом на алгоритмическом языке.

Каждое понятие алгоритмического языка подразумевает некоторую синтаксическую единицу (конструкцию) и определяемые ею свойства программных объектов или процесса обработки данных.

Понятие языка определяется во взаимодействии синтаксических и семантических правил.

Синтаксические правила показывают, как образуется данное понятие из других понятий и букв алфавита, а семантические правила определяют свойства данного понятия

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

1. Имена (идентификаторы) -- употpебляются для обозначения объектов пpогpаммы (пеpеменных, массивов, функций и дp.).

2. Опеpации. Типы операций:

· аpифметические опеpации: +, , *, / и дp.;

· логические опеpации и (AND), или (OR), не (NOT);

· опеpации отношения <, >, <=, >=, =, <>;

· опеpация конкатенации (присоединения, сцепки) символьных значений дpуг с другом с образованием одной длинной строки; изображается знаком +.

3. Данные -- величины, обpабатываемые пpогpаммой. Имеется тpи основных вида данных:

· Константы -- данные, зафиксированные в тексте программы и не изменяемые в процессе ее выполнения. К ним относятся:

- числовые константы: 7.5, 12;

- логические: да (истина, true), нет (ложь, false);

- символьные (содержат ровно один символ) "А", "+";

- литеpные (содержат произвольное количество символов) "a0", "Мир", ""(пустая строка).

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

· Массивы -- последовательности однотипных элементов, число которых фиксировано и которым присвоено одно имя. Положение элемента в массиве однозначно определяется его индексами (одним, в случае одномерного массива, или несколькими, если массив многомерный).

4. Выpажения -- пpедназначаются для выполнения необходимых вычислений, состоят из констант, пеpеменных, указателей функций (напpимеp, exp(x)), объединенных знаками опеpаций.

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

Различают выражения:

· арифметические - служат для определения одного числового значения. Например, (1+sin(x))/2;

· логические - описывают некоторые условия, которые могут удовлетворяться или не удовлетворяться. Логическое выражение может принимать только два значения -- "истина" или "ложь" (да или нет). Например, логическое выражение x*x + y*y < r*r определяет принадлежность точки с координатами (x, y) внутренней области круга радиусом r c центром в начале координат. При x=1, y=1, r=2 значение этого выражения -- "истина", а при x=2, y=2, r=1 -- "ложь";

· строковые (литерные) - их значениями являются текcты. В строковые выражения могут входить литерные и строковые константы, литерные и строковые переменные, литерные функции, разделенные знаками операции конкатенации. Например, А + В означает присоединение строки В к концу строки А. Если А = "куст ", а В = "зеленый", то значение выражения А + В есть "куст зеленый".

5. Операторы (команды) -- это наиболее крупные и содержательные понятия языка: каждый оператор представляет собой законченную фразу языка и определяет некоторый вполне законченный этап обработки данных. В состав опеpатоpов входят:

· ключевые слова;

· данные;

· выpажения и т.д.

Операторы подpазделяются на исполняемые и неисполняемые. Неисполняемые опеpатоpы пpедназначены для описания данных и стpуктуpы пpогpаммы, а исполняемые -- для выполнения pазличных действий (напpимеp, опеpатоp пpисваивания, опеpатоpы ввода и вывода, условный оператор, операторы цикла, оператор процедуры и дp.).

6. Стандартные функции - заранее запрограммированные и встроенные в транслятор языка подпрограммы вычисления часто употребляемых функций.

В табл. 1.2 приведены стандартные функций языка Turbo Pascal.

Таблица 1.2. Примеры стандартных математических функций

Название и обозначение функции	Указатель функции
Абсолютная величина (модуль)	| х |	abs(x)
Корень квадратный		sqrt(x)
Возведение в квадрат	х2	sqr(х)
Натуральный логарифм	ln x	ln(x)
Экспонента	ex	exp(x)
Синус (угол в радианах)	sin x	sin(x)
Косинус (угол в радианах)	cos x	cos(x)
Арктангенс (главное значение в радианах)	arctg x	arctan(х)
Целая часть числа		int(x), trunc(х)
Дробная часть числа		frac(x)
Округленное до целого число. При х>=0 round(х) означает trunc(х+0.5), при x<0 - trunc(x-0.5)		round(х)
Число «пи»		Pi

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

2. ЭВОЛЮЦИЯ ТЕХНОЛОГИЙ ПРОГРАММИРОВАНИЯ

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

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

· перечисление условий, при которых выполняется та или иная операция;

· описания самих операций, где для каждой операции определены исходные данные, результаты, а также инструкции, нормативы, стандарты, критерии и методы оценки и т.п. (рис. 2.1).

Технология также определяет способ описания модели проектируемой системы на конкретном этапе разработки.

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

Рассмотрим технологии в историческом контексте, выделяя основные этапы развития программирования, как науки.

Первый этап - «стихийное» программирование (конец 40-х - средина 60-х годов XX в.) характеризовался практическим отсутствием сформулированных технологий, и программирование фактически было искусством. Программы имели простейшую структуру: собственно программа на машинном языке плюс обрабатываемых ею данных (рис. 2.2).

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

Появление ассемблеров позволило вместо двоичных или 16-ричных кодов использовать символические имена данных и мнемоники кодов операций. В результате программы стали более «читаемыми».

Создание языков программирования высокого уровня (FORTRAN, ALGOL) существенно упростило программирование вычислений, снизив уровень детализации операций. Это, в свою очередь, позволило увеличить сложность программ.

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

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

Слабым местом такой архитектуры было то, что при увеличении количества подпрограмм возрастала вероятность искажения части глобальных данных какой-либо подпрограммой. Например, подпрограмма поиска корней уравнения на заданном интервале по методу деления отрезка пополам меняет величину интервала. Если при выходе из подпрограммы не предусмотреть восстановления первоначального интервала, то в глобальной области окажется неверное значение интервала. Чтобы сократить количество таких ошибок, было предложено в подпрограммах размещать локальные данные (рис. 2.4).

алгоритм язык программирование

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

В начале 60-х годов XX в. разразился «кризис программирования». Он выражался в том, что фирмы, взявшиеся за разработку сложного ПО (как, например, операционные системы), срывали все сроки завершения проектов. Проект устаревал раньше, чем был готов к внедрению, увеличивалась его стоимость, и в результате многие проекты так никогда и не были завершены.

Объективно это было вызвано несовершенством технологии программирования. Прежде всего, стихийно использовалась разработка «снизу-вверх» - подход, при котором вначале проектировали и реализовывали сравнительно простые подпрограммы, из которых затем пытались построить сложную программу. В отсутствии четких моделей описания подпрограмм и методов их проектирования создание каждой подпрограммы превращалось в непростую задачу, интерфейсы подпрограмм получались сложными, и при сборке программного продукта выявлялось большое количество ошибок согласования. Исправление таких ошибок, как правило, требовало серьезного изменения уже разработанных подпрограмм, что еще более осложняло ситуацию, так как при этом в программу часто вносились новые ошибки, которые также необходимо было исправлять... В конечном итоге процесс тестирования и отладки программ занимал более 80% времени разработки, если вообще когда-нибудь заканчивался. На повестке дня самым серьезным образом стоял вопрос разработки технологии создания сложных программных продуктов, снижающей вероятность ошибок проектирования.

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

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

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

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

Поддержка принципов структурного программирования была заложена в основу процедурных языков программирования. Как правило, они включали основные «структурные» операторы передачи управления, поддерживали вложение подпрограмм, локализацию и ограничение области «видимости» данных. К наиболее известным языкам этой группы относятся PL/1, ALGOL-68, Pascal, С.

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

Модульное программирование предполагает выделение групп подпрограмм, использующих одни и те же глобальные данные в отдельно компилируемые модули (библиотеки подпрограмм), например, модуль графических ресурсов, модуль подпрограмм вывода на принтер (рис. 2.5). Связи между модулями при использовании данной технологии осуществляются через специальный интерфейс, в то время как доступ к реализации модуля (телам подпрограмм и некоторым «внутренним» переменным) запрещен. Эту технологию поддерживают современные версии языков Pascal и С (C++), языки Ада и Modula.

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

Практика показала, что структурный подход в сочетании с модульным программированием позволяет получать достаточно надежные программы, размер которых не превышает 100 000 операторов. Узким местом модульного программирования является то, что ошибка в интерфейсе при вызове подпрограммы выявляется только при выполнении программы (из-за раздельной компиляции модулей обнаружить эти ошибки раньше невозможно). При увеличении размера программы обычно возрастает сложность межмодульных интерфейсов, и с некоторого момента предусмотреть взаимовлияние отдельных частей программы становится практически невозможно. Для разработки программного обеспечения большого объема было предложено использовать объектный подход.

Третий этап - объектный подход к программированию (середина 80-х - конец 90-х годов XX в.) - определяется как технология создания сложного ПО, основанная на представлении программы в виде совокупности объектов, каждый из которых является экземпляром определенного типа (класса), а классы образуют иерархию с наследованием свойств. Взаимодействие программных объектов в такой системе осуществляется путем передачи сообщений (рис. 2.6).

Объектная структура программы впервые была использована в языке имитационного моделирования сложных систем Simula, появившемся еще в 60-х годах XX в. Естественный для языков моделирования способ представления программы получил развитие в другом специализированном языке моделирования - Smalltalk (70-е годы XX в.), а затем был использован в новых версиях универсальных языков программирования, таких, как Pascal, C++, Modula, Java.

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

Бурное развитие технологий программирования, основанных на объектном подходе, позволило решить многие проблемы. Так были созданы среды, поддерживающие визуальное программирование, например, Delphi, C++ Builder, Visual C++ и т.д. При использовании визуальной среды у программиста появляется возможность проектировать некоторую часть, например, интерфейсы будущего продукта, с применением визуальных средств добавления и настройки специальных библиотечных компонентов. Результатом визуального проектирования является заготовка будущей программы, в которую уже внесены соответствующие коды.

Использование объектного подхода имеет много преимуществ, однако его конкретная реализация в объектно-ориентированных языках программирования, таких, как Pascal и C++, имеет существенные недостатки:

· фактически отсутствуют стандарты компоновки двоичных результатов компиляции объектов в единое целое даже в пределах одного языка программирования;

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

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

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

Компонентный подход лежит в основе технологий, разработанных на базе COM (Component Object Model - компонентная модель объектов), и технологии создания распределенных приложений CORBA (Common Object Request Broker Architecture - общая архитектура с посредником обработки запросов объектов). Эти технологии используют сходные принципы и различаются лишь особенностями их реализации.

Технология СОМ фирмы Microsoft является развитием технологии OLE (Object Linking and Embedding - связывание и внедрение объектов), которая используется в ОС Windows для создания составных документов. Технология СОМ определяет общую парадигму взаимодействия программ любых типов: библиотек, приложений, операционной системы, т.е. позволяет одной части ПО использовать функции (службы), предоставляемые другой, независимо от того, функционируют ли эти части в пределах одного процесса, в разных процессах на одном компьютере или на разных компьютерах (рис. 2.7). Модификация СОМ, обеспечивающая передачу вызовов между компьютерами, называется DCOM (Distributed COM - распределенная СОМ).

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

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

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

· локальный сервер - создается отдельным процессом (модулем), который работает на одном компьютере с клиентом;

· удаленный сервер - создается процессом, который работает на другом компьютере.

Взаимодействие клиента и сервера обеспечивается базовыми механизмами СОМ или DCOM, поэтому клиенту безразлично местонахождение объекта.

На базе технологии СОМ и ее распределенной версии DCOM были разработаны компонентные технологии, решающие различные задачи разработки программного обеспечения:

· OLE-automation или просто Automation (автоматизация) -- технология создания программируемых приложений, обеспечивающая программируемый доступ к внутренним службам этих приложений. Вводит понятие диспинтерфейса (dispinterface) - специального интерфейса, облегчающего вызов функций объекта. Эту технологию поддерживает, например, Microsoft Excel, предоставляя другим приложениям свои службы.

· ActiveX - технология, построенная на базе OLE-automation, предназначена для создания ПО как сосредоточенного на одном компьютере, так и распределенного в сети. Предполагает использование визуального программирования для создания компонентов - элементов управления ActiveX. Полученные таким образом элементы управления можно устанавливать на компьютер дистанционно с удаленного сервера, причем устанавливаемый код зависит от используемой операционной системы. Это позволяет применять элементы управления ActiveX в клиентских частях приложений Интернет. Основными преимуществами технологии ActiveX, обеспечивающими ей широкое распространение, являются:

- быстрое написание программного кода;

- открытость и мобильность;

- возможность написания приложений с использованием знакомых средств разработки, например, Visual Basic, Visual C++, Borland Delphi, Borland C++ и любых средств разработки на Java;

- большое количество уже существующих бесплатных программных элементов ActiveX;

- стандартность.

· MTS (Microsoft Transaction Server - сервер управления транзакциями) технология, обеспечивающая безопасность и стабильную работу распределенных приложений при больших объемах передаваемых данных.

· MIDAS (Multitier Distributed Application Server - сервер многозвенных распределенных приложений) - технология, организующая доступ к данным разных компьютеров с учетом балансировки нагрузки сети.

Все указанные технологии реализуют компонентный подход, заложенный в СОМ. Так, с точки зрения СОМ элемент управления ActiveX - внутренний сервер, поддерживающий технологию OLE-automation. Для программиста же элемент ActiveX - «черный ящик», обладающий свойствами, методами и событиями, который можно использовать как строительный блок при создании приложений.

Технология CORBA, разработанная группой компаний ОМС (Object Management Group - руппа внедрения объектной технологии программирования), реализует подход, аналогичный СОМ, на базе объектов и интерфейсов CORBA. Программное ядро CORBA реализовано для всех основных аппаратных и программных платформ и потому эту технологию можно использовать для создания распределенного программного обеспечения в гетерогенной (разнородной) вычислительной среде. Организация взаимодействия между объектами клиента и сервера в CORBA осуществляется с помощью специального посредника, названного VisiBroker, и другого специализированного программного обеспечения.

Отличительной особенностью современного этапа развития технологии программирования, кроме изменения подхода, является создание и внедрение автоматизированных технологий разработки и сопровождения программного обеспечения, которые были названы CASE-технологиями (Computer-Aided Software/System Engineering - разработка программного обеспечения/программных систем с использованием компьютерной поддержки). Без средств автоматизации разработка достаточно сложного программного обеспечения на настоящий момент становится трудно осуществимой: память человека уже не в состоянии фиксировать все детали, которые необходимо учитывать при разработке программного обеспечения. На сегодня существуют CASE-технологии, поддерживающие как структурный, так и объектный (в том числе и компонентный) подходы к программированию.

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

Выводы

1. Алгоритм - это точно определенное правило действий, для которого задано указание, как и в какой последовательности это правило необходимо применять к исходным данным задачи, чтобы получить ее решение за конечное число шагов.

2. Алгоритм характеризуется рядом свойств, к которым относятся: детерминированность, дискретность, массовость и результативность.

3. Алгоритм может представлен словесно, графически, аналитически, псевдокодом или на языке программирования.

4. Программа - это упорядоченная последовательность команд (инструкций) компьютера для решения конкретной задачи. Основными характеристиками программ являются:

· алгоритмическая сложность (логика алгоритмов обработки информации);

...