Оглавление

1 Графика 2

1.1 Алгоритм Сазерленда-Кохена, отсечение отрезка прямоугольным окном 2

1.2 Алгоритм Лианга-Барски, отсечение отрезка прямоугольным окном 2

2 Представление разреженных матриц. 4

2.1 Форматы представления разреженных матриц 4

2.2 Конвертация разреженной матрицы из нормальной формы в формат RR(C)O 6

2.3 Конвертация разреженной матрицы, представленной в формате RR(C)U в нормальную форму 6

2.4 Транспонирование разреженной матрицы, заданной в формате RR(C)U 6

2.5 Сложение двух матриц, заданных в формате RR(C)U.(1-й способ) 6

2.6 Сложение двух матриц, заданных в формате RR(C)U.(2-й способ) 7

2.7 Умножение двух матриц, заданных в формате RR(C)U.(1-й способ) 7

2.8 Умножение двух матриц, заданных в формате RR(C)U.(2-й способ) 7

3 Интегральные уравнения. 8

3.1 Введение 8

3.2 Уравнение Вольтерра первого рода 9

3.3 Линейное уравнение Вольтерра второго рода 9

3.4 Уравнение Фредгольма второго рода 9

4 Методы оптимизации 10

4.1 Метод наискорейшего спуска 10

4.2 Минимизация функции многих переменных методом конфигураций 11

5 Теория графов 11

5.1 Способы задания графа 11

5.2 Путь с минимальным количеством промежуточных вершин.(волновой алгоритм) 11

5.3 Путь минимальной суммарной длины во взвешенном графе с произвольными весами для всех пар вершин.(алгоритм Флойда) 12

5.4 Нахождение K путей минимальной суммарной длины во взвешенном графе с неотрицательными весами.(Алгоритм Йена) 13

5.5 Построения минимального остовного дерева (Алгоритм Краскала) 14

6 Сетевое программирование 15

1Графика

1.1Алгоритм Сазерленда-Кохена, отсечение отрезка прямоугольным окном

Часто возникает необходимость отсечь выводимое изображение по границе области, область обычно имеет вид прямоугольника. Данный алгоритм позволяет для некоторого отрезка заданного координатами начала и конца((x1,y1),(x2,y2)), и некоторой прямоугольной области, определить координаты начала и конца части отрезка лежащей внутри области.

Алгоритм разделяет плоскость на 9 частей, и каждой из них ставит в соответствие 4-х битный код следующим образом: включенный бит 0 означает, что точка лежит левее прямоугольника, включенный бит 1 означает, что точка лежит правее прямоугольника, включенный бит 2 означает, что точка лежит выше прямоугольника, включенный бит 3 означает, что точка лежит ниже прямоугольника, Таким образом, получаем:

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

1.2Алгоритм Лианга-Барски, отсечение отрезка прямоугольным окном

Данный алгоритм решает ту же задачу, что и предыдущий, но используя другую идею. Пусть (x0,y0);(x1,y1) - координаты соответственно начала и конца отрезка. (XS1,YS1);(XS2,YS2) - координаты соответственно левого-верхнего и правого-нижнего углов "экрана"(- области по которой производим отсечения).

Так как область отсечения является прямоугольником, то ее можно представить в виде неравенств.

XS1 ≤ x ≤ XS2,

YS1 ≤ y ≤ YS2

Представим наш исходный отрезок в параметрическом виде.

x=x0+dx t,

y=y0+dy t, 0 ≤ t ≤ 1

здесь dx=x1-x0 , dy=y1-y0, при этом в случае когда t изменяется вне отрезка (0,1), получаем координаты точки лежащей на прямой содержащей исходный отрезок, но вне самого отрезка. Подставим это представление в неравенства, определющие область отсечения. Получаем

-dx·t ≤ x0 - XS1 ,

dx·t ≤ XS2 - x0 ,

-dy·t ≤ y0 - YS1 ,

dy·t ≤ YS2 - y0 .

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

Pit ≤ Qi , i=1,2,3,4.

при этом

P1=-dx; Q1=x0 -XS1

P2=dx; Q2=XS2-x0

P3=-dy; Q3=y0 -YS1

P4=dy; Q4=YS2-y0

Решение неравенства зависит от знака Pi, а именно: если Pi < 0, то получаем ограничение на параметр t снизу. если Pi > 0, то получаем ограничение на параметр t сверху. если Pi = 0, то все зависит от знака Qi: если Qi < 0, то решений нет и делаем вывод, что отрезок не видим, если Qi ≥ 0, то любое t является решением и данное неравенство можно не рассматривать.

Таким образом решив систему получим ограничения на t. Следует учесть, что для отрезка диапозон изменения параметра ограничен, а именно 0 ≤ t ≤ 1. И наконец если нашли решение системы с учетом пары ограничений для отрезка можем используя параметрическое представление получить координаты концов точек отсеченного отрезка.

Непосредственно алгоритм будет выглядеть следующим образом: Зададимся величинами t0=0,t1=1 Для i=1,2,3,4 изменим в соответствии со знаком Pi нижнее (t0) или верхнее (t1) ограничение на параметр, или в случае если Pi=0 и Qi < 0, то отрезок не видим и выйдем из цикла. Если отрезок видим вычислим координаты начала и конца видимой части отрезка, используя параметрическое задание.