Структуры и алгоритмы компьютерной обработки данных рабочая программа



Скачать 145.02 Kb.
Дата26.07.2014
Размер145.02 Kb.
ТипРабочая программа
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

УТВЕРЖДАЮ

Декан факультета информатики

_________________ С.П. Сущенко

« » 2010 г.



СТРУКТУРЫ И АЛГОРИТМЫ КОМПЬЮТЕРНОЙ

ОБРАБОТКИ ДАННЫХ

РАБОЧАЯ ПРОГРАММА


Специальность 351500 – МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ И АДМИНИСТРИРОВАНИЕ ИНФОРМАЦИОННЫХ СИСТЕМ

Статус дисциплины:

федеральный компонент специальности

Томск - 2010 г.



ОДОБРЕНО кафедрой теоретических основ информатики
Протокол №05/10 от 01.09.2010
Зав. кафедрой, профессор _________________Ю.Л.Костюк
РЕКОМЕНДОВАНО методической комиссией факультета информатики

Председатель комиссии, профессор _____________________ Б.А.Гладких


“___”_____________2010 г.

Рабочая программа по курсу “Структуры и алгоритмы компьютерной обработки данных” составлена на основе требований Государственного образовательного стандарта высшего профессионального образования по специальности 351500 – МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ И АДМИНИСТРИРОВАНИЕ ИНФОРМАЦИОННЫХ СИСТЕМ, утвержденного 10 марта 2000 г. Общий объем курса 420 часов. Из них: лекции – 140 часов, лабораторные занятия – 70 часов, самостоятельная работа студентов – 210 часов. Экзамен в третьем и четвертом семестрах. Общая трудоемкость курса 8,8 зач. ед.



СОСТАВИТЕЛЬ:

Костюк Юрий Леонидович – доктор технических наук, заведующий кафедрой теоретических основ информатики


  1. Организационно-методический раздел

Выписка

из Государственного образовательного стандарта высшего профессионального образования по специальности 351500 – МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ И АДМИНИСТРИРОВАНИЕ ИНФОРМАЦИОННЫХ СИСТЕМ (квалификация – математик-программист).


ОПД.Ф.01 Структуры и алгоритмы компьютерной обработки данных


Нелинейные структуры данных: классификация; деревья: ориентированные, упорядоченные и бинарные; представление деревьев в памяти компьютера: последовательное и связанное размещение элементов; операции над деревьями; графы и их представление в компьютере; алгоритмы, оперирующие со структурами типа графа; задачи поиска; исчерпывающий поиск: перебор с возвратом, метод ветвей и границ, динамическое программирование; быстрый поиск: бинарный и последовательный поиски в массивах, хеширование; использование деревьев в задачах поиска: бинарные, случайные бинарные, оптимальные и сбалансированные деревья поиска; алгоритмы поиска на графах; задачи сортировки; внутренняя и внешняя сортировки; алгоритмы сортировки; анализ сложности и эффективности алгоритмов поиска и сортировки; файлы: организация и обработка, представление деревьями: B-деревья; теория сложности алгоритмов: NP-сложные и труднорешаемые задачи.


  1. Цель курса

Целью курса является изучение основных алгоритмов работы с дискретными объектами, структур данных и методов их исследования.

  1. Задача учебного курса

формирование устойчивого алгоритмического мышления у студентов; изучение фундаментальных свойств алгоритмов.

  1. Требования к уровню освоения курса

Студент должен знать: основные алгоритмы работы с дискретными объектами, структуры данных и методы их исследования.

Студент должен уметь применять алгоритмы при профессиональной разработке программ.



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

Для изучения курса необходимо знание следующих курсов: программирование, дискретная математика, алгебра и теория чисел.

II. Содержание курса

Часть1. МЕТОДЫ АНАЛИЗА АЛГОРИТМОВ

1.1. Доказательство правильности алгоритмов

Вход и выход алгоритма. Пред- и постусловие. Математическая индукция. Инвариант. Эквивалентность алгоритмов. Поэтапное доказательство сложных алгоритмов.

1.2. Исследование сложности алгоритмов

Представление алгоритмов в командах компьютера и на языке высокого уровня. Временная и емкостная сложности алгоритма. Полиномиальные и экспоненциальные виды функций сложности. Исследование временной сложности в наихудшем и в среднем. Теоремы о рекуррентных соотношениях для сложности. Экспериментальное исследование сложности алгоритмов. Генерация случайных входных данных. Статистическая обработка результатов исследования сложности алгоритмов.

1.3. Структуры данных и методы разработки эффективных алгоритмов

Стеки, очереди, списки, их моделирование с помощью массивов. Представления множеств в виде массивов и списков. Графы и различные способы их представления. Прошитые списки. Выбор наиболее эффективных структур данных. Методы разработки эффективных алгоритмов: "разделяй и властвуй", "балансировка", "жадный метод", "динамическое программирование".

Часть2. СОРТИРОВКА

2.1. Задача сортировки

Дерево решений в задаче сортировки. Минимально возможная трудоемкость в наихудшем. Оптимальные алгоритмы. Инверсии. Перестановки.

2.2. Алгоритмы внутренней сортировки

Простейшие алгоритмы. Алгоритм Шелла. Быстрая сортировка Хоара, оценка его сложности в среднем. Пирамидальная сортировка. Сортировка слиянием. Цифровая сортировка. Цифровая сортировка строк.

2.3. Порядковые статистики

Задача определения k-го элемента. Алгоритм, основанный на быстрой сортировке, его сложность в среднем. Алгоритм, эффективный в наихудшем случае.

2.4. Внешняя сортировка

Особенности задачи сортировки информации на файлах. Сбалансированное слияние. Многофазная сортировка, ее анализ. Особенности практической реализации.

Часть3. ПОИСК

3.1. Поиск в таблицах и массивах

Задача поиска. Поиск в неупорядоченном массиве. Минимально возможная трудоемкость в наихудшем. Дихотомический поиск в упорядоченном массиве. Таблица, как база данных. Иерархическая упорядоченность в таблице. Косвенная адресация. Поиск по нескольким ключам. Включающий поиск. Операции проекции и соединения таблиц, как обобщение поиска.

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

Задача хеширования. Хеш-функция. Хеш-таблица с областью переполнения, поиск, удаление элементов. Хеш-таблица с открытой адресацией, эффективность поиска в среднем. Применение хеш-таблиц в файлах.

3.3. Деревья поиска

Построение случайного дерева. Поиск в случайном дереве, его средняя трудоемкость. Идеально сбалансированные деревья. Удаление элементов из дерева. АВЛ-деревья. Фибоначчиевы деревья, их максимальная высота. Добавление и удаление в АВЛ-дереве. Деревья для задачи объединения множеств. В-деpевья, их пpименение для файлов. 2-3-деревья, их применение для словарей, сцепляемых очередей, очередей с приоритетами. Прошитые словари и очереди.

3.4. Поиск цепочек символов

Алфавит. Цепочка. Автоматные грамматики. Порождение цепочек.Задача распознавания. Конечный автомат (КА), его функционирование. Недетерминированный КА. Регулярные множества и выражения.Распознавание цепочек с помощью КА. Алгоритм распознавания по функции отказов. Алгоритм Бауэра-Мура. Распознавание множества цепочек.

Часть4. КОМБИНАТОРНЫЕ АЛГОРИТМЫ, АЛГОРИТМЫ НА ГРАФАХ

4.1. Поиск решения в комбинаторных задачах

Перебор вариантов. Бэктрекинг, общий алгоритм. Генерация цепочек символов по грамматике.Оптимизационные задачи. Метод ветвей и границ для решения оптимизационных задач. Задача коммивояжера. Оценки трудоемкости. Приближенные решения задачи коммивояжера. Жадный алгоритм ближайшего города и локальная оптимизация, оценки качества решения. Приближенное решение задачи коммивояжера с помощью минимального остова.

4.2. Комбинаторные задачи на графах

Минимальная раскраска графа, переборный алгоритм. Приближенные алгоритмы раскраски графа,основанные на понятии соцветных веpшин. Раскраска методом ветвей и границ. Гамильтонов цикл.Поиск клик в графе. Узельное покрытие.

4.3. Эффективные алгоритмы на графах.

Эйлеров путь в графе. Остовное дерево наименьшей стоимости, алгоритмы Прима и Крускала. Поиск в глубину в неориентированном графе. Выделение компонент связности. Двусвязные компоненты. Сильно связные компоненты. Нахождение кратчайших путей во взвешенном графе, алгоритмы Флойда и Дейкстры. Транзитивное замыкание, алгоритм Воршалла.

Часть5. КОДИРОВАНИЕ

5.1. Коды, информация, энтропия

Канал связи и сообщение. Информация дискретного сообщения. Энтропия. Кодирование. Избыточность. Кодирование Хаффмана. Методы сжатия сообщений.

5.2. Помехоустойчивое кодирование

Коды проверки на четность. Кодовое расстояние, его влияние на свойства кода. Линейные коды, их свойства. Простой и расширенный код Хемминга. Полиномиальная арифметика. Циклические коды, их свойства.

5.3. Случайные числа

Случайная и псевдослучайная последовательность. Линейные конгруэнтные последовательности, их свойства. Дважды случайный датчик. Статистические тесты. Генерирование случайных чисел для произвольных распределений.

5.4. Алгоритмы над сверхдлинными числами

Двоичное представление сверхдлинных целых чисел. Сложение, вычитание и умножение чисел в двоичном виде и в виде машинных слов. Русский крестьянский метод деления двоичных чисел. Деление "в столбик" для чисел в виде машинных слов. Наибольший общий делитель (алгоритм Евклида) для сверхдлинных чисел. Обобщенный алгоритм Евклида, вычисление обратных по модулю чисел. Рекурсивный алгоритм умножения по методу "разделяй и властвуй". Модульная арифметика. Китайская теорема об остатках. Алгоритм Гарнера восстановления чисел по остаткам.

5.5. Криптография

Задачи криптографии. Требования к надежности кода. Шифрование симметричными ключами. Подстановки. Перестановки. Битовые преобразования. Использование случайных последовательностей. Возведение в степень по модулю. Необратимые функции и их применение. Метод Диффи-Хелмана рассылки ключей. Шифрование двумя ключами. Электронная подпись. Метод RSA. Генерация парных ключей в методе RSA. Проверка чисел на простоту.

Часть6. ТЕОРИЯ АЛГОРИТМОВ И NP-ПОЛНЫЕ ЗАДАЧИ

6.1. Модели вычислений и машины Тьюринга

Модель равнодоступной адресной машины (РАМ), ее связь с языком программирова­ния. Машина Тьюринга. Связь машины Тьюринга и РАМ. Детерминированная (ДМТ) и недетерминированная (НМТ) машины Тьюринга. Детерминированное моделирование НМТ.

6.2. Теория алгоритмов

Языки и задачи. Машина Тьюринга, как распознаватель цепочки языка. Тезис Черча. Частичные алгоритмы. Алгоритмически неразрешимые проблемы.

6.3. NP-полнота задачи выполнимости

Классы P и NP задач. Теорема Кука о задаче выполнимости булевых формул. NP-полнота задачи выполнимости.

6.4. Связь NP-полных задач

Задача 3-выполнимости. Раскраска графа. Клики. Узельное покрытие. Гамильтоновы циклы. Задача коммивояжера.

6.5. Связь задач по сложности

NP-трудные задачи. Класс языков P-SPACE. Связь ДМТ и НМТ по емкостной сложности. Связь классов языков P-SPACE, P, NP-полных и NP-трудных.

Лабораторные работы

Лабораторные работы выполняются по ИНДИВИДУАЛЬНЫМ ЗАДАНИЯМ:



1. Сортировка Шелла.
2. Быстрая сортировка Хоара. Рекурсивный вариант.
3. Быстрая сортировка Хоара. Улучшенный вариант с одним рекурсивным вызовом.
4. Пирамидальная сортировка. Рекурсивный вариант.
5. Пирамидальная сортировка. Нерекурсивный вариант.
6. Цифровая сортировка однобайтовых чисел.
7. Цифровая сортировка строк одинаковой длины.
8. Цифровая сортировка строк различной длины.
9. Сортировка слиянием. Рекурсивный вариант.
10. Сортировка слиянием. Нерекурсивный вариант.
11. Вычисление k-го элемента методом Хоара.
12. Внешняя сортировка сбалансированным двухпутевым слиянием.
13. Внешняя многофазная сортировка двухпутевым слиянием.
14. Дихотомический поиск одного элемента массива.
15. Дихотомический поиск всех одинаковых элементов.
16. Хеширование с открытой адресацией. Вставка, поиск элементов.
17. Хеширование, метод цепочек. Вставка, поиск элементов.
18. Хеширование, метод цепочек. Вставка, поиск, удаление элементов.
19. Построение случайного дерева, поиск в дереве.
20. Построение случайного дерева, поиск, удаление вершин в дереве.
21. Построение выровненного дерева, поиск в дереве.
22. Построение выровненного дерева, поиск, удаление вершин в дереве.
23. Построение АВЛ-дерева, добавление вершин.
24. Построение АВЛ-дерева, добавление и удаление вершин.
25. Построение АВЛ-дерева, поиск минимального и максимального элемента.
26. Построение прошитого АВЛ-дерева, поиск соседнего элемента.
27. Построение 2-3-дерева, добавление вершин.
28. Построение 2-3-дерева, добавление и удаление вершин.
29. Построение 2-3-дерева, поиск минимального и максимального элемента.
30. Построение прошитого 2-3-дерева, поиск соседнего элемента.
31. Иерархическая сортировка таблицы.
32. Независимая сортировка ссылками таблицы по двум ключам.
33. Хеширование для независимого поиска в таблице по двум ключам. Добавление и поиск.
34. Хеширование для независимого поиска в таблице по двум ключам. Добавление, поиск и удаление.
35. Вычисление проекции таблицы с помощью иерархической сортировки.
36. Вычисление проекции таблицы с помощью предварительной независимой сортировки по двум ключам.
37. Вычисление проекции таблицы с помощью хеширования.
38. Вычисление соединения двух таблиц по одному ключу. Таблицы отсортированы по этому ключу.
39. Вычисление соединения двух таблиц по одному ключу. Имеется сортировка ссылками таблиц по этому ключу.
40. Вычисление соединения двух таблиц по одному ключу. Имеются хеш-таблицы со ссылками по этому ключу.
41. Детерминированный автомат для грамматики, задаваемой таблицей.
42. Недетерминированный автомат для грамматики, задаваемой списком правил.
43. Простейший алгоритм распознавания подцепочки.
44. Алгоритм распознавания подцепочки, вычисляющий функцию отказов.
45. Алгоритм Бауэра-Мура распознавания подцепочки.
46. Поиск в лабиринте. Рекурсивный вариант.
47. Поиск в лабиринте. Нерекурсивный вариант.
48. Бэктрекинг для какой-либо головоломки.Рекурсивный вариант.
49. Алгоритм порождения всех цепочек автоматной грамматики.
50. Алгоритм порождения всех цепочек КС-грамматики.
51. Задача коммивояжера. Полный перебор, рекурсивный вариант.
52. Задача коммивояжера. Алгоритм ближайшего соседа.
53. Задача коммивояжера. Алгоритм ближайшего города.
54. Задача коммивояжера. Алгоритм, основанный на построении остовного дерева наименьшей стоимости.
55. Минимальная раскраска графа переборным алгоритмом с отсечениями.
56. Минимальная раскраска транзитивно-ориентированного графа.
57. Приближенная раскраска графа методом склеивания соцветных вершин.
58. Поиск гамильтонового цикла переборным алгоритмом.
59. Нахождение наибольшей максимальной клики переборным алгоритмом с отсечениями.
60. Вычисление эйлерова цикла в графе.
61. Остовное дерево наименьшей стоимости, алгоритм Прима.
62. Остовное дерево наименьшей стоимости, алгоритм Крускала.
63. Остовное дерево наименьшей стоимости, алгоритм Крускала с алгоритмом быстрого объединения множеств (сжатие путей).
64. Остовное дерево наименьшей стоимости c предварительным построением пирамиды для весов ребер.
65. Поиск в глубину, выделение компонент связности графа. Рекурсивный вариант.
66. Поиск в глубину, выделение компонент связности графа. Нерекурсивный вариант.
67. Поиск в глубину, выделение компонент сильной связности графа. Рекурсивный вариант.
68. Поиск в глубину, выделение компонент сильной связности графа. Нерекурсивный вариант.
69. Нахождение всех кратчайших путей в графе.
70. Нахождение кратчайшего пути из одной вершины в графе. Алгоритм Дейкстры.
71. Транзитивное замыкание, алгоритм Воршалла.
72. Транзитивное замыкание, алгоритм Воршалла с использованием битовых операций.
73. Построение кода Хаффмана для символов конкретного текста.
74. Кодирование и декодирование текста заданным неравномерным кодом.
75. Построение кода со сжатием повторяющихся символов. Кодирование и декодирование для этого кода.
76. Линейный случайный датчик и его исследование.
77. Дважды случайный датчик.
78. Датчик для битовых последовательностей.
79. Шифрование и дешифрование случайной последовательностью.
80. Шифрование и дешифрование методом подстановки.
81. Шифрование и дешифрование методом перестановки.
82. Шифрование и дешифрование методом воэведения в степень по модулю.
83. Кодирование и декодирование линейным корректирующим кодом.
84. Кодирование и декодирование кодом Хемминга.
85. Кодирование и декодирование циклическим кодом.
86. Деление длинных чисел "в столбик".
87. Быстрое возведение в степень длинных чисел.
88. Быстрое возведение в степень длинных чисел по модулю.
89. Быстрое умножение длинных чисел рекурсивным разрезанием пополам.
90. Обобщенный алгоритм Евклида для коротких чисел.
91. Проверка делимости сверхдлинного числа на короткие простые числа.

Ш. Распределение часов курса по темам и видам работ



Наименование тем

Всего часов

Аудиторные занятия (час)

Самостоя-

тельная








в том числе

работа







лекции

семинары

лабораторные

занятия





1

Методы анализа алгоритмов

36

14




4

18

2

Сортировка

64

20




12

32

3

Поиск

76

22




16

38

4

Комбинаторные алгоритмы, алгоритмы на графах

84

24




18

42

5

Кодирование

120

40




20

60

6

Теория алгоритмов и NP-полные задачи

40

20






20

ИТОГО




420

140



70

210

IV. Форма итогового контроля
Экзамен по теории и зачет по лабораторным работам
V. Учебно-методическое обеспечение курса

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир,1979.


2. Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985.
3. Галлагер Р. Теория информации и надежная связь. М.: Советское радио, 1974.
4. Гудман С., Хидетмиеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981, 368 с.
5. Дейкстра Э. Дисциплина программирования. М.: Мир, 1978, 275 c.
6. Ершов А.П. Теоретическое программирование.
7. Дэвис Д., Барбер Д., Прайс У., Соломонидес С. Вычислительные сети и сетевые протоколы. М.:Мир, 1982.
8. Кнут Д. Искусство программирования для ЭВМ. Т. 2. Получисленные алгоритмы. М.: Мир, 1977.
9. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. М.: Мир, 1978.
10. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.
11. Рейнгольд Э., Нивергельд Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир,1980, 476 с.

Похожие:

Структуры и алгоритмы компьютерной обработки данных рабочая программа iconРабочая программа дисциплины "структуры и алгоритмы обработки данных"
Рабочая программа составлена в соответствии с государственным образовательным стандартом по направлению
Структуры и алгоритмы компьютерной обработки данных рабочая программа iconУчебное пособие по дисциплине «Структуры и алгоритмы обработки данных» для специальностей «Программное обеспечение информационных технологий»
Структуры и алгоритмы обработки данных: Учеб пособие. – Мн: бнту, 2010. – 151 с.: ил
Структуры и алгоритмы компьютерной обработки данных рабочая программа iconВопросы к экзамену по курсу «Структуры и алгоритмы обработки данных»
Вопросы к экзамену по курсу «Структуры и алгоритмы обработки данных» в 2009-2010 уч году
Структуры и алгоритмы компьютерной обработки данных рабочая программа iconТ. О. Сундукова алгоритмы компьютерной обработки данных учебное пособие
Ваныкина, Г. В., Сундукова, Т. О. В17Алгоритмы компьютерной обработки данных: Учеб пособие / Г. В. Ваныкина, Т. О. Сундукова.– Тула,...
Структуры и алгоритмы компьютерной обработки данных рабочая программа iconУчебное пособие Чебоксары 2008 п 36 Пичугин В. Н
П36 Структуры и алгоритмы компьютерной обработки данных: учеб пособие / В. Н. Пичугин, Р. В. Фёдоров. Чебоксары: Изд-во Чуваш ун-та,...
Структуры и алгоритмы компьютерной обработки данных рабочая программа iconКраткое содержание курса Форматы данных, структура данных Структура программы Подпрограммы, рекурсия
Цели и задачи курса: структуры данных, алгоритмы обработки данных, работа с динамическими структурами, графами
Структуры и алгоритмы компьютерной обработки данных рабочая программа iconСтруктуры и алгоритмы обработки данных
Структура данных работа с элементами которой организована по принципу fifo (первый пришел первый ушел) это
Структуры и алгоритмы компьютерной обработки данных рабочая программа iconВопросы к экзамену по дисциплине "структуры и алгоритмы обработки данных"
Динамическая память. Основные процедуры и функции работы с динамическими переменными
Структуры и алгоритмы компьютерной обработки данных рабочая программа iconПрограмма по курсу информатика и применение компьютеров в научных исследованиях (Алгоритмы и структуры данных) по направлению
Информатика и применение компьютеров в научных исследованиях (Алгоритмы и структуры данных)
Структуры и алгоритмы компьютерной обработки данных рабочая программа iconКурсовая работа "Структуры и алгоритмы обработки данных" вариант 11 студент группы п 64 Ивантеева А. В
Хранящуюся в файле базу данных загрузить в оперативную память компьютера и построить индексный массив, упорядочивающий данные по...
Разместите кнопку на своём сайте:
ru.convdocs.org


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