Оператор (программирование)
Инструкция или оператор (англ. statement ) — наименьшая автономная часть языка программирования; команда. Программа обычно представляет собой последовательность инструкций.
Многие языки (например, Си) различают инструкцию и определение. Различие в том, что инструкция исполняет код, а определение создаёт идентификатор (то есть можно рассматривать определение как инструкцию присваивания).
Ниже приведены основные общие инструкции императивных языков программирования.
См. также
 |
Полезное
Смотреть что такое «Оператор (программирование)» в других словарях:
Оператор — В Викисловаре есть статья «оператор» Оператор может означать: Оператор (математика) то же, что математическая функция; Оператор (биология) последовательность ДНК, принимающая участие в регуляции активности генов; Оператор… … Википедия
оператор — 4.22 оператор (operator): Какой либо объект, осуществляющий работу системы. Примечание 1 Роль оператора и роль пользователя могут возлагаться одновременно или последовательно на одно и то же лицо или организацию. Примечание 2 В контексте данного… … Словарь-справочник терминов нормативно-технической документации
Программирование — процесс составления упорядоченной последовательности действий (программы (См. Программа)) для ЭВМ; научная дисциплина, изучающая программы для ЭВМ и способы их составления, проверки и улучшения. Каждая ЭВМ является автоматом,… … Большая советская энциклопедия
ПРОГРАММИРОВАНИЕ ТЕОРЕТИЧЕСКОЕ — математическая дисциплина, изучающая математич. абстракции программ, трактуемых как объекты, выраженные на формальном языке, обладающие определенной информационной и логич. структурой и подлежащие исполнению на автоматич. устройствах. П. т.… … Математическая энциклопедия
оператор ЭЭ оборудования и/или ЭЭ систем — 3.17. оператор ЭЭ оборудования и/или ЭЭ систем (operator of an EDM equipment and/or system): Человек, который осуществляет программирование, установку, регулировку, наблюдение за работой, техническое обслуживание и чистку станка. Источник: ГОСТ Р … Словарь-справочник терминов нормативно-технической документации
Генетическое программирование — В искусственном интеллекте генетическое программирование (ГП) автоматическое создание или изменение программ с помощью генетических алгоритмов. С помощью этой методологии «выращиваются» программы, всё лучше и лучше (в соответствии с определенной… … Википедия
Функциональное программирование — Парадигмы программирования Агентно ориентированная Компонентно ориентированная Конкатенативная Декларативная (контрастирует с Императивной) Ограничениями Функциональная Потоком данных Таблично ориентированная (электронные таблицы) Реактивная … Википедия
Структурное программирование — Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите статью в соответствии с правилами написания статей … Википедия
Цикл (программирование) — У этого термина существуют и другие значения, см. цикл. В данной статье или разделе имеется список источников или внешних … Википедия
Функциональное программирование на Питоне — Функциональное программирование является одной из парадигм, поддерживаемых языком программирования Python. Основными предпосылками для полноценного функционального программирования в Python являются: функции высших порядков, развитые средства… … Википедия
Операторы языка программирования
Оператор — это элемент языка, задающий полное описание действия, которое необходимо выполнить. Каждый оператор представляет собой законченную фразу языка программирования и определяет некоторый вполне законченный этап обработки данных. В состав операторов могут входить служебные слова, данные, выражения и другие операторы. В английском языке данное понятие обозначается словом “statement”, означающим также “предложение”.
Каждый оператор в любом языке программирования имеет определенный синтаксис и семантику. Под синтаксисом оператора понимается система правил (грамматика), определяющая его запись с помощью элементов алфавита данного языка, в который наряду с различными символами входят, например, и служебные слова. Под семантикой оператора понимают его смысл, т.е. те действия, которым соответствует запись того или иного оператора. Например, запись i := i + 1 является примером синтаксически корректной записи оператора присваивания в языке Pascal, семантика которого в данном случае такова: извлечь значение ячейки памяти, соответствующей переменной i, сложить его с единицей, результат записать в ту же ячейку памяти.
В большинстве процедурных языков программирования набор операторов практически одинаков и состоит из оператора присваивания, операторов выбора, операторов цикла, оператора вызова процедуры, операторов перехода. Иногда выделяют также пустой (отсутствие действия) и составной операторы. Многие операторы являются способом представления определенных алгоритмических конструкций (см. “Алгоритмические конструкции” ) в языке программирования. Рассмотрим группы операторов подробнее, используя синтаксис языка Pascal.
Оператор присваивания
Присваивание — это действие компьютера, в результате которого переменная получает значение вычисленного выражения (оно помещается в соответствующую переменной ячейку памяти). Для описания такого действия в языках программирования существует оператор присваивания.
В общем виде оператор присваивания записывается так:
Например, в языке Pascal в качестве знака присваивания используется комбинация символов :=. В ряде других языков — знак равенства.
Результатом выполнения оператора присваивания является изменение состояния данных: все переменные, отличные от переменной, стоящей в левой части оператора присваивания, не меняют своего значения, а указанная переменная получает значение выражения, стоящего в правой части оператора присваивания. В большинстве случаев требуется, чтобы тип выражения совпадал с типом переменной. Если это не так, то оператор либо считается синтаксически некорректным, либо производится преобразование типа выражения к типу переменной (см. “Типы данных” ).
Операторы выбора
По-другому эти операторы называют условными операторами. Условные операторы используются для программирования алгоритмов, содержащих алгоритмическую конструкцию ветвление.
В языках программирования имеется несколько видов условных операторов. Полный условный оператор соответствует алгоритмической структуре полного ветвления:
В языке программирования соответствующий условный оператор имеет вид:
if B then S1 else S2
Если выражение B, которое вычисляется в начале выполнения условного оператора, имеет значение “истина”, то будет выполняться оператор S1, в противном случае — оператор S2. Операторы S1 и S2 могут быть составными.
Алгоритмическая структура неполного ветвления реализуется с помощью неполного условного оператора, который имеет вид:
Здесь B — логическое выражение, а S — произвольный оператор. Оператор S будет выполняться, если выражение B окажется истинным.
Если условный оператор реализует всего две ветви выбора (“да” и “нет”), то с помощью оператора варианта (case-оператора) можно запрограммировать многоветвящуюся структуру. Оператор варианта имеет вид:
Выполняется данный оператор так: значение выражения E ищется среди перечисленных в записи оператора значений V1, V2, …, Vn, и если такое значение находится, то выполняется соответствующий оператор S1, S2, …, Sn.
В разных языках программирования синтаксис и даже семантика перечисленных операторов могут отличаться, но возможности, предоставляемые программисту подобными конструкциями, примерно одинаковы.
Пример 1. В статье “Алгоритмические конструкции” 2 был приведен пример записи алгоритма решения обобщенного квадратного уравнения с помощью конструкций ветвления. Приведем фрагмент программы на языке Pascal, реализующий этот же алгоритм:
if c = 0 then writeln(‘x — любое’)
else writeln(‘нет корней’)
В цикле с постусловием тело цикла предшествует условию В. В отличие от цикла с предусловием здесь В — это условие окончания цикла. Оператор цикла с постусловием в Паскале имеет вид:
При такой организации цикла тело цикла S хотя бы один раз обязательно выполнится.
Практически во всех процедурных языках существует оператор цикла c параметром. Схематично его можно представить так:
Здесь значение переменной (параметра цикла) меняется от значения выражения E1 до E2 с шагом E3. Для каждого такого значения параметра цикла выполняется оператор S. В языке Pascal понятие шага в описании этого оператора отсутствует, а сам шаг для целочисленного параметра цикла может быть равен либо 1, либо –1. Оператор “цикл с параметром” используется для программирования циклов с заданным числом повторений. Для программирования итерационных циклов (число повторений которых заранее неизвестно) он не годится.
Оператор вызова процедуры
В статье “Подпрограммы” подробно рассказывается о таком виде подпрограмм, как процедуры. Стандартные подпрограммы языка программирования, которые входят в одну из библиотек подпрограмм, а также пользовательские подпрограммы, описанные внутри данного блока, вызываются с помощью оператора вызова процедуры:
Здесь E1,E2,…,En — переменные или выражения, представляющие собой фактические параметры обращения к процедуре. Наиболее часто используемыми стандартными процедурами являются процедуры ввода и вывода данных (read и write в Pascal).
Вызов процедуры семантически эквивалентен выполнению блока, описанного в качестве тела процедуры, после передачи в него начальных значений некоторых переменных (параметров-значений) или замены имен некоторых переменных (параметров-переменных) на имена фактических переменных, указанных при вызове процедуры.
Пример 3. Пусть у нас описана процедура abc:
procedure abc(a,b:integer;var c: integer);
Вызов этой процедуры abc(2,3,x) эквивалентен блоку действий:
Операторы перехода
Наиболее известным в данной группе операторов является оператор безусловного перехода goto. Если ко всем или некоторым уже имеющимся операторам программы добавить метки, то в программе становится возможным использовать оператор перехода вида:
Метка в данном случае соответствует началу того оператора, с которого должно продолжиться выполнение программы. Такой оператор позволяет записывать в языке программирования алгоритмы, имеющие сколь угодно сложную структуру. Но зачастую использование безусловного перехода неоправданно, т.к. ведет к запутанной, плохо читаемой программе. Практически единственным осмысленным применением оператора goto является выход сразу из нескольких вложенных циклов, например, при обработке двухмерных массивов.
Пример 4. Пусть нам требуется определить, есть ли в двухмерном массиве a элемент, равный 0:
if a[i,j] = 0 then begin
1: if b then write(‘есть’) else write(‘нет’);
Программа, разработанная по правилам структурного программирования, не должна содержать операторов безусловного перехода. Приведенную выше программу без использования оператора goto можно переписать следующим образом:
then writeln(‘Мне ‘,k,’ года’)
else writeln(‘Мне ‘,k,’ лет’)
При рассмотрении операторов цикла полезно предложить одну и ту же задачу запрограммировать тремя разными способами с использованием трех операторов цикла, и наоборот, по условию задачи научиться определять, какой именно оператор цикла является наиболее подходящим в том или ином случае.
Оператор вызова процедуры только на первый взгляд является простым. Здесь важно объяснить правила передачи параметров в процедуры и функции, различие между параметрами-переменными и параметрами-значениями (в последнем случае мы можем передавать не только имя переменной, но и константу или даже выражение соответствующего типа). Формальные и фактические параметры должны соответствовать по типам, но не по именам, что является далеко не очевидным для учеников.
Изучение условного и особенно составного оператора — хороший повод поговорить с учениками о стиле написания программ. Для языка Pascal существует несколько распространенных способов записи структурированных программ, но все они содержат отступы для размещения вложенных структур. Важны для записи программ и комментарии.
Компьютерное программирование — операторы
Оператор в языке программирования — это символ, который указывает компилятору или интерпретатору выполнить определенную математическую, реляционную или логическую операцию и получить конечный результат. В этой главе будет объяснено понятие операторов, и вы познакомитесь с важными арифметическими и реляционными операторами, доступными в C, Java и Python.
Арифметические Операторы
Компьютерные программы широко используются для математических расчетов. Мы можем написать компьютерную программу, которая может выполнять простые вычисления, такие как сложение двух чисел (2 + 3), и мы также можем написать программу, которая может решить сложное уравнение, такое как P (x) = x 4 + 7x 3 — 5x + 9. Если вы даже были плохим учеником, вы должны знать, что в первом выражении 2 и 3 — операнды, а + — оператор. Подобные понятия существуют в компьютерном программировании.
Взгляните на следующие два примера —
Точно так же язык программирования предоставляет различные арифметические операторы. В следующей таблице перечислены некоторые важные арифметические операторы, доступные на языке программирования Си. Предположим, что переменная A содержит 10, а переменная B содержит 20, тогда —
Ниже приведен простой пример программирования на C для понимания вышеприведенных математических операторов:
Когда вышеуказанная программа выполняется, она дает следующий результат —
Операторы отношений
Рассмотрим ситуацию, когда мы создаем две переменные и присваиваем им некоторые значения следующим образом:
Здесь очевидно, что переменная A больше, чем B по значениям. Итак, нам нужна помощь некоторых символов для написания таких выражений, которые называются реляционными выражениями. Если мы используем язык программирования C, то он будет записан следующим образом:
Здесь мы использовали символ>, и он называется реляционным оператором, и в простейшей форме они выдают логические результаты, что означает, что результат будет либо истинным, либо ложным. Аналогично, язык программирования предоставляет различные реляционные операторы. В следующей таблице перечислены некоторые важные реляционные операторы, доступные в языке программирования C. Предположим, что переменная A содержит 10, а переменная B содержит 20, тогда —
| оператор | Описание | пример |
|---|---|---|
| == | Проверяет, равны ли значения двух операндов или нет, если да, тогда условие становится истинным. | (A == B) не соответствует действительности. |
| знак равно | Проверяет, равны ли значения двух операндов или нет, если значения не равны, тогда условие становится истинным. | (A! = B) верно. |
| > | Проверяет, больше ли значение левого операнда, чем значение правого операнда, если да, тогда условие становится истинным. | (A> B) не соответствует действительности. |
| Проверяет, меньше ли значение левого операнда, чем значение правого операнда, если да, тогда условие становится истинным. | (A | |
| > = | Проверяет, больше ли значение левого операнда или равно значению правого операнда, если да, тогда условие становится истинным. | (A> = B) не соответствует действительности. |
| Проверяет, меньше ли значение левого операнда или равно значению правого операнда, если да, тогда условие становится истинным. | (A |
Когда вышеуказанная программа выполняется, она дает следующий результат —
Логические Операторы
Логические операторы очень важны для любого языка программирования и помогают нам принимать решения на основе определенных условий. Предположим, мы хотим объединить результат двух условий, тогда логические операторы И и ИЛИ помогают нам в получении конечного результата.
В следующей таблице показаны все логические операторы, поддерживаемые языком Си. Предположим, что переменная A содержит 1, а переменная B содержит 0, тогда —
| оператор | Описание | пример |
|---|---|---|
| && | Называется логический оператор И. Если оба операнда отличны от нуля, условие становится истинным. | (A && B) неверно. |
| || | Вызывается логическим оператором ИЛИ. Если любой из двух операндов отличен от нуля, условие становится истинным. | (A || B) верно. |
| ! | Вызывается логическим оператором НЕ. Используйте для изменения логического состояния своего операнда. Если условие истинно, то оператор Логический НЕ будет делать ложь. | ! (A && B) верно. |
Попробуйте следующий пример, чтобы понять все логические операторы, доступные на языке программирования C —
Когда вы компилируете и запускаете вышеуказанную программу, она дает следующий результат —
Операторы в Java
Вы можете попробовать выполнить следующую программу, чтобы увидеть выходные данные, которые должны быть идентичны результату, сгенерированному в приведенном выше примере.
Когда вышеуказанная программа выполняется, она дает следующий результат —
Операторы в Python
Вы можете попробовать выполнить следующую программу, чтобы увидеть выходные данные, которые должны быть идентичны результату, сгенерированному в приведенном выше примере.
Когда вышеуказанная программа выполняется, она дает следующий результат —
Что такое оператор в языке программирования
Оператор — это элемент языка, задающий полное описание действия, которое необходимо выполнить. Каждый оператор представляет собой законченную фразу языка программирования и определяет некоторый вполне законченный этап обработки данных. В состав операторов могут входить служебные слова, данные, выражения и другие операторы. В английском языке данное понятие обозначается словом “statement”, означающим также “предложение”.
Каждый оператор в любом языке программирования имеет определенный синтаксис и семантику. Под синтаксисом оператора понимается система правил (грамматика), определяющая его запись с помощью элементов алфавита данного языка, в который наряду с различными символами входят, например, и служебные слова. Под семантикой оператора понимают его смысл, т.е. те действия, которым соответствует запись того или иного оператора. Например, запись i := i + 1 является примером синтаксически корректной записи оператора присваивания в языке Pascal, семантика которого в данном случае такова: извлечь значение ячейки памяти, соответствующей переменной i, сложить его с единицей, результат записать в ту же ячейку памяти.
В большинстве процедурных языков программирования набор операторов практически одинаков и состоит из оператора присваивания, операторов выбора, операторов цикла, оператора вызова процедуры, операторов перехода. Иногда выделяют также пустой (отсутствие действия) и составной операторы. Многие операторы являются способом представления определенных алгоритмических конструкций (см. “Алгоритмические конструкции” 
) в языке программирования. Рассмотрим группы операторов подробнее, используя синтаксис языка Pascal.
Оператор присваивания
Присваивание — это действие компьютера, в результате которого переменная получает значение вычисленного выражения (оно помещается в соответствующую переменной ячейку памяти). Для описания такого действия в языках программирования существует оператор присваивания.
В общем виде оператор присваивания записывается так:
Например, в языке Pascal в качестве знака присваивания используется комбинация символов :=. В ряде других языков — знак равенства.
Результатом выполнения оператора присваивания является изменение состояния данных: все переменные, отличные от переменной, стоящей в левой части оператора присваивания, не меняют своего значения, а указанная переменная получает значение выражения, стоящего в правой части оператора присваивания. В большинстве случаев требуется, чтобы тип выражения совпадал с типом переменной. Если это не так, то оператор либо считается синтаксически некорректным, либо производится преобразование типа выражения к типу переменной (см. “Типы данных” ).
Операторы выбора
По-другому эти операторы называют условными операторами. Условные операторы используются для программирования алгоритмов, содержащих алгоритмическую конструкцию ветвление.
В языках программирования имеется несколько видов условных операторов. Полный условный оператор соответствует алгоритмической структуре полного ветвления:
В языке программирования соответствующий условный оператор имеет вид:
if B then S1 else S2
Если выражение B, которое вычисляется в начале выполнения условного оператора, имеет значение “истина”, то будет выполняться оператор S1, в противном случае — оператор S2. Операторы S1 и S2 могут быть составными.
Алгоритмическая структура неполного ветвления реализуется с помощью неполного условного оператора, который имеет вид:
Здесь B — логическое выражение, а S — произвольный оператор. Оператор S будет выполняться, если выражение B окажется истинным.
Если условный оператор реализует всего две ветви выбора (“да” и “нет”), то с помощью оператора варианта (case-оператора) можно запрограммировать многоветвящуюся структуру. Оператор варианта имеет вид:
Выполняется данный оператор так: значение выражения E ищется среди перечисленных в записи оператора значений V1, V2, …, Vn, и если такое значение находится, то выполняется соответствующий оператор S1, S2, …, Sn.
В разных языках программирования синтаксис и даже семантика перечисленных операторов могут отличаться, но возможности, предоставляемые программисту подобными конструкциями, примерно одинаковы.
Пример 1. В статье “Алгоритмические конструкции” 2 был приведен пример записи алгоритма решения обобщенного квадратного уравнения с помощью конструкций ветвления. Приведем фрагмент программы на языке Pascal, реализующий этот же алгоритм:
if c = 0 then writeln(‘x — любое’)
else writeln(‘нет корней’)
В цикле с постусловием тело цикла предшествует условию В. В отличие от цикла с предусловием здесь В — это условие окончания цикла. Оператор цикла с постусловием в Паскале имеет вид:
При такой организации цикла тело цикла S хотя бы один раз обязательно выполнится.
Практически во всех процедурных языках существует оператор цикла c параметром. Схематично его можно представить так:
for 
E1 to E2 step E3 do S
Здесь значение переменной (параметра цикла) меняется от значения выражения E1 до E2 с шагом E3. Для каждого такого значения параметра цикла выполняется оператор S. В языке Pascal понятие шага в описании этого оператора отсутствует, а сам шаг для целочисленного параметра цикла может быть равен либо 1, либо –1. Оператор “цикл с параметром” используется для программирования циклов с заданным числом повторений. Для программирования итерационных циклов (число повторений которых заранее неизвестно) он не годится.
Оператор вызова процедуры
В статье “Подпрограммы” 2 подробно рассказывается о таком виде подпрограмм, как процедуры. Стандартные подпрограммы языка программирования, которые входят в одну из библиотек подпрограмм, а также пользовательские подпрограммы, описанные внутри данного блока, вызываются с помощью оператора вызова процедуры:
Здесь E1,E2,…,En — переменные или выражения, представляющие собой фактические параметры обращения к процедуре. Наиболее часто используемыми стандартными процедурами являются процедуры ввода и вывода данных (read и write в Pascal).
Вызов процедуры семантически эквивалентен выполнению блока, описанного в качестве тела процедуры, после передачи в него начальных значений некоторых переменных (параметров-значений) или замены имен некоторых переменных (параметров-переменных) на имена фактических переменных, указанных при вызове процедуры.
Пример 3. Пусть у нас описана процедура abc:
procedure abc(a,b:integer;var c: integer);
Вызов этой процедуры abc(2,3,x) эквивалентен блоку действий:
Наиболее известным в данной группе операторов является оператор безусловного перехода goto. Если ко всем или некоторым уже имеющимся операторам программы добавить метки, то в программе становится возможным использовать оператор перехода вида:
Метка в данном случае соответствует началу того оператора, с которого должно продолжиться выполнение программы. Такой оператор позволяет записывать в языке программирования алгоритмы, имеющие сколь угодно сложную структуру. Но зачастую использование безусловного перехода неоправданно, т.к. ведет к запутанной, плохо читаемой программе. Практически единственным осмысленным применением оператора goto является выход сразу из нескольких вложенных циклов, например, при обработке двухмерных массивов.
Пример 4. Пусть нам требуется определить, есть ли в двухмерном массиве a элемент, равный 0:
if a[i,j] = 0 then begin
1: if b then write(‘есть’) else write(‘нет’);
Программа, разработанная по правилам структурного программирования, не должна содержать операторов безусловного перехода. Приведенную выше программу без использования оператора goto можно переписать следующим образом:
while not b and (i =) and (n a[imax] then imax := i else
Эта программа не просто проще и эффективней. В ней практически невозможно сделать ошибку. Если значений K среди элементов массива несколько, то найдено будет первое справа.
Поиск числа К в упорядоченном массиве
Рассмотрим массив, элементы которого упорядочены по неубыванию. То есть a1 
a2 … an. Поиск элемента, равного K, в таком массиве осуществляется с помощью алгоритма “деления пополам”. По-другому его еще называют бинарным поиском, или дихотомией. Алгоритм заключается в том, что мы сравниваем средний элемент массива с числом K и, в зависимости от результата сравнения, переходим к поиску K либо в левой, либо в правой частях массива. Далее наши действия повторяются, пока рассматриваемая часть массива не будет состоять из одного элемента. Если он не равен K, то такого значения в массиве нет. Приведем пример эффективной реализации данного алгоритма, в результате которой будет найден один из элементов, равный K, или будет обнаружено, что такой элемент в массиве отсутствует:
Алгоритмы сортировки массивов
Задача сортировки массива, то есть перестановки элементов массива так, чтобы они были упорядочены по возрастанию, убыванию или другой аналогичной характеристике, является одной из основных технических задач программирования. С этой задачей мы сталкиваемся и при записи фамилий учеников в классном журнале, и при подведении итогов соревнований, и даже при упорядочении игральных карт, например, при игре в преферанс. Очень часто сортировка используется как первый шаг в алгоритме решения более сложной задачи. Рассмотрим наиболее простые алгоритмы сортировки массивов и подсчитаем их вычислительную сложность (см. “Теория алгоритмов”).
“Пузырьковая” сортировка
Традиционно наиболее простой в реализации считается так называемая “пузырьковая” сортировка. Суть ее в случае упорядочения по неубыванию заключается в следующем. Будем просматривать слева направо все пары соседних элементов: a1 и a2, a2 и a3, …, an-1 и an. Если при этом ai > ai+1, то элементы меняем местами. В результате такого просмотра массива максимальный элемент окажется на крайнем справа (своем) месте. Об остальных элементах ничего определенного сказать невозможно. Будем просматривать массив снова, исключив из рассмотрения правый элемент. На своем месте теперь окажется уже второй по величине элемент. И так далее. В последнем просмотре будут участвовать только первый и второй элементы. Общее число просмотров при этом равно N–1. Приведем фрагмент программы, реализующий описанный алгоритм:
for j := 1 to n — 1 do
При оценке вычислительной сложности алгоритмов сортировки обычно отдельно подсчитывают количество операций сравнения и количество операций присваивания, т.к. заранее неизвестно, какая из них окажется более трудоемкой, ведь сравниваться между собой могут не только числа, но и строки, и другие достаточно сложные объекты. Иногда обе операции сопоставимы по трудоемкости.
Количество сравнений в данном алгоритме равно
Количество присваиваний в три раза больше, чем число выполненных обменов. В худшем случае обмен будет производиться после каждого сравнения и общее число присваиваний будет равно
Говорят, что данный алгоритм имеет квадратичную сложность как по числу сравнений, так и по числу присваиваний. “Пузырьковым” он называется потому, что в результате каждого просмотра максимальный из оставшихся элементов оказывается на своем месте — “всплывает”. По-другому такая сортировка называется обменной.
Сортировка “прямым выбором”
Рассмотрим алгоритм сортировки, основанный на принципиально иной идее. Найдем минимальный элемент в массиве и поменяем его с первым элементом массива. В результате он окажется на своем месте. Затем найдем минимальный элемент среди оставшихся и поменяем его со вторым элементом. На N–1-м шаге мы закончим упорядочивание нашего массива. Такой алгоритм называется сортировкой прямым выбором. Приведем фрагмент программы, реализующий описанный алгоритм:
for j := i + 1 to n do
За рамками статьи остались алгоритмы обработки двухмерных массивов — таблиц. Подобная структура данных часто не рассматривается в базовом курсе информатики. При углубленном изучении программирования зачастую достаточно показать, как с помощью вложенных циклов просмотреть все элементы таблицы. Приведем фрагмент программы, печатающий двухмерный массив, состоящий из N строк
и M столбцов, в виде соответствующей таблицы:
12. Подпрограммы
Вспомогательные алгоритмы и подпрограммы
Алгоритм, выполняющий некоторую относительно автономную, законченную часть основной задачи, называют вспомогательным алгоритмом, а соответствующую “вспомогательную программу” — подпрограммой (или процедурой). Во многих языках программирования процедура оформляется так же или почти так же, как головная программа.
Когда используют подпрограммы? Во-первых, если один и тот же алгоритм используется несколько раз по ходу решения задачи. Это вполне очевидно: зачем несколько раз писать одни и те же команды? Последовательность операторов, составляющих подпрограмму, определена и записана только в одном месте программы, однако их можно вызвать для выполнения из одной или нескольких точек программы. Одна и та же подпрограмма может обрабатывать различные данные, переданные ей в качестве аргументов. Это не просто выделенный кусок кода — для этого куска кода определены входные и выходные параметры, а от прочих данных он, в идеале, изолирован (хотя многие языки программирования позволяют использовать внутри кода подпрограммы и глобальные переменные).
Во-вторых, в разных программах часто используется большое количество однотипных, шаблонных действий — вывод данных на экран, сортировка чисел по возрастанию в числовых массивах или сортировка списков фамилий по алфавиту, различные алгоритмы поиска необходимых данных в массивах — этот перечень стереотипных работ можно продолжать долго. Совершенно очевидна целесообразность однократного составления таких часто употребляемых вспомогательных алгоритмов, хранение их и последующее использование в самых разнообразных задачах. Наборы таких часто употребимых подпрограмм обычно объединяют в библиотеки подпрограмм. Развитой системой библиотечных подпрограмм обладают такие языки программирования, как С++ и Java.
Но, оказывается, на практике подпрограммами гораздо чаще пользуются, чтобы упростить процесс разработки программы. По мере прогресса в искусстве программирования, как пишет автор языка Pascal Н.Вирт, программы стали создаваться методом последовательных уточнений. На каждом этапе программист разбивает задачу на некоторое число подзадач. Таким образом, подпрограммы — это реализация в языке программирования основного и вспомогательных алгоритмов, на которые, как правило, распадается решение общей задачи в процедурном программировании. Концепция процедур (т.е. подпрограмм) позволяет выделить подзадачу как отдельную подпрограмму, даже если вызываться она будет всего один раз. Допустим, нужно составить какую-нибудь достаточно сложную программу: она должна получать от человека исходные данные, проверяя при этом правильность ввода (чтоб не было ошибок, вроде “32 февраля”), затем выполнять несколько разных вычислений, наконец, — красиво выводить результаты на экран. Можно попытаться написать сразу всю программу целиком. Однако она скорее всего получится очень большой и настолько запутанной, что поиск любой самой простой ошибки займет много времени (а написать даже не очень большую программу сразу без ошибок практически невозможно). Но можно поступить по-другому. Сначала разобьем решение задачи на несколько этапов. Получится программа примерно такого вида:
Мы еще не знаем, как будут реализовываться эти этапы, но то, что они необходимы, нам известно; не возникает вопросов и с их последовательностью. Далее, каждый из этапов разбиваем на более мелкие, затем, при необходимости — еще. Так продолжаем, пока подзадачи не окажутся настолько мелкими, что каждую из них можно будет записать с помощью небольшой простой и понятной процедуры. Можно сказать, что подпрограммы являются основными строительными блоками программы. Такой способ разработки программ называют проектированием методом сверху вниз.
Каковы достоинства этого метода? Во-первых, сокращение времени разработки больших программ: на решение 10 простых задач обычно нужно гораздо меньше времени, чем на одну, в 10 раз более сложную. Во-вторых, локализация мест ошибок при отладке программ: разобраться в работе процедуры и найти возможную ошибку намного проще, если эта процедура — короткая. В-третьих, относительная автономность модификации программы: когда нужно будет что-либо изменить в программе, переделывать придется не всю ее, а только некоторые процедуры. Наконец, такой метод позволяет легко распределить работу между несколькими программистами: при разработке процедуры абсолютно не важно, что содержится внутри других.
Процедуры и функции
Во многих языках программирования явно (как в Pascal) или неявно (как в С и С++) различают два вида подпрограмм — процедуры и функции. Основное отличие функций от процедур заключается в том, что функция возвращает результат некоторого типа.
После описания функции ее, как лексическую единицу, можно использовать в выражениях наряду со стандартными функциями. Функция активируется только при вызове ее из тела основной программы или из другой уже вызванной подпрограммы (процедуры или функции). При вызове функции указывается имя функции и конкретные параметры (их называют фактические параметры), необходимые для вычисления функции.
В описании процедуры или функции задается список формальных параметров. Каждый параметр, описанный в этом списке, является локальным по отношению к описываемой процедуре или функции, т.е. на него можно ссылаться по его имени из данной подпрограммы, но не из основной программы.
Приведем пример программы на языке Pascal нахождения максимума из трех чисел, использующей описание функции max нахождения максимума из двух чисел:
function max(a, b: integer): integer;
if a > b then max := a
Процедура либо вообще не возвращает результат, либо делает это через параметры. Процедура активируется (вызывается) с помощью оператора процедуры. Он представляет собой то же имя, что и название процедуры, с перечислением в скобках фактических параметров (процедура параметров может и не содержать, например, процедура очистки экрана).
Приведем пример описания процедуры на языке Pascal, которая печатает первые N элементов массива. Используем эту процедуру для печати различных частей массива:
type aa = array[1..100] of integer;
procedure print(n: integer; var m: aa);
for i := 1 to 100 do a[i] := random(100);
for i := 1 to 100 do print(a,i)
Процедура или функция является рекурсивной, если она прямо или косвенно вызывает сама себя. То есть либо при описании функции или процедуры используется обращение к ней же самой, но с другим набором параметров, либо подпрограмма вызывает какую-либо другую подпрограмму, в описании которой содержится вызов исходной (например, процедура A вызывает процедуру В, а процедура В вызывает процедуру А).
Рекурсивный вариант реализации алгоритма обычно выглядит изящнее и дает более компактный текст программы, но исполняется медленнее. Приведем пример уместного использования рекурсивного алгоритма. Рассмотрим алгоритм эффективного возведения вещественного числа x в целую неотрицательную степень n, основанный на следующих очевидных соотношениях:
Зададим по данному описанию рекурсивную функцию на языке Pascal:
function power(x:real; n:integer):integer;
if n = 0 then power := 1
power := power(x*x,n div)
else power := power(x,n-1)*x
Данная функция для вычисления x n будет использовать не более 2log2n умножений, а ее нерекурсивный аналог написать и отладить существенно сложнее.
Процедурное программирование
Процедурное программирование — это одна из парадигм программирования.
Парадигма программирования представляет (и определяет) то, как программист подходит к реализации алгоритма и проектированию программы. Так, процедурное программирование основано на представлении программы, как определенной последовательности вызова процедур.
Процедурное программирование — оформившаяся в начале 70-х годов XX века идея разработки программ. Это фундаментальная концепция, являющаяся основой всех современных подходов к проектированию и реализации. В то же время суть ее проста и отражает широко известные методы, заключающиеся в поиске и реализации некоторого базового набора элементов, комбинация которых дает решение задачи.
Если концепция структурного программирования предлагает некоторый универсальный алгоритмический базис, то процедурное программирование состоит в разработке под конкретную задачу или круг задач (предметную область) собственного базиса в виде набора подпрограмм, позволяющего наиболее эффективно по целому ряду критериев построить программный комплекс. С применением процедурного программирования появились возможности коллективной разработки программ как набора “независимых” частей, последовательного уменьшения сложности методом разбиения сложной задачи на более простые подзадачи, наконец, возможности повторного использования созданного ранее кода.
Решение общей задачи даже в простейших случаях представляет собой многоступенчатый процесс расчленения на все более простые действия. Конечно, можно составить весь алгоритм без явного выделения вспомогательных действий, но такую программу будет не только неудобно составлять и отлаживать, ее будет чрезвычайно сложно читать и практически невозможно совершенствовать.
Обычно процедурная программа состоит из главной подпрограммы (она нужна для определения начала и конца общего алгоритма), которая что-то делает сама, а что-то поручает вызываемым на выполнение вспомогательным подпрограммам, которые, в свою очередь, делают что-то сами и, возможно, вызывают на выполнение другие вспомогательные подпрограммы и т.д. После завершения подпрограмма должна возвратить управление в точку вызова — точнее, на оператор, следующий за вызовом подпрограммы.
Процедуры и функции позволяют создавать большие структурированные программы, которые можно делить на части. Это дает преимущества в следующих ситуациях:
1. Если программа большая, разделение ее на части облегчает создание, тестирование и ее сборку.
2. Если программа большая и повторная компиляция всего исходного текста занимает много времени, разделение ее на части экономит время компиляции.
3. Если процедуру надо использовать в разных случаях разным образом, можно записать ее в отдельный файл и скомпилировать отдельно.
Более современная парадигма программирования — объектно-ориентированное программирование (см. статью “Объектно-ориентированное программирование”) — фактически включает в себя и процедурную парадигму.
Методические рекомендации
Данная тема возникает при изучении программирования на языках высокого уровня или на языке исполнителя, например, LOGO. Слово подпрограмма (routine) использовалось уже в 1949 г. при программировании на машине EDSAC, которую принято считать первой построенной машиной с хранением программ в памяти. Подпрограмма является основным строительным блоком в императивном программировании (такое программирование описывает процесс выполнения программы в виде инструкций, изменяющих состояние исполнителя, альтернативой императивному программированию служит декларативное — логическое или функциональное — программирование).
Подпрограммы используются главным образом для целей абстракции. Под абстракцией понимается действие, состоящее в выборе для дальнейшего изучения или использования небольшого числа свойств объекта и изъятии из рассмотрения остальных свойств, которые нам в данный момент не нужны. Основное свойство, которое выделяется при написании подпрограммы, — это то, что она делает. Главное свойство, которое опускается из рассмотрения, — как она это делает. В некотором смысле использование подпрограммы — в точности то же самое, что и использование любой другой операции, применимой в том или ином языке программирования, например, +. А написание подпрограммы — это расширение языка путем включения в него новой операции.
Существуют подходы к изучению языка программирования, в которых подпрограммы предлагается использовать на самых ранних этапах изучения языка, а в таких языках, как С, этого вообще практически не избежать. При этом допускается сначала не полное понимание того, что же представляют собой подпрограммы, какую память они используют и как происходит передача параметров при их вызове. Возможно, такой подход позволяет сразу вырабатывать правильный стиль написания структурированных программ. Однако учебные программы, которые ученикам приходится писать на первых этапах обучения, зачастую не требуют детализации с помощью процедур и функций, поэтому изучение последних можно отложить и на более поздний срок (или опустить совсем, если курс программирования является чисто ознакомительным).
В некоторых языках программирования, например в языке Pascal, достаточно сложным является механизм передачи параметров и следующие из него правила разделения параметров на параметры-значения и параметры-ссылки. Попробуйте объяснить учащимся этот механизм, только в этом случае они смогут грамотно и без ошибок выбирать тип параметров при описании процедур и функций.
Подробное изучение данной темы в 10–11-х профильных классах заканчивается рассмотрением рекурсии, ее применением и механизмом реализации в тех языках программирования, в которых она разрешена.
13. Разработка программ
Программирование — одна из первых автоматизированных информационных технологий — начиная с 70-х годов прошлого столетия начала новый виток бурного развития. Связано это в первую очередь с информатизацией общества в целом: сегодня практически все виды человеческой деятельности в той или иной степени автоматизированы, для чего разрабатывается специальное программное обеспечение. В сфере разработки программного обеспечения работают миллионы людей. Программирование как область человеческой деятельности характеризуется определенными этапами и способами создания законченного программного продукта, формами организации взаимодействия разработчиков-программистов. И в первую очередь среди этих характеристик важно выделить парадигмы и технологии программирования.
Парадигма программирования
Слово парадигма (от гр. paraRdeigma) означает пример, образец. Известный американский философ Кун Томас Самюэл дал следующее определение этого понятия. Парадигма — совокупность знаний, методов и ценностей, безоговорочно разделяемых членами научного сообщества. Под парадигмой программирования сегодня понимают некоторый взаимосвязанный набор идей и рекомендаций, определяющих стиль написания программ. Парадигма программирования представляет (и определяет) то, как программист видит выполнение программы. В современном программировании сложилось несколько видов парадигм программирования: императивное, процедурное (см. “Подпрограммы”), объектно-ориентированное, декларативное программирование, к которому относят логическое и функциональное программирование.
Так, в объектно-ориентированном программировании (см. “Объектно-ориентированное программирование”) программист рассматривает программу как набор взаимодействующих объектов, тогда как в функциональном программировании программа представляется в виде цепочки вычисления функций. В императивном программировании исполнителю программы четко предписывается последовательность выполняемых действий, в то время как в функциональном программировании способ решения задачи описывается при помощи зависимости функций друг от друга (в том числе возможны рекурсивные зависимости), но без указания последовательности шагов. В логическом программировании программа представляет собой множество пар (логическое условие, новые факты), при этом так же, как и в функциональном программировании, программист остается в неведении о методах, применяемых при вычислении, и последовательности исполнения элементарных действий. БoRльшая часть ответственности за эффективность вычислений в логическом и функциональном программировании перекладывается на транслятор используемого языка программирования. Успешность реализации выбранной парадигмы программирования во многом определяется выбором соответствующего языка программирования (см. “Языки программирования”).
Технологии программирования
Вне зависимости от выбранной парадигмы разработка программы включает в себя следующие этапы: проектирование (уточнение способов организации данных — структур и типов данных (см. “Структуры данных”, “Типы данных”), разработка алгоритма и запись его на выбранном языке программирования), тестирование, отладка и документирование программы. Промышленная разработка программ сталкивается с проблемами стоимости и надежности. Некоторые программы содержат миллионы строк исходного кода, которые, как ожидается, должны правильно исполняться в реальных условиях. Для эффективной разработки больших или сложных программ используются различные технологии программирования.
Как правило, программы разрабатываются в расчете на то, чтобы ими могли пользоваться люди, не участвующие в их разработке (их называют пользователями). Программа или логически связанная совокупность программ на носителях данных, снабженная программной документацией, называется программным средством (ПС). Программа позволяет осуществлять некоторую автоматическую обработку данных на компьютере. Программная документация позволяет понять, какие функции выполняет та или иная программа ПС, как подготовить исходные данные и запустить требуемую программу для выполнения, а также, что означают получаемые результаты (или каков эффект выполнения этой программы). Кроме того, программная документация помогает разобраться в самой программе, что необходимо, например, при ее модификации.
В соответствии с обычным значением слова “технология” (см. “Информационные технологии”) под технологией программирования понимается совокупность производственных процессов, приводящая к созданию требуемого ПС, а также описание этой совокупности процессов. Другими словами, под технологией программирования понимается как технология разработки программных средств, включая в нее все процессы, начиная с момента зарождения идеи этого средства, так и процессы, связанные с созданием необходимой программной документации.
По мере повышения мощности компьютеров и развития средств и методологии программирования растет и сложность решаемых на компьютерах задач, что привело к повышенному вниманию к технологии программирования. Резкое удешевление стоимости компьютеров и в особенности стоимости хранения информации на компьютерных носителях привело к широкому внедрению компьютеров практически во все сферы человеческой деятельности, что существенно изменило направленность технологии программирования. Сформировалось понятие качества ПС, в котором акценты ставятся не только на его эффективности, но и на удобстве работы с ним для пользователей (не говоря уже о его надежности). Широкое использование компьютерных сетей привело к интенсивному развитию распределенных вычислений, дистанционного доступа к информации и электронного способа обмена сообщениями между людьми. Компьютерная техника из средства решения отдельных задач все более превращается в средство информационного моделирования реального и мыслимого мира. Все это ставит перед технологией программирования новые и достаточно трудные проблемы.
В 50-е годы мощность компьютеров была невелика (компьютеры первого поколения), а программирование для них велось в основном в машинном коде. Решались главным образом научно-технические задачи (расчет по формулам), задание на программирование уже содержало, как правило, достаточно точную постановку задачи. Использовалась интуитивная технология программирования: почти сразу приступали к составлению программы по заданию, при этом часто задание несколько раз изменялось, минимальная документация оформлялась уже после того, как программа начинала работать. Тем не менее именно в этот период родилась фундаментальная для технологии программирования концепция модульного программирования (для преодоления трудностей программирования в машинном коде). Появились первые языки программирования высокого уровня.
В 60-е годы можно было наблюдать бурное развитие и широкое использование языков программирования высокого уровня (АЛГОЛ-60, ФОРТРАН, КОБОЛ и др.), роль которых в технологии программирования явно преувеличивалась. Надежда на то, что эти языки решат все проблемы разработки больших программ, не оправдалась. В результате повышения мощности компьютеров и накопления опыта программирования на языках высокого уровня быстро росла сложность решаемых на компьютерах задач: стало понятно, что важно не только то, какой язык программирования используется, но и то, как создается программа. Появление прерываний в компьютерах 2-го поколения привело к развитию мультипрограммирования и созданию больших программных систем. Последнее стало возможным с использованием коллективной разработки, которая поставила ряд серьезных технологических проблем.
В 70-е годы широкое распространение и обоснование получили технологии нисходящей разработки и структурного программирования, модульного программирования, создание методики управления коллективной разработкой ПС, появление инструментальных программных средств (программных инструментов) поддержки технологии программирования. Развитие технологии структурного программирования связано с публикацией письма Эдсгера Дийкстры в Ассоциацию вычислительной техники (1968 г.) (ACM — Association for Computing Machinery), озаглавленного так: “О вреде использования операторов GOTO”. В те времена программы писались с активным использованием операторов безусловного перехода. Обращая внимание на недостатки таких программ, Дийкстра предложил концепцию структурного программирования, позволяющую избежать использования этих операторов. Концепция Дийкстры основывалась на доказательстве Бома и Джакопини, что для записи любой программы в принципе достаточно только трех конструкций управления — последовательного выполнения, ветвления и цикла, то есть что теоретически необходимость в использовании операторов перехода отсутствует (см. также статью “Алгоритмические конструкции”).
Следующий шаг в развитии структурного программирования связан с введением аппарата подпрограмм, позволяющих разбивать структурную программу на обозримые по своим размерам части. При таком подходе программа пишется в терминах вызова подпрограмм верхнего уровня, которые реализуются при помощи подпрограмм более низкого уровня, и т.д. На основе нисходящего структурного программирования (программирование по технологии “сверху вниз”, см. статью “Подпрограммы”) была разработана технология коллективной разработки больших программных комплексов.
80-е и 90-е годы знаменательны широким охватом человеческого общества международной компьютерной сетью, персональные компьютеры стали подключаться к ней как терминалы. Это поставило ряд проблем регулирования доступа к компьютерно-сетевой информации (как технологического, так и юридического и этического характера). Остро встала проблема защиты компьютерной информации и передаваемых по сети сообщений. Стали бурно развиваться CASE—технологии (Computer-Aided Software Engineering) разработки ПС и связанные с ними формальные методы спецификации программ.
В связи с широким внедрением персональных компьютеров во все сферы человеческой деятельности важной составляющей разработки программ стало проектирование взаимодействия пользователя с программой (ее интерфейса). Широкое применение графического пользовательского интерфейса ведет к тому, что многие аспекты разработки приложений лежат за пределами математики и даже алгоритмики и требуют серьезного внимания к психологическим основам взаимодействия “человек — машина”. При разработке графического интерфейса большую роль играет технология визуального программирования, в которой программист оформляет свою будущую программу, используя некоторый конструктор элементов интерфейса, и видит результаты своей работы еще до запуска самой программы.
В последнее время получила распространение еще одна технология разработки программ — экстремальное программирование. По этой технологии с самого начала программа пишется в предположении, что заказчик заранее не может сформулировать все требования к программному продукту, поэтому программа все время будет меняться, в том числе в процессе работы над ней. Одним из элементов экстремального программирования является парное программирование. Оно означает, что любой кусок кода создается парами людей, программирующими одну задачу сидя за одним рабочим местом. Один программист работает над кодированием конкретных частей программы, другой сосредоточен на картине в целом и непрерывно просматривает код, производимый первым программистом с целью сделать его абсолютно прозрачным. Время от времени люди меняются ролями. Пары не фиксированы: рекомендуется “перемешивать” их насколько это возможно, так чтобы каждый знал, что делает каждый другой, и все были знакомы со всей системой в целом.
Отладка и тестирование программ
Отладка программы — это деятельность, направленная на обнаружение и исправление ошибок в программе. Обнаружить ошибки, связанные с нарушением правил записи программы на языке программирования (синтаксические и семантические ошибки), помогает используемая система программирования. Пользователь получает сообщение об ошибке, исправляет ее и снова повторяет попытку исполнить программу.
Тестирование программы — это процесс выполнения программы с целью обнаружения ошибки в программе на некотором наборе данных, для которого заранее известен результат применения или известны правила поведения этих программ. Указанный набор данных называется тестовым или просто тестом. Прохождение теста — необходимое условие правильности программы. На тестах проверяется правильность реализации программой запланированного алгоритма. Таким образом, отладку можно представить в виде многократного повторения трех процессов: тестирования, в результате которого может быть констатировано наличие в ПС ошибки, поиска места ошибки в программах и документации ПС и редактирования программ и документации с целью устранения обнаруженной ошибки.
Успех отладки в значительной степени предопределяет рациональная организация тестирования. При отладке отыскиваются и устраняются в основном те ошибки, наличие которых в программе устанавливается при тестировании. Тестирование не может доказать правильность программы, в лучшем случае оно может продемонстрировать наличие в нем ошибки. Другими словами, нельзя гарантировать, что тестированием программы на соответствующих наборах тестов можно установить наличие каждой имеющейся в программе ошибки. Поэтому возникают две задачи. Первая: подготовить такой набор тестов и применить к ним программу, чтобы обнаружить в нем по возможности большее число ошибок. Однако чем дольше продолжается процесс тестирования (и отладки в целом), тем большей становится стоимость программы. Отсюда вторая задача: определить момент окончания отладки программы (или отдельной ее компоненты). Признаком возможности окончания отладки является полнота охвата тестами, к которым применена программа, множества различных ситуаций, возникающих при выполнении программы, и относительно редкое проявление ошибок в программе на последнем отрезке процесса тестирования. Последнее определяется в соответствии с требуемой степенью надежности программы, указанной в спецификации ее качества.
Для оптимизации набора тестов, т.е. для подготовки такого набора тестов, который позволял бы при заданном их числе (или при заданном интервале времени, отведенном на тестирование) обнаруживать большее число ошибок, необходимо, во-первых, заранее планировать этот набор и, во-вторых, использовать рациональную стратегию планирования тестов.
Таким образом, тестирование и отладка включают в себя синтаксическую отладку; отладку семантики и логической структуры программы; тестовые расчеты и анализ результатов тестирования. Затем идет совершенствование программы.
Документирование программы
При разработке ПС создается большой объем разнообразной документации. Продуманная документация программных разработок облегчает совместную работу над проектом больших групп программистов, позволяет подключать новых людей, избегать дублирования многих действий. В итоге повышается производительность труда программистов и увеличивается надежность кода. Кроме того, документация необходима для управления разработкой ПС и для передачи пользователям информации, необходимой для применения и сопровождения ПС. На создание этой документации приходится большая доля стоимости ПС.
Всю документацию можно разбить на две группы:
· документы управления разработкой ПС;
· документы, входящие в состав ПС.
Документы управления разработкой ПС протоколируют процессы разработки и сопровождения ПС, обеспечивая связи внутри коллектива разработчиков и между коллективом разработчиков и менеджерами — лицами, управляющими разработкой.
Пользовательская документация ПС объясняет пользователям, как они должны действовать, чтобы применить данное ПС. Она необходима, если ПС предполагает какое-либо взаимодействие с пользователями. К такой документации относятся документы, которыми руководствуется пользователь при инсталляции ПС, при применении ПС для решения своих задач и при управлении ПС (например, когда данное ПС взаимодействует с другими системами). Эти документы частично затрагивают вопросы сопровождения ПС, но не касаются вопросов, связанных с модификацией программ.
Системы программирования
Написание даже учебных программ практически невозможно без соответствующей системы программирования (среды программирования или интегрированной среды разработки IDE — integrated development environment). Первая среда разработки была создана для языка Basic. Среда программирования включает прежде всего текстовый редактор, позволяющий конструировать программы на заданном языке программирования, а также инструменты, позволяющие компилировать или интерпретировать программы на этом языке, тестировать и отлаживать полученные программы. Кроме того, могут быть и другие инструменты, например, для анализа программ, контроля версий, автоматического создания кода элементов интерфейса и др.
Различают следующие классы сред программирования (см. схему):
· среды общего назначения;
Классификация инструментальных сред программирования
Среды общего назначения содержат набор программных инструментов, поддерживающих разработку программ на разных языках программирования. Языково-ориентированная инструментальная среда программирования предназначена для поддержки разработки программы на каком-либо одном языке программирования, и знания об этом языке существенно использовались при построении такой среды. Вследствие этого в такой среде могут быть доступны достаточно мощные возможности, учитывающие специфику данного языка. Такие среды разделяются на два подкласса.
Классификация инструментальных сред программирования
Интерпретирующие и компилирующие среды, помимо текстового редактора, обеспечивают интерпретацию или компиляцию программ на данном языке программирования. Синтаксически-управляемая среда программирования уже на этапе написания текста программы использует знание синтаксиса языка программирования, на который она ориентирована.
В такой среде вместо текстового используется синтаксически-управляемый редактор, позволяющий пользователю использовать различные шаблоны синтаксических конструкций (в результате этого разрабатываемая программа по окончании написания всегда будет синтаксически правильной). Наряду с промышленными синтаксически-управляемыми средами, например для языка JAVA, подобными свойствами обладают и некоторые специально разработанные учебные среды, например, для языка Pascal.
Многие современные среды программирования поддерживают технологию визуального программирования. В среде визуальной разработки наиболее распространенные блоки программного кода представлены в виде графических объектов. Программист располагает на будущих окнах своей программы необходимые элементы, позиционирует, устанавливает нужные размеры, меняет их свойства. Остается написать только программный код, реализующий свойства элементов интерфейса, доступных только во время работы приложения: описание реакций на события — появление окна, нажатие на кнопку и др. Для задания каких-либо свойств элементу разрабатываемого приложения вовсе не обязательно писать строки программного кода, достаточно изменить это свойство в инспекторе объектов (так называемом “мониторе свойств выбранного элемента”). Это изменение автоматически дополнит или модифицирует программный код. Преимуществами этой технологии являются быстрота разработки, относительная легкость освоения, стандартизация внешнего вида программ. Недостатки заключаются в том, что часть кода не контролируется программистом, код может получиться менее эффективным, нежели при написании его “вручную”. Примерами визуальных сред программирования являются системы программирования Borland Delphi и Visual Basic.
Методические рекомендации
Государственный образовательный стандарт предусматривает изучение в профильной школе принципов разработки программ и знакомство с системами программирования. Очевидно, что изучение данных тем невозможно в отрыве от изучения языка программирования и практических занятий по написанию программ. Знакомство со средами программирования обычно начинается еще в начальной школе или 5–7-х классах основной школы с работы в среде учебного исполнителя или в среде LOGO. Наиболее совершенные версии последней (например, LOGO-миры) фактически представляют собой современные среды, поддерживающие визуальную технологию разработки программ и объектно-ориентированную парадигму программирования.
Работа со средами программирования для универсальных языков программирования высокого уровня (см. “Языки программирования””) обычно начинается в 8–9-х классах с системы Borland Pascal или Quick Basic. На этом этапе учащиеся знакомятся с принципами отладки программ, получают навыки их тестирования. В профильном курсе информатики для старших классов средней школы возможна продуктивная работа с современными профессиональными средами программирования, такими, как Borland Delphi и Visual Basic. Курс по освоению последней среды подкреплен материалами учебника Н.Д. Угриновича “Информатика и информационные технологии. Учебник для 10–11-х классов”, 2005, изд-во “БИНОМ. Лаборатория Знаний”. Здесь на первый план выходит овладение визуальной технологией разработки программы, оптимизация ее интерфейса. Несмотря на то что в учебное время работа с подобными средами ведется практически в ознакомительном режиме, зачастую этого достаточно, чтобы наиболее заинтересованные школьники получили мощный толчок для самостоятельного углубленного освоения возможностей системы. В результате некоторые из них уже в школе создают прикладные программы практически профессионального уровня, которые с успехом демонстрируют на различных конференциях и конкурсах программ.
14. Способы записи алгоритмов
Для записи алгоритмов (см. статью “Алгоритм”) существуют различные формы записи: словесная, блок-схема, программа на каком-либо алгоритмическом языке, нормальный алгоритм Маркова, машина Тьюринга, машина Поста и др. Такое многообразие форм записи алгоритмов обусловлено разными целями работы с алгоритмами. Математики, доказывая правильность алгоритма, естественно, будут работать с формальным представлением алгоритма, например, в виде нормального алгоритма Маркова. Учитель, объясняя сложный алгоритм в школе, может для наглядности использовать запись в виде блок-схемы. Опытные программисты запишут алгоритм в виде программы. При изучении в школе темы “Алгоритмизация и программирование” основными являются следующие способы представления алгоритмов: запись алгоритмов в виде текстовых описаний, блок-схемы и запись в виде программы для того или иного исполнителя (см. “Исполнители алгоритмов”).
Здесь нельзя не упомянуть и учебный Алгоритмический язык, введенный в школьную информатику Ершовым, затем используемый в учебниках А.Г. Кушниренко, А.Г. Гейна, И.Г. Семакина. Учебный Алгоритмический язык — это русскоязычный структурный псевдокод. Педагогический опыт показывает эффективность на начальных этапах обучения программированию “трехступенчатой” методики разработки программ: блок-схема — Алгоритмический язык — язык программирования (лучше всего — Паскаль, поскольку АЯ — паскалеобразен).
Текстовые описания
Текстовая (словесно-формульная) форма записи алгоритмов обычно используется для алгоритмов, ориентированных на исполнителя-человека. Алгоритм задается в произвольном изложении на естественном языке, возможно, с использованием формул. Описание может быть разбито на пункты (шаги алгоритма). Команды такого алгоритма выполняются в естественной последовательности, если не оговорено противного. Словесный способ записи алгоритмов допускает неоднозначность толкования отдельных предписаний, особенно если система команд исполнителя того или иного алгоритма (конкретного человека) четко не фиксирована.
Такой способ широко распространен при описании решения математических, химических, физических и бытовых задач, в том числе в соответствующих школьных учебниках. В решении этих задач практически отсутствуют циклические алгоритмические конструкции (см. “Алгоритмические конструкции”). Алгоритмическая конструкция ветвление записывается либо с помощью одного предложения: “Если дискриминант меньше нуля, то у уравнения нет решения, в противном случае …”, либо с помощью указания, какой из пунктов алгоритма нужно выполнять в том или ином случае: “Если при звонке по телефону гудки короткие, то п. 4, а если длинные, то п. 6”.
Блок-схемы
Блок-схемы алгоритмов — это графическое описание алгоритмов как последовательности действий. Описание алгоритма с помощью блок-схем осуществляется рисованием последовательности функциональных блоков, каждый из которых подразумевает выполнение определенного действия алгоритма. Порядок выполнения действий указывается стрелками. Написание алгоритмов с помощью блок-схем регламентируется ГОСТом. Внешний вид основных блоков, применяемых при написании блок-схем, приведен на рисунке:
В схеме алгоритма каждому типу действий соответствует геометрическая фигура. Фигуры соединяются линиями переходов, определяющими очередность выполнения действий. В блок-схемах всегда есть начало и конец, обозначаемые эллипсами, между ними — последовательность шагов алгоритма, соединенных стрелками. Шаги бывают безусловными (изображаются прямоугольниками, параллелограммами) и условными (изображаются ромбами). Из ромба всегда выходят две стрелки — одна означает дальнейший путь, в случае выполнения условия (обозначается обычно словом “да” или “+”), другая — невыполнение (слово “нет” или “–”). Ввод с клавиатуры или вывод на экран значения выражения изображается параллелограммом. Команда, выполняющая обработку действий (обычно команда присваивания), изображается в прямоугольнике.
Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным. Однако сохраняет и некоторые недостатки. С помощью блок-схем можно записывать в том числе и неформальные (например, бытовые) алгоритмы, содержание функциональных блоков при этом остается относительно произвольным. Отсутствие явных ограничений на правила перехода в блок-схемах приводит к тому, что в них не всегда можно явно выделить базовые алгоритмические конструкции, т.е. алгоритм, записанный таким образом, может не соответствовать требованиям структурного программирования. Наконец, обозримыми являются блок-схемы только для небольших алгоритмов. При составлении блок-схем надо внимательно следить за структурностью алгоритма, т.е. блок-схема произвольного алгоритма должна быть композицией схем основных алгоритмических конструкций, в противном случае программирование подобного алгоритма будет затруднено.
Программы
При записи алгоритма как в словесной форме, так и в виде блок-схем допускается определенный произвол при изображении команд. Вместе с тем такая запись точна настолько, что позволяет человеку понять суть дела и исполнить алгоритм. Однако на практике в качестве исполнителей алгоритмов используются специальные автоматы, в частности, компьютеры. Поэтому алгоритм, предназначенный для того или иного исполнителя, должен быть записан на “понятном” ему языке, c использованием только СКИ (см. статью “Исполнитель алгоритмов”). И здесь на первый план выдвигается необходимость точной записи команд, не оставляющей места для произвольного толкования их исполнителем. Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык для компьютера-исполнителя принято называть языком программирования (см. статью “Языки программирования”), а запись алгоритма на этом языке — программой для компьютера.
Программами являются и запись нормальных алгоритмов Маркова, и машина Тьюринга для решения конкретной задачи (см. статью “Теория алгоритмов”).
Методические рекомендации
На разных ступенях школьного образования используются различные способы записи алгоритмов. В начальной школе это в первую очередь словесная форма записи, реже — блок-схемы. При работе с учебными исполнителями, например, входящими в комплект “Роботландии”, алгоритмы записываются на языке соответствующего исполнителя, что является очень важным шагом к осмыслению понятия формализации алгоритмов.
В базовом курсе информатики алгоритмы записывают с помощью блок-схем, на школьном алгоритмическом языке или языке программирования высокого уровня. В школьном курсе информатики наиболее часто используют такие языки, как Pascal и Basic.
В профильной школе возможен переход к профессиональным версиям языков программирования, например, Delphi или Visual Basic. Однако неоправданным является построение сквозного курса информатики, в котором акцент делается на изучение именно языков программирования, например, сначала изучается Basic, потом Pascal, а потом С. Если на освоение программирования можно выделить достаточное число часов, то правильнее отвести их на изучение различных алгоритмов, в том числе выходящих за рамки базового курса информатики, а также на знакомство с современными технологиями и парадигмами программирования (см. “Разработка программ”, “Объектно-ориентированное программирование”).
15. Структуры данных
Понятие структуры данных
Необходимым условием построения алгоритма является формализация данных, т.е. приведение информации к некоторой информационной модели (см. “Информационные модели”), уже описанной и исследованной. Когда такая модель найдена, говорят, что определена абстрактная структура данных.
Абстрактная структура данных описывает признаки и свойства объекта, взаимосвязь между элементами объекта, а также возможные операции над данным объектом или классом объектов.
Одной из задач информатики является нахождение форм представления информации, удобных для компьютерной обработки. Информатика как точная наука работает с формальными (описанными математически строго) объектами. Такими объектами — базовыми абстрактными структурами данных, используемыми в информатике, являются:
Для компьютерной обработки этих объектов в языках программирования существуют соответствующие типы данных (см. “Типы данных”). Базовые объекты можно объединять в более сложные структуры, добавляя операции уже над структурой в целом и правила доступа к отдельным элементам этой абстрактной структуры данных.
К таким абстрактным структурам данных относятся:
· векторы (конечные массивы);
· таблицы (матрицы), а в общем случае — многомерные массивы;
o последовательности символов, чисел;
Удачный выбор структуры данных часто является залогом создания эффективного алгоритма и программы, его реализующей: используя аналогию структур данных и реальных объектов, можно находить эффективные решения задач.
Заметим, что перечисленные структуры существуют независимо от их реализации при программировании. С этими структурами данных работали и в XVIII, и в XIX веках, когда еще не придумали вычислительную машину. Мы можем разрабатывать алгоритм в терминах абстрактной структуры данных, но для реализации алгоритма в конкретном языке программирования необходимо найти способ ее представления в терминах типов данных и операторов, поддерживаемых данным языком программирования (см. “Операторы языка программирования”). Для компьютерного представления абстрактных структур используются структуры данных, которые представляют собой набор переменных, возможно различных типов данных, объединенных определенным образом. Для конструирования таких структур, как вектор, таблица, строка, последовательность, в большинстве языков программирования присутствуют стандартные типы данных: одномерный массив, двухмерный массив, строка, файл (реже список) соответственно. Организацию остальных структур данных, в первую очередь динамических структур, размер которых меняется во время выполнения программы, программисту приходится осуществлять самостоятельно, используя базовые типы данных. Рассмотрим такие структуры подробнее.
Списки
Линейный список — последовательность линейно связанных элементов, для которых разрешены операции добавления элементов в произвольное место списка и удаление любого элемента. Линейный список однозначно задается указателем на начало списка. Типовыми операциями над списками являются: обход списка, поиск заданного элемента, вставка элемента сразу после или перед определенным элементом, удаление заданного элемента, объединение двух списков в один, разбиение одного списка на два и более списков и т.п.
В линейном списке для каждого элемента, кроме первого, есть предыдущий элемент; для каждого элемента, кроме последнего, есть следующий элемент. Таким образом, все элементы списка упорядочены. Однако обработка линейного односвязного списка не всегда удобна, т.к. отсутствует возможность движения в противоположную сторону — от конца списка к началу. В линейном списке можно обойти все элементы, только двигаясь последовательно от текущего элемента к следующему, начиная с первого, прямой доступ к i-му по счету элементу невозможен.
Пример 1. Порядок следования записей фамилий читателей в компьютере библиотекаря определяет отношение “предыдущий–следующий”. Как правило, сами записи имеют дополнительное свойство — они упорядочены по алфавиту. Над этим списком реализованы операции добавления нового читателя и, при необходимости, удаления старого. Если к тому же ведутся записи выданных каждому читателю книг, то каждую такую запись удобно представлять опять же с помощью списка выданных книг.
Кольцевые списки — такая же структура, как и линейный список, но имеющая дополнительную связь между последним и первым элементом, то есть следующим за последним элементом является первый элемент.
В кольцевом списке в отличие от линейного все элементы равноправны (поскольку для каждого элемента определены и предыдущий, и следующий элементы). Выделение “первого” и “последнего” элементов в кольцевом списке весьма условно, так как собственно структура списка не имеет явно выделенных элементов!
Пример 2. Во многих играх дети используют считалочки, чтобы выбрать ведущего, разделиться на команды и т.п. Как правило, считалочки длинные, и дети (сами того не зная) организуют кольцевой список. Отношение “предыдущий–следующий” определяется тем, в какую сторону ведущий считает. Типичная операция в такой структуре — удаление элемента из списка с сохранением его кольцевой структуры.
Линейные списки, в которых операции вставки, удаления и доступа к значениями элементов выполняются только с крайними элементами (первым или последним), получили специальные названия.
Стек — частный случай линейного односвязного списка, для которого определены две операции: добавление элемента в вершину стека (перед первым элементом) и удаление элемента из вершины стека (удаление первого элемента).
i — номер анализируемого символа;
n — количество символов в выражении.
3. Если i n, то переход на п. (4), иначе если стек пуст, то выдаем сообщение “скобки сбалансированы”, в противном случае выдаем сообщение “скобки не сбалансированы”. Конец алгоритма.
4. Если i-й символ отличен от символов скобок, то переход на п. (2).
5. Если i-й символ равен “(” или “[”, то помещаем его в стек, переход на п. (2).
6. Если i-й символ равен “)”, то проверяем вершину стека: если в вершине стека находится “(”, то извлекаем ее из стека; переход на п. (2), иначе выдаем сообщение “скобки не сбалансированы”. Конец алгоритма.
7. Если i-й символ равен “]”, то проверяем вершину стека: если в вершине стека находится “[”, то извлекаем ее из стека; переход на п. (2), иначе выдаем сообщение “скобки не сбалансированы”. Конец алгоритма.
Очередь — частный случай линейного односвязного списка, для которого разрешены только две операции: добавление элемента в конец (хвост) очереди и удаление элемента из начала (головы) очереди.
Понятие очереди действительно очень близко к бытовому термину “очередь”. Очередь покупателей в магазине хорошо описывается в терминах этой структуры данных.
Деревья
Дерево — это совокупность элементов, называемых узлами, в которой выделен один элемент (корень), а остальные элементы разбиты на непересекающиеся множества (поддеревья), каждое из которых является деревом, при этом корень каждого поддерева является потомком корня дерева, т.е. все элементы связаны между собой отношением (предок–потомок). В результате образуется иерархическая структура узлов. Узлы, которые не имеют ни одного потомка, называются листьями. Над деревом определены следующие операции: добавление элемента в дерево, удаление элемента из дерева, обход дерева, поиск элемента в дереве.
Пример 4. Дерево является наиболее удобной структурой данных для представления генеалогического дерева, с помощью которого можно решать задачи определения степени родства между двумя людьми.
Используются деревья и для определения выигрышной стратегии в играх (см. статью “Игры. Выигрышные стратегии”), и для построения различных информационных моделей (см. “Информационные модели”).
Особенно важную роль в информатике играют так называемые бинарные деревья.
Двоичное (бинарное) дерево — частный случай дерева, в котором каждый узел может иметь не более двух потомков, являющихся корнями левого и правого поддерева.
Если дополнительно для узлов дерева выполняется условие, что все значения элементов левого поддерева меньше значения корня дерева, а все значения элементов правого поддерева больше значения корня, то такое дерево называется деревом бинарного поиска и предназначено для быстрого поиска элементов. Алгоритм поиска в таком дереве работает так: искомое значение сравнивается со значением корня дерева, и в зависимости от результата сравнения поиск либо заканчивается, либо продолжается только в левом или только в правом поддереве соответственно. Общее количество операций сравнения не будет превосходить так называемую высоту дерева — максимальное количество элементов на пути от корня дерева к одному из листьев. Так, высота изображенного на рисунке дерева равна 4.
Граф — это множество элементов, называемых вершинами графа вместе с набором отношений между этими вершинами, называемых ребрами графа. Графической интерпретацией этой структуры данных является множество точек, соответствующих вершинам, некоторые пары из которых соединены линиями или стрелками, которые соответствуют ребрам. В последнем случае граф называется ориентированным (см. также статьи “Графические модели” и “Табличные модели”).
В силу того, что с помощью графов можно описывать объекты произвольной структуры, графы являются основным средством для описания структур сложных объектов и функционирования систем. Например, для описания вычислительной сети, транспортной системы, иерархической структуры (дерево является одной из разновидностей графа). Блок-схемы алгоритмов (см. “Способы записи алгоритмов”) также представляют собой графы.
Если каждому ребру к тому же приписано некоторое число (вес), то такой граф называют взвешенным. Например, при описании с помощью графа системы дорог России важным является длина дороги (вес ребра графа), соединяющей те или иные населенные пункты (вершины графа). При этом на рисунке длины соответствующих ребер не обязаны соответствовать приписанным им весам, в отличие от карты дорог.
Пример 5. В терминах взвешенного графа удобно решать следующую задачу. Правительство России составляет план строительства современных автомагистралей, соединяющих города, население которых превышает миллион человек. Какие именно дороги следует построить, чтобы из любого такого города можно было добраться в любой другой по новым автомагистралям, а общая длина дорог была бы минимальной?
Эта задача в теории графов имеет простое и точное решение. Мы можем начать планирование сети дорог, начиная с любого города, например, Санкт-Петербурга. Соединим его с ближайшим городом-миллионником. Далее на каждом шаге к имеющейся сети добавляется кратчайшая дорога, которой можно соединить город, еще не присоединенный к сети, с одним из городов, уже включенных в сеть. Количество дорог будет, таким образом, на единицу меньше, чем число городов.
Методические рекомендации
При объяснении понятия структуры данных можно воспользоваться следующей иллюстрацией.
При решении любой задачи возникает необходимость работы с данными и выполнения операций над ними. Набор этих операций для каждой задачи, вообще говоря, свой. Однако, если некоторый набор операций часто используется при решении различных задач, то полезно придумать способ организации данных, позволяющий выполнять именно эти операции как можно эффективнее. После того, как такой способ придуман, при решении конкретной задачи можно считать, что у нас в наличии имеется “черный ящик” (его мы и будем называть структурой данных), про который известно, что в нем хранятся данные некоторого рода, и который умеет выполнять некоторые операции над этими данными. Это позволяет отвлечься от деталей и сосредоточиться на характерных особенностях задачи. Внутри (т.е. в компьютере) этот “черный ящик” может быть реализован различным образом, при этом следует стремиться к как можно более эффективной (быстрой и экономично расходующей память) реализации.
Государственный образовательный стандарт предусматривает изучение различных структур данных как в базовом курсе основной школы, так и в старших классах. В курсе программирования основной школы в Примерной программе упоминаются в качестве обрабатываемых объектов цепочки символов (строки), числа, списки, деревья, графы. Однако в практических работах из данных сложной структуры упоминается только массив (см. статью “Операции с массивами”). В основной школе остальные структуры, видимо, имеет смысл изучать в первую очередь при построении графических и других моделей (см. раздел IV энциклопедии).
Примерная программа для профильной школы предполагает работу с числами, матрицами, строками, списками, деревьями. В качестве простой иллюстрации работы со списками можно выбрать организацию стека с помощью одномерного массива и целочисленной переменной, указывающей на вершину стека (“дно” стека при этом всегда находится в первом элементе массива). Помимо приведенной в статье задачи проверки скобок на сбалансированность, можно изучить работу стекового калькулятора на примере алгоритма перевода арифметического выражения в обратную польскую запись (постфиксную запись) из привычной нам инфиксной записи и дальнейшее вычисление значения арифметического выражения.
Бинарное дерево также легко представить в памяти компьютера с помощью одномерного массива, при этом в первом элементе массива будет храниться корень дерева, а потомки узла дерева, хранящегося в i-м элементе массива, будут располагаться в 2i-м и (2i + 1)-м элементах соответственно. Если потомок у узла отсутствует, то соответствующий элемент будет равен, например, 0. Рекурсивная процедура обхода дерева t и печати его элементов в этом случае будет выглядеть так:
О реализации списков и массивов с помощью динамических переменных можно прочитать, например, в классической книге Н.Вирта “Алгоритмы и структуры данных”.
В программу для профильной школы включены и алгоритмы на графах. В частности, упоминается поиск кратчайшего пути в графе. Для невзвешенного графа решать эту задачу можно, например, с использованием алгоритма “поиска в ширину”, когда сначала помечаются вершины графа, соединенные ребром с исходной вершиной, затем все вершины, соединенные с помеченными, и т.д. Для взвешенного графа чаще всего используют алгоритм Дийкстры (см., например, статью Е.В. Андреевой “Олимпиады по информатике. Пути к вершине”, “Информатика” № 8/2002). Знание таких алгоритмов необходимо для успешного решения олимпиадных задач по информатике. Так, на IV федеральном окружном этапе Всероссийской олимпиады по информатике 2007 г. предлагалась задача “Окопы и траншеи”, решение которой как раз и сводилось к поиску кратчайшего пути во взвешенном графе.
16. Теория алгоритмов
Теория алгоритмов как раздел математики возникла в начале 30-х годов XX столетия в связи с необходимостью уточнения понятия алгоритма. Ранее, решая различные задачи, математики использовали интуитивное понятие алгоритма (см. статью “Алгоритм”). Но в связи с усложнением ставящихся задач у математиков стала возникать мысль, что не для всех задач можно найти процедуру решения, которая являлась бы алгоритмом, что впоследствии подтвердилось получением результатов о существовании алгоритмически неразрешимых проблем. Для доказательства факта отсутствия алгоритма необходимо было дать точное определение алгоритма. Ведь одно дело найти разрешающий алгоритм — это можно сделать, используя интуитивное понятие алгоритма. Другое дело — доказать несуществование алгоритма, для этого нужно знать точно, отсутствие чего мы доказываем. Попытки сформулировать такое определение привели в рамках математической логики к возникновению теории алгоритмов.
В теории алгоритмов используются различные подходы к формализации понятий алгоритма и вычислимой функции. Поиск таких подходов проходил в трех направлениях. В первом всякий алгоритм вычисляет значение некоторой числовой функции, а его элементарные шаги — это арифметические операции. Последовательность шагов определяется с помощью суперпозиции — подстановки функций в функции, рекурсии — определения значения функции через ранее вычисленные значения этой же функции, и оператора минимизации, благодаря которому из всюду определенной функции можно получить не всюду определенную вычислимую функцию. Класс функций, порождаемый этими тремя операторами, называется классом частично-рекурсивных функций. Второе направление основано на определении алгоритмического процесса как процесса, осуществимого на конкретной теоретической машине. Примерами таких алгоритмических моделей являются “машина Тьюринга” и “машина Поста”. Третье направление отвлекается от конкретных машин (т.е. в этих моделях отсутствуют понятия “память”, “состояние машины” и т.п.). Наиболее известная алгоритмическая модель этого типа — нормальные алгоритмы Маркова.
Все эти подходы привели к одному и тому же классу алгоритмически вычислимых функций. Указанные результаты составляют основу так называемой дескриптивной теории алгоритмов, основным содержанием которой является классификация задач по признаку алгоритмической разрешимости, т.е. получение высказываний типа “Задача П алгоритмически разрешима” или “Задача П алгоритмически неразрешима” (см. статью “Алгоритмически неразрешимые проблемы”). В данном направлении получен ряд фундаментальных результатов. Среди них доказательство Ю.В. Матиясевичем в 1970 году алгоритмической неразрешимости знаменитой десятой проблемы Гильберта.
Применение теории алгоритмов осуществляется как в использовании самих результатов (особенно это касается использования разработанных алгоритмов), так и в обнаружении новых понятий и уточнении старых. С ее помощью исследуются доказуемость, эффективность, разрешимость и др. Всякому алгоритму соответствует задача, для решения которой он предназначен. В обратную сторону это неверно — задача может решаться различными алгоритмами. Тем не менее задача определения эквивалентности двух алгоритмов является алгоритмически неразрешимой.
Применение ЭВМ послужило стимулом развития теории алгоритмов и изучения алгоритмических моделей, самостоятельного изучения алгоритмов с целью их сравнения по рабочим характеристикам (числу действий, расходу памяти), а также их оптимизации. Возникло важное направление в теории алгоритмов — сложность алгоритмов и вычислений. Начала складываться так называемая метрическая теория алгоритмов, основным содержанием которой является классификация задач по классам сложности. Сами алгоритмы стали объектом точного исследования, как и те объекты, для работы с которыми они предназначены.
Формальное определение алгоритма и вычисление функции*
Все задачи принято делить на два класса: задачи, связанные с вычислением функций, и задачи, связанные с распознаванием принадлежности объекта заданному множеству (или ответом на вопрос: обладает ли объект заданным свойством?). В первом случае алгоритм A вычисляет функцию fA, т.е., начав работать с входными данными x, он должен через некоторое время остановиться и выдать результат y = fA(x). Функция fA не обязательно числовая. Например, функция “телефонный справочник” может по фамилии абонента выдать его телефонный номер. Алгоритм вычисления этой функции заключается в поиске нужной фамилии в упорядоченном по алфавиту списке абонентов. Во втором случае алгоритм отвечает на вопрос: “Истинно ли высказывание x 
M?” — и выдает один из двух возможных результатов: да или нет. Мы также можем считать это функцией, принимающей два значения. Многие практические задачи включают в себя оба случая. Например, при решении квадратного уравнения сначала нужно выяснить вопрос о существовании действительных корней уравнения, и только при положительном ответе на этот вопрос вычисляются корни. Первое из понятий приводит к так называемым вычислимым функциям.
При всех известных подходах к формализации понятия вычислимости сначала вводится в рассмотрение множество конструктивных объектов, которые в конечном счете могут быть представлены словами конечной длины в конечном алфавите. В частности, конструктивными являются конечные натуральные числа, которые можно трактовать как слова в алфавите “0”..”9”.
Функция f с натуральными аргументами и значениями называется вычислимой, если существует алгоритм, ее вычисляющий, то есть такой алгоритм A, что
· если f(n) определено для какого-либо натурального n, то алгоритм A, получая на вход n, останавливается и печатает fA(n) = f(n);
· если f(n) не определено, то алгоритм A не останавливается, получив на входе n, т.е. fA(n) не определено.
Понятие вычислимости определяется здесь для частичных функций (областью определения которых является некоторое подмножество натурального ряда). Например, нигде не определенная функция вычислима (в качестве A надо взять программу, которая всегда зацикливается).
Любые конструктивные объекты реального мира также можно изображать словами в различных конечных алфавитах. Это позволяет считать, что объектами работы алгоритмов могут быть только слова. Слово, которое подается на вход алгоритма, называется входным словом; слово, получаемое в результате работы алгоритма, называется выходным. Совокупность слов, к которым применим алгоритм, называется областью применимости алгоритма.
Алан Матисон Тьюринг
(Alan Mathison Turing)
Утверждение о том, что та или иная алгоритмическая модель универсальна, означает, что для любой вычислимой функции существует алгоритм, описываемый средствами этой модели. В теории алгоритмов была доказана равносильность всех известных формализаций понятия алгоритма.
До сих пор неизвестно ни одного алгоритма из числа алгоритмов, изобретенных человечеством за свою многотысячелетнюю историю, который не был бы эквивалентен ни одному из формализованных алгоритмов (например, алгоритму Маркова, машине Тьюринга или частично рекурсивной функции — функции, не являющейся всюду определенной).
Андрей Андреевич Марков
Оказалось, что все эти понятия эквивалентны между собой и каждое из них можно рассматривать в качестве одного из способов точного определения понятия алгоритма.
Машина Тьюринга и Поста
Машиной Тьюринга (МТ) называется упорядоченный набор вида 
>, где
A — конечное множество, называемое основным алфавитом МТ,
a0 A и называется пустой буквой алфавита,
Q — конечное множество, называемое алфавитом состояний МТ,
q1 Q — начальное состояние МТ,
q0 Q — заключительное, или состояние останова МТ,
t — программа МТ, то есть
.: A x Q \ <q0> 
A x T x Q
Нетрудно убедиться, что в этом определении фигурируют только математические и логические термины (или символы), например, множество, конечное множество, элемент множества, принадлежность множеству, произведение множеств.
Для любого наугад взятого алгоритма, работающего не над словами, его объекты можно закодировать так, что они становятся словами в некотором алфавите, а суть алгоритма от этого не меняется.
Что же представляет собой машина Тьюринга? В каждой машине Тьюринга есть две части:
1) неограниченная в обе стороны лента, разделенная на ячейки;
2) головка для считывания/записи, управляемая программой.
С каждой машиной Тьюринга связаны два конечных алфавита: алфавит входных символов A = <a1, a2, …, am>и алфавит состояний Q = <q1, q2, …, qm>. (С разными машинами Тьюринга могут быть связаны разные алфавиты A и Q.) Состояние q0 называется заключительным, или состоянием останова. Считается, что если машина попала в это состояние, то она заканчивает свою работу. Состояние называется начальным. Находясь в этом состоянии, машина начинает свою работу.
Входное слово размещается на ленте по одной букве в расположенных подряд ячейках. Слева и справа от входного слова находятся только пустые ячейки (в алфавит А всегда входит “пустая” буква а0 — признак того, что ячейка пуста).
Автомат может двигаться вдоль ленты влево или вправо, читать содержимое ячеек и записывать в ячейки буквы своего алфавита. Ниже схематично нарисована машина Тьюринга, автомат которой обозревает первую ячейку с данными.
· записать новую букву в обозреваемую ячейку;
· выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться неподвижным;
· перейти в новое состояние.
Программа для машины Тьюринга представляет собой таблицу, в каждой клетке которой записана команда.
Клетка (qj, ai) определяется двумя параметрами — символом алфавита и состоянием машины. Команда представляет собой указание: какой символ записать в текущую ячейку, куда передвинуть головку чтения/записи, в какое состояние перейти машине. Для обозначения направления движения автомата используем одну из трех букв: “Л” (влево), “П” (вправо) или “Н” (неподвижен).
После выполнения очередной команды МТ переходит в состояние qk (которое может в частном случае совпадать с прежним состоянием qj). Следующую команду нужно искать в k-й строке таблицы на пересечении со столбцом, соответствующим букве, которую автомат видит после сдвига. В процессе работы автомат перескакивает из одной клетки программы, записанной в виде таблицы, в другую, пока не дойдет до клетки, в которой записано, что автомат должен перейти в состояние q0, т.е. остановиться. Будем говорить, что такие клетки содержат команду останова.
Если клеток останова в программе вообще нет или в процессе работы над входным словом МТ никогда не окажется в заключительном состоянии, то считается, что машина Тьюринга неприменима к данному входному слову. Машина Тьюринга применима к входному слову только в том случае, если, начав работу над этим входным словом, она окажется в заключительном состоянии.
Пример. Пусть требуется построить машину Тьюринга, которая прибавляет единицу к числу на ленте. Входное слово состоит из цифр целого десятичного числа, записанных в последовательные ячейки на ленте. В начальный момент машина находится против самой правой цифры числа.
Решение. Машина должна прибавить единицу к последней цифре числа. Если последняя цифра равна 9, то ее заменить на 0 и прибавить единицу к предыдущей цифре. Программа для данной машины Тьюринга может выглядеть так:
Тезис Тьюринга состоит в том, что всякий алгоритм может быть реализован соответствующей машиной Тьюринга. Тезис Тьюринга является основной нематематической гипотезой теории алгоритмов, понимаемых по Тьюрингу. Одновременно этот тезис приводит к формальному определению алгоритма.
Алгоритм (по Тьюрингу) — программа для машины Тьюринга, приводящая к решению поставленной задачи.
В статье “Исполнители алгоритмов” 2 говорилось, что у каждого исполнителя есть своя система команд, свой круг задач. Тьюрингом же был описан универсальный исполнитель — машина Тьюринга, этот исполнитель способен решить любую алгоритмически разрешимую задачу. Этот фундаментальный результат был получен в то время, когда универсальных вычислительных машин еще не существовало. Более того, сам факт математического построения воображаемого универсального исполнителя позволил высказать предположение о целесообразности построения универсальной вычислительной машины, которая бы могла решать любые задачи при условии соответствующей кодировки исходных данных и разработки соответствующей программы действий исполнителя.
Почти одновременно с А.Тьюрингом (1937 г.) американский математик Эмиль Пост предложил иную абстрактную машину, характеризующуюся еще большей простотой, чем машина Тьюринга. Это строгое математическое построение было также предложено в качестве уточнения понятия алгоритма.
Эмиль Леон Пост
(Emil Leon Post)
В машине Поста в ячейках бесконечной ленты можно записывать всего два знака: 0 и 1 (ставить метку в ячейку или стирать метку). Это ограничение не влияет на ее универсальность, так как любой алфавит может быть закодирован двумя знаками. Кроме ленты, в машине Поста имеется каретка (головка чтения/записи), которая:
· умеет двигаться вперед, назад и стоять на месте;
· умеет читать содержимое, стирать и записывать 0 или 1;
Как и машина Тьюринга, машина Поста может находиться в различных состояниях, но каждому состоянию соответствует не строка состояния с клетками, а некоторая команда одного из следующих шести типов (все строки в программе пронумерованы):
1. Записать 1 (метку), перейти к i-й строке программы;
2. Записать 0 (стереть метку), перейти к i-й строке программы;
3. Сдвиг влево, перейти к i-й строке программы i;
4. Сдвиг вправо, перейти к i-й строке программы;
6. Если 0, то перейти к i, иначе перейти к j.
Состояние машины — это состояние ленты и положение головки чтения/записи. Тезис Поста заключается в том, что: “Всякий алгоритм представим в форме машины Поста”. Отсюда следует другое формальное определение алгоритма.
Алгоритм (по Посту) — программа для машины Поста, приводящая к решению поставленной задачи. Тезис Поста невозможно строго доказать, так же, как и тезис Тьюринга.
Как уже говорилось выше, в теории алгоритмов доказано, что машина Поста и машина Тьюринга эквивалентны по своим возможностям. Более того, для каждого неформализованного алгоритма A существует формализованный алгоритм B (например, машина Тьюринга). В этом состоит полнота формализации понятия вычислимой функции.
Универсальная функция
В теории алгоритмов установлен важный факт: во всех алгоритмических моделях всегда существует универсальный алгоритм, т.е. алгоритм, который способен моделировать работу любого другого алгоритма, описанного в этой же модели. Покажем существование универсальной функции для вычислимых функций одного аргумента.
Теорема. Существует вычислимая функция двух аргументов U, являющаяся универсальной функцией для класса вычислимых функций одного аргумента.
Алгоритм, вычисляющий саму функцию U, есть, по существу, интерпретатор для используемого языка программирования (если отождествлять программу и ее номер, то он применяет первый аргумент ко второму).
Аналогично можно ввести универсальные функции для произвольного числа аргументов. Концепция универсального алгоритма еще в 30-е годы XX века показала возможность создания универсального устройства (компьютера), способного выполнять любые алгоритмы.
Индуктивное определение объектов**
В одной из наиболее общих форм индуктивное определение какого-либо класса (множества) объектов K осуществляется по следующей схеме. 1) Задается класс исходных (атомарных, простейших) объектов A определяемого класса K [Базис индуктивного определения].) Задается система правил R, позволяющих из уже определенных (или построенных, порожденных) объектов получать (строить, порождать) новые объекты определяемого класса K [Шаг индуктивного определения]. 3) Объектами определяемого класса K считаются те и только те объекты, которые могут быть получены (построены, порождены) согласно пунктам 1) и) этого определения. При этом пункт 3) данного определения часто только подразумевается, но не формулируется явно.
С приведенным выше индуктивным определением класса объектов связан обобщенный принцип индукции (называемый также индукцией по построению объектов), который состоит в следующем. Для того чтобы доказать, что любой объект из класса, задаваемого данным индуктивным определением, обладает каким-либо свойством P, достаточно доказать, во-первых, что каждый исходный (атомарный, простейший) объект, задаваемый пунктом 1) данного индуктивного определения, обладает этим свойством P [Базис индукции], и, во-вторых, что этим свойством P будет обладать любой объект, который может быть получен (построен, порожден) по какому-либо правилу пункта) данного индуктивного определения, из объектов, уже обладающих этим свойством P [Шаг индукции].
Пример 1. Индуктивное определение класса высказывательных формул, принятое в математической логике (см. “Логические выражения”).
2) Если 
и 
какие-то уже построенные высказывательные формулы, то формальные выражения 
— также высказывательные формулы.
3) Высказывательными формулами считаются те и только те формальные выражения, которые могут быть построены согласно пунктам 1) и) этого определения.
Пример 2. Индуктивное определение класса термов (говоря нестрого, терм — это формальный аналог имени существительного).
Мы предполагаем, что нам даны попарно непересекающиеся множества:
Теперь мы даем следующее индуктивное определение класса термов.
3) Термами считаются те и только те формальные выражения, которые могут быть получены (построены, порождены) согласно пунктам 1) и) этого определения.
Это определение используется, в частности, для построения грамматик различных языков программирования (см. “Языки программирования”).
Сложность алгоритма
Сложность алгоритма — это количественная характеристика, которая говорит либо о том, сколько времени он работает (временная или вычислительная сложность), либо о том, какой объем памяти он использует. Вычислительным процессом, порожденным алгоритмом, называется последовательность шагов алгоритма, пройденных при исполнении этого алгоритма.
Вычислительная сложность алгоритма — количество элементарных шагов в вычислительном процессе этого алгоритма. Обратите внимание: именно в вычислительном процессе, а не в самом алгоритме. Очевидно, для сравнения сложности разных алгоритмов необходимо, чтобы сложность подсчитывалась в одних и тех же элементарных действиях.
Временная сложность алгоритма — это время Т, необходимое для его выполнения. Оно равно произведению числа элементарных действий на среднее время выполнения одного действия: Т = kt. Поскольку t зависит от исполнителя, реализующего алгоритм, то естественно считать, что сложность алгоритма в первую очередь зависит от k. Очевидно, что в наибольшей степени количество операций при выполнении алгоритма зависит от количества обрабатываемых данных. Действительно, для упорядочивания по алфавиту списка из 100 фамилий требуется существенно меньше операций, чем для упорядочивания списка из 100 000 фамилий. Поэтому сложность алгоритма выражают в виде функции от объема входных данных. Пусть есть алгоритм А. Для него существует параметр n, характеризующий объем обрабатываемых алгоритмом данных, этот параметр часто называют размерностью задачи. Обозначим через T(n) время выполнения алгоритма, через f — некую функцию от n.
Будем говорить, что T(n) алгоритма имеет порядок роста f(n) при n 
, или, по-другому, алгоритм имеет теоретическую сложность O(f(n)) (читается “о большое от f(n)”), если найдется такая константа с > 0 и число n0, что T(n) сf(n) при всех n 
n0. Здесь предполагается, что f(n) неотрицательно, по крайней мере при n n0.
Для решения задачи могут быть разработаны алгоритмы различной сложности. Логично воспользоваться лучшим среди них, т.е. имеющим наименьшую сложность.
Сложность алгоритма по памяти определяется числом ячеек памяти, используемых в процессе его работы. Число шагов алгоритма может сколь угодно сильно превосходить объем памяти за счет циклов по одним и тем же объектам. Поэтому временная сложность считается основной характеристикой алгоритма.
Методические рекомендации
Материал данной темы носит теоретический характер и достаточно сложен для понимания. Он включен в Стандарт профильной школы. Цель раскрытия данной темы — проследить вместе со школьниками цепочку
формальное определение алгоритма алгоритмически неразрешимые задачи вычислимые функции универсальный исполнитель
Проще всего объяснить школьникам формальное определение алгоритма можно с помощью машины Поста или машины Тьюринга. Полезно рассмотреть и примеры решения задач с помощью одной из этих машин. Программирование машины Поста учащимся дается легче, чем программирование машины Тьюринга. Во-первых, это связано с тем, что все действия, выполняемые машиной Поста, прописаны в командах, которые выполняются в привычном нам порядке (последовательное выполнение + условный переход) (не надо блуждать по таблице-программе машины Тьюринга). В пользу машины Поста говорит простота ее описания (хотя многие задачи в силу ограниченных возможностей машины по сравнению с машиной Тьюринга решать становится сложнее), а в пользу машины Тьюринга — то, что на ее примере учащиеся могут познакомиться с таким новым для них и очень важным понятием, как конечный автомат.
Полезным может оказаться и выполнение упражнений на индуктивное определение объектов. Зачастую это единственный способ достаточно просто описать не только весьма непростые вещи, такие, как грамматика языка программирования, но и арифметические или логические выражения. Индуктивные определения объектов непосредственно связаны с рекурсивными описаниями подпрограмм в языках программирования.
В теории алгоритмов важным является и следующий факт: в любой алгоритмической модели всегда существует универсальная вычислимая функция, т.е. алгоритм, который способен моделировать работу любого другого алгоритма, описанного в этой же модели. Этот результат, установленный еще в 30-е годы прошлого века, показывает, что в основе работы компьютера как универсального вычислителя лежат не только физические, но и математические принципы.
После введения точного определения алгоритма в разных областях математики стали обнаруживать алгоритмически неразрешимые проблемы. Знание примеров неразрешимостей предостерегает от увлечения глобальными проектами всеобщей алгоритмизации точно так же, как знание основных законов физики предостерегает от попытки создать вечный двигатель.
17. Типы данных
Информация, поступающая в компьютер, состоит из определенного множества данных, относящихся к какой-то проблеме, — это именно те данные, которые относятся к конкретной задаче и из которых требуется получить желаемый ответ. В математике классифицируют данные в соответствии с некоторыми важными характеристиками. Принято различать целые, вещественные и логические данные, множества, последовательности, векторы, матрицы (таблицы) и т.д. В обработке данных на компьютере классификация играет даже боRльшую роль.
Любая константа, переменная, выражение или функция относятся к некоторому типу. Тип данных определяет диапазон допустимых значений и операций, которые могут быть применены к этим значениям. Кроме того, тип данных задает формат представления объектов в памяти компьютера, ведь в конце концов любые данные будут представлены в виде последовательности двоичных цифр (нулей и единиц). Тип данных указывает, каким образом следует интерпретировать эту информацию. Тип любой величины может быть установлен при ее описании, а в некоторых языках может выводиться компилятором по ее виду (Fortran, Basic).
Например, если переменная имеет целочисленный тип данных, то таким образом определен диапазон значений, которые могут быть сохранены в этой переменной (целые числа) и определены операции, которые могут быть применены к этой переменной (арифметические, логические, возможность ввода и вывода значений этой переменной). Каждый язык программирования поддерживает один или несколько типов данных. Наличие в языке программирования типизации означает жесткую связку операций и типов объектов, над которыми их можно выполнять. Не все языки обладают таким свойством. Например, в языке С практически любые операции можно выполнять над любыми данными (например, складывать два символа или число с логическим значением, но в большинстве случаев такие операции бессмысленны и соответствуют ошибке в программе, на которую компилятор указать не сможет).
Классификация типов данных
Любые данные могут быть отнесены к одному из двух типов: простому (основному), форма представления которого определяется архитектурой ЭВМ, или сложному, конструируемому пользователем для решения конкретных задач. Данные простого типа — это символы, числа и т.п. элементы, дальнейшее дробление которых не имеет смысла. Из таких элементарных данных формируются структуры (сложные типы) данных.