Лекции Содержание лекции Курсовая работа 1 01. 09 1 0 3



Скачать 77.35 Kb.
Дата15.10.2012
Размер77.35 Kb.
ТипЛекции



Факультет компьютерных технологий и информатики (ФКТИ)

Кафедра математического обеспечения и применения ЭВМ (МО ЭВМ)


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

2008 год

3-й (осенний) семестр

План лекций и практических занятий по выполнению курсовой работы

недели


Дата

понедельника

и дата лекции

Содержание лекции

Курсовая работа

1

01.09

1 – 03.09


Введение.

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




2

08.09

2 – 10.09

Рекурсивная обработка линейных списков

Занятие 1

Задание 1. Разреженные матрицы

3 – 10.09

Иерархические списки. Рекурсивная обработка.




3

15.09

4 – 17.09

Стек, очередь, дек.




4

22.09

5 – 24.09

Деревья (леса) и бинарные деревья: определения, спецификация, соответствие лесов и бинарных деревьев.

Занятие 2

6 – 24.09


Обходы бинарных деревьев и лесов. Представление и реализация бинарных деревьев. Рекурсивные функции на бинарных деревьях.





5

29.09

7 – 01.10


Задача кодирования и сжатия сообщений. Префиксные коды и кодовые деревья. Метод Шеннона-Фано. Метод Хаффмана.




6

06.10

8 – 08.10

8. Оптимальность кода Хаффмана. Неравенство Крафта.

Занятие 3

Задание 2. Стек, Очередь

9 – 08.10


Энтропийная оценка средней длины оптимального кода.

Динамический метод Хаффмана.




7

13.10

10 – 15.10


Поиск с возвращением (backtracking). Общая схема. Пример: задача о ферзях. Усовершенствования.




8

20.10

11 – 22.10

Backtracking. Оценка сложности: метод Монте-Карло. Другие способы программирования backtracking'а: рекурсия и использование макросредств.

Занятие 4

Задание 3. Деревья

12 – 22.10

Метод ветвей и границ. Общая схема. Задача коммивояжера.




9

27.10

13 – 29.10


Задача коммивояжера. Метод ветвей и границ.




10

03.11

14 – 05.11

Задача коммивояжера. Эвристические методы.

Занятие 5


15 – 05.11

Динамическое программирование. Пример и общая идея. Задача определения порядка умножения цепочки матриц.




11

10.11

16 – 12.11


Быстрый поиск. Идеально сбалансированное бинарное дерево. Бинарные деревья поиска. Случайные бинарные деревья поиска.




12

17.11

17 – 19.11


Подсчет числа структурно различных бинарных деревьев с заданным числом узлов. Среднее время поиска в случайных деревьях.

Операция вращения в БДП

Занятие 6

Задание 4. Backtracking

18 – 19.11

Случайные БДП с рандомизацией

Рандомизированные пирамиды поиска




13

24.11

19 – 26.11


АВЛ-деревья. Включение и исключение из АВЛ-дерева. Оценка сложности в худшем случае: деревья Фибоначчи.




14

01.12

20 – 03.11

Реализация упорядоченных линейных списков на базе (АВЛ-деревьев или) рандомизированных пирамид поиска. Операции сцепления и расщепления списков.

Занятие 7


21 – 03.12

Оптимальные деревья поиска. Алгоритм построения оптимального дерева.




15

08.12

22 – 10.12



Хорошие бинарные деревья поиска.

Аналогии (умножение матриц, оптимальные БДП, оптимальная триангуляция выпуклого многоугольника)




16

15.12

23 – 17.12

Хеширование.

Занятие 8

Сдача–прием курсовой работы

24 – 17.12

Резерв (вставить примерно в середине семестра ТК по рекурсивным спискам !)




17

22.12

25 – 24.12

Резерв (2-3-деревья. Б-деревья и т.п.).




18

29.12

31.12

Установочная лекция (обзор, вопросы к экзамену, процедура экзамена) ?














Литература

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

    2. Ивановский С. А. Деревья кодирования и поиска: Учеб. пособие. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2006. 84 с.

Похожие:

Лекции Содержание лекции Курсовая работа 1 01. 09 1 0 3 iconЛекции Содержание лекции Курсовая работа 1 01. 09 1 0 3
Деревья (леса) и бинарные деревья: определения, спецификация, соответствие лесов и бинарных деревьев
Лекции Содержание лекции Курсовая работа 1 01. 09 1 0 3 iconЛекции лекции лекции, зачет лекции лекции Зимняя сессия
Памятка для студентов 1 курса экономического факультета заочной формы обучения по направлению подготовки
Лекции Содержание лекции Курсовая работа 1 01. 09 1 0 3 iconЛекции. Тема и содержание лекции Соответствие тематическому плану рабочей программы курса
Информативность; раскрытие основных понятий темы; сочетание теоретического материла с конкретными примерами
Лекции Содержание лекции Курсовая работа 1 01. 09 1 0 3 iconЛекции по трем критериям, где: Интерес Ваша заинтересованность в теме лекции
Для того, чтобы наши лекции соответствовали вашим интересам, пожалуйста, заполните эту
Лекции Содержание лекции Курсовая работа 1 01. 09 1 0 3 iconЛекции по философии истории перевод А. М. Водена Гегель Г. В. Ф. Лекции по философии истории. Спб.: Наука, 1993, 2000. 480с. С. 57-480
Эти лекции,— к 1822/23, 1824/25, 1826/27, 1828/29, 1830/31 гг.,—а именно тетради, в которых лекции записывались господином тайным...
Лекции Содержание лекции Курсовая работа 1 01. 09 1 0 3 iconКраткое содержание лекции 2 Структура и деление атомного ядра 2 Утечка нейтронов из реактора 5 Критический радиус 6
Несколько лекций могут быть только введением в круг этих вопросов. В рамках настоящей лекции мы обсудим самые основные физические...
Лекции Содержание лекции Курсовая работа 1 01. 09 1 0 3 iconАкимов Ю. К. «Современные методы регистрации частиц» Количество часов
Во время лекции вопросы следует задавать преподавателю по ходу ее изложения. Материал после каждой лекции прорабатывается, и возникающие...
Лекции Содержание лекции Курсовая работа 1 01. 09 1 0 3 iconЛекции Самост работа 1
Предмет, цель и содержание дисциплины «Безопасность жизнедеятельности». Принципы, методы и средства обеспечения безопасности жизнедеятельности...
Лекции Содержание лекции Курсовая работа 1 01. 09 1 0 3 iconЛекции по науке Твен Марк Две краткие лекции по науке
Только в 1961 году, через 90 лет после их первой публикации, "Лекции" Твена вместе с другими его статьями, очерками и рассказами...
Лекции Содержание лекции Курсовая работа 1 01. 09 1 0 3 iconЛекции Тема Специфика, проблемы и генезис философии -2 часа. План лекции: Специфика и функции философии
Охватывает сферы права, морали и нравственности (семья, гражданское общество, государство), учение об абсолютном духе – стремится...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org