Лекция 1 Введение




НазваниеЛекция 1 Введение
Дата конвертации11.03.2013
Размер445 b.
ТипЛекция


Структуры и алгоритмы обработки данных, 1

  • 2008-09 учебный год

  • Лекция 1

  • Введение

  • Разреженные матрицы и ортогональные списки


Часть 1. Введение Учебный курс – 3 и 4-й семестры

  • Отчетность:

  • 3-й семестр (осенний): К/р + Экзамен

  • 4-й семестр (весенний): К/р + Т/к



Осенний семестр

      • Основные темы
      • См. файл «Вопросы2007осень как план»


Напоминание материала 1-го курса

  • Представление и реализация линейных списков (например, Л1-списка):

  • Непрерывная реализация

  • Ссылочное представление в связанной (динамической) памяти

  • Ссылочное представление на базе вектора



Непрерывная реализация на базе вектора

  • Линейный список представлен одномерным массивом так, что соседние элементы списка записаны в соседние элементы массива.

  • Пример операции «удалить элемент списка»:



Непрерывная реализация на базе вектора

  • Очевидный недостаток – необходимость сдвига элементов массива при выполнении операций вставки и удаления элемента списка.

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



Ссылочное представление в связанной (динамической) памяти



Ссылочное представление на базе вектора



Литература

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


Структуры и алгоритмы обработки данных, 1

  • Лекция 1

  • Часть 2. Разреженные матрицы

  • и ортогональные списки

    • Стандартные способы представления матриц
    • Плотное и разреженное представление полиномов
    • Разреженные матрицы на базе ортогональных списков (ссылочная реализация в динамической памяти)
    • Разреженные матрицы на базе ортогональных списков (ссылочная реализация на базе вектора)












В общем случае полином (многочлен) P(x) представляется последовательностью пар чисел, каждая из которых (c, d) соответствует моному (одночлену) сxd,

  • В общем случае полином (многочлен) P(x) представляется последовательностью пар чисел, каждая из которых (c, d) соответствует моному (одночлену) сxd,

  • т. е. P(x)  (q1, q2, …, qm-1, qm),

  • где qk = (ck, dk) и ck  0.

  • Удобно использовать упорядоченное разреженное представление полинома, расположив пары “коэффициентпоказатель” в порядке убывания показателей степеней мономов, т. е. так, что

  • ( k 1.. 1: dk dk+1).

  • Во-первых, такое представление единственно,

  • а во-вторых, многие операции над полиномами в таком представлении выполняются более эффективно.



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

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

  • В такой ситуации целесообразно использовать динамические структуры данных,

  • например, линейные Л1- или Л2-списки.

  • Отметим, что стандартное математическое ("человеческое") представление полиномов  разреженное. Например:

  • P7(x) = 3x7 + 13x2 – 7 .

  • Конец аналогии.







Замечания

  • Списки по строкам и столбцам – кольцевые однонаправленные (Л1-списки).

  • В списках введены сторожевые элементы.

  • Эти сторожевые элементы, они же – «представители» строк и столбцов, сгруппированы в массивы «входов» в списки по столбцам (BaseCol [*] ) и по строкам (BaseRow [*] ).

  • Можно было бы вместо массивов входов организовать списки входов.



  • Типы данных для представления разреженной матрицы в динамической памяти

  • 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;













Представление

  • 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};







Литература по теме “Разреженные матрицы и ортогональные списки”

  • Основная

  • 1. Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. М.: Мир, 1976. [с.371-380, 2.2.6. Массивы и ортогональные списки]; 3-е изд. М.: Издательский дом «Вильямс», 2000. [с.341-351]

  • Дополнительная

  • 2. Дал У., Дейкстра Э., Хоор К. Структурное программирование. М.: Мир, 1975. [Хоар К. О структурной организации данных, с.169, п.10. Разреженные структуры данных]

  • 3. Писсанецки С. Технология разреженных матриц. М.: Мир, 1988. [гл.1]



КОНЕЦ ЛЕКЦИИ

  • КОНЕЦ ЛЕКЦИИ



Похожие:

Лекция 1 Введение iconЛекция №1 : Введение в базы данных Лекция №1 : Введение в базы данных Учебные цели занятия: Изучить: основные понятия теории баз данных
К. Дж. Дейт. Введение в системы баз данных, 7-е издание.: Пер с англ. М.: Издательский дом «Вильямс», 2001. 1072 с., ил
Лекция 1 Введение iconЛекция 12 Введение

Лекция 1 Введение iconЛекция введение
Широкий диапазон точностей от единиц метров до субсантиметров практически на любых расстояниях
Лекция 1 Введение iconЛекция динамика конфликта гаранина Елена Юрьевна, кафедра сервиса и моды 2 часа Введение Цель

Лекция 1 Введение iconЛекция 1 Введение в машинную графику Основные направления компьютерной графики Литература
Попов В. Б. Основы компьютерных технологий: учеб пособие. М.: Финансы и статистика, 2002. 704 с
Лекция 1 Введение iconЛекция 1 Введение в предмет и Рабочие определения
Феноменология познавательных процессов. Мышление Психология в ряду других наук о мышлении: философия, логика, нейронауки, кибернетика,...
Лекция 1 Введение iconЛекция 10. Конфликты между руководителями и подчиненными гаранина Елена Юрьевна, кафедра сервиса и моды 2 часа Введение Цель
Сложность социальной и профессиональной адаптации руководителя к должности управленца
Лекция 1 Введение iconЛекция 13. Теория и практика разрешения конфликтов гаранина Елена Юрьевна, кафедра сервиса и моды 2 часа Введение Цель
Оперативное самостоятельное вмешательство третьей стороны в конфликт необходимо в тех ситуациях, когда
Лекция 1 Введение iconЛекция 1 Основные понятия и определения теоретической механики Лекция 2 Виды связей и реакции связей Лекция 3 Момент силы относительно точки Лекция 4 Кинематика точки
Теоретическая механика это наука о наиболее общих законах механиче­ского движения и равновесия материальных объектов
Лекция 1 Введение iconЛекция №14. Введение
Аналитическая индивидуальная психокоррекция А. Адлера Человек, по А. Адлеру, прежде всего существо сознательное, которое само себя...
Разместите кнопку на своём сайте:
hnu.docdat.com


База данных защищена авторским правом ©hnu.docdat.com 2012
обратиться к администрации
hnu.docdat.com
Главная страница