Метод волны: от простого к сложному

В статье рассматривается один из базовых алгоритмов решения задач, связанных с нахождением пути, содержащем минимальное количество ходов. Суть этого алгоритма заключается в следующем. Имеется двумерный массив, в нем задана начальная и конечная клетки, а также в нем есть некоторые препятствия – клетки, ходить по которым нельзя. Из начальной точки запускаем волну: все клетки, в которые можно попасть из начальной за 1 шаг, получают значение равное 1. Затем перебираем все точки, в которые можно попасть за 1 шаг, и соседним с ними клетками присваиваем значение 2. Процесс продолжается до тех пор пока не дойдем до конечной клетки (нашли путь) или пока можем совершить очередной ход, если сходить не удается, то пути из начальной в конечную клетку не существует. Такой алгоритм получил название метода волны или поиска в ширину.

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

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

Для увеличения быстродействия метода волны можно применить некоторое его улучшение – двойной поиск в ширину. Его отличие в том, что запускается сразу 2 волны, одна из начальной клетки, другая из конечной. Серыми клетками обозначены начальная и конечная клетки. Слева (Рис.2а) пример с запусканием одной волны, справа (Рис.2б) – запускаются сразу две волны. Теоретически вторая волна может дать улучшение в 3-4 раза, но практике, как всегда все оказывается «немного» не так.

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

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

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

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

Задача о «блохах». На шахматной доске размером NxM имеется Q блох и имеется кормушка в клетке с координатами (x,y) – Рис.5а (Х-кормушка, Б-блоха). По полю блохи передвигаются ходом шахматного коня. Необходимо определить для каждой блохи, за какое минимальное количество прыжков она сможет добраться до кормушки, или определить, что этого сделать невозможно. (1
Можно брать координаты каждой блохи как начальную клетку, а координаты кормушки - как конечную, и запускать волну Q раз. Но при Q=10000, данный алгоритм не будет проходить по времени. Здесь целесообразно запустить волну из кормушки, если на очередном ходе попадаем в клетку с блохой, то мы нашли длину ее пути до кормушки. Результат виден на Рис.5б: черные клетки – первоначальные места расположения блох, клетка, в которой записан 0, представляет собой кормушку.

Можно также модифицировать метод волны на трехмерное пространство (Рис.6), для этого потребуется трехмерный массив с лабиринтом, и на каждом шаге просматривать не 4 или 8, 6 и 26, соответственно, соседних клеток. Можно модифицировать данный алгоритм для тел произвольной формы. Для этого естественно надо будет изменить логику установления факта встречи с препятствием, и при необходимости предусмотреть возможность поворота объекта для прохождения в узких местах лабиринта.

Метод волны используется также и в алгоритмах на графах – поиск в ширину, для нахождения кратчайших путей между исходной вершиной и конечной (или всеми остальными). Дано: граф (Рис.7а). Необходимо найти путь от первой вершины до девятой, содержащий минимальное количество ребер. На Рис.7б показана очередность просмотра вершин графа.

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

Данный метод также применяется для векторизации изображений. Допустим, у нас имеется растровое изображение (для каждой точки задан определенный цвет), мы хотим преобразовать его в векторную форму (изображение состоит из векторов, т.е. известно положение двух точек, между которыми строится прямая). Для простоты будем полагать, что фон изображения белый, а сам рисунок изображен только черным цветом.
Рис.9.Слева (Рис.9) пример растрового изображения (черным цветом) и построенного векторного (серым цветом). Векторизация заключается в построении графа, т.е. нам необходимо найти в растровом изображении «контрольные точки» (вершины в графе) и соединить их отрезками (ребра в графе). Данный метод основан на том, что мы предполагаем определенную ширину линий, и основываясь на этом пытаемся выделить ее в растровом изображении. Необходимо также учитывать, «линии» в растровом изображении могут пересекаться и соединяться (как показано на рис.9). Для определения этих линий и мест их пересечения и используется метод волны. Запускаем волну из какого-либо места растрового изображения, через 2*N шагов (N – ширина «линии» в пикселях) волна принимает устойчивых характер, на каждом шаге нам необходимо отслеживать «ширину» волны, т.е. количество точек образующих текущую генерацию волны. В местах пересечения «линий» растрового изображения, наша волна будет разделяться на две дочерние волны. Следовательно, перед разделением волны, ее «ширина будет увеличиваться», а затем произойдет разделение волны. Т.о. можно определить точку соединения или пересечения «линий» в растровом изображении. После построения такого каркаса, возможна дальнейшая оптимизация, например, уточнение места положения точек пересечения, удаление лишних точек и т.д., но это не входит в рассмотрение данной статьи. Данный метод может применяться для создания программ распознавания текста, конструкторской документации, САПР.

Применение метода волны для решения задач на графах или задач о лабиринте и близких к ним подробно описаны в работах [1, 2]. Применение волнового алгоритма и его модификации для компьютерных игр рассмотрены в статьях [3].

КОМПЬЮТЕРНАЯ МАТЕМАТИКА

Понятие «компьютерная математика» было введено Д.Куком и Г.Бейзом [1]. Конечно, как и всякий новый термин, вводимый в структуру науки, требуется уточнение этого понятия путем очерчивания сферы, которую он охватывает. Авторы наполняют его различными разделами математики: множества, отношения, функции, основные понятия арифметики, алгебраические структуры, матрицы, автоматы, компьютерная геометрия.
В 2001 году в журнале «Информатика и образование» N 2 была опубликована статья [2], некоторые из предложений которой могут послужить темой для обсуждения. Авторы статьи также используют термин «компьютерная математика». Они даже предлагают ввести вузовскую дисциплину с таким названием, и она по их мнению должна состоять из разделов:
1) основания конструктивной математики, состоящие из элементов семиотики, а также математической логики и теории алгоритмов;
2) конструктивная дискретная математика;
3) численные методы (включая компьютерную алгебру?)
4) компьютерная геометрия.
Первое, что вызывает несогласие – это попытка обособить «компьютерную математику» от общего и единого материнского дерева математики. Второе – вольное обращение с термином «конструктивная математика», который в системе математических наук имеет устоявшийся и определенный смысл, отличный от смысла, придаваемого ему авторами. Третье – в состав предлагаемого курса так или иначе в качестве разделов предлагается ввести большинство предметов существующего учебного цикла. Мы считаем, что принятый сейчас учебный план более полон и содержателен, и кроме того, структурирован по семестрам и по количеству отводящихся на предметы часов.
Осознание глубинной связи информатики и математики привело к тому, что в систему учебных дисциплин, входящих в учебный план подготовки учителя информатики, в 2000 году были включены предметы теоретической информатики и математические предметы, тесно с ними связанные. Принятый в 2000 году государственный образовательный стандарт предусматривает следующие предметы профессиональной подготовки учителя информатики (в порядке изучения по семестрам):
– математическая логика (4-й семестр);
– дискретная математика (4-й семестр);
– элементы абстрактной и компьютерной алгебры (5-й семестр);
– уравнения математической физики (5-й семестр);
– теория алгоритмов 6-й семестр);
– численные методы (6-й, 7-й семестры);
– теоретические основы информатики (6-й семестр);
– исследование операций (8-й семестр);
– компьютерное моделирование;
– основы искусственного интеллекта (10-й семестр).
Перечень теоретических дисциплин говорит о необходимости основательной предварительной и текущей подготовки и корреляции этих дисциплин между собой и теоретической и прикладной математикой. Ранее предпринимаемые попытки готовить специалистов по информатике без серьезных математических и теоретических (по информатике) знаний не принес успеха. Названный подход возможен лишь в отношении информационных технологий (с известными оговорками), к которым, конечно, не сводится информатика. Здесь уместно упомянуть, что в 2002 году при утверждении организационных структур Академии Наук России было выделено отделение математики в составе двух секций: 1) теоретическая математика; 2) прикладная математика и информатика. Это еще раз подтверждает единство математики и теоретической информатики – два ствола одного дерева.
С большим внутренним сопротивлением автор настоящей статьи согласился на условное использование термина «компьютерная математика» только для обозначения совокупности перечисленных предметов учебного плана, с включением в нее основ теоретической математики.
С одной стороны этимологически ясна связь этой группы наук с принятыми в информатике разделами «компьютерная геометрия» и «компьютерная алгебра». С другой – дословный перевод термина «computer science» означает вычислительная наука, что можно, не переводя слово «computer», трактовать, как компьютерная наука. Тогда «компьютерная математика» – это математические разделы вычислительной науки («computer science»), а вместе с этим – информатики (информатика – синоним англоязычного «computer science»). Не вдаваясь в дальнейшее обсуждение удачности или неудачности термина «компьютерная математика», воспользуемся им, и будем этим условным термином называть разделы информатики, которые тесно связаны с математическими науками (теоретическая информатика) и собственно математическими науками, идеи которых постоянно питают и теоретически обосновывают собственно информатику.
Рассматривая любой из перечисленных предметов, в каждом конкретном случае можно указать сферу использования соответствующих знаний либо для решения конкретных задач, либо в качестве обоснования некоторых теоретических положений информатики. Встает вопрос о том, что является самым важным, объединяющим все предметы моментом (кроме всеобщности отношения к информатике). На наш взгляд составители государственного стандарта по информатике впервые последовательно проводят идею универсальности основного методологического принципа информатики: математическое, информационное и компьютерное моделирование изучаемых систем и явлений. Таким образом, выделен инвариант информатики как науки.
Информатика является одной из основополагающих наук естественнонаучного цикла, наряду с философией, математикой и физикой. В этом качестве ее способы исследования различных явлений (систем и т.п.), методы решения задач, возникающих в самых разных сферах интеллектуальной деятельности современного человека, обладают единством подхода – методологией.
Воспроизведем в виде тезисов (в нашем изложении) некоторые мысли академика А.П.Ершова, высказанные им на 6-м Международном конгрессе по математическому образованию в Будапеште в 1988 году, которые полностью могут быть отнесены к предмету обсуждения этой статьи.
1. Резкое расширение математической практики. Повсеместное применение компьютеров, строительство информационной модели мира раздвинули объем и многообразие математической практики в грандиозных масштабах. Построение знаковых систем, схематизация конкретных объектов путем выделения их свойств, атрибутов и отношений, построение моделей, дедукция, редукция и рекурсивное мышление, выделение и поддержание уровней абстракции, прогнозирование поведения, анализ законов, установлений и правил, наконец, конструирование огромного количества алгоритмов и их оценка – все это оружие современного интеллекта, каркас информационной культуры.
2. Изменение номенклатуры математических знаний. Компьютер воспроизводит человеческое поведение. Через программирование и построение информационных моделей в содержательную часть математики входят абстракции человеческой деятельности, свойства искусственных и живых систем. Это же усиливает роль и место дискретной математики. Выявляется роль разделов дискретного анализа параллельных классическому анализу. На первый план выходит изучение связи между дискретным и непрерывным, например, в синергетике и теории катастроф. Появляются новые приемы математической деятельности – доказательные вычисления. Еще один пример неортодоксальных математических доказательств – решение задачи о четырех красках.
3. Системная роль математической теории. Понятие теории родилось в недрах математики. С другой стороны, в информатике имеется важнейшее понятие обстановки. Обстановка – это воплощенная в компьютере замкнутая модель мира, в котором предстоит действовать программируемому исполнителю. Поскольку все исходы должны быть предусмотрены, необходимо иметь полное знание обстановки и сознавать пределы этого знания в реальном мире. Все это знание должно предшествовать конкретному моделированию. Выработка этого знания составляет сущность системного анализа. Системный анализ – новый массовый вид человеческой практики.
4. Вычислительный эксперимент с математической и компьютерной моделью. Его роль в инженерной практике общеизвестна. Следует подчеркнуть, что вычислительный эксперимент все в большей степени становится источником чисто теоретических открытий. Можно отметить практичность этого подхода как нового метода в познавательной деятельности в учебной педагогической практике.
От себя отметим, что построение когнитивных методов дидактики следует начинать с построения той или иной модели обучения.
5. Визуализация абстракций. Визуальное восприятие человека является поистине магическим кристаллом, позволяющим делать открытия. Поиски того, как сделать мысль наглядной, всегда мучили ученых и педагогов. Интеллектуальная графика имеет многовековую историю. За последнее время появилась масса публикаций – образы, порожденные абстрактным знанием, оживленным союзом ученого программиста и компьютера.
Отметим, что академик А.Н. Колмогоров подчеркивал различие между формальной символической системой и содержательным (математическим) знанием. Это отлично чувствует любой математик или информатик, решая творческую задачу. Компьютер, действительно, по строго формализованным правилам выполняет действия над конструктивной информацией (словами некоторого алфавита, или наборами символов). Законы мышления человека не таковы.
6. Динамизация математических объектов. Математика – наука об инвариантах. Познать природу инварианта можно, только осознав диалектику постоянства и изменчивости параметров этого инварианта. Увидеть в логической константе все проявления реальной жизни, описанной законом, – это значит понять закон и научиться его применять. Компьютер со своими средствами визуализации и вычислений позволяет исследователю извлечь из статической упаковки математических отношений всевозможные траектории развития динамического процесса во времени и пространстве, обогащая тем самым его опыт, интуицию и способность к предсказыванию.
7. Становление структуры из хаоса. Среди возможностей, предоставляемых вычислительным экспериментом и средствами визуализации, заслуживают особого упоминания эксперименты по наблюдению становления регулярных структур из исходного беспорядка. В их простейшем проявлении – это разнообразные конструкции, возникающие при итеративном применении некоторых нелинейных операторов к случайным исходным данным или попутным параметрам. Здесь формируется совершенно новый и исключительно мощный канал для распространения знаний на огромный класс природных явлений: движение материков, формирование береговой линии, горные ландшафты, рисунки полярных сияний, формообразование у растений, расцветка животных, развитие конфликтов и возникновение кризисов. Материал, поставляемый синергетикой и математикой нелинейного, позволяет сделать важный общенаучный вывод о принципиальной важности вычислительного эксперимента как познавательного инструмента: если источником всего нового в природе является нелинейность, то умозрительные представления экстраполяционного типа линейны по своей природе и поэтому ограничены в своей познавательной силе, как, например, любой вывод в существующей аксиоматике. Поэтому для добычи поистине нового знания необходим нелинейный синергетический процесс либо в мозгу человека, либо в памяти компьютера.
Отметим, процесс получения новых знаний при обучении также нелинеен. Осознание этого обстоятельства наконец-то начинает проникать в современные теории когнитивной психологии и дидактики.
8. Союз информатики, математики и лингвистики. Можно дать одно ограниченное определение информатики: информатика – это наука о правилах целеустремленной деятельности. Это определение становится просто справедливым, если мы признаем компьютер в соответствии с тезисом Черча и тьюринговым понятием универсальной машины (с оракулом) всеобъемлющей моделью целеустремленной деятельности. Если мы согласимся с этим, то информатика по праву входит в союз с математикой и лингвистикой, закладывая уже в школьное образование опорный треугольник развития главных проявлений человеческого интеллекта: способность к обучению, способность к рассуждению и способность к действию. Дисциплина действия так же нужна, как и дисциплина речи. Понимая, как компьютер решает задачу, он сохраняет это понимание в себе. Наблюдая катастрофы в искусственных мирах, он многократнее и безопаснее для себя вырабатывает опыт сопоставления решений и их последствий.
Направления развития информатики обозначены А.П. Ершовым очень четко и впечатляюще. Каким образом воплотить это в сфере образования, в конкретном вузе?
На наш взгляд «компьютерной математике», как она понимается нами, не хватает детальной проработки логических и функциональных связей между составляющими ее предметами и разделами. Следуя принятой парадигме обучения предметам цикла «компьютерная математика», с неизбежностью приходится (или придется) решать отмеченные проблемы. В связи с этим кафедра прикладной математики и ИМОИ факультета информатики выступила с инициативой по созданию экспериментальной методической площадки «компьютерная математика». Предполагается, что в процессе работы площадки будут выделены ключевые понятия и основные положения каждого из входящих в комплекс предметов, установление логических связей между ними и последовательность освоения соответствующих понятий.
Очень важным представляется выделение понятий, теорем и методов их доказательств в курсе основ теоретической математики. В настоящее время заметно некоторое несогласование разделов и тем основ теоретической математики потребностям предметов теоретической математики. В качестве одного из первых шагов автор предлагает введение на 1-м курсе пропедевтического предмета – введение в математику, в котором бы рассматривались важные понятия математики, нужные в самом начале обучения в университете и не изучаемые в средней школе. К ним стоит отнести: элементы теории множеств, отношения, отображения, элементы математической логики, элементарные логические средства рассуждений и доказательств в математике, необходимые и достаточные условия, метод полной математической индукции, метод доказательства от противного, дедукция, конструктивные доказательства.
Очень важным представляется создание некоего мостика, способного помочь студентам преодолеть известные эмоциональные трудности в освоении абстрактных разделов теоретической математики. В этом плане представляется интересной публикация перевода с английского языка монографии Р.Грэхема, Д.Кнута и О.Паташника «Конкретная математика». В предисловии к монографии Владимир Игоревич Арнольд написал. Созданная Ньютоном и Эйлером, Бернулли и Гауссом, Лейбницем и Дирихле математика оказывается вечно юной и вновь возрождается следующими поколениями математиков. Польза этого труда в том, что в ней рассматриваются конкретные примеры как дискретных, так и непрерывных систем. Противопоставление «конкретной математики» и «абстрактной математики», погоня за обобщениями оказалась столь захватывающей, что целое поколение математиков потеряло способность находить прелести в частностях, в том числе получать удовольствие от решения численных задач или оценить по достоинству роль математических методов. Абстрактная математика стала вырождаться и терять связь с действительностью. Конкретная математика – смесь континуальной и дискретной математики. Исчисление сумм, рекуррентные соотношения, элементарная теория чисел, дискретная теория вероятностей представляют большой интерес с технической стороны.
Вопросы, задачи и упражнения, рассматриваемые в «Конкретной математике», не относятся, строго говоря, к «компьютерной математике». Это разделы классической математики того периода, когда не было четкого разделения теоретической и прикладной математики. Несмотря на то, что и сами задачи, и приемы их решения достаточно серьезны, доведение решения до числа или формулы снимают у читателя чувство недоступности рассматриваемого материала. Можно организовать проведение специального курса на базе материала этой монографии.
В заключение отметим, что ведущие преподаватели факультета информатики достаточно отчетливо представляют себе направление и содержание работы, которую необходимо осуществить в рамках экспериментальной площадки университета «Компьютерная математика». Имеется определенный задел в виде разработанных учебных программ по всем дисциплинам цикла, а также большое количество публикаций, связанных с намеченными работами.

Увеличение скорости сходимости

Большинство задач, решаемых вычислительной математикой, имеют одну из двух форм:
Ax = b (b Î Y) (1)
y = Ab (b Î X) , (2)
где A – некоторый абстрактный оператор, действующий из полного нормированного пространства X в пространство Y ( A: X ® Y).
Задачам первого типа соответствуют (в зависимости от оператора A) уравнения различного рода.
Примеры: 1) Если A – вещественная функция вещественной переменной (A: R ® R), то речь идет о решении обычного уравнения (линейного, квадратичного, нелинейного); 2) если A – дифференциальный оператор, то решается дифференциальное уравнение (обыкновенное или с частными производными); 3) если A – матрица, то решается система линейных алгебраических уравнений.
Задачи второго типа соответствуют задачам, аналогичным вычислению значения функции (значение оператора на элементе из пространства X). Например, если A – определенный интеграл, то речь идет о нахождении значения определенного интеграла от некоторой интегрируемой функции (пространство X– множество интегрируемых на заданном интервале функций).
Основным методом решения задач (1), (2) является дискретизация, то есть замена (аппроксимация) элементов исходных пространств X и Y конечными векторами из эвклидовых пространств En и Em, а оператор A заменяется (аппроксимируется) матрицей Am,n размерности m*n. Таким образом, задачи (1), (2) аппроксимируются задачами (1/) и (2/):
Am,n xn = bm (xn Î En, bm Î Em) (1/)
ym = Am,n bn (ym Î Em, bn Î En) (2/)
Как правило, при аппроксимации задач (1), (2) задачами (1/), (2/) качество аппроксимации (ее точность) характеризуется некоторым числовым параметром h, связанным с n и m. Поэтому можно обозначить Am,n = A(h). Для корректно поставленных задач (и исходных и аппроксимирующих) всегда справедливо утверждение о том, что если при h ® 0 оператор A(h) в некотором смысле сходится к оператору A (по некоторой норме), то и приближенные решения xn и ym сходятся к точным решениям (h ® 0 – эквивалентно n ® ¥ и m ® ¥). Иными словами, при приближенном решении задач (1), (2) мы всегда имеем дело с процессом предельного перехода (точное решение – это предел последовательности решений аппроксимационных задач). Тогда можно говорить о скорости сходимости этого процесса и об его ускорении.
Говорят, что процесс предельного перехода имеет скорость сходимости a, если можно установить справедливость неравенства
ôx* – xnô = C∙ha + O(ha+1) или ôy* – ymô = C∙ha + O(ha+1) ,
где x*, y* – решения соответствующих точных задач, xn, ym – решения аппроксимационных задач, C – константа (не зависит от h), ô∙ô – норма в соответствующем пространстве, a > 0, h < 1.
В нашем контексте под ускорением сходимости будем понимать нахождение линейных комбинаций
(h) = a1x(h1) + a2x(h2) + … + apx(hp),
(h) = a1y(h1) + a2y(h2) + … + apy (hp),
причем hi £ h < 1 при i = 1, …p. Пусть каждое приближенное решение x(hi) и y(hi) имеют скорость сходимости a, то есть
ôx* – x(hi)ô= C∙hia + O(hia+1), ôy* – y(hi)ô= C∙hia + O(hia+1).
Если построенные решения будет удовлетворять равенствам
ôx* – (h)ô = C1∙hb + O(hb+1), ôy* – (h)ô= C∙hb + O(hb+1) при b > a,
то это решение дает лучшую скорость сходимости по сравнению с решениями x(hi), из которых оно составлено (произошло улучшение сходимости).
Рассмотрим три примера ускорения сходимости в различных методах приближенных вычислений.
1. Метод Эйлера численного решения задачи Коши для обыкновенного дифференциального уравнения первого порядка.
Пусть требуется найти решение задачи Коши
x/ (t) = f(t, x), t Î [0; T], при x(0) = g. (3)
Метод Эйлера заключается в следующем. Отрезок [0; T] разбивается равноотстоящими точками (узлами) tk = k∙h, k = 0, 1, …, n, h = T/n. Это –дискретизация промежутка [0; T], на котором ищется решение, – этот отрезок заменили дискретным множеством точек {tk}. Затем в каждой узловой точке производная x/(tk) заменяется (аппроксимируется) разностным отношением
x/(tk) » .
Тогда исходная задача (3) аппроксимируется дискретной задачей
xk+1 = xk + h∙f(tk, xk), x0 = g, при k = 0, 1, …, n–1. (3/)
Алгоритмически получилась очень простая схема: по известному значению x0 = g вычисляется x1 и т.д. Схема нахождения приближенного решения задачи Коши в узловых точках относится к рекуррентным формулам. В (3/) мы воспользовались обозначением xk » x*(tk) (xk – приближенное решение, x*(tk) – точное решение в узловой точке).
В качестве пространства X в задаче (3) можно взять пространство непрерывно дифференцируемых на [0; T] функций, Y – множество непрерывных на [0; T] функций, A – дифференциальный оператор (Ax ≡ x/(t)). В качестве нормы и в пространстве X, и в пространстве Y возьмем
ôxô = maxïx(t)ï, при t Î [0; T].
Пространство Xn – множество векторов x = (x0, x1, …, xn), а пространство Ym – множество векторов y = (y0, y1, …, yn–1). В качестве нормы в этих пространствах возьмем первую норму вектора, согласованную с нормами в пространствах X и Y: ôxôI = maxïxkï, по всем k = 1, …, n. Вид дискретного оператора Am,n определяется тождеством Am,n x ≡ , при k = 0, 1, …, n–1.
Выясним, какова погрешность метода Эйлера на одном шаге. Будем считать, что на k-м шаге известно точное решение, то есть xk = x*(tk). Тогда абсолютная погрешность e(tk+1) на k + 1 шаге определяется разностью
e(tk+1) = x*(tk+1) – xk+1.
В предположении существования у точного решения x*(t) непрерывной производной третьего порядка можно x*(tk+1) представить в виде отрезка ряда Тейлора с остаточным членом
x*(tk+1) = xk + h∙x*/(tk) + ∙ + ∙ , q Î [tk; tk+1].
Отсюда x*(tk+1) = xk + h∙f(tk, xk) + ∙ + ∙ =
= xk+1 + ∙ + ∙ .
Обозначим ï ï = C. Тогда имеем
ïe(tk+1)ï = ïx*(tk+1) – xk+1ï = С∙h2 + O(h3).
Показали, что скорость сходимости метода Эйлера на одном шаге имеет порядок 2 (a = 2).
Выберем h1=h/2, h2 = h. Опираясь на значение в точке tk = k∙h, найдем три приближенных решения:
xk+1 = xk + h∙f(tk, xk),
= xk + ∙f(tk, xk), = + ∙f(tk + , ).
Таким образом, в точке tk+1 имеем два приближенных решения: первое – вычислено при шаге разбиения h, второе – . По доказанному ранее свойству имеем
x*(tk+1) = xk+1 + C∙h2 + O(h3). (4)
Для имеем
x*(tk + ) = + x//(h1) = + x//(tk) + O(h3),
В точке tk+1 имеем
x*(tk + h) = + x//(h1) + f(tk + , ) + x//(h2) =
= + x//(h1)+ x//(h2) – × x//(h1)=
= + x//(h)– × x//(h1)= + x//(tk) + O(h3),
то есть
x*(tk + h) = + x//(tk) + O(h3), или
x*(tk+1) = + 2C∙( )2 + O(h3). (5)
Умножим равенство (4) на a1, а (5) – на a2 и сложим получающиеся равенства
a1×x*(tk+1) + a2 ×x*(tk+1) = a1×xk+1 + a2× + (a1×h2 + a2× )×С + O(h3).
Пренебрегая слагаемыми порядка h3, выбирая a1 и a2 так, чтобы выполнялись два равенства
a1 + a2 = 1,
a1 + = 0 ,
получаем a1 = –1, a2 =2. С помощью линейной комбинации –xk+1 + 2∙ , получаем новое решение, скорость сходимости которого на единицу лучше, чем у решений полученных при значениях шага h и . Конкретнее, имеем
x*(tk+1) – [–xk+1 + 2∙ ] = O(h3).
Итак, вдвое увеличивая количество вычислений, улучшаем точность (повышаем скорость сходимости) на порядок. Увеличение точности на порядок без приема ускорения скорости сходимости потребовало бы увеличение количества вычислений приблизительно в 1/h раз.
В предположении большей гладкости решения x*(t) (а, значит, и функции f(t, x)) аналогичным образом можно повысить скорость сходимости еще на единицу и т.д.
Пример. Рассмотрим задачу Коши для обыкновенного дифференциального уравнения
x/ (t)= –x2 + t× x + ; x(0) = 1. (6)

T
0.1
0.05
x**
0.025
0.0125
x**
x*(t)
0.1
0.95491
0.95710
0.95931
0.95836
0.95877
0.95918
0.95917
0.2
0.92704
0.93059
0.93414
0.93263
0.93329
0.93395
0.93395
0.3
0.91265
0.91704
0.92144
0.91958
0.92041
0.92124
0.92123
0.4
0.90924
0.91417
0.91911
0.91703
0.91797
0.91891
0.91890
0.5
0.91508
0.92036
0.92566
0.92345
0.92446
0.92547
0.92546
0.6
0.92900
0.93452
0.94004
0.93775
0.93881
0.93987
0.93986
0.7
0.95017
0.95585
0.96154
0.95918
0.96028
0.96138
0.96137
0.8
0.97801
0.98381
0.98962
0.98722
0.98835
0.98947
0.98946
0.9
1.01213
1.01803
1.02392
1.02149
1.02264
1.02378
1.02377
1.0
1.05225
1.05822
1.06419
1.06173
1.06289
1.06405
1.06405
В таблице приведены результаты решения задачи (6) методом Эйлера при различных значениях шага интегрирования h = 0.1; 0.05; 0.025; 0.0125, причем решения распечатаны не все, а только в узлах кратных 0.1. Через x** обозначено решение, полученное методом ускорения сходимости. В четвертом столбце это решение было получено линейной комбинацией решений в методе Эйлера для h = 0.1 и h = 0.05, а в седьмом – h = 0.025 и h = 0.0125. В последнем столбце приведены точные решения. Выводы может сделать сам читатель.
2. Приближенное вычисление определенного интеграла.
Пусть стоит задача вычисления определенного интеграла
y = .
В качестве метода выберем квадратурную формулу трапеций (составную).
y(h) = yn = , (7)
где xk = k×h, k = 0, 1, …, n, h = .
Найдем представление остаточного члена квадратурной формулы трапеций на отрезке [xk; xk+1], то есть
R1(f; xk) = – ×[f(xk) + f(xk+1)].
В предположении существования третьей производной у подинтегральной функции f(x), разлагая ее в ряд Тейлора с остаточным членом в точке xk, используя обобщенную теорему о среднем значении интеграла, можно получить следующее представление:
R1(f; xk) = – ∙f //(xk) + ∙[f ///(hk) – f ///(xk)],
где hk, xk Î [xk; xk+1]. Отсюда ясно, что скорость сходимости формулы трапеций на отрезке [xk; xk+1] имеет порядок О(h3).
Составная формула трапеций (7) получается, как сумма простых формул трапеций при интегрировании на частичных отрезках [xk; xk+1], поэтому остаточный член интегрирования по составной формуле трапеций является суммой остаточных членов на [xk; xk+1], то есть
Rтр(f, h) = –yn = = – f //(xk) + [f ///(hk) – 2 f ///(xk)].
Уменьшая шаг в два раза, то есть h1 = , получим новую составную формулу трапеций с остаточным членом
Rтр(f, h1) = –y(h1) = – f( ) – f( ) +
+ [f ///( ) – 2 f ///( )].
В последнем представлении = k∙ , при k = 0, 1, …, N, N = 2n. Таким образом, первые суммы (без коэффициентов) в представлениях Rтр(f, h) и Rтр(f, h1) совпадают. Обозначим эту сумму через М. Вторую сумму заменим на следующую
f( ) = f(xk) + f /(γk) = M + f /(γk),
где γk Î [xk; xk+1].
Легко заметить, что
n∙ min f(x) ≤ f(xk) ≤ n∙ max f(x),
поэтому существует такая точка η Î [0; 1] , что f(xk)= n∙f (η)= ∙ f (η). Рассуждая аналогично, можно получить
[f ///(hk) – 2 f ///(xk)] = [f ///(α) – 2f ///(β)],
[f ///( ) – 2 f ///( )] = [f ///(α1) – 2f ///(β1)],
f /(γk) = f /(γ),
где α, β, α1, β1, γ – некоторые числа из [ 0; 1 ]. Тогда можно записать
Rтр(f, h) = – ∙ f (η ) + O(h3), Rтр(f, h1) = – ∙ f (η ) + O(h3).
Итак, имеем = y(h) – ∙ f (η ) + O(h3),
= y( ) – ∙ f (η ) + O(h3).
Умножая первое равенство на C1, а второе – на С2 и складывая полученные равенства, приходим к соотношению
(С1 + С2)∙ = С1 ∙y(h) + C2 ∙y( ) – ∙[C1 + C2]∙ f (η ) + O(h3).
Полагая C1 = – , а C2 = , приходим к равенству
= – ∙ y(h) + ∙ y( ) + O( h3).
Получили новую формулу численного интегрирования, которая на порядок точнее двух исходных
» – ∙ y(h) + ∙ y( ). (8)
Таким образом, рассмотренный прием улучшения сходимости квадратурной формулы трапеций можно рассматривать как один из способов получения новых неинтерполяционных квадратурных формул большей точности.
Пример. Вычислить интеграл
I = .
Решения сведены в таблицу
n=20
n=40
n=80
20 – 40
40 – 80
I (точное)
0.6353102
0.6362925
0.6365380
0.6366199
0.6366198
0.6366198
В трех первых столбцах приведены приближенные значения интеграла I, полученные по составной формуле трапеций при различных значениях n, в четвертом и пятом – по формуле (8), в последнем – точное значение интеграла I.
3. Предельный переход и машинная арифметика.
В качестве модельной задачи рассмотрим задачу нахождения точных знаков числа e, опираясь непосредственно на определение числа e как предела
(1 + )n e.
Построим последовательность чисел {en} таких, что
en = (1 + )n . (9)
Алгоритмически процесс построения этой последовательности прост. Если бы вычисления по формуле (9) осуществлялись точно (без округлений), то в соответствии с определением предела, построив достаточно длинную последовательность {en}, можно было бы получить сколь угодно точное представление числа e (с любым, заданным, количеством верных знаков). Однако, рассматривая фактически построенную (вычисленную на компьютере) последовательность {en}, замечаем, что характер изменения членов последовательности не совпадает с теоретически ожидаемым изменением. При увеличении n до некоторого достаточно большого N действительно происходит стабилизация верных знаков, то есть последовательность ведет себя в соответствии с теорией. Дальнейшее увеличение n не добавляет верных знаков. Наконец, наступает момент, когда верные знаки начинают замещаться сомнительными знаками, вплоть до полного искажения результата (ни одного верного знака). Эта ситуация характерна при осуществлении предельного перехода при реализации его на вычислительных устройствах.
Рассмотрим структуру абсолютной погрешности a = e – en. Она состоит из двух слагаемых, первое из которых определяется заменой предела последовательности e некоторым ее членом en, а второе – погрешностью округления и количеством цифр в представлении чисел данного вычислительного устройства (разрядностью чисел).
Рассмотрим функцию f(n) = (1 + )n. Вводя новую переменную x = и доопределяя ее по непрерывности в точке x = 0, получаем хорошо изученную функцию y = f(x), которая непрерывна в точке x = 0 вместе со всеми производными. Легко вычислить, что f /(0) = . Таким образом, первое слагаемое в представлении абсолютной погрешности может быть записано в виде ×x ( × ). Учитывая, что мантиссы числа типа real в Pascal записываются в пяти байтах, причем приближенно (с округлением), погрешность числа равна 2–39, погрешность числа (1 + )n равна 2–38. Тогда вычислительная погрешность степени (1+ )n будет равна n×(1 + )n–1×2–38 » n×e×2–38. При больших значениях n эта погрешность будет влиять не только на знаки, в которых осуществляется округление, но и на информативные знаки. Так, например, при n » 238 величина погрешности будет около e (2,7…), так что у соответствующего значения en все знаки сомнительные. В связи с этим возникает проблема, каким выбирать значение n и как видоизменить вычислительный процесс, чтобы получить максимальное количество верных знаков, (например, 11– стандартная выдача числа типа real на Pascal). Ясно, что при очень большом n вычислительная погрешность не позволит найти даже меньше, чем одиннадцать верных знаков. С другой стороны, при небольших значениях n в принципе невозможно получить много верных знаков.
В создавшейся ситуации выходом из положения является применение приема ускорения сходимости. Вычислим при сравнительно небольших значениях n несколько (n = n1, n2,, …, np) чисел en. Затем с помощью линейной комбинации этих значений найдем более точное приближение. При этом, если коэффициенты линейной комбинации выбраны так, что точность ее выше точности каждого из составляющих, то получим большее количество верных знаков. Выбор небольших значений чисел n сделают вычислительную погрешность сравнительно малой.
Найдем коэффициенты упомянутых линейных комбинаций, установим точность, с которой линейная комбинация приближает число e, и проведем численный эксперимент.
Ранее введенная функция f(x) может быть разложена в ряд Тейлора в точке x = 0 с остаточным членом
f(x) = f(0) + f /(0)×x + + …+ + .
Возвращаясь к переменной n, учитывая, что f(0) = e, а f( )= en, перепишем это равенство в следующем виде
e =en – f /(0)× – … – ∙ – ∙ .
Составим линейную комбинацию E = C1×E1 + C2×E2 + … + Cp×Ep , выбрав в качестве Ci решения системы уравнений
C1 + C2 + … + Cp = 1,
C1× h1 + C2×h2 + … + Cp×hp = 0,
........................................................,
C1× h1p + C2×h2p + … + Cp×hp p = 0,
где через Ei обозначены en при соответствующих значениях ni, а hi = , при
i = 1, …, p. Написанная система линейных уравнений разрешима единственным образом, так как ее определитель – это транспонированный определитель Вандермонда. Удобнее всего величины hi выбрать равными при некотором фиксированном h. Приведем системы линейных алгебраических уравнений для определения коэффициентов Ci и их решения при различных значениях параметра p.
1. p = 1: C1 = 1. Точность – порядка O(h) = O( ).
2. p = 2: C1 + C2 = 1, C1 = –1 , C2 = 2.
C1 + C2 = 0.
3. p=3: C1 + C2 + C3 = 1, C1 = , C2 = –2, C3 = .
C1 + C2 + C3 =0,
C1 + C2 + C3 = 0.
4. p = 4: C1 + C2 + C3 + C4 = 1, C1 = – 0,0476190476,
C1 + C2 + C3 + C4 = 0, C2 = 0,6666666667,
C1 + C2 + C3 + C4 = 0, C3 = – 0,2666666667
C1 + C2 + C3 + C4 = 0. C4 = 3,0476190476.
5. p = 5: C1 + C2 + C3 + C4 + C5 = 1,
C1 + C2 + C3 + C4 + C5 = 0,
C1 + C2 + C3 + C4 + C5 = 0,
C1 + C2 + C3 + C4 + C5 = 0,
C1 + C2 + C3 + C4 + C5 = 0,
С1 = 0,00317460316, С2 = – 0,09523809522,
С3 = 0,88888888889, С4 = – 3,0476190476.
Находить линейные комбинации для p>5 нет смысла, потому что при решении систем линейных алгебраических уравнений высокого порядка с коэффициентами отмеченного характера, например, методом Гаусса вычислительная погрешность чисел Ci становится больше чем 10–10 и улучшения результата не происходит.
Ниже приведена таблица с результатами численного эксперимента.
n
P = 1
p = 2
p = 3
p = 4
p = 5
16
2,6379284974
2,7160517614
2,7182491138
2,7182815824
2,712818276
32
2,6769901294
2,7176997757
2,7182775238
2,7182818123
2,7182818283
64
2,6973449526
2,7181330868
2,7182812763
2,7182818273
2,7182818284
128
2,7077390197
2,7182442289
2,7182817584
2,7182818283
2,7182818284
256
2,7129916243
2,7182723761
2,7182818196
2,7182818284

512
2,7156320002
2,7182794587
2,7182818273


1024
2,7169557294
2,7182812351
2,7182818285

2048
2,7176184823
2,7182816801

4096
2,7179500813
2,7182817911

8192
2,7181159362

Автор не может не удержаться от комментариев по поводу поведения чисел, приведенных в этой таблице. Во-первых, числа en в первом столбце, начиная с n=32 и оканчивая n=512, уже содержат всю информацию, которая необходима для решения поставленной задачи (нахождение числа e с точностью одиннадцать верных знаков). При этом каждое из них дает приближение к числу e лишь с точностью два верных знака. Во-вторых, используя прием ускорения сходимости с помощью линейной комбинации пяти en при n = 32, 64, 128, 256, 512, мы производим лишь 992 операции возведения в степень, тогда как нахождение приближенного значения числа e без ускорения сходимости дает максимально возможную точность девять верных знаков только на предельных значениях целых чисел типа longint (количество операций возведения в степень – 231).

Аспектно-ориентированное программирование

В статье рассматривается новая парадигма программирования – аспектно-ориентированное программирование. Данная парадигма возникла сравнительно недавно и пока только определены её основные рамки. Читатель может ознакомиться с основными понятиями и получить представление об АОП, как о технике программирования. Выяснить в чём заключается различие между объектно-ориентированным программированием и аспектно-ориентированным программированием, какая из техник является более эффективной.

В процессе эволюции человечество постоянно пытается решить проблему «Как организовать максимальный выход продукта при минимальных затратах?». Причём эту проблему человек пытается решить во всех областях своей деятельности, будь то производство хлебобулочных изделий или же разработка очередного спутника NASA. То же самое можно сказать и о программировании.
Всю эволюцию программирования можно представить, как процесс, направленный на снижение программного кода и увеличение эффективности его использования. В эпоху зарождения программирования программы представляли собой набор машинных команд. Основное занятие программистов заключалось в составлении машинных инструкций. Но компьютерная индустрия развивается динамично, растут задачи и требования. Как результат появились языки программирования более высокого уровня, позволяющие отойти от машинного кода, абстрагироваться и более визуально решать поставленные проблемы. Появились структурированные языки, здесь уже пришлось думать о том, как разбить большое задание, разработку общего поведения и интерфейса для взаимосвязанных концепций и изменение обычного поведения более специализированных компонентов без обращения к реализации базовой концепции. Таким образом, на данном этапе появилась возможность избежать множества ошибок, сопутствующих структурному и модульному программированию, внести большую ясность при разработке программного обеспечения. Как вполне естественный результат развития и совершенствования техники ООП возникло компонентное программирование, позволившее более эффективную организацию данных.
Так наблюдая за развитием программирования можно сделать следующие выводы: чем дальше идет эволюция программирования, тем большему обобщению подвергаются его составляющие. Сначала организовали набор машинных инструкций в единые блоки, далее эти блоки совместили в одном модуле. Всё, очевидно, чем дальше идет развитие, тем больше уровень комплексности и абстракции, тем все более становится скрытным базовая реализация тех компонентов программирования, с которыми мы работаем.
Как мы уже говорили, сложность программного обеспечения и методологий программирования постоянно возрастает, также постоянно предпринимаются попытки разорвать этот замкнутый круг. Xerox PARC, IBM и Microsoft готовят для индустрии ПО новую парадигму программирования. Она называется аспектно-ориентированное программирование (АОП, aspect-oriented programming) и призвана прийти на смену объектно-ориентированному (ООП, object-oriented programming) и компонентному (component-based programming) программированию. Основными идеологами нового программирования являются Грегор Кишалес (Xerox PARC) и Чарльз Саймони, бывший ведущий архитектор Microsoft.
Аспектно-ориентированное программирование (АОП) (aspect-oriented programming, AOP) — парадигма, изобретенная в Xerox PARC в 90-х гг. и позволяющая разработчику четко разделять задачи, которые не следует запутывать в клубок, например математические операции и обработку исключений. АОП имеет ряд преимуществ. Во-первых, он повышает производительность, так как операции выполняются быстрее. Во-вторых, программисты тратят меньше времени на переписывание одного и того же кода. В целом, АОП обеспечивает более качественную инкапсуляцию различных процедур и облегчает взаимодействие с кодом, написанным на других языках программирования.
Состояние развития АОП похоже на состояние ООП 20 лет назад, данная методика находится на стадии исследований, ещё только определены её рамки и основные понятия. Парадигма аспектно-ориентированного программирования (АОП, aspect-oriented programming) призвана прийти на смену объектно-ориентированному (ООП, object-oriented programming) и компонентному (component-based programming) программированию. По оценкам специалистов, около 70% времени в проектах тратится на сопровождение и внесение изменений в готовый программный код. Вот почему столь важной в ближайшей перспективе становится роль АОП и подобных трансформационных подходов.
Направление развития программирования очевидно. Никому не хочется тратить время и усилия на изменение готовых разработок. Также остро стоят проблемы «повторного использования кода» и «пересекающегося кода» (code crosscutting). Проблема пересекающегося кода состоит в том, что при реализации решения задачи встречается программный код, по сути выполняющий одну и туже функцию в разных частях программы. Что выражается в: плохой трассировке, низкой продуктивности, плохом качестве программного кода, более трудной модификации и низкой эффективности повторного использования кода Проблема повторного использования кода начала решаться с появления программирования, но нашла своё решение при появлении ООП. До этого этапа можно отметить значительный вклад в решение этой задачи модульного программирования, но здесь можно было использовать модули, если между разработчиками программ были оговорены правила их использования и применения. С появлением объектно-ориентированного программирования стало возможным организовать относительно слабосвязанную систему, компоненты которой менее зависят друг от друга, как это было ранее, кроме того, разработанные объекты стало возможным применять в программе, не задумываясь о том, кто их написал. Такое положение сейчас уже вполне естественно, каждый человек, хоть немного знакомый с программированием, сейчас без проблем может написать объектно-ориентированную программу (используя, например, язык программирования Delphi), не задумываясь о том, что за компонентом, который он выбрал, стоит не одна сотня строк программного кода. Как мы уже говорили, всё очевидно. Никто не желает выполнять лишнюю работу, под словами «лень-двигатель прогресса» проходит вся эволюция человека, это касается всех сфер его деятельности, в том числе и программирования.

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

Такие языки программирования как, например, C++, VB, Delphi и т.п. ориентированы, прежде всего, на решение первой задачи. Код компонента представляется в виде класса, то есть он хорошо локализован и, следовательно, его легко просматривать, изучать, модифицировать, повторно использовать. С другой стороны, при программировании процессов, в которые вовлечены различные объекты, мы получаем код, в котором элементы, связанные с поддержкой такого процесса, распределены по коду всей системы. Эти элементы встречаются в коде множества классов, их совокупность в целом не локализована в обозримом сегменте кода. В результате мы сталкиваемся с проблемой «запутанного» и «пересекающегося» кода (code tangling и code crosscutting).
АОП создает систему, используя слабосвязанные модульные разработки пересекающихся моделей. Модульная часть в аспектно-ориентированном программировании называется аспектом, тогда как общая модель в ООП носит название - класс.
Аспект (ключевое понятие новой парадигмы) представляет собой языковую концепцию, схожую с классом, но только более высокого уровня абстракции. Аспекты могут затрагивать многие классы и используют так называемые точки вставки (insertion points) для реализации регулярных действий (например, связанных с безопасностью, обработкой ошибок и т. п.), которые обычно «размазаны» по всему тексту программы. АОП отличается от ООП, тем, как адресуются пересекающиеся модели. В АОП реализация каждой модели не подозревает о существовании другой, пересекающей ее структуру. Вспомним, что при использовании техники ООП создаётся система из объектов, связь между которыми осуществляется через действия.
Технология АОП позволяет выделить многократно повторяющийся код в простые блоки, называющиеся аспектами. Аспекты инкапсулируют множество классов в один модуль, к которому можно осуществлять обращение из любого места программного кода. Требования аспектного программирования заключаются в том, что при разработке аспект рассматривают как модель, пересекающую структуру другой модели.
В АОП каждый аспект может быть выражен в единичной форме, и далее они автоматически комбинируются в исполняемый код с помощью так называемого сборщика (aspect weaver). В результате каждый аспект представляет реализацию некоторого числа модулей или объектов, увеличивая возможности повторного использования кода. По сравнению с традиционным подходом после этапа кодирования компонентов и аспектов на соответствующих языках выполняется автоматическое построение оптимизированного для выполнения (но не для просмотра и модификации) кода. Сборщик аспектов может автоматически вставить точку входа для любого набора операций, что позволяет разделить пересекающийся код на уровне исходного кода.

Таким образом, АОП позволяет снизить объём кода программы и увеличить эффективность повторного использования кода.
В рамках АОП утверждается, что никакая технология проектирования не поможет решить данную проблему, если оставаться в рамках языка, ориентированного только на разработку компонентов. Для программирования сервисов, обеспечивающих взаимодействие объектов, нужны специальные средства, возможно специальные языки.
Понятие аспект можно определить так: «некоторая модель является аспектом другой модели, если она пересекает (crosscuts) ее структуру». Иными словами понятие аспекта относительно. Если, например, в качестве модели некоторой системы мы рассматриваем совокупность компонентов, представляющих такие сущности как вкладчик, счет, банк, то аспектами являются сервисы, обеспечивающие синхронизацию доступа к счету, распределенные транзакции, безопасность. То есть автоматически выполняемые сервисы, обеспечивающие слаженную, надежную, безопасную работу компонентов.

Преимущества АОП

Как мы уже говорили АОП помогает решить проблемы, касающиеся запутанного кода (code tangling) и разбросанного кода (code scattering). Специфичные преимущества АОП таковы:
Модульная реализация пересекающихся моделей: АОП адресует каждую модель отдельно, с минимальной связностью, что отражается в модульной реализации, даже если присутствует перекрещивание моделей. Такая реализация снижает дублирование кода. Так как каждая проблема реализуется отдельно, это позволяет снизить размер кода. В дальнейшем модульная реализация приводит к более легкому пониманию и сопровождению системы.
Системы легки для развития: Так как аспектные модули могут не знать о пересечении проблем, то легко можно добавить функциональность путем создания нового аспекта. В дальнейшем, при добавлении нового аспекта в систему, существующие аспекты пересекают его структуру, помогая создавать гармоничную эволюцию.
Более поздняя связь с проектным решением: Вспомним проблему разработчиков решить проблему, придерживаясь ее рамок, или расширить ее границы. С АОП разработчики могут задержаться с разработкой проекта для будущих требований, так как они могут быть реализованы в будущем как отдельные классы.
Более широкие возможности повторного использования: Так как АОП решение - это аспекты, как отдельные модули, каждый отдельный модуль слабо связан с остальными. Например, вы можете использовать модуль взаимодействия с базой данных в отдельном аспекте регистрационного механизма с различными требованиями регистрации. В общем, слабосвязанные реализации являются ключом к широкому повторному использования кода. АОП представляет более слабосвязанные решения, чем ООП.

Нужно ли нам АОП? Устраняет ли АОП проектировочные недостатки? В АОП каждая реализация модели означает тот факт, что она пересекает структуру другой модели, которая может не подозревать о ее существовании. Такая «забывчивость» и отличает АОП от технологий ООП. В АОП поток формируется из пересекающихся моделей в главную модель, в то время, как в ООП поток работает в противоположном направлении. Заметим, тем не менее, что АОП и ООП неплохо уживаются рядом. Например, можно представить смешанный класс, как модель, используя как АОП, так и ООП, только на уровне АОП это будет более удобно. В любом случае, реализация пересекающейся модели смешанного класса не нуждается в том, чтобы знать, каким образом она была реализована. Например, в одном случае вы можете использовать интерфейс регистратора событий, как смешанный класс, в другом как аспект. Мы только можем говорить об эволюции ООП в АОП.
Пока АОП в качестве АОП еще только новая идея, элементы которой используются в уже существующих технологиях.
АОП можно поддерживать в рамках уже существующих языков. Так, в частности, исследовательский центр Xerox PARC разработал систему AspectJ (www.aspectj.org), поддерживающую АОП в рамках языка Java. В ноябре 2002 г. вышел новый релиз AspectJ 1.1. Этот пакет встраивается в такие системы разработки, как Eclipse, Sun ONE Studio (http://forte.sun.com/ffj/articles/aspectJ.html) и Borland JBuilder. Другой исследовательский центр — IBM Research — выпустил альфа-версию HyperJ (http://www.alphaworks.ibm.com/tech/hyperj) и готовит к марту 2003 г. выпуск системы Cosmos (http://www.research.ibm.com/AEM/mdsoc.html) с гипертекстовой поддержкой требований и диаграмм. Cosmos является развитием MDSOC, которая, в свою очередь, опирается на идеи субъектно-ориентированного программирования (http://www.research.ibm.com/sop/). Помимо Java новая идеология поддерживается и в других языках, таких как Си, Си++, Squeak/Smalltalk, Perl, Python, Ruby (http://aosd.net/tools.html). Пока интерес к новой парадигме проявляют несколько сот экспертов из General Electric, Hewlett-Packard, Siemens, Motorola, Oracle и Sony. Очевидно, что их число будет расти.
 
1-1 можно быстро Скачать WoW аддоны бесплатно для всех классов очень классно! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40