Рабочая программа рассмотрена и одобрена на заседании кафедры вычислительной техники (протокол № от 20 г.). Зав кафедрой вычислительной техники icon

Рабочая программа рассмотрена и одобрена на заседании кафедры вычислительной техники (протокол № от 20 г.). Зав кафедрой вычислительной техники


Смотрите также:
Рабочая программа учебной дисциплины ф тпу 1-21...
Рабочая программа по дисциплине «Технологии программирования» (наименование дисциплины)...
Рабочая программа по дисциплине «Надежность информационных систем» (наименование дисциплины)...
Рабочая программа по дисциплине “Дискретная математика” для специальности 230105 (220400)...
Теория автоматов...
Компьютерная арифметика...
Архитектура современных ЭВМ...
Методы проектирования ЭВМ...
Периферийные устройства и интерфейсы ЭВМ...
Рабочая программа дисциплины Языки...
Лекция №2 «История развития вычислительной техники»...
Рабочая программа по дисциплине: «групповое проектное обучение» Для специальностей...



Загрузка...
скачать


ТИТУЛЬНЫЙ ЛИСТ СМ. В МАКЕТЕ РАБОЧЕЙ ПРОГРАММЫ С ПОЯСНЕНИЯМИ


Рабочая программа составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования направления подготовки дипломированного специалиста 230100 (654600) «Информатика и вычислительная техника», специальности 230105 (220400) «Программное обеспечение вычислительной техники и автоматизированных систем», утвержденным 27 марта 2000 г. (Регистрационный номер 224 тех/дс).


Составитель:

доцент кафедры

вычислительной техники Л.А. Павлов


Рабочая программа рассмотрена и одобрена на заседании кафедры вычислительной техники (протокол № _____ от ___________________20____ г.).


Зав. кафедрой

вычислительной техники,

профессор Б.М. Калмыков


Рабочая программа согласована с методической комиссией факультета информатики и вычислительной техники.


Председатель комиссии,

доцент Л.А. Павлов


Декан ФИВТ, профессор Б.М. Калмыков


Начальник УМУ Н.А. Иванова

^

1.ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ




1.1.Цель преподавания дисциплины



Цель преподавания дисциплины – знакомство с основными структурами данных, алгоритмами их создания и обработки, методами теоретического и экспериментального анализа алгоритмов для определения их сложности, приобретение практических навыков в реализации этих структур и алгоритмов в прикладных программах.

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

^

1.2.Задачи преподавания дисциплины



Задачами преподавания дисциплины являются:

  • развитие навыков применения основных структур данных и типовых алгоритмов их создания и обработки; определения теоретической и экспериментальной оценок временной и емкостной сложности алгоритмов; выбора структур данных при проектировании алгоритмов с целью повышения их эффективности;

  • выработать представление о возможностях конкретной системы программирования в плане реализации различных структур данных и об эффекте, достигаемом при применении структур и алгоритмов в программировании;

  • сформировать умение правильно выбирать структуры данных при проектировании алгоритмов с целью повышения эффективности алгоритмов, реализовать их в конкретной системе программирования;

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



^

1.3.Место дисциплины в профессиональной подготовке специалиста



Настоящая программа по дисциплине «Структуры и алгоритмы обработки данных» предназначена для подготовки специалистов по специальности 230105 «Программное обеспечение вычислительной техники и автоматизированных систем» в соответствии с требованиями, отраженными в Государственном образовательном стандарте специальности, утвержденном 27 марта 2000 г. (Регистрационный номер 224 тех/дс).

ГОС ВПО устанавливает общую трудоемкость дисциплины 210 часов и предъявляет следующие требования к содержанию дисциплины:

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

Дисциплина тесно связана с такими дисциплинами специальности как «Программирование на языке высокого уровня», «Дискретная математика», «Математическая логика и теория алгоритмов» и другие.

^

1.4.Требования к уровню освоения содержания дисциплины



В результате изучения дисциплины студенты должны:

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

  • уметь правильно выбирать структуры данных при проектировании алгоритмов с целью повышения эффективности алгоритмов, реализовать их в конкретной системе программирования;

  • иметь представление о возможностях конкретной системы программирования в плане реализации различных структур данных и об эффекте, достигаемом при применении структур и алгоритмов в программировании;

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



^

2.СОДЕРЖАНИЕ ДИСЦИПЛИНЫ




2.1.Темы и краткое содержание лекций



Введение (2 часа)


Предмет дисциплины, ее объем, содержание и связь с другими дисциплинами учебного плана. Цели и задачи дисциплины. Алгоритмизация как основная стадия проектирования прикладных программ. Временная и емкостная сложности. Общие принципы анализа алгоритмов.


  1. Стандартные структуры данных (16 часов)


Понятие данных. Примитивные данные. Абстрактные типы данных.

Последовательности. Последовательное распределение. Характеристические векторы. Связанное распределение. Разновидности связанных списков.

Стеки, очереди. Последовательное и связанное представление стеков и очередей. Очередь с приоритетами.

Деревья. Уровни узлов, высота дерева, длины внутренних и внешних путей. Бинарные деревья. Машинные представления деревьев. Прохождения деревьев. Прямой, обратный, симметричный (для бинарных деревьев) и горизонтальный порядки прохождения деревьев.

Множества и мультимножества и их представление.


  1. Исчерпывающий поиск (10 часов)


Поиск с возвратом. Оценка сложности выполнения. Способы программирования. Метод ветвей и границ. Теоретическая и экспериментальная оценка эффективности поиска с возвратом. Метод Монте-Карло.

Методы решета. Нерекурсивное модульное решето. Рекурсивное решето.

Приближения исчерпывающего поиска.



  1. Генерация элементарных комбинаторных объектов (6 часов)


Генерация перестановок. Лексикографический порядок. Циклические перестановки. Транспозиция смежных элементов. Случайные перестановки.


  1. Поиск (17 часов)


Последовательный поиск.

Логарифмический поиск в статических таблицах. Бинарный поиск. Равномерный поиск. Поиск Фибоначчи. Интерполяционный поиск.

Логарифмический поиск в динамических таблицах. Деревья бинарного поиска (ДБП). Бинарный поиск. Операции включения и исключения для ДБП. Случайные деревья бинарного поиска (СДБП). Бинарные деревья, сбалансированные по высоте (АВЛ-деревья): балансировка, включение и исключение. Красно-черные деревья: балансировка, включение и исключение. В-деревья. 2-3-деревья.

Цифровой поиск.

Методы вычисления адреса. Хеширование и его варианты. Хеш-функции. Разрешение коллизий: метод открытой адресации, метод цепочек.


  1. Сортировка (17 часов)


Внутренняя сортировка. Классификация алгоритмов внутренней сортировки. Нижние оценки эффективности алгоритмов сортировки. Сортировка вставками. Сортировка с убывающим шагом (сортировка Шелла). Обменная сортировка: пузырьковая сортировка, быстрая сортировка. Сортировка выбором: простая и пирамидальная сортировки. Сортировка подсчетом. Сортировка распределяющим подсчетом. Сортировка слиянием. Распределяющая сортировка.

Внешняя сортировка. Порождение отрезков. Слияние.

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


  1. Алгоритмы на графах (17 часов)


Представления графов: матрица смежности, матрица весов, список ребер, структура смежности. Поиск в глубину. Поиск в ширину. Остовные деревья графа. Построение остовных деревьев. Минимальное остовное дерево.

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

Фундаментальные множества циклов и их отыскание.

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

^

2.2.Темы лабораторных занятий







п/п

Тема работы

Часы

всего

ауд.

самост.

1

Стеки. Очереди.

12

4

8

2

Деревья. Бинарные деревья.

16

6

10

3

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

19

7

12

4

Исследование методов поиска.

20

6

14

5

Исследование методов сортировки.

16

6

10

6

Алгоритмы на графах.

12

5

7




Итого

95

34

61



^

2.3.Самостоятельная работа студента



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

Самостоятельная работа студентов включает в себя

  • подготовка к выполнению и защите лабораторных работ;

  • курсовое проектирование;

  • подготовка к зачетам и экзаменам.



^

2.4.Содержание курсового проектирования



Целью курсовой работы является закрепление теоретических знаний, полученных по данному курсу и смежным дисциплинам, и приобретение практических навыков формализации поставленной задачи, создания и использования эффективных структур данных и алгоритмов в прикладных задачах, теоретических и экспериментальных оценок эффективности алгоритмов. Алгоритмы реализуются в виде программы для ПЭВМ.

При выполнении курсовой работы студент должен уметь

  • формализовать поставленную задачу (перейти от словесной неформальной постановки задачи к математической формулировке);

  • приспосабливать общие методы и алгоритмы решения классов задач к решению конкретной задачи;

  • проводить сравнительную оценку различных вариантов с целью выбора наиболее эффективных структур данных и алгоритмов их обработки;

  • исследовать и оценивать теоретически (аналитически) и экспериментально методы сокращения перебора в комбинаторных задачах;

  • оценивать аналитически и экспериментально эффективность предложенных в работе алгоритмов (временную и емкостную сложности);

  • программно реализовать разработанные алгоритмы на одном из алгоритмических языков программирования;

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

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

Название темы курсовой работы – «Исследование методов поиска с возвратом». В качестве индивидуального задания на курсовое проектирование студенту предлагается комбинаторная задача. Задания могут быть связаны с инженерными или информационными задачами, решением различных головоломок и т.п. Постановка задачи должна быть неформальной, чтобы вопросы математической формализации поставленной задачи решались студентом в процессе курсового проектирования. Не должны задаваться также структуры данных для программной реализации алгоритмов решения  все эти вопросы должны решаться студентом.

Выбор комбинаторных задач в качестве заданий на курсовое проектирование в немалой степени обусловлен следующим. Непосредственное применение хорошо известных общих методов решения таких задач обычно приводит к алгоритмам, время работы которых недопустимо велико. Методы должны быть хорошо приспособлены к конкретной задаче, чтобы в результате алгоритм стал пригодным для практического использования. Это в большинстве случаев потребует от студента большой изобретательности для сокращения перебора.

Класс комбинаторных задач характеризуется тем, что в них рассматриваются задачи на существование, эффективное построение, перечисление и оптимизацию объектов, образованных из сравнительно большого числа элементов. Такие задачи обычно требуют исчерпывающего поиска множества всех возможных решений, а алгоритмы решения имеют экспоненциальную временную сложность. Одним из общих методов организации такого поиска является поиск с возвратом (backtrack), который можно взять за основу для решения поставленной перед студентом задачи. Если на курсовое проектирование поставлена задача поиска оптимального решения, то можно воспользоваться хорошо известным вариантом поиска с возвратом, называемым методом ветвей и границ.

^

2.5.Примерный перечень вопросов к зачетам и экзаменам





  1. Представление последовательностей.

  2. Характеристические векторы.

  3. Связное распределение. Разновидности связных списков.

  4. Организация стеков.

  5. Организация очередей.

  6. Деревья. Машинные представления деревьев.

  7. Уровни узлов, высота дерева, длины внутренних и внешних путей.

  8. Прохождения деревьев.

  9. Бинарные деревья. Естественное соответствие бинарных деревьев и деревьев общего вида.

  10. Прямое прохождение бинарных деревьев.

  11. Обратное прохождение бинарных деревьев.

  12. Симметричное прохождение бинарных деревьев.

  13. Горизонтальное прохождение бинарных деревьев.

  14. Прохождение бинарного дерева, соответствующее горизонтальному прохождению леса.

  15. Прошитые деревья. Прохождения прошитых деревьев.

  16. Общий алгоритм поиска с возвращением.

  17. Оценка сложности выполнения поиска с возвращением. (метод Монте-Карло).

  18. Способы программирования поиска с возвращением.

  19. Метод ветвей и границ.

  20. Эффективный метод решения задачи коммивояжера.

  21. Метод ветвей и границ для решения игровых задач.

  22. Эвристические методы решения задачи поиска с возвращением.

  23. Методы решета. Нерекурсивное модульное решето.

  24. Методы решета. Рекурсивное решето.

  25. Порождение элементарных комбинаторных объектов.

  26. Порождение перестановок в лексикографическом порядке.

  27. Порождение перестановок транспозицией смежных элементов.

  28. Последовательный поиск.

  29. Бинарный поиск в статических таблицах.

  30. Равномерный бинарный поиск.

  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. Частичная сортировка. Задача выбора.

  65. Частичная сортировка. Прямое и бинарное слияние.

  66. Представления графов.

  67. Поиск в глубину.

  68. Поиск в ширину.

  69. Построение остовных деревьев. DFS-дерево. BFS-дерево.

  70. Минимальное остовное дерево. Алгоритм Краскала.

  71. Минимальное остовное дерево. Алгоритм Дейкстры-Прима.

  72. Остовное дерево орграфов.

  73. Поиск связных компонент графа.

  74. Топологическая сортировка.

  75. Определение двусвязных компонент графа.

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

  77. Поиск фундаментальных множеств циклов.

  78. Транзитивное замыкание.

  79. Кратчайшие пути от фиксированной вершины.

  80. Кратчайшие пути между всеми парами вершин графа.



^

2.6.Программное обеспечение



Любая система программирования на алгоритмическом языке типа Паскаль, Си.

3.Распределение часов по темам и видам ЗАНЯТИЙ







п/п

Тема занятия

Всего

часов

Виды занятий

Самост.

работа

лекц.

практ.

лабор.

всего

из них

курс. работа.

1

Введение

2

2













2

Стандартные структуры данных

50

16




10

24

6

3

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

39

10




7

22

10

4

Генерация элементарных комбинаторных объектов

8

6







2

2

5

Поиск

41

17




6

18

4

6

Сортировка

37

17




6

14

4

7

Алгоритмы на графах

33

17




5

11

4




Итого

210

85




34

91

30



^

4.Учебно-методическое обеспечение дисциплины







п/п

Название

Наличие

в библ.
Основная литература

1

Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М.: Вильямс, 2003 и др. года. 384 с.

7+Э

2

Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989. 360 с.

8

3

Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981. 366 с.

9

4

Кнут Д. Искусство программирования для ЭВМ. Т. 1. Основные алгоритмы. М.: Мир, 1976. 735 с.

18+Э

5

Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. М.: Мир, 1978. 844 с.

32+Э

6

Липский В. Комбинаторика для программистов. М.: Мир, 1989. 213 с.

6

7

Павлов Л.А. Структуры и алгоритмы обработки данных. Алгоритмы на графах: Конспект лекций/Чуваш. ун-т. Чебоксары, 2001. 48 с.

150

8

Павлов Л.А. Структуры и алгоритмы обработки данных в ЭВМ: Методы быстрого поиска: Конспект лекций/Чуваш. ун-т. Чебоксары, 1995. 40 с.

150

9

Павлов Л.А. Структуры и алгоритмы обработки данных в ЭВМ: Методы сортировки: Конспект лекций/Чуваш. ун-т. Чебоксары, 1996. 44 с.

150

10

Структуры и алгоритмы обработки данных в ЭВМ: Метод. указания к курсовому проектированию/Сост. Л.А.Павлов; Чуваш. ун-т. Чебоксары, 1998. 28 с.

150

11

Структуры и алгоритмы обработки данных: Метод. указания к лабораторным занятиям/Сост. Л.А.Павлов; Чуваш. ун-т. Чебоксары, 2002. 52 с.

150
Дополнительная литература

12

Арсак Ж. Программирование игр и головоломок. М.: Мир, 1990. 220 с.

8

13

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

5

14

Бежанова М.М., Москвина Л.А., Поттосин И.В. Практическое программирование. Структуры данных и алгоритмы. М.: Логос, 2001. 224 с.

4

15

Вирт Н. Алгоритмы+структуры данных=программы. М.:Мир, 1985. 406 с.

3

16

Грин Д., Кнут Д. Математические методы анализа алгоритмов. М.: Мир, 1987. 120 с.

4+Э

17

Евстигнеев В.А. Применение теории графов в программировании./Под ред. А.П. Ершова. М.: Наука, 1985. 352 с.

1

18

Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003. 1104 с.




19

Кнут Д. Искусство программирования. В 3-х томах. М.: Вильямс, 2000.–Т1–720 с., Т2–832 с., Т3–832 с.




20

Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: изд-во МЦНМО, 2000. 960 с.

1+Э

21

Кубенский А.А. Структуры и алгоритмы обработки данных: объектно-ориентированный подход и реализация на С++. СПб.: БХВ-Петербург, 2004. 464 с.




22

Лэнгсам Й., Огенстайн М., Тененбаум А. Структуры данных для персональных ЭВМ. М.: Мир, 1989. 567 с.

4

23

Макконелл Д. Анализ алгоритмов. Вводный курс. М:Техносфера, 2002. 304 с.




24

Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. 476 с.

1

25

Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984. 455 с.

3

26

Уэзерелл Ч. Этюды для программистов. М.: Мир, 1982. 287 с.

5

27

Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си. М.: Финансы и статистика, 2004. 464 с.





Примечание: Буквой «Э» обозначено наличие электронного варианта книги на сервере кафедры вычислительной техники, доступной всем студентам.






Скачать 180,46 Kb.
оставить комментарий
Л.А. Павлов
Дата04.03.2012
Размер180,46 Kb.
ТипРабочая программа, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх