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

Министерство образования Российской Федерации Санкт-Петербургский государственный электротехнический университет “ЛЭТИ”

РАБОЧАЯ ПРОГРАММА Дисциплины “СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ” Для подготовки дипломированных специалистов по направлениям: 1) 657100 –“ПРИКЛАДНАЯ МАТЕМАТИКА” по специальности 073000 – “ПРИКЛАДНАЯ МАТЕМАТИКА” 1) 654600 – “ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА” по специальности 220400 – “ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И АВТОМАТИЗИРОВАННЫХ СИСТЕМ” Для подготовки бакалавров по направленям: 510200 – “ПРИКЛАДНАЯ МАТЕМАТИКА И ИНФОРМАТИКА” 552800 – “ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА”

Санкт-Петербург 2000

Санкт-Петербургский государственный электротехнический университет “ЛЭТИ” “УТВЕРЖДАЮ” Проректор по учебной работе проф. ___________ Ушаков В.Н. РАБОЧАЯ ПРОГРАММА Дисциплины “СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ” Для подготовки дипломированных специалистов по направлениям: 2) 657100 –“ПРИКЛАДНАЯ МАТЕМАТИКА” по специальности 073000 – “ПРИКЛАДНАЯ МАТЕМАТИКА” 2) 654600 – “ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА” по специальности 220400 – “ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И АВТОМАТИЗИРОВАННЫХ СИСТЕМ” Для подготовки бакалавров по направленям: 510200 – “ПРИКЛАДНАЯ МАТЕМАТИКА И ИНФОРМАТИКА” 552800 – “ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА” Факультет компьютерных технологий и информатики (ФКТИ) Кафедра математического обеспечения и применения ЭВМ (МО ЭВМ) Курс – 2 Семестры – 3,4 Лекции

Экзамен – 3, 4

семестр

3 семестр 4 семестр

78 ч. 48 ч. 30 ч.

Курсовое проектирование 3 семестр 4 семестр

31 ч. 16 ч. 15 ч.

Курсовая работа – 3, 4

семестр

Аудиторные занятия Самостоятельные занятия Всего часов

109 ч. 101 ч. (число часов из учебного плана) 210 ч. 2000 2

Рабочая программа обсуждена на заседании кафедры МО ЭВМ “_15_”___июня___2000г., протокол №_5_. Рабочая программа составлена в соответствии с государственным образовательным стандартом по направлению 654600 – “ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА” по специальности 220400 – “ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И АВТОМАТИЗИРОВАННЫХ СИСТЕМ” Рабочая программа согласована с рабочими программами изученных ранее дисциплин: 1) Информатика (1 семестр) 2) Программирование (1 и 2 семестры) 3) Дискретная математика (2 семестр) 4) Математическая логика и теория алгоритмов (3 семестр)

Рабочая программа утверждена на методической комиссии ФКТИ “_15_”__июня_____2000г.

3

Цель и задачи дисциплины Целью дисциплины «Структуры и алгоритмы обработки данных» является изучение применяемых в программировании (и информатике) структур данных, их спецификации и реализации, алгоритмов обработки данных и анализа этих алгоритмов, взаимосвязь алгоритмов и структур данных. Задачи дисциплины: • Сформировать базовые теоретические понятия, лежащие в основе процесса разработки алгоритмов и структур данных. • Заложить в основу конструирования и использования сложных (динамических) структур данных модель (парадигму) абстрактного типа данных (спецификация+представление+реализация). • Сформировать представления и знания об основных классах алгоритмов (исчерпывающий поиск, быстрый поиск, сортировки, алгоритмы на графах и т.п.), используемых в них структурах данных и общих схемах решения задач на их основе. • Научить реализации типовых алгоритмов и структур данных и их модификаций на выбранном рабочем языке программирования (Турбо Паскаль, С++) • Сформировать представления и знания об анализе сложности алгоритмов и программ.

• •

• • • • • •

Требования к уровню освоению содержания дисциплины В результате изучения дисциплины студенты должны (a) Знать: основные методы разработки машинных алгоритмов и программ, структуры данных, используемые для представления типовых информационных объектов, основные задачи анализа алгоритмов; основные машинные алгоритмы и характеристики их сложности для типовых задач, часто встречающихся и ставших «классическими» в области информатики и программирования; (b) Уметь: разрабатывать алгоритмы, используя изложенные в курсе общие схемы, методы и приемы построения алгоритмов, выбирая подходящие структуры данных для представления информационных объектов; доказывать корректность составленного алгоритма и оценивать основные характеристики его сложности; реализовывать алгоритмы и используемые структуры данных средствами языков программирования высокого уровня (например, на Турбо Паскале); экспериментально (с помощью компьютера) исследовать эффективность алгоритма и программы; (c) Иметь представление о: некоторых математических методах анализа алгоритмов; классификации алгоритмических задач по их сложности, сводимости алгоритмических задач к известным задачам определенного класса сложности. 4

Содержание рабочей программы Введение Предмет дисциплины и ее задачи. Связь с другими дисциплинами учебного плана направления и специальности. Тема 1. Линейные структуры данных Структуры данных и алгоритмы. Стек, очередь и дек как линейные списки (последовательности) с ограниченными наборами операций (доступа). Стек, очередь и дек как абстрактные типы данных: функциональные спецификации и аксиомы. Представление и реализация (непрерывная, ссылочная в связанной памяти и на базе вектора). Примеры алгоритмов, использующих стек, очередь, дек. Тема 2. Рекурсивная обработка иерархических списков Рекурсивное определение и функциональная спецификация линейных списков. Рекурсивное определение и функциональная спецификация иерархических (нелинейных) списков и S-выражений. Базовые функции (индикаторы, селекторы, конструкторы). Точечная форма записи S-выражений. Записи с вариантами в языках высокого уровня. Представление Sвыражений и реализация базовых функций на языках высокого уровня. Элементы функционального программирования и рекурсивная обработка S-выражений на языках высокого уровня. Примеры использования нелинейных списков: дифференцирование символических выражений, действия с полиномами многих переменных. Тема 3. Деревья и леса Определение дерева, леса, бинарного дерева. Графическое и текстовое (скобочное) представление леса. Спецификация дерева, леса, бинарного дерева: базовые функции и аксиомы. Естественное соответствие бинарного дерева и леса. Обходы бинарных деревьев: рекурсивные и не рекурсивные алгоритмы. Обходы дерева или леса. Представления и реализации бинарных деревьев: ссылочная реализация в связанной памяти, ссылочная реализация ограниченного бинарного дерева на базе вектора. Прошитые бинарные деревья: представление, обход, включение. Пример использования бинарных деревьев в задаче упаковки сообщений: префиксные коды и бинарные деревья, метод кодирования Фано-Шеннона, критерий оптимальности кода, алгоритм кодирования (сжатия) информации по 5

Хаффмену (построение дерева, кодирование и декодирование), доказательство оптимальности кода Хаффмена, неравенство Крафта, теорема кодирования в отсутствие шума (энтропийная оценка средней длины кода). Динамическое кодирование по Хаффмену. Тема 4. Исчерпывающий поиск Поиск с возвращением (backtracking). Общий алгоритм. Пример: задача о ферзях. Усовершенствования. Оценка сложности выполнения: метод МонтеКарло. Другие способы программирования поиска с возвращением: рекурсия и использование макросредств. Метод ветвей и границ. Общая схема. Задача коммивояжера: решение методом ветвей и границ. Эвристические методы: ближайшего соседа, ближайшего города. Оценки приближения. Динамическое программирование. Пример (кратчайший путь в слоистой сети) и общая идея. Задача определения порядка умножения цепочки матриц. Тема 5. Быстрый поиск Поиск и другие операции над таблицами. Последовательный и бинарный поиск. Бинарные деревья поиска. Случайные бинарные деревья поиска. Подсчет числа структурно различных бинарных деревьев с заданным числом узлов. Среднее время поиска в случайных деревьях. Рандомизированные бинарные деревья поиска (Treaps). Оптимальные бинарные деревья поиска. Алгоритм построения оптимального дерева. Хорошие бинарные деревья поиска. Сбалансированные по высоте бинарные деревья (АВЛ-деревья). Включение в АВЛ-дерево. Исключение из АВЛ-дерева. Оценка сложности в худшем случае: деревья Фибоначчи. Реализация упорядоченных линейных списков на базе АВЛ-деревьев или рандомизированных деревьев. Операции поиска, вставки и удаления элементов; операции сцепления и расщепления списков. 2-3-деревья. Б-деревья. Метод поиска с использованием функции расстановки (хеширование). Разрешение коллизий: метод внутренних и внешних цепочек, метод открытой адресации. Коэффициент загрузки, оценки сложности. Выбор функции расстановки. Задача поиска подстроки. Алгоритм Кнута-Мориса-Пратта. Алгоритм Боуера-Мура. Тема 6. Сортировка Задача сортировки (внешней и внутренней). Сортировка вставками, обменами, выбором.

6

Быстрая сортировка Хоара. Процедура разделения. Рекурсивный и не рекурсивный алгоритмы быстрой сортировки. Анализ сложности. Оптимизация программы (неполная сортировка). Пирамидальная сортировка (HeapSorting): турнирная сортировка, построение пирамиды и полное упорядочение. Анализ сложности алгоритма. Распределяющая (поразрядная) сортировка. Сравнение алгоритмов и программ внутренней сортировки. Нижняя граница сложности задачи сортировки. Оптимальная сортировка. Внешняя сортировка. Простое слияние. Естественное слияние. Задача поиска медианы: алгоритм Хоара, линейный алгоритм. Анализ сложности. Тема 7. Алгоритмы на графах Графы: определения и примеры. Упорядоченный граф. Представления графов: матрица инциденций, матрица смежности, список пар, структура смежности (списки инцидентности). Преобразования представлений. Остовные деревья графа. Минимальное остовное дерево. Теорема "о минимальном ребре". Жадный алгоритм (Краскал). Алгоритм "ближайшего соседа" (Прим, Дейкстра). Поиск в графе: алгоритм пометок. Поиск в ширину. Поиск в глубину. Связные компоненты. Алгоритм сложности О(m*log n) построения минимального остова. Построение и свойства остовных деревьев при поиске в глубину и в ширину. Поиск в глубину и топологическая сортировка. Нахождение компонент двусвязности: точки сочленения графа и их свойства в глубинном остовном дереве. Алгоритм нахождения компонент двусвязности. Сильная связность. Поиск в глубину в орграфе. Алгоритм нахождения сильно связных компонент. Клики. Алгоритм порождения клик графа. Кратчайшие пути в графе. Кратчайшие пути от фиксированной вершины. Случай неотрицательных весов: алгоритм Дейкстры. Алгоритм ФордаБеллмана. Кратчайшие пути в бесконтурном графе. Кратчайшие пути между всеми парами вершин. Матрица смежности, матрица достижимости и транзитивное замыкание отношения, алгоритм Уоршалла. Алгоритм Флойда-Уоршалла вычисления расстояний между всеми парами вершин, одновременное построение путей. Тема 8. NP-полные и труднорешаемые задачи Массовая и индивидуальная задачи. Сложность алгоритма и кодирование входных и выходных данных. Полиномиальные алгоритмы и класс P. Недетерминированные алгоритмы и класс NP. Различные формы постановки задач комбинаторной оптимизации: оптимизационная, вычислительная, форма распознавания. Примеры. 7

Полиномиальная преобразуемость задач. NP-трудные и NP-полные задачи. Задача о выполнимости булева выражения, представленного в конъюнктивной нормальной форме. Доказательство NP-полноты задачи о выполнимости. Преобразуемость задачи о выполнимости в задачу о 3-выполнимости. Полиномиальность задачи о 2-выполнимости. Задача о клике графа. Преобразуемость задачи о 3-выполнимости в задачу о клике. Задача о многопроцессорном расписании (МПР). Преобразуемость задачи о клике в задачу о МПР. Задача о 0-1-рюкзаке и криптография. Практическое решение NP-полных задач. Цели и содержание курсового проекта (работы) и его ориентировочная трудоемкость 3 семестр Цель: 1) реализация основных структур данных (стек, очередь, дек, нелинейные списки, деревья и леса) и алгоритмов с их использованием; 2) реализация схемы исчерпывающего поиска (поиск с возвращением, метод ветвей и границ, динамическое программирование) на конкретных задачах. Содержательно курсовая работа состоит в выполнении 4-х последовательных заданий: 1) реализация стека, очереди, дека и алгоритма с их использованием; 2) реализация иерархических списков и алгоритмов их обработки; 3) реализация бинарных деревьев и алгоритмов их обработки; 4) решение задачи с применением схемы исчерпывающего поиска (backtracking, метод ветвей и границ, динамическое программирование), машинное исследование реализованного алгоритма (например, методом Монте-Карло); Ориентировочная трудоемкость 16 часов самостоятельной работы, 16 часов работы за компьютером в лаборатории кафедры и консультаций с преподавателем. 4 семестр Цель: реализация алгоритмов быстрого поиска, сортировки, алгоритмов на графах и их машинное исследование. Содержательно курсовая работа состоит в выполнении 2-х последовательных заданий: 1) задания по быстрому поиску (деревья поиска различного вида, хеширование), сжатию данных (оптимальное кодирование), алгоритмам сортировки; 2) задание по алгоритмам на графах (реализация и модификация известных алгоритмов, генерация тестовых данных и исследование на них характеристик алгоритмов, визуализация работы алгоритмов на графах). Ориентировочная трудоемкость 15 часов самостоятельной работы, 15 часов работы за компьютером в лаборатории кафедры и консультаций с преподавателем. 8

Расчет учебных часов по видам занятий № темы

Название разделов и тем

Объём учебных часов

Семестр

Лекции

Аудиторные занятия по к/р)

Самостоятельная работа

Всего

Введение

1

1

0

1

3

Тема 1

Линейные структуры данных

4

4

3

7

3

Тема 2

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

6

6

5

11

3

Тема 3

Деревья и леса

10

10

8

18

3

Тема 4

Исчерпывающий поиск

8

8

7

15

3

Тема 5

Быстрый поиск

10

10

9

19

3

Тема 6

Сортировка

9

9

8

17

3

Тема 7

Курсовое проектирование, 1 Алгоритмы на графах

18

16 18

16 18

32 36

3 4

12

12

12

24

4

15 64 45 109

15 56 45 101

30 120 90 210

4

48 30 78

Тема 8

NP-полные и труднорешаемые задачи Курсовое проектирование, 2 ИТОГО за 3 семестр: ИТОГО за 4 семестр: ИТОГО:

9

ЛИТЕРАТУРА Основная Лек ции

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

К-во экз. в библ. (на кафедре)

Гриф

№

Название, библиографическое описание

1

Алексеев А.Ю., Ивановский С.А., Куликов Д.В. Динамические структуры данных. Практикум по программированию/ ГЭТУ. СПб., 1997. Опалева Э.А., Самойленко В.П. Технология программирования: Учеб.пособие/ГЭТУ. –С.-Пб., 1995. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.- М.: Мир, 1979. Ахо Альфред В., Хопкрофт Джон, Ульман Джеффри Д. Структуры данных и алгоритмы: Пер. с англ.: Уч.пос.- М.: Издательский дом “Вильямс”, 2000. Бауэр Ф.Л., Гооз Г. Информатика. Вводный курс: В 2 ч.М.:Мир, 1990.

3

3

ГК РФ по выс. обр.

3

3

3,4

4

3,4

3,4

ГК РФ по выс. обр. МВ и ССО СССР Мин. обр. РФ

3

3

Вирт Н. Алгоритмы + структуры данных = программы.- М.: Мир, 1985. (Алгоритмы и структуры данных.- М.: Мир, 1989.) (Алгоритмы и структуры данных. – СПб.: Невский Диалект, 2001. (2-е изд., испр.)) Кнут Д. Искусство программирования для ЭВМ. Том 1: Основные алгоритмы.- М.: Мир, 1976. (3-е изд.: Уч.пос.М.:Издательский дом “Вильямс”, 2000.) Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск.- М.: Мир, 1978. (2-е изд.: Уч.пос.М.:Издательский дом “Вильямс”, 2000.) Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦМНО, 1999. Липский В. Комбинаторика для программистов.- М.: Мир, 1988.

3

3,4

3

3

Мин. обр. РФ

3,4

3,4

Мин. обр. РФ

3,4

4

Мин. обр. РФ

4

4

Райли Д. Абстракция и структуры данных: Вводный курс.- 3 М.: Мир, 1993.

3

ГК СССР по нар.обр. ГК РФ по выс. обр.

2 3 * 4 * 5 6 * 7 * 8 * 9 * 1 0 * 1 1 *

ГК СССР по нар.обр. Мин. обр. РФ

* Примечание. Книги, указанные в пп.3, 4, 6-13, являются переводами с английского (по этой причине формально не являются учебными пособиями, но, например, книга в позиции 9 – учебник в США), имеют учебный характер, написаны авторитетными специалистами в данной области и соответствуют по содержанию общей направленности данной дисциплины.

10

Дополнительная Название, библиографическое описание 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

К-во экз. в библ. (на кафедре)

Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика.- М.: Мир, 1980. Седжвик Р. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ. – К.: Издательство “ДиаСофт”, 2001. Альсведе Р., Вегенер И. Задачи поиска.- М.: Мир, 1982. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов.- М.: Мир, 1981. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.М.: Мир, 1982. Дал У., Дейкстра Э., Хоор К. Структурное программирование. М.: Мир, 1975. Калинин А.Г., Мацкевич И.В. Универсальные языки программирования. . Семантический подход.- М.: Радио и связь, 1991 Кристофидес Н. Теория графов. Алгоритмический подход.- М.: Мир, 1978. Кушниренко А.Г., Лебедев Г.В. Программирование для математиков: Учеб. пособие для вузов - М.: Наука, 1988. Лекции по теории графов/Емеличев В.А. и др.- М.: Наука. Гл.ред.физ.мат.лит., 1990. Лисков Б., Гатэг Дж. Использование абстракций и спецификаций при разработке программ.- М.: Мир, 1989. Лэнгсам Й., Огенстайн М., Тененбаум А. Структуры данных для персональных ЭВМ. - М.: Мир, 1989. Майкл Ласло. Вычислительная геометрия и компьютерная графика на С++.М.: "Издательство БИНОМ", 1997. Мейер Б., Бодуэн К. Методы программирования: В 2-х томах.- М.: Мир, 1982. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. Свами М., Тхуласираман К. Графы, сети и алгоритмы.- М.: Мир, 1984. Сибуя М., Ямамото Т. Алгоритмы обработки данных.- М.: Мир, 1986. Теория расписаний и вычислительные машины/Под ред.Э.Г.Коффмана.- М.: Наука, 1984. - 335 с. (Серия: "Экономико-математическая библиотека"), (Ульман Дж. Сложность задач упорядочения, гл.4.) Хендерсон П. Функциональное программирование. Применение и реализация. М.: Мир, 1983.

11

Автор: к.т.н., доцент

С.А.Ивановский

Рецензент к.т.н., доцент каф.ВМ-1

Г.М.Коновалов

Зав. кафедрой Математического обеспечения и применения ЭВМ (разработчик программы и держатель учебного плана) Д.т.н., профессор

А.Р.Лисс

Декан факультета Компьютерных технологий и информатики (обеспечивающего дисциплину) Д.т.н., профессор

И.В.Герасимов

Зав. отделом учебной литературы

О.Н.Смирнова

Председатель методической комиссии факультета Компьютерных технологий и информатики (обеспечивающего дисциплину) к.т.н., доцент

Л.А.Чугунов

Руководитель методического отдела, к.т.н., доцент

Л.А.Марасина

12