Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.astro.spbu.ru/staff/ilin2/EDU/KURS/titov.ps Дата изменения: Fri Nov 19 16:15:21 2010 Дата индексирования: Tue Oct 2 02:12:52 2012 Кодировка: Windows-1251 Поисковые слова: п п п п п п

тенсивно обрабатывают большие объемы данных и для повышения эф-
фективности, читай быстродействия, могут использовать более сложные
структуры и для хранения данных на внешних носителях, используя,
например, индексные указатели, уточняющие положение нужного фраг-
мента данных.
5 Алгоритмы
Алгоритм  набор конечного числа правил, задающих последователь-
ность выполнения операций для решения задачи. Алгоритм имеет пять
важных свойств:
1. конечность: алгоритм всегда должен заканчиваться после конечно-
го числа шагов;
2. определенность: каждый шаг должен быть точно определен;
3. наличие входных данных: алгоритм имеет некоторое число входных
данных;
4. наличие выходных данных: алгоритм имеет одну или несколько
выходных величин, имеющих определенные отношения к входным
данным;
5. эффективность: алгоритм считается эффективным, если все необ-
ходимые операции достаточно просты, чтобы их можно было вы-
полнить точно и за конечное время.
Если мы откажемся от требования конечности, то такой набор пра-
вил можно назвать вычислительным методом. Что касается определен-
ности, то правила желательно сформулировать на языке, исключающем
неточности и известном читателю. Естественный язык (русский, англий-
ский или эсперанто) не совсем подходит для этого, поскольку он допус-
кает неоднозначную интерпретацию. Для описания алгоритмов исполь-
зуются формально определенные языки программирования, в которых
каждое утверждение имеет абсолютно точно определенный смысл. За-
пись вычислительного метода на таком языке называется программой.
На практике нужны не просто алгоритмы, а хорошие (в каком-то
определенном смысле) алгоритмы. Лепота алгоритма может, например,
характеризоваться временем, необходимым для его выполнения, просто-
той, требуемыми ресурсами и т.д. Часто нужно из нескольких алгорит-
мов нужно выбрать лучший. Исследование рабочих характеристик алго-
ритмов называется анализом алгоритмов  важная и непростая задача.
36

Можно выделить анализ алгоритмов в среднем, когда исследуется пове-
дение алгоритма в средних условиях, анализ алгоритма в самых небла-
гоприятных или, наоборот, самых благоприятных условиях. Например,
число шагов в алгоритме Эвклида нахождения наибольшего общего де-
лителя двух целых чисел m и n в среднем равно T n = (12 ln 2= 2 ) ln n
(получение этой оценки  очень трудная математическая задача).
Для построения алгоритмов существует множество стандартных
приемов (например, пошаговые алгоритмы, алгоритмы перебора, рекур-
сивные алгоритмы). Некоторые из этих приемов будут показаны в даль-
нейшем, при рассмотрение конкретных алгоритмов.
Можно ли эффективно решить, существует ли алгоритм решения той
или иной задачи? Любую ли задачу может решить компьютер? Этими
вопросами занимается наука, вернее раздел науки, которая называется
теорией алгоритмов.
5.1 Введение в теорию алгоритмов
Что не все задачи можно решить с помощью компьютера, можно инту-
итивно догадаться, осознав, что количество всех программ (на всех воз-
можных языках)  не более, чем счетно, тогда как множество задач 
не счетно. Даже множество всех функций, отображающих натуральные
числа в натуральные не является счетным. Доказывается это элементар-
но:
Предположим, что множество всех таких функций счетно, следова-
тельно мы можем их перенумеровать: f i . Определим функцию g следу-
ющим образом:
g(i) = f i (i) + 1:
Функция g безусловно входит в рассматриваемое множество, и, очевидно,
отличается по определению от каждой функции f i , что противоречит
предположению о том, что множество наших функций счетно.
Рассмотрим, например, такую, весьма простую задачу: является ли
текст hello, world первым, что печатает C-программа (можно Pascal-
программа, или даже Фортран-программа?). Разумеется, проще всего
было бы запустить ее и посмотреть на результат. Однако может оказать-
ся, что ждать придется долго, очень долго... Ну конечно, если програм-
ма состоит из одного оператора печати hello, world, то ответ будет
утвердительным, да и проверить не сложно. Но если программа должна
прежде что-то сделать, например, найти целое положительное решение
уравнения x n + y n = z n , где n  входные данные программы, и только
в случае успешного решения вывести hello, world, то вряд ли мы до-
37

ждемся приветствия  при n > 2 это уравнение не имеет решения (а
доказывалась теорема Ферма более 300, точнее 358, лет!). То есть про-
грамма в пару десятков строчек, которую каждый из вас может легко
написать, решения не найдет. Ну в данном-то случае 300-летними стара-
ниями математиков все ясно, а другие задачи? (Ограничения, связанные
с величиной представимых целых чисел мы не рассматриваем, их легко
обойти или, по крайней мере, очень сильно ослабить, определив струк-
туры для целых чисел произвольной длины, например использовав для
представления таких чисел связанные списки).
Было бы замечательно, если бы мы написали программу, которая
проверяет любую программу P со входом I и определяет, печатается ли
при ее выполнении hello, world. Покажем, что такой программы не
может быть.
Предположим, что нам удалось написать программу H, которая по-
лучая на входе некоторую программу P , выводит yes, если P печатает
hello, world, или, в противном случае, H выводит hello, world, если
P не печатает hello, world. Небольшие ограничения (вход I, например,
включается в P ) не меняют сути.
Итак
P ! H
% yes
& hello, world
Подадим на вход нашей программы H ее саму
H ! H
% yes
& hello, world
Что же получается? Если H (в рамке) выдает yes, то это означает, что
программа на входе H печатает hello, world, а если H (в рамке) вы-
дает hello, world, то это означает, что программа на входе H печатает
НЕ hello, world. В обоих случаях мы получили, не то что ожидали.
Противоречие и доказывает, что такая программа H не может существо-
вать. То есть, не может существовать программы H, которая бы могла
определить, печатает ли данная программа P со входом I текст hello,
world.
Задачи, которые нельзя решить с помощью компьютера, называются
неразрешимыми. Легко убедиться, что неразрешима, например, и такая
задача: по данной программе и ее входу определить, останавливается
ли она когда-нибудь, т.е. не зацикливается ли она при данном входе.
38

Ее легко свести к предыдущей, добавив в конец программ P , опера-
тор, выводящий текст hello, world. Поскольку задача о hello, world
неразрешима, то неразрешима и задача остановки.
Таким образом, не существует такой программы, которая для произ-
вольной программы P и произвольных входных данных I может устано-
вить, закончится ли вычисление P с данными I.
Вот еще несколько неразрешимых задач:
 Для произвольного утверждения в достаточно богатой математи-
ческой теории установить, является ли оно теоремой.
 Установить эквивалентность двух произвольных процедур.
5.2 Машина Тьюринга. Полиномиальные задачи
Установить разрешимость задачи  значит понять можно ли решить
данную задачу или нет. Важно также выделить задачи, решение которых
не требует чрезмерно большого времени.
Теория алгоритмов, вообще говоря, не должна быть связана с про-
граммами на каком-либо конкретном языке. Нужна модель компьютера,
с одной стороны, достаточно простая, а с другой  модель позволяет
делать заключения, справедливые для любого алгоритма.
Такой моделью является машина Тьюринга. Машина Тьюринга со-
стоит из конечного управления, которое может находиться в любом из
конечного множества состояний. Есть лента, разбитая на клетки, в кото-
рых могут храниться символы из некоторого конечного их множества. На
ленте записан вход, представляющий цепочку символов конечной длины
из входного алфавита, остальные символы ленты (до бесконечности сле-
ва и справа) содержат пустой символ, или пробел. Машину Тьюринга
можно описать семеркой M = (Q; ; ; Ж; q 0 ; B; F ). Здесь
Q  конечное множество состояний управления;
  конечное множество входных символов;
 множество ленточных символов,   ;
Ж  функция переходов (p; Y; D) = Ж(q; X); q 2 Q; X 2 , здесь p 2 Q 
следующее состояние, Y 2  новый записываемый на ленту символ,
D  направление сдвига головки (L или R);
q 0 2 Q  начальное состояние;
B 2 ; B: 2   пустой символ;
F  Q  множество заключительных, или допускающих состояний.
(Пример?)
Работа машины Тьюринга состоит из переходов, подразумевающих
следующие действия:
39

1. считать текущий символ и изменяем состояние управления;
2. записать ленточный символ в текущую позицию;
3. сдвинуть головку влево или вправо.
Итак входная цепочка помещается на ленту, текущая клетка ленты 
крайняя слева. Если машина Тьюринга в конце концов достигает до-
пускающего состояния, то говорят, что входная цепочка допускается, в
противном случае  нет.
Несмотря на простоту конструкции можно показать, что машина
Тьюринга в некотором смысле не отличается от обычного компьюте-
ра. Компьютер может имитировать машину Тьюринга (можете написать
соответствующую программу на любимом языке), и, наоборот, машина
Тьюринга может имитировать компьютер. Более того, число переходов
машины Тьюринга при разрешении некоторой цепочки символов можно
выразить в виде некоторого полинома от числа шагов, совершаемых ком-
пьютером, то есть если задачу можно решить за полиномиальное время
на обычном компьютере, то ее можно решить за полиномиальное время
на машине Тьюринга, и наоборот.
Таким образом, машина Тьюринга представляет собой абстрактную
вычислительную машину, мощность которой (в смысле вычислимости)
совпадает с мощностью реальных компьютеров.
Итак, мы встречали уже неразрешимые задачи (например, задача
останова). Если мы имеем дело с такой задачей, мы должны доволь-
ствоваться знанием того, что решить ее с помощью компьютера нельзя.
Как правило, мы имеем дело с полиномиальными задачами, время ра-
боты которых ограничено некоторым полиномом от размера начальных
данных, время работы на входе длины n составляет O(n k ). Очевидно,
используемые на практике алгоритмы должны быть полиномиальными.
Кроме того, бывают задачи, для которых существует решающий их
алгоритм, но время его работы не есть O(n k ) ни для какого фиксирован-
ного k. Такие алгоритмы имеют лишь теоретический интерес.
Для ряда задач не найдены полиномиальный алгоритмы и не доказа-
но, что таких алгоритмов не существует. К таким алгоритмам относятся
так называемые NP-полные алгоритмы. Время их работы, по-видимому,
не полиномиально, хотя проверить результат можно быстро.
Таких задач известно много. Например, задача о гамильтоновом цик-
ле (простой цикл, проходящий через все вершины графа), задача ком-
мивояжера, раскраска графа и т.д.
Вряд ли целесообразно искать алгоритм, решающий точно NP -
полную задачу, лучше построить приближенный алгоритм.
40

Чтобы представить, чем отличается полиномиальные задачи от экспо-
ненциальных, давайте посмотрим следующую таблицу. (Гэри, Джонсон.
Вычислительные машины и труднорешаемые задачи)
Пусть N  некий условный максимальный размер задачи, решаемой
на современной машине за 1 час. Сравнительная динамика увеличения
этого размера при росте быстродействия для задач, решаемых полино-
миальными и экспоненциальными алгоритмами, показана в таблице. Для
упрощения обозначений мы используем одну и ту же букву N для всех
типов алгоритмов.
Временная На На ЭВМ, На ЭВМ,
сложность современных в 100 раз в 1000 раз
алгоритма ЭВМ более быстрых более быстрых
n N 100N 1000N
n 2 N 10N 31:6N
n 3 N 4; 64N 10N
n 5 N 2; 5N 3; 98N
2 n N N + 6; 64 N + 9; 97
3 n N N + 4; 19 N + 6; 29
Таким образом, если мы имеем квадратичный алгоритм, то при уве-
личении производительности ЭВМ в 1000 раз, мы получим выигрыш во
времени только в 30 раз, а если наш алгоритм  экспоненциальный про-
изводительность увеличится весьма незначительно.
Грубо говоря, если на современной машине мы успеваем обработать
по экспоненциальному алгоритму 100-битовое слово, то для того, чтобы
обработать 110 бит, нам придется увеличить быстродействие в 1000 раз.
6 Построение алгоритмов. Анализ алгорит-
мов
Известно множество стандартных приемов, которые используются при
построении алгоритмов. Вот некоторые из них:
 пошаговые алгоритм (или перебор);
 разделяй и властвуй;
 рекурсивные алгоритмы;
 перебор с возвратом;
41

 построение конечного автомата;
 динамическое программирование;
 жадные алгоритмы.
Одну и ту же задачу часто можно решить, используя различные алго-
ритмы. Полезно оценить, сколько же вычислительных ресурсов (время,
память, внешняя память) требует тот или иной метод, тот или иной ал-
горитм. Нередко, одни алгоритмы требуют экспоненциального времени
решения, тогда как другие, может быть дающие лишь приближенное
решение, но зато требующие только полиномиального времени, причем
с весьма малым показателем степени. (При анализе алгоритмов будем
считать, что мы используем обычную однопроцессорную машину и не
распараллеливаем вычисления.)
И построение алгоритмов, и их анализ будем проводить при решении
конкретных задач.
Начнем с простой задачи поиска образца в строке. Допустим мы име-
ем некоторый текст T длины n символов и образец  тот текст который
мы хотим найти в T : P длины m < n. Требуется найти все вхождения
образца P в текст T . Будем говорить, что образец P входит в текст T
со сдвигом s, если 0  s  n m и T [s + 1 : : : s + m] = P [1 : : : m]. Гово-
рят, что s  допустимый сдвиг. Таким образом, наша задача состоит в
нахождении всех допустимых сдвигов.
Простейший, очевидный и прямолинейный путь  просмотр теста,
чтобы найти первую букву образца, а затем проверка совпадения сле-
дующих букв. Такая программа проста и каждый может ее без тру-
да написать. Очевидно трудоемкость алгоритма (в худшем случае)
O(m
(n m+ 1))  O(m
n).
Можно ожидать, что есть и более эффективные способы, поскольку
в простейшем случае информация о тексте T , получаемая при проверке
сдвига s, никак не используется при проверке последующих сдвигов, а
такая информация в поиске последующих сдвигов оказаться полезной.
В алгоритмах поиска строк часто оказывается полезным использова-
ние конечных автоматов. Собственно уже рассмотренная нами раньше
машина Тьюринга является конечным автоматом. Определим конечный
автомат (КА) как пятерку M = (Q; q 0 ; F; ; Ж), где
 Q  конечное множество состояний;
 q 0 2 Q  начальное состояние;
42

 F  Q  конечное множество заключительных, или допускающих
состояний;
   конечное множество (алфавит) входных символов;
 Ж  функция переходов Q  ! Q.
Первоначально конечный автомат находится в состоянии q 0 . По оче-
реди читая символы из входной строки, например символ a, автомат
переходит в состояние Ж(q; a). Если q 2 F , говорят, что он допускает
прочитанную строку, если q 62 F , прочитанная часть строки отвергает-
ся.
Для каждого образца P можно построить конечный автомат, ищущий
этот образец в тексте. Пусть, например, P = аксакал.
Как построить конечный автомат для заданного образца, с этим мы
разберемся чуть позже, а пока предположим, что конечный автомат уже
построен. Вот он
0 а
## ######## 1
а
## к
## ######## 2 с
##
##
# а
### # #
######## 3 а
## ######## 4 к
##
# # # # # # # #
# а
### # # # # # #
######## 5 а
##
##
## с
##
######## 6 л
##
# # # # # # #
# к
### # # # # #
################ 7
# # # # # # # # # #
## а
##
Здесь состояния Q нашего конечного автомата обозначены кружка-
ми; q 0 = 0  начальное состояние; F = fmg  множество допускаю-
щих состояний содержит только один элемент; функция Ж задана дугами
Ж(q; x) задает то состояние, в которое перейдет автомат после считыва-
ния символа x, находясь в состоянии q (отстутствие стрелки, отвечаю-
щей какому-либо символу, означает переход в состояние 0);   можно
считать, например, что множество входных символов содержит все од-
нобайтные символы.
Показанный на рисунке автомат можно считать построенным,
если мы построим функцию Ж(q; x). Построим сначала некото-
рую вспомогательную функцию (так называемую суффикс функцию)
 :   ! f0; 1; : : : ; mg. Эта функция должна ставить в соответствие стро-
ке x длину максимального суффикса x, являющегося префиксом P :
(x) = maxfk : P k = xg
Поскольку P 0 =  является суффиксом любой строки,  определена на
всем   (Sigma  =  [ fg. Если длина P равна m, то (x) = m тогда и
только тогда, когда P  суффикс x. Если x = y, то (x)  (y).
43

Таким образом, конечный автомат, который соответствует образцу
P [1::m], можно определить следующим образом:
 множество состояний: Q = f0; 1; : : : ; mg,
 начальное состояние q 0 = 0,
 множество допускающих состояний F = fmg,
 функция переходов Ж определена следующим образом:
Ж(q; a) = (P q a):
Здесь P q  строка P [1::q].
Легко написать программу, которая вычисляет значение функции
Ж(q; a), для этого потребуется при самой грубой реализации время по-
рядка O(jjm 3 ). Существует, однако, метод, с помощью которого функ-
ция переходов строится за время O(jjm). Таким образом, суммарная
сложность поиска подстроки в тексте O(jjm + n). Впрочем, если текст
большой, а образцы короткие, то первым слагаемым в этой оценке можно
пренебречь. Объем памяти (для хранения полученной таблицы перехо-
дов  O((jj + 1)m))???
Мы рассмотрели предыдущий метод так подробно прежде всего пото-
му, чтобы поближе познакомиться с конечными автоматами. Разумеется
вышеизложенный алгоритм совсем не единственный, выполняющий по-
иск образца в тексте за приемлемое время. Алгоритм КнутаМорриса-
Пратта очень похож на предыдущий, но вместо функции перехода вы-
числяется префикс-функция (за время O(m)), которая несет информа-
цию о том, где в образце P повторно встречаются различные префиксы
этой строки(образца). Использование этой информации позволяет избе-
жать проверки заведомо недопустимых сдвигов.
В алгоритме Рабина-Карпа строки P и T рассматриваются как боль-
шие числа в системе счисления с основанием d = 255:
P = P [1]d m 1 + P [2]d m 2 + : : : + P [m]
T s = T [s + 1]d m 1 + T [s + 2]d m 2 + : : : + T [s +m]
Ищутся те сдвиги s, где T s = P .
P по схеме Горнера вычисляется за время O(M), за такое же время
вычисляется T 0 , остальные T i вычисляются за время O(1):
T s+1 = (T s T [s + 1]d m 1 )d + T [s + 1 +m]
44

Конечно, числа T s и P будут настолько велики, что операции с ни-
ми придется реализовывать вручную, и таким образом сложность опе-
раций умножения, сложения и т.д. будет намного больше, чем O(1). К
счастью, эту трудность можно преодолеть: будем производить все выше-
приведенные вычисления по модулю некоторого фиксированного числа q
(своего рода хэш-функция!). В этом то случае все числа не будут превос-
ходить q и все T j вместе с P будут действительно вычислены за время
O(n + m). Обычно в качестве q выбирают такое простое число, чтобы
dq помещалось в машинное слово. Увы из равенства чисел T s и P не
следует равенства соответствующих строк, мы должны проверить сов-
падают ли строки на самом деле. Если не совпадают, то произошло так
называемое холостое срабатывание. В худшем случае алгоритм требует
времени O((n m + 1)
m), то есть такого же как и самый элементар-
ный алгоритм (плюс затраты на арифметические действия). В среднем
же ожидаемое время работы алгоритма O(n) + O(m(v + n=q)), где v 
количество вхождений образца в текст.
По-видимому, наиболее эффективным алгоритмом поиска образцов
является алгоритм Бойера-Мура. Этот алгоритм отличается от рассмот-
ренных выше. Во-первых, он производит сравнение P [1::m] и T [s +1::s+
m] справа налево. Во-вторых, он вводит две так называемые эвристики
(эвристика стоп-символа и эвристика безопасного суффикса). Эти эври-
стики позволяют вовсе не рассматривать некоторые значения сдвига s.
Если при проверке сдвига s обнаруживается что строка не совпадает с
образцом, то каждая из эвристик указывает значение, на которое можно
увеличить s, не опасаясь пропустить допустимый сдвиг. Из двух сдвигов
(j [T [s + j]] для эвристики стоп-символа и [j] для эвристики безопас-
ного суффикса) выбирается наибольший.
Стоп-символ  это первый справа символ в тексте, отличный от со-
ответствующего символа образца. Например, если стоп-символ выявля-
ется при первом же сравнении (P [m] 6= T [s +m]) и не встречается нигде
в образце, то сдвиг s можно сразу увеличить на m. Если стоп-символ
встретился на j-й позиции, а в образе он появляется на k месте (k = 0,
если он не появляется в образце вообще), то можно увеличить сдвиг s на
j k, если k < j.
Эвристика безопасного суффикса предлагает в случае несовпадения
P [j] и T [s + j] (j < m) увеличить сдвиг на
[j] = m maxfk : 0  k < mP [j + 1::m]  P k g
где  означает, что одна из подстрок является суффиксом другой.
В худшем случае время алгоритма Бойера-Мура O((n m+ 1)
m+
jj). На практике, однако, этот алгоритм часто оказывается наиболее
45

эффективным.
6.1 Построение оптимального по Парето множества
в задачах управления системой КА
Рассмотрим задачу об управлении системой из N ИСЗ. Если в начальный
момент элементы орбит всех наших спутников удовлетворяют некоторым
условиям, позволяющим системе функционировать нормально (напри-
мер для системы навигационных спутников с каждой точки поверхности
Земли одновременно должны быть видимы не менее трех спутников), то
под действием различных возмущений эти условия в конце концов пе-
рестают выполняться. Требуется с помощью каких-либо управляющих
воздействий, например, включая в определенные моменты двигатели,
восстанавливать нужную конфигурацию системы.
Естественно проводить оптимизацию по критериям, обеспечиваю-
щим экономичность управления. Для наших управляющих воздействий
(включение двигателей в определенные моменты) можно ограничиться
двумя минимизируемыми критериями. Один из этих критериев  ко-
личество затрачиваемого топлива, а другой  общее число коррекций.
Последний критерий связан с надежностью системы.
Если бы мы оптимизировали лишь по одному критерию, задача реша-
лась бы просто: либо численно, либо аналитически мы нашли бы значе-
ния параметров управления (моменты, в которые мы должны включать
двигатели, дополнительные импульсы, которые мы придаем спутникам
и т.д.), при которых требовалось бы, например, минимальные затраты
топлива.
Если же таких критериев два или больше, то вообще говоря, мы не
можем найти значения параметров, которые одновременно минимизиро-
вали бы и тот, и другой критерий. Дело тут не в астрономии или небес-
ной механике, а в сути оптимизации. Действительно, если мы найдем
параметры, минимизирующие решение по какому-то одному критерию,
например, по топливу, то маловероятно, чтобы это решение было оп-
тимально и по другому (независимому) критерию, например, по числу
коррекций. Исключением могут быть только зависимые критерии, ска-
жем, если бы одним критерием служило количество топлива в тоннах, а
другим  количество топлива в пудах.
В общем же случае мы можем получить только кривую (в случае
двух критериев), состоящую из точек, которые нельзя улучшить по
обоим критериям сразу. Такие решения называются оптимальными по
Пар
ето.
46

Вернемся к нашим спутникам. Рассмотрим систему навигационных
спутников типа Navstar (12-часовые ИСЗ на трех круговых орбитах с
одинаковым наклонением и равноотстоящими восходящими узлами; на
одной орбите находятся N = 8 спутников). Требование к системе  обес-
печить видимость из любой точки поверхности Земли в любой момент
времени четырех ИСЗ  выполняется при равномерном распределении
спутников по орбитам.
Допустим мы умеем (подробности в других курсах) вычислять, когда
и какие импульсы осуществлять, для системы из N спутников, в зависи-
мости от их эволюции, то есть умеем вычислять и положения спутников,
и импульсы для поддержания их конфигурации. Задача состоит в том,
чтобы сделать это оптимальным по Парето (то есть по двум критери-
ям сразу) образом. Ясно, что чем реже мы будем делать коррекции, тем
сильнее должны быть импульсы. Вряд ли можно использовать очень ма-
лые импульсы очень редко.
Из чего выбирать? Будем шевелить положения каждого спутников,
перебирая все допустимые конфигурации. Для первого спутника возь-
мем некоторый сектор 0 <   2=N (чуть больше) и будем перебирать
с некоторым шагом угол, определяющий положения спутника. Положе-
ние второго спутника будем перебирать в секторе от h < h+ от первого
спутника и т.д. Для каждой допустимой конфигурации вычисляются тре-
буемые для поддержания рабочего состояния импульсы и вычисляются
два критерия: F 1  суммарный импульс и F 2  общее число коррекций
(в единицу времени).
Итак, мы знаем как перебирать, мы умеем поддерживать систему в
рабочем состоянии и вычислять значения критериев. Нужно построить
множество оптимальных по Парето точек.
В процессе перебора формируется массив оптимальных точек. Что-
бы поиск оптимальных точек осуществить наиболее эффективным спо-
собом, этот массив следует упорядочить по одному из критериев, напри-
мер, по F 1 . Для элементов этого массива требуется определить лишь три
операции  поиск места элемента в массиве, включение нового элемента
в массив, исключение элемента из массива. Все эти операции особенно
эффективно реализуются, если используется списковая структура. То-
гда для каждой новой точки z = fx i ; y j g находится место в списке,
такое, что F 1 (z 1 )  F 1 (z)  F 1 (z 2 ), где z 1 и z 2  два последовательных
элемента списка. Если F 2 (z 1 )  F 2 (z) > F 2 (z 2 ), то точка z должна быть
включена в список, а все последующие точки z k = z 2 ; z 3 ; : : :, для которых
F 2 (z k ) > F 2 (z), должны быть исключены. Отметим, что машинное время
в основном тратится на перебор. Для шага в 2 Ж общее число рассмотрен-
ных точек N  1:6
10 11 .
47

На рисунке изображено множество оптимальных по Парето значений
критериев для системы из восьми ИСЗ,  = 50 Ж . Возможные значения
критериев расположены выше и правее кривой и на кривой.
6.2 Работа с деревьями в Treecode
Решение задачи N тел, даже численное, весьма трудоемкая задача. Осо-
бенно, если требуется высокая точность (эволюция солнечной системы на
временах порядка ее жизни), или нас интересует системы с очень больши-
ми N (до 10 8 и больше). Ясно, что если мы честно будем вычислять силы
взаимодействия для всех тел, то ресурсоемкость такого алгоритма будет
O(N 2 ). Конечно это не экспоненциальная задача, но при рассматривае-
мых (больших) N даже небольшое снижение ресурсоемкости алгоритма,
например, до N ln N , может позволить нам прослеживать эволюцию си-
стемы, состоящей из существенно б
ольшего числа тел, возможно за счет
некоторой потери точности, с чем можно, однако смириться, если такая
потеря не окажет заметного влияния на качественное изучение эволюции
нашей системы.
Именно для решения таких задач и был разработан иерархический
метод. Суть его состоит в следующем. Каждый временной шаг состоит
из двух фаз:
1. строится дерево нашей системы: корень дерева  вся система,
листья  частицы;
2. построенное дерево обходится и при этом с нужной точностью вы-
числяются силы для каждой частицы.
Начинается дерево с большой ячейки (куба в трехмерном случае или
квадрата  в двумерном, для иллюстрации мы будем использовать имен-
но двумерный), содержащей всю систему. Далее каждую ячейку делим
на 8 равных кубов в трехмерном случае или на 4 квадрата в двумерном.
Если оказывается, что в какой-то из полученных ячеек частиц нет, такая
ячейка в дерево не включается, в противном случае процесс рекурсивно
продолжается дальше, пока в ячейке не окажется ровно одна частица. В
результате получается дерево.
Ясно, что при вычислении силы, действующей на частицу 1, можно,
если тела 2 и 3 достаточно далеки от тела 1, заменить тела 2 и 3 фиктив-
ным телом ячейки с массой, равной сумме масс тел 2 и 3 и находящейся в
центре их масс. Если требуется б
ольшая точность, то можно заменить их
диполем, добавив к предыдущему еще некоторые дополнительные чле-
ны. Если же тела близки (как 2 и 3 в нашем случае), придется вычис-
лить силу честно. Конечно, необходимо определить критерии, когда мы
48

Рис. 1: Построение дерева Барнса-Хата
для системы из 3 частиц (двумерный случай).
должны честно вычислять силу, а когда мы можем целую ветвь дере-
ва заменить всего лишь одной фиктивной массой. Рассмотрение таких
критериев выходит за рамки данного курса, но если они установлены,
вычисление силы, скажем для тела p, выполняется за один обход дерева,
начиная с корня.
В каждом узле q, в который мы попадаем при обходе, мы можем
встретиться с тремя возможностями: Случай первый: q  тело. В этом
случае сила взаимодействия p и q должна непосредственно учитываться,
точнее ссылка на q добавляется в список взаимодействий тела p (чтобы
впоследствии вычислить силу). Если q  не тело, то необходимо выде-
лить еще два случая. Случай второй: если q достаточно далека от p (до-
статочно отделена от p), то в список взаимодействий добавляется сама
ячейка q. Случай третий: ячейка q слишком близка к p, чтобы вычислить
силу в этом случае необходимо проверить всех потомков q.
Подчеркнем, что только в первом случае мы честно вычисляем силу;
во втором случае мы заменяем ВСЕ поддерево одной фиктивной массой,
или мультиполем, что тоже не требует больших вычислений; в послед-
нем случае нам еще только предстоит столкнуться с одним из первых
двух случаев, и чаще всего это будет именно второй случай, когда мы
исключаем из рассмотрения все поддерево.
Конечно, для реального решения задачи придется рассмотреть еще
много деталей. В частности, и дерево можно строить по-другому. На-
пример, идя снизу и объединяя попарно ближайшие тела (вообще-то
49

Рис. 2: Дерева Барнса-Хата
для приведенной системы.
считается, что это хуже). Можно рассматривать различные критерии
отделенности ячеек, применять различные интеграторы (как правило,
применяется симплектический leap-frog интегратор), но основное уже
сделано: использование иерархической структуры позволяет нам силь-
но облегчить задачу и снизить ее ресурсоемкость с O(N 2 ) до O(N ln N)
(в некоторых случаях утверждается, что даже до O(N)).
6.3 Операция с символьными строками. Обратная
польская запись
Давайте построим дерево для вычисления арифметического выражения:
A*B+C
(Рис.)
В таких языках, как C, Pascal, Fortran, любое арифметическое выра-
жение преобразуется в последовательность инструкций процессора, вы-
числяющих это выражение. То есть, на самом деле это выражение при-
водится к более прозрачному виду.
Его (это дерево) можно записать, например, так (см. представления
деревьев).
50

(+ (* A B) C)
Такая запись, когда сначала записываются операции, затем идут операн-
ды, называется префиксной записью. Символы + и * здесь можно
трактовать как имена функций. Можно заменить их более человечески-
ми именами:
(add (multiply A B) C)
Выражения в таком виде можно практически без обработки вычис-
лять на компьютере. Действительно, вызываем функцию add, и если
какой-то из операндов тоже записан в виде вызова функции (у нас это
multiply), то вызываем сначала функцию для вычисления операндов, и
т.д. Снова рекурсивное определение и рекурсивный процесс!!! Собственно
в некоторых языках программирования именно так и задаются вычисле-
ния (и не только числовые), программисты просто используют префикс-
ную, а не привычную инфиксную запись, зато транслятору (или интер-
претатору) вычислить такое выражение, не преобразуя его к какому-либо
иному виду, не составляет труда.
Обрабатывать арифметические выражения станет еще проще, если
знак операции (или имя функции) поместить не перед операндами, а
после них:
A B * C +
Ряд языков (и ряд калькуляторов!) использует именно такое представ-
ление арифметических выражений. Такое (постфиксное представление)
называют обратной польской записью (реже префиксное представление
называют прямой польской записью)
Реализация вычисления записанного в обратной польской записи вы-
ражения удивительно проста. Если встречается операнд, то его значе-
ние помещается на стек (вспомните, что это такое). Если операция (имя
функции), то со стека снимается столько операндов, сколько требует дан-
ная операция, и выполняется соответствующая функция.
Реализация такого механизма столь проста, что языки его исполь-
зующие, были чрезвычайно популярны во времена, когда оперативная
память составляла несколько десятков килобайт. Один из таких языков
широко используется и сейчас (Postscript).
51

7 Языки программирования и программное
обеспечение
7.1 Модель фон Неймана
В 1946(?5) году (???1954???) Джон фон Нейман, (с соавторами???) опи-
сал архитектуру некоторого абстрактного вычислителя, который сей-
час принято называть машиной фон Неймана. Эта машина является
абстрактной моделью ЭВМ, однако, эта абстракция отличается от аб-
страктных исполнителей алгоритмов (например, машины Тьюринга). Ес-
ли машину Тьюринга принципиально нельзя реализовать из-за входящей
в еe архитектуру бесконечной ленты, то машина фон Неймана не под-
дается реализации, так как многие детали в архитектуре этой машины
намеренно не конкретизированы (чтобы не сковывать творческого под-
хода к делу у инженеров-разработчиков новых ЭВМ).
В машине фон Неймана зафиксированы особенности архитектуры,
которые, по мнению авторов, должны быть присущи всем компьюте-
рам. Все современные компьютеры по своей архитектуре отличаются от
машины фон Неймана, но эти отличия, так сказать, второго порядка.
Их удобно рассматривать именно как отличия от базовой архитектуры.
Принципы, сформулированные фон Нейманом, до сих пор еще лежат в
основе архитектуры большинства ЭВМ.
Вот схема машины фон Неймана (толстые стрелки  потоки команд
и данных):
Рис. 3: Схема машины фон Неймана
Вот эти общие принципы:
1. Принцип линейности и однородности памяти: структурно основная
память состоит из перенумерованных ячеек; процессору в любой
52

момент времени доступна любая ячейка. (Т.о. можно давать имена
областям памяти, чтобы впоследствии можно было обращаться к
этим областям.) Время доступа к ячейки одинаково для всех ячеек
памяти (время записи и время чтения могут различаться);
2. Принцип неразличимости команд и данных: программы и данные
хранятся в одной и той же памяти. Программа в процессе выполне-
ния также подвергнуться изменению. Команды одной программы
могут быть получены, как результат исполнения другой.
3. Принцип автоматической работы. Программа состоит из набора ко-
манд, которые выполняются процессором (УУ) автоматически в
определенной последовательности (если командой не предписыва-
ется эту последовательность изменить, программа  набор запи-
санных в памяти машинных команд, описывающих шаги некото-
рого алгоритма, т.е. программа  это запись алгоритма на языке
машины. Язык машины  набор всех возможных команд).
4. Принцип последовательного выполнения команд: Устройство
Управления выполняет некоторую команду от начала до конца, а
затем выбирает для выполнения следующую команду.
Конечно, современные ЭВМ в какой-то степени нарушают все эти
принципы. Существуют машины, которые различаются команды и дан-
ные (в ячейках памяти присутствует специальный тег). В известной мере
нарушается принцип однородности и линейности памяти (адрес памяти
представляется двумя числами ?сегмент-смещение?, или память вооб-
ще может не иметь адресов, т.н. ассоциативная память). Принцип по-
следовательного выполнения команд нарушается в многопроцессорных
(векторных) архитектурах. Нарушаются и некоторые принципы, кото-
рые фон Нейман считал самоочевидными и поэтому не формулировал
их явно. Например, в архитектуре фон Неймана предполагается, что во
время выполнения программы не меняются ни число узлов компьютера,
ни взаимосвязи между этими узлами, таким образом, если Вы вставля-
ете в дисковод дискету, то тем самым Вы нарушаете этот принцип. Тем
не менее, все эти отличия не нарушают, а лишь расширяют общее пред-
ставление об архитектуре.
Явно не фон-неймановские компьютеры, существуют в теории, напри-
мер, квантовые компьютеры, но большинство, как уже было сказано, 
компьютеры с архитектурой фон Неймана, либо отличающиеся от них
лишь некоторым числом деталей.
53

7.2 Императивные языки программирования
Итак, поскольку б
ольшая часть компьютеров следует архитектуре фон
Неймана, то естественно, что б
ольшая часть языков программирования
языков программирования разрабатывалась на основе этой архитекту-
ры. Такие языки называются императивными. Директивные или про-
цедурные  синоним императивных.
Несколько слов о том, зачем вообще нужно знакомиться с различны-
ми концепциями языков программирования. Причин для этого много
 Язык, который используется для решения той или иной зада-
чи, естественно налагает ограничения на используемые структу-
ры управления, структуры данных, абстракции. Выразительная си-
ла языка влияет на глубину наших мыслей. Осознав разнообразие
свойств языков программирования, мы получим больше возможно-
стей для выражения своих идей, даже если те или иные средства
отсутствуют в используемом языке, мы можем их смоделировать с
помощью доступных средств.
 Чем больше языков мы знаем, тем более обоснованный выбор наи-
более подходящего языка мы делаем, решая стоящую перед нами
задачу.
 Чем больше языков мы знаем, тем легче нам понять концепции
новых языков программирования (аналогия с естественными язы-
ками).
 Разобравшись почему тот или иной язык разработан так, а не ина-
че, мы лучше будем представлять, как наиболее рационально ис-
пользовать этот язык.
 Критический разбор языков программирования помогает при кон-
струировании сложных систем.
 Познакомившись с концепциями языков программирования можно
(относительно) объективно оценить текущее состояние используе-
мого программного обеспечения.
Конечно, в задачу данного курса не входит сравнительное изучение
языков программирования, но познакомиться с существующими пара-
дигмами программирования. (Парадигма  способ мышления, не свя-
занный с конкретным языком, свод норм мышления, модель постановки
проблем и их решения.) В своей алгоритмической части современные
54

языки поддерживают несколько парадигм программирования, самыми
распространенными являются императивные языки.
Главными элементами императивных языков программирования, яв-
ляются переменные, которые моделируют ячейки памяти; операторы
присваивания основаны на пересылке данных; итеративная форма по-
вторений является наиболее эффективным методом в архитектуре фон
Неймана. Операнды выражений передаются из памяти в процессор, а ре-
зультат вычисления возвращается в ячейку памяти (левая часть опера-
тора присваивания). Команды хранятся в соседних ячейках памяти, что
облегчает использование итерации, и, наоборот, использование рекурсии,
даже в случаях, когда это использование более естественно, зачастую не
столь эффективно.
Первым таким языком был созданный Конрадом Цузе в 1945 году
язык Plankalkul. Наиболее широко известен Фортран. Примеры импера-
тивных языков программирования привести не трудно. Эти языки из-
вестны каждому. Кроме Фортрана, это Паскаль, С, Алгол, Basic и т.д.
Директивная программа предписывает, как достичь заданную цель,
описывая по шагам все (промежуточные) действия. Заметим, что даже
определение алгоритма, приведенное нами в предыдущей части, тяготеет
к этой классической (императивной) парадигме.
Рассмотрим пример. Предположим, вам надо пройти в городе из
пункта А в пункт Б. Директивная программа  это список команд
примерно такого рода:
от пункта А по ул. Садовой на север до Сенной площади, оттуда по Мо-
сковскому проспекту два квартала, потом повернуть налево и идти до
Серпуховской улицы, по этой улице направо и по левой стороне до дома 12,
который и есть пункт Б.
В директивной программе действия задаются явными командами,
подготовленными ее составителем. Исполнитель же просто им следу-
ет. Хотя команды в различных языках директивного программирования
и выглядят по-разному, все они сводятся либо к присваиванию какой-
нибудь переменной некоторого значения, либо к выбору следующей ко-
манды, которая должна будет выполняться. Присваиванию может пред-
шествовать выполнение ряда арифметических и иных операций, вычис-
ляющих требуемое значение, а команды выбора реализуются в виде
условных операторов и операторов повторения (циклов).
Для классических директивных языков характерно, что последова-
тельность выполняемых команд совершенно однозначно определяется ее
входными данными. Как говорят, поведение исполнителя императивной
55

программы полностью детерминировано.
Собственно наш мир локально императивен. Если взять достаточно
узкую задачу, то ее можно вполне легко описать методами последова-
тельного программирования. Практика показывает, что более сложные
императивные программы (компиляторы, например) пишутся и отлажи-
ваются долго (годами). Переиспользование кода и создание предметно-
ориентированных библиотек упрощает программирование, но ошибки в
реализации сложных алгоритмов проявляются очень часто.
Императивное программирование наиболее пригодно для реализации
небольших подзадач, где очень важна скорость исполнения на современ-
ных компьютерах. Кроме этого, работа с внешними устройствами, как
правило, описывается в терминах последовательного исполнения опера-
ций ("открыть кран, набрать воды"), что делает такие задачи идеаль-
ными кандидатами на императивную реализацию.
Императивные языки хорошо известны и мы не будем углубляться в
их анализ.
7.3 Декларативные языки
Функциональное программирование, как и другие модели неимператив-
ного программирования, обычно применяется для решения задач, ко-
торые трудно сформулировать в терминах последовательных операций.
Практически все задачи, связанные с искусственным интеллектом, по-
падают в эту категорию. Среди них следует отметить задачи распозна-
вания образов, общение с пользователем на естественном языке, реали-
зацию экспертных систем, автоматизированное доказательство теорем,
символьные вычисления. Эти задачи далеки от традиционного приклад-
ного программирования.
Пример о движении из пункта A в пункт B из предыдущего раздела
в декларативном изложении будет выглядеть так:
план города, в котором указаны оба пункта, плюс правила уличного движе-
ния. Руководствуясь этими правилами и планом города, курьер сам найдет
путь от пункта А к пункту Б.
Декларативные программы не предписывают выполнять определен-
ную последовательность действий, в них лишь дается разрешение со-
вершать их. Исполнитель должен сам найти способ достижения постав-
ленной перед ним составителем программы цели, причем зачастую это
можно сделать различными способами  детерминированность в данном
случае отсутствует.
56

Согласитесь, такая возможность впечатляет.
Функциональная программа состоит из совокупности определений
функций, которые в свою очередь представляют собой вызовы других
функций и предложений, управляющих последовательностью вызовов.
При этом функции часто либо прямо, либо опосредованно вызывают са-
ми себя (рекурсия).
Каждая функция возвращает некоторое значение в вызвавшую его
функцию, вычисление которой после этого продолжается; этот процесс
повторяется до тех пор, пока начавшая процесс вычислений функция не
вернет конечный результат пользователю.
Чистое функциональное программирование не содержит оператора
присваивания, в нем вычисление любой функции не приводит ни к каким
побочным эффектам, отличным от собственно вычисления ее значения.
Разветвление вычислений основано на механизме обработке аргументов
условного предложения, а циклические вычисления реализуются с помо-
щью рекурсии.
Отсутствие оператора присваивания делает переменные, используе-
мые в функциональных языках программирования, очень похожими на
переменные в математике  получив однажды свои значения, они боль-
ше никогда их не меняют. Отсутствие побочных эффектов в процессе
вычисления функций приводит к тому, что порядок выполнения отдель-
ных фрагментов программы не существенен  итоговое значение в лю-
бом случае будет одинаковым.
Функциональное программирование весьма красиво и иногда в ка-
честве первого языка программирования, изучаемого студентами, выби-
рается Haskell или Lisp. Для успешного овладения данным стилем про-
граммирования, впрочем, необходимо весьма глубокое понимание многих
разделов математики.
В чистом LISP'е существует только два типа структур данных: атомы
и списки. Атомы  либо символы, либо числовые константы. Списки
определяются круглыми скобками:
(A B C D)
или
(A (B C) D (E (F G)))
Списки, как правило, представляются в виде односвязных линейных
списков, каждый узел которых содержит два указателя и представля-
ет собой элемент списка. Первый указатель указывает на атом или пер-
вый узел подсписка, второй указатель указывает на следующий элемент
списка.
57

Список (A B C D) можно интерпретировать, как данные, тогда это
список из четырех элементов, а можно как программу. В последнем слу-
чае функция A применяется к трем параметрам B, C и D.
Собственно мы описали весь синтаксис языка LISP.
Поразительно, что такой простой язык на протяжении четверти ве-
ка доминировал в области искусственного интеллекта, да и сейчас еще
остается самым распространенным в этой сфере.
Вот пример LISP-программы. Здесь определяется функция, сравни-
вающая два списка и возвращающая TRUE, если списки идентичны, и NIL,
в противном случае
(DEFUN equal_lists (l1 l2)
(COND
((ATOM l1) (EQ l1 l2))
((ATOM l2) NIL)
((equal_lists (CAR l1) (CAR l2))
(equal_lists (CDR l1) (CDR l2)))
(T NIL)
)
)
На LISP'е реализованы многие системы аналитических вычислений:
Reduce, Macsyma, многие программы автоматического проектирования,
например AutoCAD, и много других программ, включая редактор всех
времен и народов Emacs.
Функциональные языки программирования: Lisp, Scheme, ML,
Haskell.
Чтобы программировать на LISP'е недостаточно познакомиться с его
правилами и функциями. И синтаксис, и семантика LISP'а, как мы ви-
дели, просты. Однако парадигма функциональных языков настолько от-
лична от парадигмы привычных нам языков императивных, что глав-
ная трудность заключается в том, чтобы думать по-лисповски, повер-
нуть свои мозги, приучить себя мыслить по-другому. Нужно ли такое
преодоление себя? Да, многие (трудные) задачи решаются проще всего
именно с использованием функциональных языков. Например системы
аналитических вычислений. Пусть в выражение (символьное) 1 X 2 мы
хотим вместо X подставить, например, cos(). Это обычное действие при
работе с символьными выражениями. Если наше первоначальное выра-
жение представлено списком (MINUS 1 (POWER X 2)), то все, что нам
нужно сделать, это вместо атома X подставить список (COS ). Ну воз-
можно, потом еще обработать получившийся список и получить, если со-
58

ответствующее правило определено, sin(). В рамках парадигмы LISP'а
такие действия описываются чрезвычайно просто.
Интересно, что на протяжении многих лет (вечность по компьютер-
ным меркам) во многих университетах США LISP был первым языком,
с которого студенты начинали изучение программирования.
Замечание о том, что при переходе от императивных языков к функ-
циональным необходимо переучиваться думать, в полной мере относит-
ся и к языкам, относящимся к другим парадигмам, например, к языкам
логического программирования.
7.4 Языки логического программирования
Языки логического программирования, самым известным из которых яв-
ляется Пролог, конечно можно было бы отнести к декларативным язы-
кам, в том смысле, что в программах указывается лишь описание жела-
емого результата, а не детальная процедура его получения, но отличие
от функциональных языков столь велико, что их можно выделить в от-
дельный класс.
И синтаксис, и семантика логических языков отличается отличается
от синтаксиса и семантики и императивных, и функциональных языков.
Логическое программирование  это использование формальной ло-
гической записи для описание программы. В качестве такой записи ис-
пользуется исчисление предикатов. Исчисление предикатов обеспечива-
ет основную форму для передачи информации, а метод доказательства,
названные резолюцией и разработанный Робинсоном в 1965 году, предо-
ставляет способы логического вывода.
Программы языка Пролог состоят из набора утверждений. Утвержде-
ния могут быть двух видов: факты и правила.
раздел(астрометрия, астрономия).
раздел(астрофизика, астрономия).
раздел(небесная механика, астрономия).
предмет(движение тел, небесная механика).
предмет(положение звезд, астрометрия).
Эти факты утверждают, что выполнено отношение раздел между объек-
тами астрофизика и астрономия и между объектами небесная механика
и астрономия и т.д.
А вот правила:
астрономическая_наука(X) :- раздел(X, астрономия).
астрономия_изучает(X) :- предмет(X, Y), раздел(Y, астрономия).
59

Первое правило утверждает, что если X  раздел астрономии, то X яв-
ляется астрономической наукой, а второе  что если X предмет науки Y
и Y  раздел астрономии, то астрономия изучает X.
Имеющиеся факты и правила можно использовать для того, чтобы
задать вопрос:
?- астрономическая_наука(астрология).
и получить ответ
нет
На вопрос
?- астрономическая_наука(X).
получим ответ
X = астрометрия;
X = астрофизика;
X = небесная механика;
А на вопрос:
?- астрономия_изучает(движение тел).
естественно получим ответ
да
В Прологе присутствуют также основные операции работы со спис-
ками.
Несмотря на ряд проблем, возникающих при использовании Пролога,
логическое программирование способно работать во многих приложени-
ях. Например, логическое программирование естественным образом со-
ответствует нуждам реализации систем управления реляционными ба-
зами данных.
Реально используется язык Пролог для создания экспертных систем,
где база данных (или база знаний) может быть неполной.
Подходит Пролог для обработки текстов на естественных языках.
И вообще концепция логического программирования интересна и кра-
сива сама по себе, а развитие компьютерной техники и разработка новой
техники логического вывода может привести к развитию языков логиче-
ского программирования, которые позволят эффективно решать задачи,
указывая только что, а не как следует сделать.
60

7.5 Программирование в ограничениях
Программирование в ограничениях (constraint programming)  достаточ-
но новое направление в декларативном программировании. Появилось
оно во многом в результате развития систем символьных вычислений,
искусственного интеллекта и исследования операций.
Программирование в ограничения  подход, в котором в программе
определяется тип данных решения, предметная область решения и огра-
ничения на значение искомого решения. Решение находится системой.
Программирование в ограничениях  это программирование в тер-
минах постановок задач.
Постановка задачи  это конечный набор переменных V =
fv 1 ; : : : ; v n g, соответствующих им конечных (перечислимых) множеств
значений D = fD 1 ; : : : ; D n g, и набор ограничений = fC 1 ; : : : ; Cm g. Огра-
ничения представлены как утверждения, в которые входят в качестве
параметров переменные из некоторого подмножества V j ; j = 1::m набо-
ра V . Решение такой задачи  набор значений переменных, удовлетво-
ряющий всем ограничениям C j .
Синтаксически такую постановку задачи можно записать как прави-
ло для типизированного Пролога:
problem(V1:D1, ..., Vn:Dn) :-
С1, ... Cm.
Семантически, однако, программирование в ограничениях отличает-
ся от традиционного логического программирования в первую очередь
тем, что исполнение программы рассматривается не как доказательство
утверждения, а нахождение значений переменных. При этом порядок
удовлетворения отдельных ограничений не имеет значения, и система
программирования в ограничениях, как правило, стремится оптимизи-
ровать порядок доказательства утверждений с целью минимизации от-
ката в случае неуспеха. С этой целью набор ограничений может быть
соответствующим образом преобразован  по правилам, аналогичным
правилам Пролога. Любую задачу можно рассматривать как ограниче-
ние: значения переменных должны быть решением этой задачи. Часто
о программировании в ограничениях говорят исключительно как о до-
полнительной ветви логического программирования.
В качестве примера, мы можем задать системе программирования в
ограничениях следующий запрос:
? (X : integer) X>1, member(X, [1,2,3]).
61

Типичная Пролог-система на таком запросе выдаст ошибку: явля-
ется неинициализированной переменной, и его нельзя сравнивать с чис-
лом 1. Система, поддерживающая программирование в ограничениях,
воспримет эти утверждения как ограничения (а не как цели, которые
требуется доказать), и выдаст нам требуемые решения: = 2 и = 3.
Системы символьных вычислений нередко позволяют использовать
допущения  по сути, те же ограничения. И на следующий (простой)
запрос:
assume X>0.
when X+1<10 ?
выдавать ответ:
X in (0..9).
Как правило, такие системы могут доказывать достаточно нетриви-
альные математические утверждения, выводя минимальными необхо-
димыми ограничениями, и проверяя эти ограничения на совместность.
В задачах исследования операций и реализации искусственного ин-
теллекта часто используется некоторое пространство решений, сужени-
ем которого достигается необходимый результат. Такие сужения есте-
ственным образом представляются как ограничения.
7.6 Объектно-ориентированное программирование
Объектно-ориентированное программирование появилось на свет божий
из недр событийно-управляемого программирования.
В событийно-управляемом программировании отдельные процессы
максимально автономны, единственное средство общения между ними 
посылка сообщений (порождение новых событий). События могут быть
как общими для всей системы, так и индивидуальными для одного или
нескольких процессов. В таких терминах достаточно удобно описывать,
например, элементы графического интерфейса пользователя, или моде-
лирование каких-либо реальных процессов (например, управление улич-
ным движением)  так как понятие события является для таких задач
естественным.
Поддержка объектно-ориентированного программирования в насто-
ящее время включена во все популярные языки, как императивные
(Python, C++, Java), так и декларативные (CLOS, Prolog++).
62

Несмотря на такую поддержку парадигма объектно-
ориентированного программирования отличается от всех уже рас-
смотренных и и, чтобы эффективно использовать его необходимо
думать объектно-ориентировано.
Основу ООП обеспечивают три свойства
 абстрактные типы данных;
 наследование;
 полиморфизм.
Абстрактные типы данных
Абстракция  представление о некотором объекте, содержащее толь-
ко существенные в данном контексте свойства. Абстракция позволяет
объединить экземпляры объектов в группы, внутри которых можно не
рассматривать общие свойства, абстрагироваться от них, а изучать толь-
ко свойства, отличные для отдельных элементов группы. Таким обра-
зом, абстракция, позволяя программисту сосредоточиться лишь на су-
щественных свойствах объекта, является средством против сложности
программирования, она позволяет сделать большие и сложные програм-
мы более управляемыми.
Собственно один вид абстракции вам хорошо знаком. Это абстракция
процесса. Действительно, вызов подпрограммы, скажем подпрограммы
сортировки, не зависит от алгоритма сортировки, используемого в дан-
ной подпрограмме, является абстракцией реального процесса сортиров-
ки. Все, что нам нужно знать при вызове этой подпрограммы,  это
имя упорядочиваемого объекта, тип его элементов и тот факт, что этот
самый вызов выполнит требуемую сортировку.
Собственно эта абстракция, использование подпрограмм, хорошо зна-
кома. Но давайте вспомним (из первой части), что данные неразрывно
связаны с теми операциями, которые для них определяются, то есть аб-
стракция данных связана с абстракцией процессов, реализующих эти
операции.
Теперь представим, что мы пишем большую программу. Если размер
нашей программы превышает несколько тысяч строк, мы сталкиваемся
с необходимостью разделить ее на группы логически связанных подпро-
грамм и данных (такие группы часто называют модулями). Это позво-
ляет нам, во-первых, лучше организовать и поддерживать логическую
структуру программы и управлять ею и, во-вторых, избежать повтор-
ной компиляции неизменных частей программы. Способ объединения в
единое целое подпрограмм и данных известен как инкапсуляция. Инкап-
суляция является основой абстрактной системы.
63

Абстрактный тип данных  это инкапсуляция, которая содержит
только представления (структуры) данных одного конкретного типа и
подпрограммы, которые выполняют операции с данными этого типа. С
помощью управления доступом несущественные детали описания типа
можно скрыть от внешних модулей, использующих данный тип, внеш-
ний модуль, как правило, даже не знает, как реально представляется ис-
пользуемый тип. Экземпляр абстрактного типа данных называется объ-
ектом.
Абстрактный тип данных должен удовлетворять следующим услови-
ям:
 представление (определение типа) и операции над объектами дан-
ного типа содержатся в одной синтаксической единице (такой еди-
ницей может быть модуль или другая конструкция, определяемая
тем или иным языком), создавать переменные этого типа можно и
в других модулях;
 представление объектов данного типа скрыто от программных мо-
дулей, использующих этот тип, над такими объектами можно про-
изводить лишь те операции, которые прямо предусмотрены в опре-
делении типа.
Наследование
Допустим, мы разработали какой-то сложный тип данных, описали
множество операций над этим типом данных и хотим использовать уже
созданные программы в другой, близкой задаче. Проблема заключается
в том, что в новой задаче и свойства и операции уже разработанного
типа данных не вполне подходят для решения нашей новой задачи. Уже
имеющиеся типы необходимо как-то, пусть немного, но модифицировать.
Модификации, хоть и небольшие, не так то просто выполнить, для этого
надо разобраться в уже существующем коде. Кроме того, как правило
модификации влекут за собой изменения в программах, использующих
этот тип данных.
И еще. По крайней мере до сих пор, все наши типы данных являлись
независимыми, находились на одном уровне иерархии. В то же время
наша задача может содержать связанные между собой объекты, находя-
щиеся в некоторой субординации друг с другом.
Эти проблемы позволяет решить второе важное свойство ООП 
наследование.
Абстрактные типы данных обычно называются классами. Классы
представляются в виде иерархической древовидной структуры, в которой
64

классы с более общими чертами располагаются в корне дерева, а специ-
ализированные классы и в конечном итоге индивидумы располагаются
в ветвях. На рисунке показана одна из возможных иерархий классов,
включающая класс Солнечная система на самом верхнем уровне иерар-
хии, объекты класса Планета  на втором уровне, и объекты класса
Спутники  на нижнем.
Рис. 4: Наследование
Класс, который определяется через наследование от другого клас-
са, называется производным классом или подклассом. Класс, от которо-
го производится новый класс, называется родительским классом. Под-
программы, определяющие операции над объектами класса, называются
методами. Вызовы методов иногда называют сообщениями (вспомним
событийно-управляемое программирование). Весь набор методов объек-
та называют протоколом сообщений или интерфейсом. Таким образом
вычисления в объектно-ориентированном программе определяются сооб-
щениями, передаваемого от одного объекта другому.
В простейшем случае класс наследует все сущности (переменные и ме-
тоды) родительского класса, этим наследованием, однако, можно управ-
лять. В дополнение к наследуемым сущностям производный класс может
добавлять новые и модифицировать методы. Новый метод замещает на-
следуемую версию метода.
Полиморфизм
Полиморфизм это концепция, позволяющая иметь различные реали-
зации для одного и того же метода. Их выбор осуществляется в зависи-
мости от типа объекта, переданному методу при вызове.
Это свойство позволяет подменять один объект другим, способным
обрабатывать те же сообщения. Таким образом обеспечивается более лег-
кое расширение программных средств при их разработке и поддержке.
Объектно-ориентированное программирование активно используется
как средство проектирования сложных систем и моделирования, напри-
мер, в языке UML.
65

7.7 Параллельное программирование
Внимательный читатель (слушатель?) может заметить некоторую
неувязку в изложении различных парадигм программирования. Дей-
ствительно, парадигма императивного программирования основана на
архитектуре фон Неймана. Даже определение алгоритма несет оттенок
именно этой архитектуры. Вспомним: Алгоритм  набор конечного чис-
ла правил, задающих последовательность выполнения операций для ре-
шения задачи. То есть, согласно этому определению, алгоритм указывает
как решать задачу. Языки логического программирования ставят во гла-
ву угла не как следует решать задачу, а что надо получить. А для этого
необходимо сформулировать что является объектом решения, то есть
построить модель исследуемых объектов. Тем не менее, пока архитекту-
ра фон Неймана оставалась по существу единственной распространенной
архитектурой, императивное, последовательное программирование наи-
более полно отвечало используемым компьютерам.
Развитие компьютерной техники, однако, привело к появлению ком-
пьютеров (CDC, середина шестидесятых), в которых имелась возмож-
ность обрабатывать данные параллельно, выполняя одну и ту же опера-
цию одновременно над целым массивом (вектором) значений  появи-
лась векторная архитектура. Появились машины с несколькими про-
цессорами, несколько компьютеров (в том числе и многопроцессорных),
объединенных высокоскоростной коммуникационной сетью, составляли
одну параллельную машину. Именно компьютеры с несколькими век-
торными процессорами и высокоскоростной общей памятью первона-
чально назывались суперкомпьютерами. Сейчас под суперкомпьютером
подразумевают вычислительную систему, входящую в список TOP500 са-
мых высокопроизводительных компьютеров мира (самый медленный 
245/384 Гигафлопс, здесь первое число  максимальная достигнутая
производительность, второе  теоретическая; а самый быстрый Earth-
Simulator/5120 фирмы NEC  35860/40960 Гигафлопс, работает в Япо-
нии; из TOP500 два компьютера работают в России, один, собственной
разработки, в Объединенном суперкомпьютерном центре  734.60/1024
Гигафлопс  на 95 месте, второй  HP SuperDome 750, 345/576 Гига-
флопс, 357 место, в СберБанке; данные на 16.11.2003, 22 версия TOP500).
Использование таких параллельных компьютеров, даже если они не
входят в список TOP500, требуют своего подхода, своей парадигмы па-
раллельных вычислений. Если обратиться к уже рассмотренным пара-
дигмам, то можно сделать вывод, что императивное программирование,
по крайней мере в своем чистом виде, никак не подходит к организации
параллельной работы. А вот функциональное программирование име-
66

ет черты для такой работы весьма ценные. Вспомним, что в LISP'е нет
операторов присваивания, нет побочных эффектов, а переменные, раз
получившие значение, уже не меняют его. Все это облегчает параллель-
ные вычисления. В Прологе тоже не важен порядок разрешения правил,
и поиск подходящих правил и фактов легко организовать параллельно.
Однако это лишь общие соображения. Для того, чтобы познакомить-
ся с парадигмой параллельных вычислений поближе, нужно и более де-
тально изучить архитектуру параллельных компьютеров, и рассмотреть
различные подходы к организации параллельных вычислений.
7.7.1 Архитектуры параллельных компьютеров
Но сначала рассмотрим различные архитектуры компьютеров. Наибо-
лее известна классификация компьютерных архитектур Майкла Флинна
(1972). В ее основу положено описание работы компьютера с потоками
команд и данных. Выделяется четыре класса архитектур:
1. SISD  один поток команд и один поток данных. Это, как легко
догадаться, обычные компьютеры, выполняющие в каждый момент
времени только одну операцию над одним элементом данных, то
есть уже известная архитектура фон Неймана.
2. SIMD  один поток команд и несколько потоков данных. Все про-
цессоры находятся под управлением главного процессора, называ-
емого контроллером, и нескольких процессоров обработки данных
или процессорных элементов. Если в команде встречаются данные,
контроллер рассылает команду на все процессорные элементы, ко-
торая и выполняется одновременно на всех или на нескольких про-
цессорных элементах. Этот подход пригоден только для ограничен-
ного круга задач, характеризующихся высокой степенью регуляр-
ности (упорядоченности). Большинство параллельных алгоритмов
не могут эффективно выполняться на SIMD-компьютерах. Приме-
ром компьютеров данной архитектуры являются обычно машины
с векторными процессорами. Вот реальные машины этого класса:
MasPar MP, CM-2, DAP и другие.
3. MISD  несколько потоков команд и один поток данных. Машин
этого не существует. С большими оговорками можно отнести сю-
да компьютеры с конвейерными процессорами. Впрочем, известна
конструкция с систолическим массивом процессоров, где в каж-
дом цикле работы каждый процессорный элемент получает данные
67

от своих соседей, выполняет одну команду и передает результат
соседям.
4. MIMD  несколько потоков команд и несколько потоков данных.
Наиболее богатая и давно известная категория. Довольно давно по-
явились компьютеры с несколькими независимыми процессорами,
но поначалу на разных процессорах выполнялись разные и незави-
симые программы. MIMD-компьютеры являются лидерами на рын-
ке высокопроизводительных систем. Индивидуальные процессоры
в этом случае работают под управлением своих собственных про-
грамм, чем достигается большая гибкость заданий, выполняемых
процессорами в каждый данный момент. Машины MIMD типа мо-
гут эмулировать машины SIMD типа полностью или частично. В
этот класс попадают симметричные параллельные вычислительные
системы, рабочие станции с несколькими процессорами, кластеры
рабочих станций и т.д. Примерами подобных машин являются IBM
SP, Intel Paragon, Thinking Machines CM5, Cray T3D, Cray T3E,
Meiko CS-2, HP SPP-1600, Parsytec CC и другие. Собственно кла-
стер рабочих станций настолько дешевое решение, что каждый у
есть, скажем дома, два компьютера может легко создать парал-
лельную машину.
Не менее важна классификация параллельных машин по организации
памяти. Память может быть доступна глобально всем процессорам или
локально  у каждого процессора своя память. В первом случае говорят
об общей (разделяемой) памяти (shared memory). Во втором случае мы
имеем дело с распределенной (локальной) памятью (distributed memory),
каждый процессор может адресоваться только к собственной памяти, а
обмены между процессорами происходят путем передачи сообщений, со-
держащих ту или иную информацию. Для вычислений естественно пред-
почтительнее машины с разделяемой памятью, но они заметно дороже
и, кроме того, их труднее изменять (например, добавив несколько про-
цессоров), поэтому б
ольшее распространение получили машины с рас-
пределенной памятью.
И, наконец, еще одной важной характеристикой параллельной маши-
ны является способ общения отдельных процессоров друг с другом. За-
дачей соединения процессоров является обеспечение наименьшего числа
пересылок (или времени пересылок), необходимых для переноса данных
между любыми двумя процессорами системы. Машины с разделяемой
памятью обычно используют динамическую связь между различными
узлами (процессорами) и памятью. Связь реализуется с помощью пере-
ключателей, которые устанавливают связь между процессорами и памя-
68

тью. Машины с распределенной памятью обычно используют статиче-
скую сеть. Топология связей определяет пространственные связи про-
цессоров и является важным параметром в реализации параллельного
алгоритма. Процессоры не связанный друг с другом непосредственно
передают свои сообщения через промежуточный процессор. Кластеры
персональных компьютеров или рабочих станций объединяются относи-
тельно низкоскоростной сетью.
7.7.2 Распараллеливание вычислений
Теперь от архитектур параллельных систем вернемся к параллельному
программированию. Важно понять, что тот или иной подход к програм-
мированию параллельных вычислений, зависит в первую очередь от ар-
хитектуры используемой для решения задачи параллельной машины.
Существуют два основных подхода к распараллеливанию вычисле-
ний. Это параллелизм данных и параллелизм задач. В англоязычной
литературе соответствующие термины  data parallel и message passing.
В основе обоих подходов лежит распределение вычислительной рабо-
ты по доступным пользователю процессорам параллельного компьютера.
При этом приходится решать разные проблемы. Прежде всего это доста-
точно равномерная загрузка процессоров, так как если основная вычис-
лительная работа будет ложиться на один из процессоров, то вся работа
будет мало отличаться от обычных последовательных вычислений. Дру-
гая проблема  скорость обмена информацией между процессорами. Ес-
ли вычисления выполняются на высокопроизводительных процессорах,
загрузка которых достаточно равномерная, но скорость обмена данными
низкая, основная часть времени будет тратиться впустую на ожидание
информации, необходимой для дальнейшей работы данного процессора.
Рассматриваемые подходы различаются методами решения этих двух
основных проблем. Разберем более подробно параллелизм данных и па-
раллелизм задач.
Параллелизм данных предполагает, что одна операция выполняется
сразу над всеми элементами массива данных. Различные фрагменты та-
кого массива обрабатываются на векторном процессоре или на разных
процессорах параллельной машины. Распределением данных между про-
цессорами занимается программа. Распараллеливание выполняется уже
на этапе компиляции, а роль программиста сводится лишь к управлению
оптимизацией такого распараллеливания. В этом случае, как правило
память разделяемая и используются специальные компиляторы, High
Perfomance Fortran или C*, например.
Однако векторные машины и машины с разделяемой памятью не так
69

доступны, как, скажем, кластеры персональных компьютеров. В слу-
чае кластеров персональных компьютеров или MIMD-машин с распре-
деленной памятью. Программирование, основанное на параллелизме за-
дач предполагает, что задача разбивается на несколько самостоятельных
задач, и каждый процессор решает свою задачу. Чем больше число за-
дач, которые допускают одновременное решение, тем б
ольшую эффек-
тивность мы получаем, при этом все эти программы должны обмени-
ваться результатами своей работы с помощью вызова неких стандарт-
ных процедур. Программист при этом ответственен за распределение
данных между процессорами и подзадачами и обмен данных. Это бо-
лее трудоемкий процесс, чем в предыдущем случае, как в отладке, так
и в обеспечении равномерной загрузки процессоров и минимизации об-
менов между процессами, кроме того возможны тупиковые ситуации,
когда посланные данные не доходят до процесса, которому они посла-
ны. Вместе с тем эта более гибкая система может использоваться на
параллельных компьютерах самой дешевой архитектуры  кластерах
персональных компьютеров. Специализированные библиотеки для орга-
низации таких параллельных процессов (MPI, Message Passing Interface)
или PVM (Parallel Virtual Machines) доступны (в том числе и в исход-
ных кодах) и работают в различных операционных средах (Linux, MS
Windows и т.д.).
Кроме доступности и дешевизны, программирование, основанное на
параллелизме задач, еще и достаточно близк
о к привычной архитектуре
(фон Неймана), поскольку задача разбивается на ряд последовательных
подзадач.
7.7.3 Закон Амдала
Попробуем оценить выигрыш (ускорение), который мы можем получить,
используя для решения задачи n процессоров. Определим выигрыш па-
раллельного алгритма S p :
S p =
T 1
T p
;
здесь T 1  время работы параллельного алгоритма на одном процес-
соре, T p  время работы параллельного алгоритма на p процессорах
1  S p  p.
Закон Амдала. Пусть   доля вычислений, которые выполняются
в параллельном режиме, 1   доля вычислений в последовательном
режиме (эти режимы не совмещаются). Тогда последовательные вычис-
ления занимают время (1 )T 1 , а параллельные  T 1 =p. Оба режима
70

занимают время T p = T 1 (1  + =p). Формула для выигрыша (ускоре-
ния) имеет вид:
S p =
p
p (p 1)
и
lim
p!1
S p =
1
1 
Зависимость ускорения S p от числа процессоров и от доли параллель-
ных вычислений представлена на рисунке.
Рис. 5: Закон Амдала
Из рисунка видно, что для программ с небольшой степенью парал-
лелизма использование большого числа процессоров не дает сколько-
нибудь заметного выигрыша в быстродействии. Начиная с некоторого
места, увеличение числа процессоров дает только небольшой выигрыш в
производительности. Отметим, что на практике приходится принимать
во внимание время обмена данными и это еще ухудшает ситуацию, мо-
жет даже наблюдаться снижение производительности при увеличении
числа процессоров.
Разработка программ для параллельных машин  непростое (по
крайней мере непривычное) дело. Если архитектура используемой Ва-
ми машины предполагает параллелизм данных, большую часть работы
можно возложить на транслятор. Векторные машины в этом случае
хорошо справятся с операциями, требующими одних и тех же действий
над массивами данных, например, сложение, перемножение, : : : матриц.
Задачи, решающиеся методами конечных элементов, в которых для вы-
числения значений некоторых параметров требуется только знание этих
71

параметров в соседних точках, хорошо укладываются в эту схему. Одна-
ко, во-первых, не все задачи позволяют эффективно использовать век-
торные машины, и, во-вторых, как мы знаем, по причине своей деше-
визны наиболее распространенными являются параллельные машины,
состоящие из нескольких самостоятельных компьютеров (кластеры PC,
например). В этом случае мы должны использовать другой подход к
распараллеливанию задачи  параллелизм процессов. Разбиение зада-
чи на ряд параллельно выполняющихся процессов целиком ложится на
разработчика программы, здесь нет общих решений и эту часть нельзя
возложить на компилятор.
Вспомним задачу N тел и рассмотренный нами алгоритм Treecode.
Допустим N = 10 6 . Если бы мы могли использовать N машин для реше-
ния нашей задачи, мы могли бы каждой поручить вычисление на каждом
шаге сил, действующих на каждое из N тел. Вряд ли, однако, нам это
удастся. Во-первых, 10 6 тел это далеко не предел, а, во-вторых, алгоритм
TreeCode хорош тем, что позволяет нам не вычислять силу для каждой
пары, заменяя с небольшой потерей точности множество далеких тел
одним. Как же разбить задачу на несколько независимых процессов, на
относительно независимые параллельные части? Как решить, что си-
лы, действующие на данное тело, нужно вычислять в одном процессе, а
силы, действующие на другое  в другом. При этом процессы по возмож-
ности должны обрабатывать близкие тела (минимизируя таким образом
обмен сообщениями между процессами), а алгоритм такого разбиения
должен быть и концептуально, и технически прозрачен и обеспечивать
сбалансированную работу p процессоров. Идея состоит в том, чтобы раз-
бить все тела на p групп с весами, зависящими от требуемого времени
вычислений. Сделать это в пространственном случае невозможно (вспо-
мните Парето, где было два параметра), поэтому все сводится к разби-
ению на p равных в смысле затрат на вычисления групп одномерного(!)
пространства, в котором тела упорядочены, и таким образом разбиение
элементарно. Как строить требуемую кривую, хорошо известно. Такие
кривые (которым принадлежат, например, все точки квадрата, или куба
в пространственном случае) известны уже более ста лет и носят название
кривых Пеано-Гильберта.
72

На рисунке приведена кривая Пеано-
Гильберта, которая иллюстрирует метод
разбиения метод распараллеливания алго-
ритма TreeCode в двумерном случае на 16
процессоров. Трехмерный случай принци-
пиально ничем не отличается. Организо-
вав разбиение на p процессов, мы, конеч-
но, еще должны обеспечить взаимодействие
различных процессов с помощью посылае-
мых процессами друг другу сообщений, с
информацией о состоянии процесса и полученными данными.
7.8 Специализированные языки. Языки управления
базами данных
Мы рассмотрели различные парадигмы программирования. Можно
классифицировать известные языки и по другим признакам. (В одном
из докладов военно-морскому флоту было приведено более 2570 различ-
ных свойств языков программирования.) Например, по принадлежности
к тому или иному семейству языков:
 C-подобные,
 Pascal-подобные,
 Prolog-подобные,
 семейства универсальных языков,
 семейство уникальных языков (Forth, Postscript) и т.д.
По степени абстракции от аппаратуры:
 языки низкого уровня (ассемблер);
 языки высокого уровня (сложные структуры, доступ к памяти осу-
ществляется только через операции);
 языки сверхвысокого уровня (команды выполняются на полностью
абстрактной машине, доступ к памяти скрыт).
По ориентации на предметные области, специализированные языки:
 языки форматирования текстов (TeX, LaTex),
73

 языки разметки (SGML, XML),
 языки скриптов (Perl, Tcl/Tk, bash, csh),
 языки описания аппаратуры (VHDL  Very high speed integrated
circuit Hardware Description Language),
 языки создания графики (Postscript),
 языки описания виртуальной реальности (VRML),
 языки конфигурирования (autoconf),
 промежуточные языки (расширения, PSP).
К языкам, ориентированным на предметные области, можно отнести
и языки работы с базами данных. Несколько слов о БД. Террабайты ин-
формации наблюдательных данных, прежде всего с космических миссий,
нельзя эффективно использовать без баз данных.
БД  совокупность, связанных между собой данных. Можно выде-
лить такие блоки:
 поля  поле содержит один элемент данных;
 запись  несколько связанных полей представляют собой запись;
 таблицы  наиболее общий элемент базы данных  объединение
идентичных по смыслу записей.
Если рассматривать реляционные БД, то каждую таблицу можно
трактовать как некоторое отношение, запись (строка таблицы) назы-
вают еще кортежем, а поле  аттрибутом отношения k 2 K, K 
множество всех атрибутов отношения  называют схемой отношений.
Если определить домен как множество возможных значений атрибутов
D k , то отношение D(K)  это подмножество прямого произведения до-
менов X k2K D k .
Такое, может быть чересчур формальное, определение отношения
позволяет свести все требуемые для работы с базой данных операции
к операциям реляционной алгебры.
Как правило БД содержит несколько (много) связанных таблиц, то
есть для описания какой-либо совокупности данных нужно разработать
совокупность схем отношений, которые используются для представления
информации. Эта совоукупность называется схемой БД. Схема  это
скелет базы, а саму базу данных составляет набор описанных в схеме та-
блиц  значение отношений. База данных Солнечной системы могла бы
74

содержать два отношения: таблицу, описывающую планеты Солнечной
системы
 N : номер планеты k 2 [0; 1; : : : ; 9];
 Name: название планеты;
 M : масса;
 Elements: элементы орбиты;
 NoS: число спутников;
 N_Sat: номер спутника (ссылка на другое отношение);
 : : :.
Пример кортежа:
3, Земля, 332958, {1, 0.167, ...}, 1, 1, ...
Здесь масса приведена в обратных массах Солнца (M & = 1=332958M  ).
Второе отношение  таблица спутников планет
 N : номер спутника;
 Name: название спутника;
 M : масса;
 Elements: элементы орбиты;
 N_planet: родительская планета;
 : : :.
Пример кортежа этого отношения:
1, Луна, 81.3, {1, 384402, 0.055, ...}, 3, ...
Между отношениями могут существовать функциональные зависи-
мости. Зависимость один к одному связывает единичный кортеж одно-
го отношения с кортежем другого. Зависимость один ко многим свя-
зывает единичный кортеж (планеты) одного отношения с несколькими
кортежами другого (спутники).
75

Для поддержки целостности данных в каждом кортеже обязательно
должен быть ключ, поле, значение которого уникально для каждой запи-
си. В нашем случае это номер планеты для первого отношения и номер
спутника  для второго.
Представление данных в БД не зависит от их физической организа-
ции, а только от их структуры и отношений. В реляционных базах дан-
ных это обеспечивается за счет использования математической теории
отношений. Собственно для получения информации из базы необходи-
мо выполнить преобразования таблиц, причем достаточно использовать
небольшое число операций (реляционной алгебры):
 объединение (нескольких наборов кортежей в один в теоретико-
множественном смысле);
 пересечение (нескольких наборов кортежей в один),
 вычитание (эти три операции  теоретико-множественные и опе-
ранды должны иметь одну и ту же схему отношения);
 произведение (из двух таблиц составляется таблица, в которой каж-
дый кортеж одной сцепляется с каждым кортежем другой);
 выборка (получение таблицы, в которой присутствуют только кор-
тежи, удовлетворяющие заданному условию);
 проекция (удаление из таблицы некоторых атрибутов);
 расширение (добавление в таблицу некоторых атрибутов);
 соединение (в произведении оставляются только кортежи, в кото-
рых одинаковы значения некоторых атрибутов, например, список
планет со спутниками);
 деление.
Эти операции применяются для формирования новых таблиц, которые
представляют интересующий нас результат. Существует специальный
язык запросов SQL (Structured Query Language) служит для работы с
реляционными базами данных, то есть позволяет создавать требуемую
таблицу из имеющихся в БД, используя эти операции.
В теории БД определен ряд свойств, так называемые нормальные
формы, для отношений, имеющих зависимости. Эти свойства, если они
соблюдаются, позволяют избежать многих проблем, возникающих при
создании базы данных, например, проблему избыточности данных.
76

БД должна обеспечивать целостность данных. В процессе обновления
данных целостность может нарушаться. Во избежании таких событий
вводится понятие транзакции  последовательность операций, которые
должны быть или все выполнены, или все не выполнены. Например, если
мы хотим изменить нашу базу данных, чтобы хранить массы планет не в
обратных массах Солнца, а в граммах, мы не должны встретиться с си-
туацией, когда часть записей уже заменена и массы заданы в граммах, а
часть еще имеет массы, заданные в обратных к массе Солнца значениях.
Средства управления транзакциями, разумеется, тоже входят в SQL.
7.9 Программное обеспечение
Несколько слов о программном обеспечении. Прежде всего это, конечно,
операционная система.
В настоящее время, если не принимать во внимание различные мо-
дификации, можно ограничиться знанием только двух систем  это
Windows и UNIX. Да, разумеется, можно вспомнить еще несколько, из
которых я бы выделил Plan9, но две приведенные системы  вне кон-
куренции. У каждой есть свои достоинства и недостатки и нет смысла
противопоставлять их, можно просто сравнить:
Windows Linux
архитектура PC PC, Alpha, Sparc, HP, : : :
приложения клиентские серверные
интерфейс графический командная строка/графический
пользователи все чайники профессионалы разработчики
создатели много Кен Томпсон, Денис Ритчи
Они решают разные задачи и у них разные цели. Windows прежде всего
коммерческая система. (Байка Джона?) С Linux вы уже познакомились,
и знаете, почему выбрана именно эта система. Повторю еще раз.
Самое важное, что UNIX  это открытая система. Вот определение
открытой системы (комитет IEEE POSIX, вспомним стандарт IEEE-754):
Открытая система  это система, реализующая открытые спе-
цификации на интерфейсы, службы и форматы данных, достаточные
для того, чтобы обеспечить:
 возможность переноса (мобильность) прикладных систем, разрабо-
танных должным образом, с минимальными изменениями на ши-
рокий диапазон систем;
 совместную работу (интероперабельность) с другими прикладными
системами на локальных и удаленных платформах;
77

 взаимодействие с пользователями в стиле, облегчающем последним
переход от системы к системе (мобильность пользователей).
Открытые спецификации в данном определении понимается как об-
щедоступная спецификация, которая поддерживается открытым, глас-
ным согласительным процессом, направленным на постоянную адапта-
цию новой технологии, и соответствует стандартам.
Согласно этому определению открытая спецификация не зависит от
конкретной технологии (от конкретных технических или программных
средств или продуктов отдельных производителей). Спецификация оди-
наково доступна любой заинтересованной стороне.
А теперь вспомним, что любой научный результат должен быть
а доступен всему научному сообществу;
б воспроизводим.
Очевидно, что, если все программное обеспечение, в нашем случае астро-
номическое, будет реализовано в рамках концепции открытых систем, то
оно будет и доступно, и переносимо (воспроизводимо).
Unix, работающий практически на всех существующих архитектурах,
является открытой системой. Именно поэтому он так распространен в
научных исследованиях.
Собственно и сама парадигма Интернета зародилась в рамках на-
учного учреждения  в Европейском центре ядерных исследований
(CERN)  сотрудники, участвующие в программе CERN'а, но живущие
в разных концах света, нуждались в инструменте, позволяющем инту-
итивно понятным способом обмениваться данными и информацией по
сети. И протокол HTTP, и схема адресации URL были разработаны Ти-
мом Бернерс-Ли в CERN'е и естественно (для научного сообщества) к
результатам этой работы был предоставлен доступ всему Интернет со-
обществу. В том же CERN'е Андерс Берглунд, отвечающий за органи-
зацию текстовой обработки, ввел в употреблению SGML, принятый в
1986 году в качестве международного стандарта. Не удивительно, что
Тим Бернерс-Ли разработал HTML под большим влиянием и буквы и
духа SGML. (Формально DTD для HTML было разработано лишь через
несколько лет.)
Конечно, если вы пишете небольшую программу (порядка 1000 опе-
раторов), то достаточно использовать языковые средства, имеющие об-
щепринятые стандарты. Например, Фортран или С. Правда, нужно еще
убедиться насколько используемый компилятор придерживается приня-
тых (открытых) стандартов. В UNIX'е практически всегда можно быть
78

уверенным в том, что стандарты доступны и соблюдаются. Это стано-
вится особенно важным, если разрабатывается большой программный
комплекс, над которым одновременно работает несколько человек, да и
находятся они далеко друг от друга. В астрономии проблема стоит еще
более остро. Объем данных наблюдений столь велик (и продолжает рас-
ти), что без стандартов, без неукоснительно следования этим стандартам,
было бы просто невозможно работать с имеющимися данными.
Астрономам всегда требовалось проводить большой объем вычисле-
ний (или обработки данных). Будь то вычисление эфемерид, построение
высокоточных теорий движения планет и спутников, расчет эволюции
звезд или обработка террабайт информации, поступающей с многочис-
ленных космических проектов. Именно поэтому они всегда были самыми
квалифицированными и пользователями, и разработчиками программ-
ного обеспечения. Начиная с Чарльза Беббиджа (середина позапрошло-
го века), создавшего первую, хотя и не электронную, Аналитическую
машину, которая имела многие черты современного компьютера (на-
пример, выполняемая программа). Впервые Беббидж доложил о своей
разностной машине членам Королевского Астрономического общества 
для создания астрономических таблиц требовалось множество вычисле-
ний. Кстати, первым программистом (не из притчи) можно считать Аду
Лавлайс, которая заинтересовавшись проектом Аналитической машины
Беббиджа, разработала первые программы.
В 50-х годах, когда появились первые языки программирования (Фор-
тран, Алгол), был разработан метод описания их синтаксиса, известный
как форма Бэкуса-Наура. Питер Наур известен и как астрометрист.
<цифра> ::= 0|1|2|3|4|5|6|7|8|9
<целое число> ::= <цифра>|<цифра><целое число>
<число со знаком> ::= <число>|+<число>|-<число>
Потребности управления астрономической аппаратурой привели к со-
зданию языка Forth, который позволял писать программы, которые за-
нимали не больше памяти, чем такие же программы, написанные непо-
средственно на машинном языке. Создан этот язык был в Астрономи-
ческом учреждении Чарльзом Муром и стал в 80-е годы чрезвычай-
но популярным. И сейчас широко используется язык описания страниц
PostScript, имеющий много общего с Фортом.
Уже довольно давно (70-е годы ) астрономы осознали необходимость
стандартов для переносимости данных, разработав специальный фор-
мат (FITS). Еще до эры Интернета астрономы использовали удаленные
наблюдения, а в эпоху Интернета самые большие, самые используемые
научные Базы Данных  астрономические. Сюда включаются и данные
79

многочисленных миссий, и электронные публикации, и различные астро-
номические приложения.
Вернемся к программному обеспечению.
Все, перечисленное выше, эффективно работает в открытых систе-
мах, следующих общепринятым стандартам.
Кроме всего прочего, парадигма открытых систем позволяет решать
задачи, используя ортогональные средства, то есть средства, не завися-
щие друг от друга. Не важно, пользуетесь ли вы для вычислений языком
Фортран или Питон (что хуже в смысле эффективности), вы можете лег-
ко визуализировать ваши результаты с помощью любой доступной гра-
фической системы. Альтернативное решение, например, визуализация с
помощью вызовов фортрановских подпрограмм из некоторой библиоте-
ки потребовало бы изменения вашей программы и в случае, если у вас
изменился алгоритм вычислений, и в случае, если вам потребовалось из-
менить, скажем, цвет некоторой кривой.
К программному обеспечению относятся трансляторы (C, Fortran),
интерпретаторы (Perl, Python), командные языки (bash, csh), инстру-
ментальные средства (утилиты, сжатие, архивация и т.д.), прикладные
программы (обработку текстов; проведение вычислений; организация ин-
формации; управление вводом-выводом). Обычно различные функции
настолько тесно переплетаются друг с другом, что трудно сказать, где
кончается одна и начинается другая. Хотя большинство функций в той
или иной степени используется в любой программе, одна из них всегда
преобладает.
Среди прикладных программ, по преобладанию некоторых функций,
выделяют:
 текстовые редакторы (Emacs, VI),
 средства разработки (в том числе отладчики),
 графические редакторы (GIMP),
 средства работы с документами ((La)TeX, OpenOffice),
 электронные таблицы (OpenOffice Calc),
 системы управления базами данных (MySQL, Postgress),
 музыкальные редакторы (MusiXTeX),
 мультимедийные средства,
 интегрированные пакеты прикладных программ.
80