Алгоритмизация и программирование
план-конспект занятия по информатике и икт на тему

4. АЛГОРИТМИЗАЦИЯ И ПРОГРАММИРОВАНИЕ.
   ЯЗЫКИ ПРОГРАММИРОВАНИЯ ВЫСОКОГО УРОВНЯ

4. ПОНЯТИЕ АЛГОРИТМА И ЕГО СВОЙСТВА

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

Алгоритм – описанная на некотором языке точная конечная система правил, определяющая содержание и порядок действий над некоторыми объектами, строгое выполнение которых дает решение поставленной задачи. Понятие алгоритма, являющееся фундаментальным в математике и информатике, возникло задолго до появления средств вычислительной техники. Слово «алгоритм» появилось в средние века, когда европейцы познакомились со способами выполнения арифметических действий в десятичной системе счисления, описанными узбекским математиком Муххамедом бен Аль-Хорезми («аль-Хорезми» – человек из города Хорезми; в настоящее время город Хива в Хорезмской области Узбекистана). Слово алгоритм – есть результат европейского произношения слов аль-Хорезми. Первоначально под алгоритмом понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи.

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

Значение слова «алгоритм» очень схоже со значениями слов «рецепт», «метод», «процесс». Однако, в отличие от рецепта или процесса, алгоритм характеризуется следующими свойствами:

• дискретность (разрывность - противоположно непрерывности) – это свойство алгоритма, характеризующее его структуру: каждый алгоритм состоит из отдельных законченных действий, говорят: «Делится на шаги»;
• массовость – применимость алгоритма ко всем задачам рассматриваемого типа, при любых исходных данных. Например, алгоритм решения квадратного уравнения в области действительных чисел должен содержать все возможные исходы решения, т.е., рассмотрев значения дискриминанта, алгоритм находит либо два различных корня уравнения, либо два равных, либо делает вывод о том, что действительных корней нет;
• определенность (детерминированность, точность) – свойство алгоритма, указывающее на то, что каждый шаг алгоритма должен быть строго определен и не допускать различных толкований; также строго должен быть определен порядок выполнения отдельных шагов. Помните сказку про Ивана-царевича? «Шел Иван-царевич по дороге, дошел до развилки. Видит большой камень, на нем надпись: «Прямо пойдешь – голову потеряешь, направо пойдешь – жену найдешь, налево пойдешь – разбогатеешь». Стоит Иван и думает, что дальше делать». Таких инструкций алгоритм содержать не может;
• результативность – свойство, состоящее в том, что любой алгоритм должен завершаться за конечное (может быть очень большое) число шагов. Вопрос о рассмотрении бесконечных алгоритмов остается за рамками теории алгоритмов;
• формальность – это свойство указывает на то, что любой исполнитель, способный воспринимать и выполнять инструкции алгоритма, действует формально, т.е. отвлекается от содержания поставленной задачи и лишь строго выполняет инструкции. Рассуждать «что, как и почему?» должен разработчик алгоритма, а исполнитель формально (не думая) поочередно исполняет предложенные команды и получает необходимый результат.

4. СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ

Рассмотрим следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.

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

Никаких правил составления словесного описания не существует. Запись алгоритма осуществляется в произвольной форме на естественном, например, русском языке. Этот способ описания не имеет широкого распространения, так как строго не формализуем (под «формальным» понимается то, что описание абсолютно полное и учитывает все возможные ситуации, которые могут возникнуть в ходе решения); допускает неоднозначность толкования при описании некоторых действий; страдает многословностью.

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

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

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

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

Блок, характеризующий начало/конец алгоритма (для подпрограмм – вызов/возврат):

Блок – процесс, предназначенный для описания отдельных действий:

Блок – предопределенный процесс, предназначенный для обращения к вспомогательным алгоритмам (подпрограммам):

Блок – ввода/вывода с неопределенного носителя:

Блок – ввод с клавиатуры:

Блок – вывод на монитор:

Блок – вывод на печатающее устройство:

С Начало   j  (    Конец   J

<Действие>

Г/

Блок – решение (проверка условия или условный блок):

Блок, описывающий цикл с параметром:

Нет

Да

<тело цикла>

Блок — границы цикла, описывающий циклические процессы типа: «цикл с предусловием», «цикл с постусловием»:

<тело цикла>

Соединительные блоки

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

Программа – описание структуры алгоритма на языке алгоритмического программирования. С другой стороны, понятие «программа» нельзя трактовать только таким образом, как уже говорилось в главе 5 (п. 5.5.2), программа на языке декларативного программирования представляет собой совокупность описанных знаний и не содержит явного алгоритма исполнения.

5. ОСНОВНЫЕ АЛГОРИТМИЧЕСКИЕ КОНСТРУКИИИ

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

1. Линейная алгоритмическая конструкция

Линейной называют алгоритмическую конструкцию, реализованную в виде последовательности действий (шагов), в которой каждое действие (шаг) алгоритма выполняется ровно один раз, причем после каждого i-го действия (шага) выполняется (i+1)-е действие (шаг), если i-е действие – не конец алгоритма.

2. Разветвляющаяся алгоритмическая конструкция

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

Действия 2

L

Ложь (Нет) /         \^    Истина (Да)

Условие

Действия 1

_Г

Рис. 6.2. Полное ветвление

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

Пример 6.2.

Вывести значение наибольшего из двух чисел. Псевдокод:

1.  Ввод двух чисел а, Ь.

2.  ЕСЛИ а > Ъ, ТО «выводим а»,

ИНАЧЕ «выводим Ь».

3.  Конец.

297

Ложь (Нет)

Рис. 6.3. Неполное ветвление

(    Начало     J

I

/Ввод     /

/      «■*    /

Нет

Да

Рис. 6.4. Блок-схема к примеру 6.2

В данном примере реализовано полное ветвление. ЕСЛИ значения входных данных таковы, что а > Ь, ТО выполняется линейный алгоритм:

1.  Ввод двух чисел а, Ь.

2.  Вывод а.

ИНАЧЕ, когда а <Ь, выполняется линейный алгоритм:

298

1.  Ввод двух чисел а, Ь.

2.  Вывод Ь.

Вывод: алгоритм является разветвляющимся и состоит из двух ветвей.

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

Пример 6.3.

Заданы три числа. Найти значение наименьшего из них.

Заданные числа обозначим: а, Ь, с; результирующее наименьшее — тт. На рис. 6.5 представлена блок-схема алгоритма реше-            рИс. 6.5. Алгоритм поиска ния данной задачи.                                    наименьшего значения

среди трех заданных

299

КолланЭа «Выбор»

Часто при выборе одного из возможных вариантов действий приходится проверять значение выражения на принадлежность заданному набору данных. Для этого существует команда «Выбор». При ее исполнении сначала вычисляется значение некоторого выражения Z. Затем последовательно проверяются условия VI, V2, ..., V« относительно Z, начиная с первого, до тех пор, пока не встретится условие, принимающее значение ИСТИНА. Далее выполняется соответствующее этому условию действие (или серия действий), после чего команда выбора завершается. Если ни одно из условий не является истинным, то выполняется действие (или набор действий), идущее по ветви ЛОЖЬ для каждого из условий. На рис. 6.6 представлена блок-схема команды «Выбор» для п = 3.

Рис. 6.6. Команда «выбор»

3. Алгоритмическая конструкция «Цикл»

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

Рассмотрим три типа циклических алгоритмов: цикл с параметром (который называют арифметическим циклом), цикл с предусловием и цикл с постусловием (их называют итерационными).

Арифметический цикл

В арифметическом цикле число его шагов (повторений) однозначно определяется правилом изменения параметра, которое задается с помощью начального (N) и конечного (К) значений параметра и шагом (h) его изменения. Т.е., на первом шаге цикла значение параметра равно N, на втором - N + h, на третьем - N + 2h и т.д. На последнем шаге цикла значение параметра не больше К, но такое, что дальнейшее его изменение приведет к значению, большему, чем К.

Пример 6.4.

Вывести 10 раз слово «Привет!».

Параметр цикла обозначим /, он будет отвечать за количество выведенных слов. При / = 1 будет выведено первое слово, при / = 2 будет выведено второе слова и т.д. Так как требуется вывести 10 слов, то последнее значение параметра / = 10. В заданном примере требуется 10 раз повторить одно и то же действие: вывести слово «При-

300

301вет!». Составим алгоритм, используя арифметический цикл, в котором правило изменения параметра / = 1,10,1. Т.е. начальное значение параметра /= 1; конечное значение/= 10; шаг изменения И = 1. На рис. 6.7 представлена блок-схема алгоритма решения данной задачи.

 Привет!   J (   Конец J

Рис. 6.7. Блок-схема к примеру 6.4

Цикл с предусловием

Количество шагов цикла заранее не определено и зависит от входных данных задачи. В данной циклической структуре сначала проверяется значение условного выражения (условие) перед выполнением очередного шага цикла. Если значение условного выражения истинно, исполняется тело цикла. После чего управление вновь передается проверке условия и т.д. Эти действия повторяются до тех пор, пока условное выражение не примет значение ЛОЖЬ. При первом же несоблюдении условия цикл завершается.

Рис. 6.8. Блок-схема цикла с предусловием

302

Блок-схема данной конструкции представлена на рис. 6.8'двумя способами: с помощью условного блока а и с помощью блока границы цикла б.

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

Пример 6.5.

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

Рис. 6.9. Блок-схема алгоритма Евклида

303Опишем его на псевдокоде:

1.  Ввод натуральных чисел тип.

2.  Пока т t- n делать.

2.1.  Если т>п, то т=т — п, иначе п— п — т .

2.2.  Переход к шагу 2.

3.  Вывод т (найденный наибольший общий делитель).

4.  Конец.

Цикл с постусловием

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

Тело цикла

I

Условие

а

Рис. 6.10. Блок-схема цикла с постусловием

304

Пример 6.6.

Составим алгоритм игры «Угадай число». Первый игрок вводит задуманное число от 1 до 50. Второй (угадывающий) вводит другое число и получает один из ответов: «Ваше число меньше», «Ваше число больше» или «Вы угадали». Игра продолжается до тех пор, пока второй игрок не угадает задуманное число.

Составляя алгоритм игры, обозначим х - число, задуманное первым игроком, у — число, вводимое на очередном шаге вторым игроком. Блок-схема алгоритма приведена на рис. 6.11.

С   Начало   J

I / Ввод х  /

Рис. 6.11. Блок-схема игры «Угадай число» (пример 6.6)

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

Суммирование.

Пример 6.7.

Для заданного натурального числа N вычислить сумму

2    3            N

Подсчет суммы осуществляется следующим образом. Сначала счи-  ' таем, что сумма S есть первое слагаемое (S = 1). Далее к первому сла-

1 гаемому прибавляем второе, получаем новую сумму   5 = 1 + — . Но

на предыдущем шаге S = 1, поэтому можно записать S = S + — . к сумме двух первых слагаемых прибавляем третье 5 = 1 + — + -. Но на

1                                                                 1 предыдущем шагу 5 = 1 + — , поэтому можно записать S = S + - и т.д.

2                                                                3

Получили следующую последовательность шагов: 1)      S = 1.

2)

3)

2" 3'

Запишем /-и шаг, опираясь на два предыдущих:

1

i

Выясним правило изменения номера шага /. В описанной последовательности / = 1, 2, 3 и т.д. В сумме N слагаемых, поэтому последним значением / будет N. Отсюда нашли правило изменения / = 1, N, 1.

306

Сверяя инструкции каждого шага, находим, что выражение на первом шаге отличается от других (однотипных). Чтобы оно стало таким как все, в сумму надо добавить S, т.е. записать: S = S + 1 (учи-

1 тываем, что 1 = 7)- Отсюда для S возникает необходимость задания

начального значения, но такого, чтобы S + 1 = 1 (таким должно быть выражение для / = 1), этим числом является нуль, при сложении с нулем сумма не меняется.

Так как известно число шагов цикла, то для построения алгоритма используем цикл с параметром /.

Алгоритм на псевдокоде:

1.  Ввод N.                                                                                   .

2.  S = 0.                                                                                      "

3.  Для / = 1, N, 1 повторить:

3.1. S =

4.  Вывод S.

5.  Конец.

Блок-схема алгоритма приведена на рис. 6.12.

Сформулируем правило суммирования:

•    начальное значение суммы S = 0;

•    в теле некоторой циклической конструкции выполнить команду:

S = S + <слагаемое>.

Упражнения для самостоятельной работы:

Для заданного натурального числа N вычислите суммы N-сла-гаемых:

12    3

1.  - + - + - + ...; 2     3    4

12    3

2.  - + - + - + ...; 2    4    6

3073.

sin 1

 sin 2

 sin3

+  1 + 2    1+2+3

+ ...

(       Начало      J

S = 0

s = s + -

(       Конец       j

Рис. 6.12. Алгоритм вычисления суммы

Подсчет количества элементов. Произведем счет: 1, 2, 3, 4, 5 и т.д., этот процесс является циклическим, так как каждый раз мы совершаем одно и то же действие: предыдущее натуральное число увеличиваем на единицу. Обозначив через К - счетчик искомых элементов, легко получить правило счетчика: К = К + 1 (на очередном шаге цикла). Но при первом подсчете должны получить значение К, равное единице, а до начала счета счетчик должен быть пуст, следовательно, начальное значение счетчика равно нулю.

Правило счетчика:

•    начальное значение счетчика К = 0;

•    в теле некоторой циклической конструкции выполнить команду:

К = К + 1.

Пример 6.8

Задано 20 чисел. Сколько среди них чисел, больших 10? Псевдокод:

1.  К = 0 {Счетчик чисел, больших 10}.

2.  Повторить 20 раз (для / = 1, 20, 1).

2.1.  Ввод числа х.

2.2.  Если х > 10, то К = К+ 1.

3.  Вывод К.

4.  Конец.

Блок-схема алгоритма приведена на рис. 6.13. Замечание: в фигурных скобках {....} принято помещать комментарии к алгоритму.

Рис. 6.13. Алгоритм примера 6.8

308

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

а - последовательные         б — вложенные             в - запрещенные

Рис. 6.14. Расположение циклов

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

4. Рекурсивный алгоритм

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

6. ПРОСТЫЕ ТИПЫ ЗОННЫМ: ПЕРЕМЕННЫЕ И КОНСТАНТЫ

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

Переменная – есть именованный объект (ячейка памяти), который может изменять свое значение. Имя переменной указывает на значение, а способ ее хранения и адрес остаются скрытыми от программиста. Кроме имени и значения, переменная имеет тип, определяющий, какая информация находится в памяти. Тип переменной задает:                          ■                                                                            "*

•   используемый способ записи информации в ячейки памяти;

•   необходимый объем памяти для ее хранения.

Объем памяти для каждого типа определяется таким образом, чтобы в него можно было поместить любое значение1 из допустимого диапазона значений данного типа. Например, тип «байт» может принимать значения от 0 до 255, что в двоичном коде (255(10) = = 11111111 2) соответствует ячейке памяти длиной в 8 бит (или 1 байт).

В описанных выше алгоритмах (примеры 6.1 - 6.8) все данные хранятся в виде переменных. Например, инструкция «Ввод двух чисел а, Ь» означает введение пользователем значений двух переменных, а инструкция «К=К+1» означает увеличение значения переменной К на единицу.

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

Все остальные данные в программе, значения которых не изменяются на протяжении ее работы, называют константами или постоянными. Константы, как и переменные, имеют тип. Их можно указывать явно, например, в инструкции «К = К + 1» 1 есть константа, или для удобства обозначать идентификаторами: pi = 3,1415926536. Только значение pi нельзя изменить, так как это константа, а не переменная.

310

3116.5. Структурированные Зонные и алгоритмы ин обработки

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

Массивом называется упорядоченная совокупность однотипных величин, имеющих общее имя, элементы которой адресуются (различаются) порядковыми номерами (индексами). В качестве иллюстрации можно представить шкаф, содержащий множество пронумерованных ящиков (совокупность — «Ящик № 1», «Ящик № 2», «Ящик № 3» и т.д.; «Ящик» - общее имя всех ее элементов). Доступ к содержимому конкретного ящика (элементу массива) осуществляется после выбора ящика по его номеру (индексу). Элементы массива в памяти компьютера хранятся по соседству, одиночные элементы простого типа такого расположения данных в памяти не предполагают. Массивы различаются количеством индексов, определяющих их элементы.

Одномерный массив (шкаф ящиков в один ряд) предполагает наличие у каждого элемента только одного индекса. Примерами одномерных массивов служат арифметическая (а.) и геометрическая (Ь) последовательности, определяющие конечные ряды чисел. Количество элементов массива называют размерностью. При определении одномерного массива его размерность записывается в круглых скобках, рядом с его именем. Например, если сказано: «задан массив А(10)», это означает, что даны элементы: ар а2, ... , а]0. Рассмотрим алгоритмы обработки элементов одномерных массивов.

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

312

Псевдокод:

1. Повторить 10 раз (для i = 1, 10, 1): 1.1. Вввод а.

Блок-схема

Рис. 6.15. Ввод элементов одномерного массива А( 10)

Пример 6.9.                                                              -»

Рассмотрим алгоритм вычисления среднего арифметического положительных элементов числового массива А(10).

Среднее арифметическое есть отношение суммы к числу ее слагаемых, т.е.

среднее арифметическое —

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

Псевдокод:

1.  Повторить 10 раз (для i = 1, 10, 1). 1.1. Ввод а.

2.  Начальное значение суммы: S = 0.

3.  Начальное значение счетчика: N = 0.

4.  Повторить 10 раз (для /= 1, 10, 1):

4.1. ЕСЛИ а. > 0, ТО S = S + а. ; N = N + 1.

5.  ЕСЛИ N > 0, ТО вычисление среднего арифметического SA = S/N; вывод SA.

ИНАЧЕ: вывод «Положительных элементов в массиве нет».

6.  Конец.

313С     Начало     1

" '■'»■■

>-;

S = 0

N = 0

Нет

Да

Положительных элементов нет

Рис. 6.16.   Блок-схема задачи «подсчета среднего арифметического положительных элементов массива» (пример 6.9)

(    Начало    J

щ

т= 1

X^i = 2,10,

Пример 6.10.

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

Обозначим индекс наибольшего элемента т. Будем считать, что первый элемент массива является наибольшим (т = 1). Сравним поочередно наибольший с остальными элементами массива. Если оказывается, что текущий элемент массива о. (тот, с которым идет сравнение) больше выбранного нами наибольшего а , то считаем его наибольшим (т = i) (рис. 6.17).

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

индекса а.., первый индекс / определяет номер строки, в которой находится элемент (координата по горизонтали), а второй j — номер столбца (координата по вертикали). Двумерный массив характеризуется двумя размерностями N и М, определяющими число строк и столбцов соответственно (рис. 6.18).

Ввод элементов двумерного массива осуществляется построчно, в свою очередь, ввод каждой строки производится поэлементно, тем

ат,т

(

-Г

 Конец

Рис 6.17. Алгоритм поиска

наибольшего элемента массива

и его индекса (пример 6.10)

314

7. ЯЗЫКИ ПРОГРАММИРОВАНИЯ

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

Писать программы в машинных кодах очень сложно, причем с ростом размера программы эта задача усложняется. В компьютерах первого поколения использовались программы, написанные в машинных кодах, причем для каждого компьютера существовал свой собственный машинный код. Числовая кодировка команд, адресов ячеек и обрабатываемых данных, зависимость вида программы от ее места в памяти не давали возможность следить за смыслом программы. Это во многом ограничивало область применения компьютеров первого поколения. В тот период (начало 50-х гг.) средства программирования и программное обеспечение только зарождались и были еще не развиты. Для того чтобы сделать программу читабельной и иметь возможность следить за ее смысловой структурой, придумали символический язык ассемблер, близкий к машинному (конец 50-х -начало 60-х гг.), в котором появилось понятие переменной. Ассемблер стал первым полноценным языком программирования. Благодаря этому заметно уменьшилось время разработки и возросла надежность программ. Для записи кодов операций и обрабатываемой информации в ассемблере используются стандартные обозначения, позволяющие записывать числа и текст в общепринятом виде, для кодов команд приняты мнемонические обозначения. Для обозначения величин, размещаемых в памяти, можно применять имена. После ввода программы ассемблер сам заменяет символические имена на адреса памяти, а символические коды команд на числовые. Использование ассемблера сделало процесс программирование более наглядным. Дальнейшее развитие этой идеи привело к созданию языков программирования высокого уровня, в которых длинные и сложные последовательности машинных кодов были заменены одним единственным обозначающим их словом – операторы.

5. Понятие «Язык программирования»

Сегодня практически все программы создаются с помощью языков программирования. Теоретически программу можно написать и на естественном языке (говорят: программирование на метаязыке), но из-за неоднозначности естественного языка автоматически перевести такую программу в машинный код пока невозможно.

Языки программирования — это формальные искусственные языки. Как и естественные языки, они имеют алфавит, словарньш'запас, грамматику и синтаксис, а также семантику.                              '

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

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

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

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

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

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

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

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

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

6. Компиляторы и интерпретаторы

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

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

Компиляторы полностью обрабатывают весь текст программы (его называют исходным кодом или source code). Они осуществляют поиск синтаксических ошибок, выполняют семантический аналиЪ и только затем, если текст программы в точности соответствует правилам языка, его автоматически переводят (транслируют) на машинный язык (говорят: генерируют объектный код или object code). Нередко при этом выполняется оптимизация с помощью набора методов, позволяющих повысить быстродействие программы. Сгенерированный объектный код обрабатывается специальной программой - сборщиком или редактором связей, который производит связывание объектного и машинного кодов. Текст программы преобразуется в готовый к исполнению ЕХЕ-файл (исполнимый код), его можно сохранить в памяти компьютера или на диске. Этот файл имеет самостоятельное значение и может работать под управлением операционной системы. Его можно перенести на другие компьютеры с процессором, поддерживающим соответствующий машинный код.

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

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

II Информатика

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

об ошибках.

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

7. Системы программирования

Процесс создания программы включает:

•   Составление исходного кода программы (рис. 6.21) на языке программирования.

•   Этап трансляции, необходимый для создания объектного кода

программы.

•   Построение загрузочного модуля, готового к исполнению.

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

Исходны!П|  Трансляция  ЦрбГектныйЦ    Редактор      II Загрузочный

^'         """         Ч                            ~                 II         МОДУЛЬ

код

код

связей

модуль

Рис. 6.21. Процесс создания программы, готовой к исполнению Совокупность этих программных средств входит в состав системы программирования:

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

•   Компилятор.

•   Редактор связей.

•   Отладчик.

322

•   Библиотеки функций.

•   Справочная система.

8. Классификация и обзор в программирования

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

языки

ПРОГРАММИРОВАНИЯ

Процедурные (императивные)

Объектно-ориентрованные

Рис. 6.22. Классификация языков программирования

Процедурное программирование

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

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

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

Одним из первых процедурных языков программирования высокого уровня стал Фортран (FORmula ZR/LVslation), созданный в начале 50-х гг. в США фирмой IBM. Первая публикация о нем появилась в 1954 г. Основное назначение языка – программирование научно-технических задач. Объектами языка являются целые и вещественные числа и числовые переменные. Выражения в нем формируются с помощью четырех арифметических действий: возведения в степень, логических операций И, ИЛИ, НЕ, операций отношения и круглых скобок. Основные операторы Фортрана – ввод, вывод, присваивание, условный и безусловный переход, цикл, вызов подпрограмм. Долгие годы он был одним из самых распространенных языков в мире. За это время накоплена огромная библиотека программ, написанных на Фортране. И сейчас ведутся работы над очередным стандартом Фортрана. В 2000 г. была реализована версия Фортран F2k, имеется стандартная версия HPF (High Performance Fortran) для параллельных суперкомпьютеров. Многие средства Фортрана использованы в языках PL-1 и Бейсик.

Кобол (COmmon business Oriented .Language – общепринятый деловой язык) – язык программирования, ориентированный на решение задач обработки данных. Широко используется для решения учетно-экономических и управленческих задач. Разработан в США в 1958–1960 гг. Программа на Коболе имеет вид ряда предложений на английском языке и напоминает обычный текст. Группы последовательно записанных операторов объединяются в предложения, предложения – в параграфы, параграфы – в секции. Программист присваивает параграфам и секциям имена (метки), что облегчает непосредственное обращение к нужному участку программы. В СССР был принят русский вариант языка. В Коболе были реализованы мощные средства работы с большими объемами данных, хранящимися на различных внешних носителях. На этом языке создано много приложений, некоторые из них активно эксплуатируются и сейчас. Достаточно сказать, что одной из высокооплачиваемых категорией граждан в США являются программисты на Коболе.

Алгол (/itGOrithmic .Language) разработан группой зарубежных специалистов в 1960 г., явился результатом международного сотрудничества конца 50-х гг. (Алгол-60). Алгол предназначался для записи алгоритмов, построенных в виде последовательности процедур, применяемых при решении поставленных задач. Специалисты–практики воспринимали этот язык неоднозначно, но тем не менее, он как признанный международный язык сыграл большую роль в становлении основных понятий программирования и для обучения программистов. В нем впервые введены понятия «блочная структура программы», «динамическое распределение памяти». Внутри блока в Алголе можно вводить локальные обозначения, которые не зависят от остальной части программы. Несмотря на свое интернациональное происхождение, Алгол-60 получил меньшее распространение, чем Фортран. Например, не на всех зарубежных ЭВМ имелись трансляторы с Алгола-60. В 1968 г. в результате дальнейшего развития и усовершенствования Алгола-60 была создана версия Алгол-68. Это многоцелевой универсальный расширенный язык программирования. Последнее свойство позволяло с помощью одной и той же программы транслятора осуществлять трансляцию с различных расширенных версий языка без дополнительных затрат на приспособление этого языка к различным категориям пользователей, на получение проблемно-ориентированных диалектов языка. По своим возможностям Алгол-68 и сегодня опережает многие языки программирования, однако из-за отсутствия эффективных компьютеров для него не удалось своевременно создать хорошие компиляторы. В нашей стране в те годы под руководством академика Андрея Петровича Ершова был создан транслятор Альфа, который представлял достаточно удачную русифицированную версию Алгола.

В середине 60-х гг. сотрудники математического факультета Дартмутского колледжа Томас Курц и Джон Кемени создали специализированный язык программирования, который состоял из простых английских слов. Новый язык назвали универсальным символическим кодом для начинающих (beginners ЛИ-purpose Symbolic /nstruction Code) или сокращенно BASIC (Бейсик). 1964 г. считают годом рождения этого языка. Он получил самое широкое распространение при работе на персональных компьютерах в режиме интерактивного диалога. Популярность Бейсика объясняется как простотой его освоения, так и наличием достаточно мощных универсальных средств, пригодных для решения научных, технических и экономических задач, а также задач бытового характера, игровых и т.д. Согласно концепциям, заложенным в Бейсике, в нем широко распространены различные правила умолчания, что считается плохим тоном в большинстве языков программирования подобного типа. Возникло множество версий языка, зачастую мало совместимых друг с другом. Однако, зная одну из версий, можно без особого труда освоить любую другую. Бейсик активно поглощает многие концепции и новинки из других языков. Первоначально интерактивный режим осуществлялся с использованием интерпретатора, в настоящее время для этого языка имеются также и компиляторы.

В начале 60-х гг. каждый из существующих языков программирования был ориентирован на разные классы задач, но в той или иной мере привязан к конкретной архитектуре ЭВМ. Были предприняты попытки преодолеть этот недостаток путем создания универсального языка программирования. ПЛ/1 (PL/1 - Programming Language One) — первый многоцелевой универсальный язык, разработан в США фирмой IBM в 1963—1966 гг. Это один из наиболее распространенных универсальных языков, он хорошо приспособлен для решения задач в области вычислительной техники: исследования и планирования вычислительных процессов, моделирования, решения логических задач и исследования логических схем, разработки систем математического обеспечения. При разработке PL/1 были широко использованы основные понятия и средства языков Фортран, Алгол-60, Кобол. PL/1 — богатый и гибкий язык, дает возможность производить вставки, исправлять текст программы в процессе ее отладки. Язык получил широкое распространение, трансляторы с него имеются для многих типов компьютеров. Компания IBM и сегодня продолжает поддерживать этот язык.

Паскаль (Pascal) является одним из наиболее популярных процедурных языков программирования, особенно для персональных компьютеров. Созданный как учебный язык программирования в 1968-1971 гг. Никлаусом Виртом в Высшей технической школе (ЕТН) в Цюрихе (Швейцария), он был назван в честь французского математика и философа Блеза Паскаля (1623-1662). Целью работы Н. Вирта было создание языка, который

•   строился бы на небольшом количестве базовых понятий;

•   имел простой синтаксис;

•   допускал перевод программ в машинный код простым компилятором.

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

326

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

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

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

Период с конца 60-х до начала 80-х гг. характеризуется бурным ростом числа различных языков программирования, сопровождавшим, как это ни парадоксально, кризис программного обеспечения. Этот кризис особенно остро переживало военное ведомство США. В январе 1975 г. Пентагон решил навести порядок среди бесчисленного множества трансляторов и создал комитет для разработки одного универсального языка. На конкурсной основе комитет рассмотрел сотни проектов и выяснил, что ни один из существующих языков не может удовлетворить их требованиям, для окончательного рассмотрения было оставлено два проекта. В мае 1979 г. был объявлен победитель - группа ученых во главе с Жаном Ихбиа. Победивший язык назвали АДА, в честь Ады Лавлейс, дочери великого поэта Байрона. Она в юности была увлечена идеями Чарльза Бэббиджа и помогала ему составлять описание машины, а в начале 40-х гг. XIX в. разработала первую в мире программу для вычислительной машины. Язык АДА - прямой наследник Паскаля. Он предназначен для создания и длительного сопровождения больших программных систем, управления процессами в реальном масштабе времени. В языке четко выражена модульность его конструкций, причем обеспечивается удобство организации разнообразных связей между модулями. Важным его достоинством является возможность параллельного программирования ветвей программы, которые затем могут реализоваться

327на многопроцессорных компьютерах. Язык АДА сложен для изучения.

Язык программирования С (Си) был разработан в лаборатории Bell для реализации операционной системы UNIX в начале 70-х гг. и не рассматривался как массовый. Он планировался для замены Ассемблера, чтобы иметь возможность создавать столь же эффективные и компактные программы, и в то же время не зависеть от конкретного типа процессора. В С сочетаются достоинства современных высокоуровневых языков в части управляющих конструкций и структур данных с возможностями прямого доступа к аппаратным средствам компьютера. Синтаксис языка С обеспечивает краткость программы, его компиляторы генерируют эффективный объектный код. Одна из наиболее существенных особенностей С состоит в том, что различия между выражениями и операторами нивелируются, это приближает его к функциональным языкам. Например, выражение может обладать побочным эффектом присваивания, а также может использоваться в качестве оператора. Нет четкого различия между процедурами и функциями, более того, понятие процедуры вообще не вводится. Синтаксис языка затрудняет программирование и восприятие составленных программ. Отсутствует строгая типизация данных, что предоставляет дополнительные возможности программисту, но не способствует созданию надежных программ. Язык С приобрел большую популярность среди системных и прикладных программистов. В настоящее время этот язык реализован для большинства компьютерных платформ.

Функциональное программирование

Суть функционального (аппликативного) программирования определена А.П. Ершовым как «способ составления программ, в которых единственным действием является вызов функции, единственным способом расчленения программы на части является введение имени функции, а единственным правилом композиции - оператор суперпозиции функций. Никаких ячеек памяти, ни операторов присваивания, ни циклов, ни, тем более, блок-схем, ни передачи управления».

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

•   классы констант, которыми могут манипулировать функции;

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

•   правила построения новых функций из базовых;

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

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

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

Первым таким языком стал Лисп (LISP, LISt Processing — обработка списков), созданный в 1959 г. Джоном Маккарти. Этот язык ориентирован на структуру данных в форме списка и позволяет организовать эффективную обработку больших объемов текстовой информации. Существенная черта языка — унификация программных структур и структур.данных: все выражения записываются в виде списков.

Логическое программирование

Создание языка искусственного интеллекта Пролог (PROLOG, Programming in LOGic — программирование в терминах логики) в 1973 г. французским ученым Аланом Кольмероэ открыло новую область - логическое или реляционное программирование.

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

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

Объектно-ориентрованное программирование (ООП)

Пионером данного направления явился язык Смолток (Smalltalk), первоначально предназначенный для реализаций функций машинной графики. Работа над языком началась в 1970 г. в исследовательской лаборатории XEROX (США), а закончилась в 1980 г. окончательным вариантом интерпретатора Smalltalk-80. Данный язык оригинален тем, что его синтаксис очень компактен и базируется исключительно на понятии объекта. В нем отсутствуют операторы или данные, все, что входит в Смолток, является объектами, а объекты общаются друг с другом исключительно с помощью сообщений. В настоящее время версия VisualAge for Smalltalk активно развивается компанией IBM.

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

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

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

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

К наиболее современным объектно-ориентированным языкам программирования относятся C++ и Java.

Язык C++ был разработан в начале 80-х гг. Бьярном Страустру-пом в лаборатории Bell корпорации AT&T. Им была создана компактная компилирующая система, в основе которой лежал язык С, дополненный элементами языков BCPL, Simula-67 и Алгол-68. Более ранние версии языка были известны как «С с классами». В июле 1983 г. C++ был впервые использован за пределами исследовательской группы автора, однако тогда еще многие особенности языка не были придуманы. К 1990 г. была выпущена третья версия языка C++, стандартизированная американским государственным комитетом стандартов ANSI. В 1990 г. сотрудник корпорации Sun Д. Гослинг на основе расширения C++ разработал объектно-ориентированный язык Oak, основным достоинством которого было обеспечение сетевого взаимодействия различных по типу устройств. Новая интегрируемая в Internet версия языка получила название Java. С января 1995 г. Java получает распространение в Internet.

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

Синтаксис языков C++ и Java практически полностью совпадает. Принципиальным различием является то, что язык C++ компилируемый в машинный код, a Java — в платформо-независимый байт-код (каждая команда занимает один байт), этот байт-код может выполняться с помощью интерпретатора - виртуальной Java-машины (Java Virtual Machine), версии которой созданы сегодня для любых платформ. С точки зрения возможностей объектно-ориентируемых средств, Java имеет ряд преимуществ перед C++. Язык Java имеет более гибкую и мощную систему инкапсуляции информации. Механизм наследования, реализованный в Java, обязывает к более строгому подходу к программированию, что способствует надежности и читабельности кода. Язык C++ обладает сложной неадекватной и трудной для понимания системой наследования. Возможности динамического связывания объектов одинаково хорошо представлены в обоих языках, но синтаксическая избыточность C++ и здесь принуждает к выбору языка Java. Сегодня Java по популярности занимает второе место в мире после Бейсика.

Идеи ООП проникли во многие процедурные языки. Например, в состав интегрированной системы программирования Паскаль (корпорации Borlahd International), начиная с версии 5.5, входит специальная библиотека ООП Turbo Vision.

С середины 90-х гг. многие объектно-ориентированные языки реализуются как системы визуального программирования. Такие системы имеют интерфейс, позволяющий при составлении текста программы видеть те графические объекты, для которых она пишется. Отличительной особенностью этих систем является наличие в них среды разработки программ из готовых «строительных блоков», позволяющих создавать интерфейсную часть профаммного продукта в диалоговом режиме, практически без написания профаммньгх операций. Система берет на себя значительную часть работы по управлению компьютером, что делает возможным в простых случаях обходиться без особых знаний о деталях ее работы. Она сама пишет значительную часть текста программы: описания объектов, заголовки процедур и многое другое. Программисту остается только вписать необходимые строчки, определяющие индивидуальное поведение программы, которые система не в состоянии предвидеть. Но даже в этих случаях система сама указывает место для размещения таких строк. К объектно-ориентированным системам визуального проектирования относятся: Visual Basic, Delphi, C++ Builder, Visual C++. Это системы программирования самого высокого уровня.

VBA (Visual Basic for Application) является общей языковой платформой для приложений Microsoft Office (Excel, Word, Power Point и др.). VBA соблюдает основной синтаксис и правила программирования языков Бейсик-диалектов. VBA помогает довольно сильно расширить возможности приложений за счет написания макросов -программ, предназначенных для автоматизации выполнения многих операций. VBA позволяет создавать объекты управления фафичес-кого интерфейса пользователя, задавать и изменять свойства объектов, подключать к ним необходимый для конкретного случая программный код. С помощью VBA можно производить интеграцию между различными профаммными продуктами. Профаммы на языке VBA для приложений создаются двумя способами: в автоматическом режиме как результат построения клавишной макрокоманды или путем написания программного кода.

Языки программирования баз данных

Эти языки отличаются от алгоритмических прежде всего своим функциональным назначением. При работе с базами данных (БД) наиболее часто выполняются следующие операции: создание, преобразование, удаление таблиц в БД; поиск, отбор, сортировка по запросам пользователя; добавление новых записей или модификация существующих; удаление записей и др. Для обработки больших массивов информации и выборки записей по определенным признакам был создан структурированный язык запросов SQL (Stractured Query Language). Он был впервые создан фирмой IBM в начале 70-х гг., назывался Structured English Query Language (SEQUEL) и предназначался для управления прототипом реляционной базы данных IBM -System R. В дальнейшем SQL стал стандартом языка работы с реляционными базами данных, что зафиксировано американским национальным комитетом стандартов ANSI в 1986 г.

Практически в каждой СУБД имеется свой универсальный язык, ориентированный на ее особенности. Сегодня в мире ведущие производители СУБД: Microsoft (SQL Server), IBM (DB2), Oracle, Software AG (Adabas), Informix и Sybase. Их продукты предназначены для совместной параллельной работы тысяч пользователей в сети, а базы данных могут храниться в распределенном виде на нескольких серверах. В Oracle имеется встроенный язык PL/SQL, в Informix -INFORMIX 4GL, в Adabas - Natural и т.д.

Языки программирования для компьютерным сетей

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

HTML (Hyper Text Markup Language) - универсальный язык раз-

334

метки гипертекста, используемый для подготовки Web-документов для сети Internet. Язык представляет собой набор элементарных команд форматирования текста, добавления графических объектов (рисунков), задания шрифтов и цвета, организации ссылок и таблиц. В соответствии с командами HTML броузер отображает содержимое документа, команды языка не отображаются. В основе языка HTML лежит механизм гипертекстовых ссылок, обеспечивающий связь одного документа с другим. В HTML текст кодируется в ASCII и поэтому может быть создан и отредактирован в любом текстовом редакторе. Все Web-страницы написаны на HTML или используют его расширение.

Perl. В 80-х гг. Ларри Уолл разработал язык Perl, который предназначался для эффективной обработки больших текстовых файлов, создания текстовых отчетов и управления задачами. В его состав'вхо-дят многочисленные функции работы со строками, массивами, всевозможные средства преобразования данных, управления процессами, работы с системной информацией и др.

Tcl/Tk. В конце 80-х гг. Джон Аустираут придумал скрипт-язык Tel и библиотеку Tk. Tel - это попытка создания идеального скрипт-языка. Он ориентирован на автоматизацию рутинных операций и состоит из мощных команд, выполняющих обработку нетипизирован-ных объектов.

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

Языки моделирования

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

8. ЭТАПЫ ПОДГОТОВКИ И РЕШЕНИЙ НА КОМПЬЮТЕРЕ

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

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

2.  Формальное построение модели задачи – предполагает построение модели с характеристиками, адекватными оригиналу, на основе какого-либо его физического или информационного принципа; анализируется характер и сущность величин, используемых в задаче.

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

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

5.  Построение алгоритма — на данном этапе составляется алгоритм решения задачи, в соответствии с выбранным методом решения. Процесс обработки данных разбивается на отдельные относительно самостоятельные блоки, определяется последовательность выполнения этих блоков.

336

6.  Составление программы — алгоритм решения переводится на конкретный язык программирования.

7.  Отладка программы — процесс устранения синтаксических и логических ошибок в программе. В процессе трансляции программы с помощью синтаксического и семантического контроля выявляются недопустимые конструкции и символы (или сочетания символов) для данного языка программирования. Компьютер выдает сообщение об ошибках в форме, соответствующей этому языку. Затем проверяется логика работы программы в процессе ее выполнения с конкретными исходными данными. Для этого используются специальные методы. Например, в программе выбираются контрольные точки, для них подбираются тестирующие примеры и вручную находятся значения в этих точках, которые  затем  и  сверяются  со значениями,  получаемыми компьютером на этапе отладки. Кроме того, используются отладчики, выполняющие специальные действия на этапе отладки, такие как удаление, замена или вставка отдельных операторов

• или целых фрагментов программы, вывод промежуточных результатов, изменение значений заданных переменных и др.

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

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

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