Лекция 2. АЛГОРИТМИЗАЦИЯ

С О Д Е Р Ж А Н И Е
Введение  Общий положения
1. Алгоритмизация аналитическими уравнениями.
2. Алгоритмизация на основе векторной алгебры.
3. Геометрические приложения векторной алгебры.
3.1. Вычисление середины отрезка р1-р2.
3.2. Задание прямой в зависимости от безразмерного параметра s.
3.3. Уравнение прямой, проходящей через точку p0 (x0, y0, z0),  в направлении вектора p2.
3.4. Уравнение прямой, проходящей через точку p0 (x0, y0, z0),  в направлении единичного вектора.
3.5. Уравнение плоскости, проходящей через три точки p1, p2, p3.
3.6. Уравнение косой плоскости, проходящей через четыре точки p1, p2, p3, р4.
3.7. Модуль (длина) вектора, отрезка.
4. Алгоритмизация как геометрическое место точек.
4.1. Прямая, все точки которой р на одинаковом расстоянии от двух заданных: |p-p1|=|p-p2|.
4.2. Окружность, все точки р которой равноудаленны от р1: s=|p-p1|.
4.3. Эллипс: s1+s2=c  или |p1-p|+|p2-p| =c
4.4. Парабола: s1=s2 или |p1-p|=|p2-p|   (x2=c)
4.5. Гипербола: s2-s1=c  или |p1-p|-|p2-p| =c
4.6. Окружность (дуга), проходящей через две точки и заданный радиус: |p1-p|=|p2-p| = с (компромисс).
4.7. Окружность (дуга), проходящей через три  точки: |p1-p|=|p2-p| = |p3-p| (компромисс).
5. Алгоритмизация, удовлетворяющая условию максимума/минимума.
6. Алгоритмизация на основе случайных чисел.
7. Алгоритмизация с помощью макрокоманд.
Пример 1. Вычисление середины отрезка р1-р2
Пример 2. Вычисление множества точек на прямой p1-р2.
Пример 3. Движение точки р1 в направлении  р2 в зависимости от расстояния от р1.
Пример 4. Вычисления точек на прямой по методу случайных чисел.


 
Введение. Общий положения

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

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

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

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

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

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

Вот некоторые общие понятия для работы с алгоритмами.

1) Метод может применяться как алгоритм только, тогда, когда он полностью схематизирован. Это означает, что должно быть однозначно установлено, какой следующий шаг должен быть сделан.
2) Алгоритм должен строиться преимущественно рекурсивно. Рекурсивный алгоритм состоит из относительно небольших составных частей, которые неоднократно реализуются для различных наборов значений.
3) Вычислительный алгоритм должен быть конечным, т.е. приводить к результату за конечное число шагов и т.д.
Набор средств и понятий, позволяющий строить не один алгоритм, а множество алгоритмов, решающих различные задачи, называют алгоритмической системой (АС).

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

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

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

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

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

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

Алгоритм и МК подразумевают:
- задание входных данных,
- исполнение,
- получение результата в виде выходных данных.

Так для вычисления точки p на отрезке прямой р1-р2 по формуле:

p=(1.-s)*p1+s*p2                                   (1)

при     0 < s < 1

входными данными будут точки р1 и р2 начала и конца отрезка и какое-то значение s в диапазоне от 0 до 1; выходными - точка р, получаемая в результате исполнения (1).


1. Алгоритмизация аналитическими уравнениями.

Аналитические, тригонометрические уравнений уже сами по себе являются удобными алгоритмами для применения их в вычислительной геометрии. Особенно удобными являются явные уравнения и параметрические. Приведем несколько из них.
Уравнение прямой проходящей через начало координат
y=ax                        (1)
В уравнении (1), переменная x - считается независимой переменной, а y - зависимой переменной, a -угловой коээфициент изменяющийся от нуля до двух пи.

Уравнение прямой вида: y=ax+b описывает прямую, отсекающую по оси y - отрезок, равный b.
В справочниках прямую, проходящую через две точки часто задают в виде:
(x-x1)/(x2-x)=(y-y1)/(y2-y1),
которое легко привести к явному виду:
y=y1+(y2-y1)*(x-x1)/(x2-x).

Окружность также можно задать через независимую переменную x и зависимую y,
y=sqrt(R*R-x*x) или
y=yc+sqrt(r*r-(x-xc)*(x-xc)).

Однако удобнее пользоваться параметрическим уравнением:
x=xс+R*sin(s)
y=yс+R*cos(s),
где pc(xc,yc) - центр окружности, а s - параметр, изменяющийся от нуля до двух пи.

Сфера задается:
x=x1+s11*cos(s1)*$sin(s2)
y=y1+s11*$sin(s1)*$sin(s2)
z=z1+s11*cos(s2)

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

2. Алгоритмизация на основе векторной алгебры.

Основные понятия векторной алгебры.
Величины, значения которых определяются размером и направлением в пространстве, называются векторами.
 
 
Рис.1 
          Рис.2 
 
Геометрически вектор - это направленный отрезок в пространстве, определяемый начальной точкой p0 и конечной p1 (рис. 1). Длина вектора называется его модулем.

В прямоугольной системе координат точку P можно представить как вектор: каждой точке Р однозначно соответствует вектор OР, который называется радиус вектором точки Р.
Координаты вектора ОР (рис.2), отнесенные осям координат называются декартовыми координатами точки Р.

Единичный вектор - это вектор длина которого равна единице. Поэтому, чтобы получить единичный вектор - надо вектор разелить на его длину.

Умножение вектор на скаляр (вещественное число).
Если s вещественное число и p вектор (определяющий двумя, тремя и т.д. числами), то произведение s*p также есть вектор с длиной |s*p|.

При реализации на ЭВМ действия с векторами записывается покомпонентно (пример произведения вектора на вещественне число - скаляр):
x=s*x1,
y=s*x1,
z=s*z1;
или в непосредственно в векторном виде:
p=s*p1.

Сумма p1+p2 двух векторов p1 и p2 геометрически получается следующим образом: p1 и p2 складываются с помощью параллельного переноса (рис. 3). Вектор P (OP) есть вектор, который имеет начало, совпадающее с началом p2, и конец, совпадающий с концом p1 (правило треугольника).

В среде системы Вектор сумма векторов определяется:
p =p1 + p2,
pn =pn1 + pn2,
где n, n1, n2 - могут быть любыми целыми числами.

Разность вектора p1-p2 рассматривается как сумма p1 и -p2.

Деление вектора на скаляр p/s рассматривается как произведение 1/s* p;

Модуль вектора вычисляется по правилу
s=|p| = sqrt (x*x + y*y + z*z)


3. Геометрические приложения векторной алгебры

3.1. Вычисление середины отрезка р1-р2.
Искомая точка без труда определяется из чертежа  и вычисляется через компаненты:
x=x1+(x2-x1)/2.
y=y1+(y2-y1)/2.
или непосредственно в векторной форме:
p=p1+ (p2-р1)/2                                (2)
Можно вичисления середины отрезка записать проще, например,
p=(p2-p1)/2., однако уравнение (2), в свою очередь, можно обобщить, и вычислять не только середину, а любую точку на отрезке р1-р2 в зависимости от безразмерного параметра s.

3.2. Задание точек на прямой в зависимости от безразмерного параметра s.
После ряда перестановок в (2), получим:
p=(1.-s)*p1+s*p2,                            (3)
где, чтобы получить ту же середину, необходимо s присвоить значение равное 0.5.
Чтобы получить точки внутри  отрезка p1-p2, нужно параметр s задавать в пределах от нуля до единицы: 0 < s < 1, в противном случае точки будут на прямой р1-р2  вне этого отрезка.

3.3. Уравнение прямой, проходящей через точку p0 (x0, y0, z0),  в направлении вектору p2:
p = p1 +t*p2,                                     (4)
где t изменяется от минус бесконечности до плюс бесконечности.

3.4. Уравнение прямой, проходящей через точку p0 (x0, y0, z0),  в направлении единичного вектора.
Чаще вместо вектора р2 в (4) используется единичный вектор (в пособии это р99), что позволяет задавать точку  в зависмости от расстояния от р1 в направлении единичного вектора р99.
p=p1+s*p99,
где р99, в свою очередь, если известна какая-то точка р2 на прямой,  вычисляется:
р99=(р2-р1)/|p2-p1|.

3.5. Уравнение плоскости, проходящей через три точки p1, p2, p3:
p = p1 + u*(p2-p1) + v*(p3-p1),
где u и v изменяются на всем интервале действительной оси.

3.6. Уравнение косой плоскости, проходящей через четыре точки p1, p2, p3, р4.
p=(1.-u)*pi+ u*pj,                      (5)
где:
pi=(1.-v)*p1+v*p3
pj=(1,-v)*p2+v*p4.

Две точки из четырех могут совпадать ( в этом случае однозначно задается плоскость).
Уравнение (5) в курсе является основным и применяеьтся очень часто.

3.7. Модуль вектора, то же самое длина вектора, отрезка определяется:

s=|p2-p1|, или:
s= $sqrt((x1-x2)*(x1-x2)+ (y1-y2)*(y1-y2)).

Геометрически это гипотенуза прямоугольного треугольника один катет которого являются разностью абсцисс (координат х) начала и конца отрезка, а вторым разностью ординат (координат y) начала и конца отрезка).
В трехмерном случае добавляется разность координат по z:
p=|p2-p1|=sqrt ((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1) + (z2-z1)*(z2-z1)).
 


4. Алгоритмизация как геометрическое место точек.

Например, все точки должны находиться на таком-то расстоянии от одной или нескольких точек.
 
 
4.1. Для прямой все ее точки p должны находиться на одинаковом (s1 и s2) расстоянии от двух заданных p1 и  p2: s1=s2  или  |p-p1|=|p-p2|. 
4.2. Для окружности как места точек р, равноудаленных (расстояние s)  от точки р1: s=|p-p1|. 
 
 
 
4.3.  Для эллипса: s1+s2=c  или |p1-p|+|p2-p| =c 
4.4.  Для параболы: s1=s2 или |p1-p|=|p2-p|   (x2=c) 
4.5.  Для гиперболы: s2-s1=c  или |p1-p|-|p2-p| =c 
 

 
4.6. Для дуги окужности, проходящей через две точки и заданный радиус: |p1-p|=|p2-p| = с (компромисс). 
4.7. Для дуги окужности, проходящей через три  точки |p1-p|=|p2-p| = |p3-p| (компромисс)
 


5. Алгоритмизация, удовлетворяющая условию максимума/минимума.

Например, все точки (или точка) должны находиться на min/max расстоянии от заданной.
Так минимальное расстояние s1 от точки p3 до отрезка p1-p2 будет:
s1=|p3-p|-> min,
где р =(1-s)*p1 +s*p2.
Более подробно об этом см. следующущий урок ВГА.
 

6. Алгоритмизация на основе случайных чисел.

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

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

В этом случае обычно формируется (автоматически в режиме диалога, или специально в текстовом редакторе) файл команд, который называется макрокомандой (МК)  Макрокоманда построения отрезка прямой линии: otrezok.mac, окружности: okr.mac были рассмотрены ранее см. урок1. В свою очередь какждая команда в системе реализована на совокупности различных алгороитмов (аналитических, векторных и т.п.). В том случае если требуется воспользоваться только одной командой, то сможно это выполнить непосредственно в диалоговом режиме, если требуется выполнить множество повторяющихся вычислений, то диалог удобнее преобразовать в МК, в которой рекурсивно организовать рекурсивный цикл (вызов программы самой себя). Рассмотрим ряд примеров.

Пример 1. Вычислить середину отрезка между точками р1 и р2.
Решение
 1. В командной строке (ctrl+c) задаем точки и параметр s:
 : р1=50.,40. р2=180., 190. s=0.5
2.  В той же командной строке (удалив предварительно вводимые параметры) вычисляем искомую точку:
p=(1.-s)*p1+s*p2
Результат будет виден внизу экрана.


Пример 2. Вычисление множества точек на прямой: p1-р2.

Решение выполняем в цикле по формуле:
p=(1.-s)*p1+s*p2.

Формируем две макрокоманды: d1.mac - МК  задания исходных данных  и tc1.mac - МК цикла расчета точек на прямой

td1.mac - МК  задания исходные точки
: p1=20.,30. p2=210.,140.
tprin: p101=p1 p102=p2 $ - изображение отрезка через базовую МК
tc1: s=0.    $ - обращение к циклу

tc1.mac - МК цикла расчета точек на прямой
s > 1.0001 ? exit  $ - условие выхода
p=(1.-s)*p1+s*p2  $ - вычисляем точку
okr: p105=p s100=3.0 $ в точке р строим окружность
tc1: s=s+0.1   $ - идем на рекурсивный цикл


Пример 3. Движение точки р1 в направлении  р2 в зависимости от расстояния от р1.
Алгоритм решения данной задачи известен в векторной форме:
p=p1+s*p99,
где р99 - единичный вектор определяется
р99=(p2-p1)/|p2-p1| = (p2-p1)/$sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))

Как и в примере 3. формируем две МК: td2.mac - МК  задания исходные точки и tc2.mac - МК цикла расчета точек на прямой

td2.mac - МК  задания исходные точки
print$on    $ включить печать
: p1=20.,30. p10=210.,140.
tprin: p101=p1 p102=p10 $ - изображение отрезка через базовую МК
s99=$sqrt((x10-x1)*(x10-x1)+(y10-y1)*(y10-y1)) $ длина отрезка
p99=(p10-p1)/s99    $ расчет единичного вектора
tc2: s=0.      $ - обращение к циклу

tc2.mac - МК цикла расчета точек на прямой
s > s99 ? exit    $ - условие выхода
p=p1+s*p99    $ - вычисляем точку
okr: p105=p s100=3.0  $ в точке строим окружность
tc2: s=s+10.    $ - идем на рекурсивный цикл


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

В модуле Vectoru случайное число выбирается командой (командной строкой):
  _Случайное_число_(в_n191)_от_ 0000  до  0000
После того как задали диапазон: от 0000 до 0000 и ввели команду, то в регистр n191 автоматически заносится случайное число.
Организуем расчет точек на прямой р1-р2 по формуле:
p=(1.-s)*p1+s*p2,
где параметр s будем выбирать случайно.

Чтобы этот алгоритм реализовать в системе "Вектор",  можно выбирать число от 1 до 10, а затем делить его на десять.
Внизу даны две МК (задания исходных данных) и цикла расчета 20 точек на прямой по методу случайных чисел.

td.mac - имя МК
print$on
: p1=80.,50. p2=240.,110.
otrezok: p101=p1 p102=p2
tsluh: n1=0

tsluh.mac - имя МК
n1 > 20 ? exit        $ условие выхода - вычисляем 20 точек
  _Случайное_число_(в_n191)_от_ 0000  до  0011    $ выбираем случайное число от нуля до десяти
s1=n191                        $ переводим случайное целое число в вещественное
s=s1/10.                        $ переводим случайное целое число в десятичное
p=(1.-s)*p1+s*p2         $ вычисление точек на прямой в зависимости от s
okr: p100=p s100=5.    $ точки изображаем окружностью
tsluh: n1=n1+1   $ рекурсия с шагом 1