Учебно-методический комплекс для специальности 1-31 03 07 «Прикладная информатика
жүктеу/скачать 3,71 Mb.
|
УМКАлгор и стр данн Инеттен (1)
|
Сравнительные оценки алгоритмов. Классификация алгоритмов по виду функции трудоёмкости. Асимптотический анализ функций. Оценка О, и др. Элементарные операции в языке записи алгоритмов (следование, ветвление, цикл) Трудоемкость алгоритмов и временные оценки. Примеры анализа простых алгоритмов. Переход к временным оценкам.Пооперационный анализ. Метод Гиббсона. Метод прямого определения среднего времени.Пример пооперационного временного анализа. Теория сложности вычислений, классы сложности задач. Теоретический предел трудоемкости задачи. Задача умножения матриц. Классы P и NP, NP – полные задачи. Примеры. Рекуррентные функции и алгоритмы. Рекуррентные соотношения. Понятие рекуррентного соотношения. Решение рекуррентных уравнений. Примеры рекуррентных уравнений.
Элементарные структуры данных (массивы, списки, стеки, очереди). Связанные списки. Множества. Представление корневых деревьев. Погятие сложных структур данных. 115 Тема 5 Базовые алгоритмы поиска и сортировки. Поиск методом полного перебора. Поиск в упорядоченных списках. Поиск в связных списках. Двоичный поиск. Следящий поиск. Сортировка выбором. Сортировка пузырьком. Алгоритм простыми вставками.
Тема 6 Алгоритмы на графах. Графы. Основные определения. Поиск в глубину и ширину в графе. Пути в графах. Кратчайшие пути. Алгоритм Дейкстры. Минимальные остовные деревья. Алгоритм Борувки. Алгоритм Крускала. Алгоритм Прима. Тема 7 Организация поиска. Деревья. Основные определения. Бинарные поисковые деревья. Сбалансированные деревья. Хеш-таблицы.
Тема 8 Методы разработки алгоритмов. Алгоритмы "разделяй и властвуй". Динамическое программирование. "Жадные" алгоритмы и оптимизационные задачи. 116 УЧЕБНО-МЕТОДИЧЕСКАЯ КАРТА УЧЕБНОЙ ДИСЦИПЛИНЫ Название раздела, темы, занятия; перечень
изучаемых вопросов Количество аудиторных часов Управляемая самостоятельная работа Лабораторные занятия Практические (семинарские) занятия 1 1
2 3 4 2 Понятие структуры данных и алгоритмов Определение алгоритма. Формальные свойства алгоритмов. Понятие структуры данных. Классификация структур данных. Операции над структурами данных. Структурность данных и технология программирования. Абстрактные вычислительные машины
Машина Поста. Маши́наТьюринга,́ детерминированная и недетерминированная машина Тьюринга. Вероятностная машина Тьюринга. Анализ алгоритмов Сравнительные оценки алгоритмов. Классификация алгоритмов по виду функции трудоёмкости. Асимптотический анализ функций. Оценка О, и др. Элементарные операции в языке записи алгоритмов (следование, ветвление, цикл) Трудоемкость алгоритмов и временные оценки Примеры анализа простых алгоритмов. Переход к временным оценкам.Пооперационный анализ. Метод Гиббсона. Метод прямого определения среднего времени.Пример пооперационного временного анализа. 3 4
4 5 2
6 2
7 Эл.
през. 8 [1-4]
2 2 2 Эл. през.
[1-4] 2 2 2 Эл. през.
[1-4] 2 2 2 Эл. през.
[1-6] 117 Формы контроля знаний 9 Опрос,
КСР Опрос, КСР
Опрос, КСР
Опрос, КСР
Номер раздела, темы, занятия
Материальное обеспечение занятия Лекции Литература Продолжение Таблицы «Учебно-методическая карта учебной дисциплины» 1 5
2 Теория сложности вычислений, классы сложности задач Теоретический предел трудоемкости задачи. Задача умножения матриц. Классы P и NP, NP – полные задачи. Примеры.
Рекуррентные функции и алгоритмы Рекуррентные соотношения. Понятие рекуррентного соотношения. Решение рекуррентных уравнений. Примеры рекуррентных уравнений Структуры данных Элементарные структуры данных (массивы, списки, стеки, очереди). Связанные списки. Множества. Представление корневых деревьев. Понятие сложных структур данных Базовые алгоритмы поиска и сортировки Поиск методом полного перебора. Поиск в упорядоченных списках. Поиск в связных списках. Двоичный поиск. Следящий поиск. Сортировка выбором. Сортировка пузырьком. Алгоритм простыми вставками Алгоритмы на графах Поиск в глубину и ширину в графе. Пути в графах. Кратчайшие пути. Алгоритм Дейкстры. Минимальные остовные деревья. Алгоритм Борувки. Алгоритм Крускала. Алгоритм Прима. Организация поиска Деревья. Основные определения. Бинарные поисковые деревья. Сбалансированные деревья. Хеш- таблицы
Методы разработки алгоритмов Алгоритмы "разделяй и властвуй". Динамическое программирование. "Жадные" алгоритмы и оптимизационные задачи.
2
4 5 2
6 2
7 Эл.
през. 8 [1-6]
9 Опрос,
КСР 6 2 2 2 Эл. през.
[1-6] Опрос, КСР
7 4 4 4 Эл. през.
[1-6] Опрос, КСР
8 4 4 4 Эл. през.
[1-6] Опрос, КСР
9 4 4 4 Эл. през.
и [1-6] Опрос, КСР
10 4 4 4 Эл. през.
[1-6] Опрос, КСР
11 4 6 6 Эл. през.
[1-6] Опрос, КСР
118 ИНФОРМАЦИОННО-МЕТОДИЧЕСКАЯ ЧАСТЬ ОСНОВНАЯ ЛИТЕРАТУРА 1. Ахо, А. В. Структуры данных и алгоритмы / А. В. Ахо, Д. Э. Хопкрофт, Д. Д. Ульман. : Учеб. пособие/ пер. с англ. М. : Вильяме, 2000. 384 с. 2. Алгоритмы : построение и анализ / Т. Кормен, и др. М. : Вильяме, 2005. 1296 с.
3. Фундаментальные алгоритмы на C++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ. / Р. Седжвик. - К.: Издательство «ДиаСофт», 2001.- 688 с. 4. Фундаментальные алгоритмы на C++. Алгоритмы на графах: Пер. с англ. / Р. Седжвик. - К.: Издательство «ДиаСофт», 2002.- 688 с. 5. Котов В. М. Разработка и анализ алгоритмов : теория и практика: пособие для студентов мат. и физ. специальностей / В. М. Котов, Е. П. Соболевская. - Минск : БГУ, 2009. - 251 с. ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА 1. Вирт Н. Алгоритмы и структуры данных. / Н. Вирт, М.: Мир, 1989.-360с. 2. Вирт Н. Алгоритмы и структуры данных. / Н. Вирт, СПб.:Невский диалект, 2001.-352с 3. Котов, В. М. Структуры данных и алгоритмы : теория и практика :/ В.М. Котов, Е- П. Соболевская. : учеб. пособие. Минск : БГУ, 2004. 252 с. 4. Головешкин В. А. Теория рекурсии для программистов. / В.А. Головешкин М. В.: Ульянов М.: ФИЗМАТЛИТ, 2006. 296 с.
119 ПЕРЕЧЕНЬ ИСПОЛЬЗУЕМЫХ СРЕДСТВ ДИАГНОСТИКИ РЕЗУЛЬТАТОВ УЧЕБНОЙ ДЕЯТЕЛЬНОСТИ Оценка промежуточных учебных достижений студента также осуществляется по десятибалльной шкале. Для оценки достижений студента используется следующий диагностический инструментарий: – защита выполненных на лаболаторных занятиях индивидуальных заданий;
– проведение текущих контрольных вопросов по отдельным темам; – выступление студента на конференции по подготовленному реферату; – сдача зачета по дисциплине; – сдача экзамена. ПРИМЕРНЫЙ ПЕРЕЧЕНЬ ТЕМ ЛАБОРАТОРНЫХ РАБОТ 1. Работа со структурами данных. Сложные структуры: стеки, очереди, деревья, кучи, контейнеры и т.д. 2. Алгоритмы поиска. 3. Алгоритмы сортировки. 4. Алгоритмы на графах. 5. Поисковые деревья. ПРИЛОЖЕНИЕ 4 ПРОТОКОЛ СОГЛАСОВАНИЯ УЧЕБНОЙ ПРОГРАММЫ (примерная форма) Название учебной
дисциплины, с которой требуется согласование 1. Название кафедры
Предложения об изменениях в содержании учебной программы учреждения высшего образования по учебной дисциплине
кафедрой, разработавшей учебную
программу (с указанием даты и номера протокола)2
по учебной дисциплине. 2 120 ПРИЛОЖЕНИЕ 5 ДОПОЛНЕНИЯ И ИЗМЕНЕНИЯ К УЧЕБНОЙ ПРОГРАММЕ на _____/_____ учебный год №№ пп
Дополнения и изменения Основание Учебная программа пересмотрена и одобрена на заседании кафедры _____________________________ (протокол № ____ от ________ 201_ г.) (название кафедры) Заведующий кафедрой _____________________ _______________ __________________ (ученая степень, ученое звание) (подпись) (И.О.Фамилия) УТВЕРЖДАЮ Декан факультета _____________________ _______________ __________________
(ученая степень, ученое звание) (подпись) (И.О.Фамилия) 121 СПИСОК ЛИТЕРАТУРЫ Основная литература 1. Кнут, Д. Искусство программирования. Том 1. Основные алгоритмы / Д. Кнут. – М.: Вильямс, 2010. – 720 с. 2. Ахо, А. Структуры данных и алгоритмы / А. Ахо, Д. Хопкрофт, Д. Ульман. – М.: Вильямс, 2010. – 400 с. 3. Сэджвик, Р. Алгоритмы на С++ / Р. Сэджвик. – М.: Вильямс, 2014. – 1056 с.
4. Алгоритмы. Построение и анализ / Т. Кормен, и др. – М.: Вильямс, 2013. – 1328 с. 5. Скиена, С. Алгоритмы. Руководство по разработке / С. Скиена. – СПб.: БХВ-Петербург, 2011. – 720 с. 6. Котов, В. М. Алгоритмы и структуры данных: учеб. пособие / В. М. Котов, Е. П. Соболевская, А. А. Толстиков. – Минск: БГУ, 2011. – 267 с.
Дополнительная литература 1. Кормен, Т. Алгоритмы. Вводный курс / Т. Кормен. – М.: Вильямс, 2015. – 208 с. 2. Кнут, Д. Искусство программирования. Том 2. Получисленные алгоритмы / Д. Кнут. – М.: Вильямс, 2011. – 832 с. 3. Кнут, Д. Искусство программирования. Том 3. Сортировка и поиск / Д. Кнут. – М.: Вильямс, 2012. – 824 с. 4. Shaffer, C. Data Structures and Algorithm Analysis, Third Edition / C. Shaffer. – Dover Publications, 2013. – 624 p. 5. Weiss, M. Data Structures and Algorithm Analysis in C++, Fourth Edition / M. Weiss. – Addison-Wesley, 2014. – 656 p. 6. Googrich, M. Data Structures and Algorithms in C++, Second Edition / M. Googrich, R. Tamassia, D. Mount. – John Wiley & Sons, 2011. – 738 p. 7. Carrano, F. Data Abstraction & Problem Solving with C++. Walls and Mirrors, 6th Edition / F. Carrano, T. Henry. – Pearson, 2013. – 840 p. 122 СОДЕРЖАНИЕ 1. МЕТОДОЛГИЯ ТЕОРИИ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ .............................................. 4 ИСТОРИЯ ВОЗНИКНОВЕНИЯ ПОНЯТИЯ «АЛГОРИТМ» ............................................................. 4 ЦЕЛИ И ЗАДАЧИ ТЕОРИИ АЛГОРИТМОВ ........................................................................................ 5 ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ РЕЗУЛЬТАТОВ ТЕОРИИ АЛГОРИТМОВ .......................... 5 ФОРМАЛИЗАЦИЯ ПОНЯТИЯ АЛГОРИТМА ..................................................................................... 6 ФОРМАЛЬНЫЕ СВОЙСТВА АЛГОРИТМОВ..................................................................................... 7 ПОНЯТИЕ СТРУКТУРЫ ДАННЫХ ...................................................................................................... 8 КЛАССИФИКАЦИЯ СТРУКТУР ДАННЫХ ........................................................................................ 9 ОПЕРАЦИИ НАД СТРУКТУРАМИ ДАННЫХ .................................................................................. 10 СТРУКТУРНОСТЬ ДАННЫХ И ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ .............................. 10 ПРИНЦИП МОДУЛЬНОГО ПРОГРАММИРОВАНИЯ ................................................................... 12 КОНТРОЛЬНЫЕ ВОПРОСЫ........................................................................................................................... 13
2. АБСТРАКТНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ МАШИНЫ ....................................................................... 15 МАШИНА ПОСТА ................................................................................................................................... 15 МАШИНА ТЬЮРИНГА И АЛГОРИТМИЧЕСКИ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ ............... 16 АЛГОРИТМИЧЕСКИ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ ................................................................ 18 ПРИЧИНЫ (СВОДИМЫЕ К ПРОБЛЕМЕ ОСТАНОВА) ВЕДУЩИЕ К АЛГОРИТМИЧЕСКОЙ НЕРАЗРЕШИМОСТИ ........................................................................... 19 КОНТРОЛЬНЫЕ ВОПРОСЫ........................................................................................................................... 20 3. АНАЛИЗ АЛГОРИТМОВ ......................................................................................................................... 20 3.1. СРАВНИТЕЛЬНЫЕ ОЦЕНКИ АЛГОРИТМОВ ......................................................................... 20 3.2. КЛАССИФИКАЦИЯ АЛГОРИТМОВ ПО ВИДУ ФУНКЦИИ ТРУДОЁМКОСТИ ............. 21 3.3. АСИМПТОТИЧЕСКИЙ АНАЛИЗ ФУНКЦИЙ ........................................................................... 22 3.4. ТРУДОЕМКОСТЬ АЛГОРИТМОВ И ВРЕМЕННЫЕ ОЦЕНКИ ............................................. 27 3.5. ПРИМЕРЫ АНАЛИЗА ПРОСТЫХ АЛГОРИТМОВ .................................................................. 28 3.6. ПЕРЕХОД К ВРЕМЕННЫМ ОЦЕНКАМ ..................................................................................... 29 1. Пооперационный анализ ................................................................................................................. 30 2. Метод Гиббсона ............................................................................................................................... 30 3. Метод прямого определения среднего времени ........................................................................... 32 3.7. ТЕОРЕТИЧЕСКИЙ ПРЕДЕЛ ТРУДОЕМКОСТИ АЛГОРИТМОВ ........................................ 35 3.8. РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ ........................................................................................... 38 КОНТРОЛЬНЫЕ ВОПРОСЫ........................................................................................................................... 45 4. ВВЕДЕНИЕ В СТРУКТУРЫ ДАННЫХ ................................................................................................ 47 4.1. МНОЖЕСТВА .................................................................................................................................... 47 ОПЕРАЦИИ ДЛЯ ДИНАМИЧЕСКИХ МНОЖЕСТВ .................................................................... 48 4.2. СТЕКИ И ОЧЕРЕДИ .......................................................................................................................... 48 4.3. СПИСКИ .............................................................................................................................................. 50 4.4. ДЕРЕВЬЯ ............................................................................................................................................. 54 4.5. КУЧА .................................................................................................................................................... 55 КОНТРОЛЬНЫЕ ВОПРОСЫ........................................................................................................................... 57
ЛАБОРАТОРНАЯ РАБОТА №1 ...................................................................................................................... 58 ДОБАВЛЕНИЕ ЭЛЕМЕНТОВ В ОДНОСВЯЗНЫЙ СПИСОК. ...................................................... 61 УДАЛЕНИЕ ЭЛЕМЕНТОВ ИЗ ОДНОСВЯЗНОГО СПИСКА. ........................................................ 63 Графическая иллюстрация ................................................................................................................... 64 СОЗДАНИЕ ОДНОСВЯЗНОГО СПИСКА. ......................................................................................... 65 ОДНОСВЯЗНЫЙ ЛИНЕЙНЫЙ СПИСОК КАК АБСТРАКТНЫЙ ТИП ДАННЫХ (ADT)...... 67 Поддерживаемые операции ................................................................................................................ 68 Пример интерфейса класса LinkedList ....................................................................................... 68 КОНТРОЛЬНЫЕ ВОПРОСЫ........................................................................................................................... 70 ПРАКТИЧЕСКИЕ ЗАДАНИЯ ................................................................................................................ 70 Задание 1................................................................................................................................................ 70 123 ЛАБОРАТОРНАЯ РАБОТА №2 ...................................................................................................................... 71 ПОДДЕРЖИВАЕМЫЕ ОПЕРАЦИИ ................................................................................................................. 71 ДОБАВЛЕНИЕ ЭЛЕМЕНТОВ В СТЭК (МЕТОД PUSH()) ................................................................... 72 УДАЛЕНИЕ ЭЛЕМЕНТОВ ИЗ СТЭКА (МЕТОД POP()) ..................................................................... 73 ПРИМЕР ИНТЕРФЕЙСА КЛАССА LINKEDSTACK И СТРУКТУРЫ NODE ........................................................ 74 КОНТРОЛЬНЫЕ ВОПРОСЫ........................................................................................................................... 75 ПРАКТИЧЕСКИЕ ЗАДАНИЯ ................................................................................................................ 75 Задание 1................................................................................................................................................ 75 Задание 2................................................................................................................................................ 75 Задание 3................................................................................................................................................ 76
ЛАБОРАТОРНАЯ РАБОТА №3.................................................................................................................. 76 ПОДДЕРЖИВАЕМЫЕ ОПЕРАЦИИ ................................................................................................................. 77 ДОБАВЛЕНИЕ ЭЛЕМЕНТОВ В ОЧЕРЕДЬ (МЕТОД ENQUEUE()) ..................................................... 78 УДАЛЕНИЕ ЭЛЕМЕНТОВ ИЗ ОЧЕРЕДИ (МЕТОД DEQUEUE()) ........................................................ 79 КОНТРОЛЬНЫЕ ВОПРОСЫ........................................................................................................................... 80 ПРАКТИЧЕСКИЕ ЗАДАНИЯ ................................................................................................................ 80 Задание 1................................................................................................................................................ 80 Задание 2................................................................................................................................................ 82
ЛАБОРАТОРНАЯ РАБОТА №4.................................................................................................................. 82 ПОДДЕРЖИВАЕМЫЕ ОПЕРАЦИИ ................................................................................................................. 82 ДОБАВЛЕНИЕ ЭЛЕМЕНТОВ В ДВУСВЯЗНЫЙ СПИСОК ........................................................... 83 УДАЛЕНИЕ ЭЛЕМЕНТОВ ИЗ ДВУСВЯЗНОГО СПИСКА ............................................................ 84 КОНТРОЛЬНЫЕ ВОПРОСЫ........................................................................................................................... 85 ПРАКТИЧЕСКИЕ ЗАДАНИЯ ................................................................................................................ 85 Задание 1................................................................................................................................................ 85 ЛАБОРАТОРНАЯ РАБОТА №5.................................................................................................................. 89 ГРАФИЧЕСКАЯ ИЛЛЮСТРАЦИЯ БИНАРНЫХ ДЕРЕВЬЕВ ............................................................................ 90 СОЗДАНИЕ БИНАРНОГО ДЕРЕВА И ДОБАВЛЕНИЕ ЭЛЕМЕНТОВ ........................................ 91 УДАЛЕНИЕ ЭЛЕМЕНТОВ ИЗ БИНАРНОГО ДЕРЕВА ................................................................... 97 ОБХОД БИНАРНОГО ДЕРЕВА(TREE TRAVERSAL) ............................................................................... 104 СИММЕТРИЧНЫЙ ОБХОД(inorder traversal) .................................................................... 104 ОБХОД В ШИРИНУ(preorder traversal)................................................................................ 105 ОБХОД В ГЛУБИНУ(postorder traversal) ............................................................................. 105 РЕКУРСИВНЫЙ АЛГОРИТМ ОБХОДА БИНАРНОГО ДЕРЕВА...................................................................... 106 ПОДДЕРЖИВАЕМЫЕ ОПЕРАЦИИ ............................................................................................................... 106 ПРИМЕР ИНТЕРФЕЙСА КЛАССОВ BINARYTREE И NODE ........................................................................... 107 КОНТРОЛЬНЫЕ ВОПРОСЫ......................................................................................................................... 109 ПРАКТИЧЕСКИЕ ЗАДАНИЯ .............................................................................................................. 109 Задание 1.............................................................................................................................................. 109 Задание 2.............................................................................................................................................. 109 Задание 3.............................................................................................................................................. 110 УЧЕБНАЯ ПРОГРАММА УЧРЕЖДЕНИЯ ВЫСШЕГО ОБРАЗОВАНИЯ ........................................... 112 СПИСОК ЛИТЕРАТУРЫ .......................................................................................................................... 122 124 жүктеу/скачать 3,71 Mb. Достарыңызбен бөлісу:
|