03.09.2008Разреженные матрицы и ортогональные списки 1 Структуры и алгоритмы обработки данных, 1 2008-09 учебный год Лекция 1 I.Введение II.Разреженные. - презентация

1 Разреженные матрицы и ортогональные списки 1 Структуры и алгоритмы обработки данных, учебный год Лекция 1 I.Введение II.Разреженные матрицы и ортогональные списки

2 Разреженные матрицы и ортогональные списки 2 Часть 1. Введение Учебный курс – 3 и 4-й семестры Отчетность: 3-й семестр (осенний): К/р + Экзамен 4-й семестр (весенний): К/р + Т/к

3 Разреженные матрицы и ортогональные списки 3 Осенний семестр Основные темы См. файл «Вопросы2007осень как план»

4 Разреженные матрицы и ортогональные списки 4 Напоминание материала 1-го курса Представление и реализация линейных списков (например, Л1-списка): Непрерывная реализация Ссылочное представление в связанной (динамической) памяти Ссылочное представление на базе вектора

5 Разреженные матрицы и ортогональные списки 5 Непрерывная реализация на базе вектора Линейный список представлен одномерным массивом так, что соседние элементы списка записаны в соседние элементы массива. Пример операции «удалить элемент списка»: чер е д а б у кв чер е д а б укв чер е д а б укв ч р е д а б у квр е д а б у квчер е д а б у кв в

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

7 Разреженные матрицы и ортогональные списки 7 Ссылочное представление в связанной (динамической) памяти а Head: S: Cur: PredCur: Пример операции «удалить элемент списка»:

8 Разреженные матрицы и ортогональные списки 8 Ссылочное представление на базе вектора Пример операции «удалить элемент списка»:

9 Разреженные матрицы и ортогональные списки 9 Литература 1.Алексеев А. Ю., Ивановский С. А., Куликов Д. В. Динамические структуры данных: Учеб. пособие. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», Ивановский С.А., Калмычков В. А., Лисс А. А., Самойленко В.П. Представление и обработка структурированных данных: Практикум по программированию / СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2002.

10 Разреженные матрицы и ортогональные списки 10 Структуры и алгоритмы обработки данных, 1 Лекция 1 Часть 2. Разреженные матрицы и ортогональные списки 1.Стандартные способы представления матриц 2.Плотное и разреженное представление полиномов 3.Разреженные матрицы на базе ортогональных списков (ссылочная реализация в динамической памяти) 4.Разреженные матрицы на базе ортогональных списков (ссылочная реализация на базе вектора)

11 Разреженные матрицы и ортогональные списки Стандартные способы представления матриц 012…j…n … i … n A[0..n, 0..n] a 0 = Адр(A[0,0]) Адр(A[i,j]) = a 0 + a 1 *i + a 2 *j, где a 1 = (n+1)*d, a 2 = d, d – размер памяти под один элемент матрицы

12 Разреженные матрицы и ортогональные списки 12 Стандартные способы представления матриц 01…j……n … i … n A[0..n, 0..n] a 0 = Адр(A[0,0]) i j Адр(A[i,j]) = = a 0 + a 1 *i*(i + 1)/2 + a 2 *j, где a 1 = d, a 2 = d, d – размер памяти под один элемент матрицы Треугольные матрицы

13 Разреженные матрицы и ортогональные списки 13 Стандартные способы представления матриц 01…j……n … i … n A[0..n, 0..n] a 0 = Адр(A[0,0]) | i – j | k На картинке k = 2 Ленточные матрицы

14 Разреженные матрицы и ортогональные списки 14 Разреженные матрицы 012…j…n … i … n Общее количество элементов N = (n + 1) 2 Количество «существенных» элементов - k k N Нерегулярная структура

15 Разреженные матрицы и ортогональные списки Плотное и разреженное представление полиномов Начнем с аналогии. Пусть рассматривается полином одной переменной с целочисленными коэффициентами P n (x) = a 0 x n + a 1 x n-1 + … + a n-1 x + a n,a 0 0. Плотное представление полинома основано на хранении последовательности (массива) всех его коэффициентов ( a 0, a 1, …, a n-1, a n ), в том числе и тех, которые равны нулю. Разреженное представление полинома использует только ненулевые коэффициенты. Например, пусть дан полином P 7 (x) = 3x x 2 – 7. Его плотное представление есть (3, 0, 0, 0, 0, 13, 0, 7). Разреженное представление есть последовательность пар чисел (коэффициент, показатель степени), т. е. ((3, 7), (13, 2), ( 7, 0)).

16 Разреженные матрицы и ортогональные списки 16 В общем случае полином (многочлен) P(x) представляется последовательностью пар чисел, каждая из которых (c, d) соответствует моному (одночлену) с x d, т. е. P(x) (q 1, q 2, …, q m-1, q m ), где q k = (c k, d k ) и c k 0. Удобно использовать упорядоченное разреженное представление полинома, расположив пары коэффициент показатель в порядке убывания показателей степеней мономов, т. е. так, что ( k 1..m 1: d k > d k+1 ). Во-первых, такое представление единственно, а во-вторых, многие операции над полиномами в таком представлении выполняются более эффективно. Плотное и разреженное представление полиномов

17 Разреженные матрицы и ортогональные списки 17 Естественно реализовать последовательность, представляющую полином, в виде линейного списка. Действительно, при операциях с полиномами, как правило, появляются новые мономы, которые надо вставлять в последовательность, и исчезают старые, которые надо удалять из последовательности. В такой ситуации целесообразно использовать динамические структуры данных, например, линейные Л1- или Л2-списки. Отметим, что стандартное математическое ("человеческое") представление полиномов разреженное. Например: P 7 (x) = 3x x 2 – 7. Конец аналогии. Плотное и разреженное представление полиномов

18 Разреженные матрицы и ортогональные списки Разреженные матрицы на базе ортогональных списков (ссылочная реализация в динамической памяти) Ненулевой элемент матрицы а[Row,Col]=Val будем представлять узлом RowColVal RowColVal DownRight (слева) или с графическим изображением указателей (справа). Для примера рассмотрим матрицу Организуем циклические списки ненулевых элементов по строкам и столбцам. Каждый ненулевой элемент матрицы а[Row,Col] будет входить в два списка (будет общим элементов двух списков): в список строки с номером Row и в список столбца с номером Col (см. рисунок).

19 Разреженные матрицы и ортогональные списки BaseRow[*] BaseCol[*]

20 Разреженные матрицы и ортогональные списки 20 Замечания 1.Списки по строкам и столбцам – кольцевые однонаправленные (Л1-списки). 2.В списках введены сторожевые элементы. 3.Эти сторожевые элементы, они же – «представители» строк и столбцов, сгруппированы в массивы «входов» в списки по столбцам ( BaseCol [*] ) и по строкам ( BaseRow [*] ). 4.Можно было бы вместо массивов входов организовать списки входов.

21 Разреженные матрицы и ортогональные списки 21 Типы данных для представления разреженной матрицы в динамической памяти type indMatr = 0.. SizeMatr; {диапазон индексов матрицы } {0 – спец.значение индекса (сторож циклического списка) } Next = ^ MatrElem; {указатель на элемент матрицы } MatrElem = record{элемент матрицы, т.е. узел списка } Row, Col : indMatr ; Val: Float ; Down, Right : Next end {MatrElem}; Base = array [indMatr] of MatrElem; {массив "входов"} Matr = record { матрица } BaseRow, BaseCol : Base end {Matr}; var n,m : indMatr;

22 Разреженные матрицы и ортогональные списки 22 Пример: вычисление скалярного произведения столбцов матрицы. Пусть a(k) - это k-й столбец матрицы A. Требуется вычислить (k:1..m, l:1..m). function ScalProd ( var A: Matr; k,l: indMatr ) : Float; {Pred: (0

23 Разреженные матрицы и ортогональные списки 23 s := 0; while ( q^.Row 0) and (p^.Row 0) do begin if q^.Row = p^.Row then begin {эл-ты из одной строки } s := s + q^.Val * p^.Val; q := q^.Down; p := p^.Down end else {текущ. эл-ты списков-столбцов из разных строк} if p^.Row > q^.Row then q := q^.Down else p := p^.Down {fi} end {while};

24 Разреженные матрицы и ортогональные списки 24 Картинка p q

25 Разреженные матрицы и ортогональные списки Разреженные матрицы на базе ортогональных списков Ссылочное представление разреженной матрицы на базе вектора (Метод Д.Кнута) NextInRow = Right,NextInCol = Down Пример матрицы и ее представление на базе вектора (типа MatE, см.далее)

26 Разреженные матрицы и ортогональные списки 26 Массивы входов Номер строки или столбца 1234 BaseRow1204 BaseCol Продолжение

27 Разреженные матрицы и ортогональные списки 27 Представление type indMatr = 1..MaxInd; {диапазон индексов матрицы } NumOfElem = 0..MaxNumElem; {=Next} {адрес в векторе памяти} MatrElem = record {элемент матрицы} Row, Col : indMatr; Val: Float; NextInRow, NextInCol : NumOfElem end {MatrElem}; MatE = array [NumOfElem] of MatrElem; Base = array [indMatr] of NumOfElem; {массив "входов"} BaseRC = record BaseRow, BaseCol : Base end; Matr = record {"матрица"} ListElem: MatE; InputList: BaseRC end {Matr};

28 Разреженные матрицы и ортогональные списки 28 Тот же пример: вычисление скалярного произведения столбцов матрицы. Пусть a(k) - это k-й столбец матрицы A. Требуется вычислить (k:1..m, l:1..m). function ScalProd ( var A: Matr; k,l: indMatr ) : Float; var s: Float; p, q: NumOfElem; begin with A.InputList do begin p := BaseCol[k]; q := BaseCol[l] end {with}; … { Cм.вставку на следующем слайде } ScalProd := s end {ScalProd}

29 Разреженные матрицы и ортогональные списки 29 s := 0; with A do begin while (q 0) and (p 0) do if ListElem[q].Row = ListElem[p].Row then begin {эл-ты из одной строки } s := s + ListElem[q].Val * ListElem[p].Val; q := ListElem[q].NextInCol; p := ListElem[p].NextInCol end else {текущ. эл-ты столбцов из разных строк} if ListElem[p].Row > ListElem[q].Row then q := ListElem[q].NextInCol else p := ListElem[p].NextInCol {fi} {end-while} end {with A};

30 Разреженные матрицы и ортогональные списки 30 Литература по теме Разреженные матрицы и ортогональные списки Основная 1. Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. М.: Мир, [с , Массивы и ортогональные списки]; 3-е изд. М.: Издательский дом «Вильямс», [с ] Дополнительная 2. Дал У., Дейкстра Э., Хоор К. Структурное программирование. М.: Мир, [Хоар К. О структурной организации данных, с.169, п.10. Разреженные структуры данных] 3. Писсанецки С. Технология разреженных матриц. М.: Мир, [гл.1]

31 Разреженные матрицы и ортогональные списки 31 КОНЕЦ ЛЕКЦИИ