Типовая учебная программа
Скачать 106.42 Kb.
|
![]() Министерство образования Республики Беларусь Учебно-методическое объединение вузов Республики Беларусь по естественнонаучному образованию УТВЕРЖДАЮ Первый заместитель Министра Образования Республики Беларусь ________________ А.И. Жук «___» __________ 2008 г. Регистрационный № ТД-______/тип. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ Типовая учебная программадля высших учебных заведений по направлению специальности: 1-31 03 01-05 Математика (информационные технологии)
Минск 2008 Составители:Романчик Валерий Станиславович, заведующий кафедрой численных методов и программирования Белорусского государственного университета, кандидат физико-математических наук, доцент;Скумс Павел Валентинович, старший преподаватель кафедры численных методов и программирования Белорусского государственного университета, кандидат физико-математических наук.Рецензенты: Кафедра экономической информатики Учреждения образования «Белорусский государственный экономический университет» (заведующий кафедрой – кандидат технических наук, профессор Б.А. Железко); В.И. Сарванов, заведующий отделом комбинаторных моделей и алгоритмов Института математики Национальной академии наук Беларуси, кандидат физико-математических наук, старший научный сотрудник. РЕКОМЕНДОВАНА К УТВЕРЖДЕНИЮ В КАЧЕСТВЕ ТИПОВОЙ: Кафедрой численных методов и программирования механико-математического факультета Белорусского государственного университета (протокол № 8 от 6 марта 2008 г.); Научно-методическим советом Белорусского государственного университета (протокол № 3 от 27 марта 2008 г.); Научно-методическим советом по математике и механике Учебно-методического объединения вузов Республики Беларусь по естественнонаучному образованию (протокол № 3 от 10 апреля 2008 г.). Ответственный за выпуск: Скумс Павел Валентинович 1. Пояснительная записка Развитие современного производства, его сложная разветвленная структура приводит к все более возрастающей потребности современного общества в новейших информационных технологиях. Это вызывает к жизни множество новых задач и проблем, требующих адекватного аппарата для своего решения. Общеизвестно, что комбинаторные методы и алгоритмы являются наиболее удобным и эффективным средством решения этих задач. Современное программирование невозможно представить себе без эффективных алгоритмов. Это связано с тем, что очень многие возникающие в области информационных технологий задачи характеризуются большим числом составляющих элементов и огромным количеством связей между ними. Такие задачи весьма сложны для решения даже с использованием новейшей и самой совершенной на данный момент вычислительной техники. Поэтому создание сложного программного продукта в настоящее время возможно лишь с использованием мощной алгоритмической базы, за которой стоит соответствующий математический аппарат – аппарат теории комбинаторных алгоритмов и дискретной оптимизации. Задача данной дисциплины – ознакомить студентов с наиболее часто используемыми комбинаторными алгоритмами, с основными идеями, методами и алгоритмическими стратегиями и тем самым подготовить их к решению реальных задач, возникающих на практике. После изучения данной дисциплины студент должен знать:
уметь:
Всего – 248 часов. Из них аудиторных – 136 часов, в том числе: лекции – 66 ч., лабораторные занятия – 38 ч., практические занятия – 32 ч. 2. Примерный тематический план
3. Содержание учебного материала 1. Введение. Основные структуры данных. Предмет теория алгоритмов. Прикладное значение эффективности алгоритмов. Связь с дискретной математикой, математической кибернетикой, программированием. Стеки, очереди, связанные списки, бинарные деревья. 2. Трудоемкость алгоритмов. Предмет теория алгоритмов. Прикладное значение эффективности алгоритмов. Связь с дискретной математикой, математической кибернетикой, программированием. Необходимость оценки алгоритмов. Принципы оценки трудоемкости комбинаторных алгоритмов. Рост функций, O-нотация. Трудоемкость «в худшем», трудоемкость «в среднем», трудоемкость «почти всегда». Примеры анализа алгоритмов. 3. Алгоритмы сортировки. Элементарные методы сортировки (сортировки выбором, вставками, пузырьковая, Шелла). Быстрая сортировка. Корневая и пирамидальная сортировка. Сортировка слиянием. Внешняя сортировка. Линейные сортировки (подсчетом и вычерпыванием). Анализ эффективности сортировок. Теорема о невозможности существования алгоритма сортировки в «худшем» и «в среднем» с трудоемкостью лучшей, чем О(n log2n). 4. Алгоритмы поиска и выборки. Последовательный поиск. Бинарный поиск. Деревья бинарного поиска. Сбалансированные деревья (2-3-4 деревья, красно-черные деревья) и реализуемые с их помощью структуры. Операции над деревьями. Хеширование. 5. Алгоритмы на строках. Основные определения. Алгоритмы поиска подстроки в строке. Алгоритмы Бойера-Мура, Кнута-Морриса-Пратта и их реализации. 6. Алгоритмы на графах. Основные понятия теории графов. Структуры данных для представления графов: матрицы смежности, матрицы инцидентности, списки смежности, списки ребер. Алгоритмы поиска в ширину и глубину, их реализация. Поиск компонент связности и компонент двусвязности. Алгоритмы нахождения эйлерова цикла. Жадные алгоритмы и матроиды. Поиск минимального остовного дерева и кратчайшего пути в графе. Алгоритмы Прима, Краскала, Дийкстры, Флойда, Беллмана-Форда. Паросочетания в двудольных графах, метод увеличивающей цепи. Алгоритмы раскраски графов. Алгоритмы для задач о независимом множестве, доминирующем множестве. Построение реализаций графической последовательности, l-процедура. Потоки в сетях, алгоритм Форда-Фалкерсона. 7. Динамическое программирование и метод “разделяй и властвуй”. Понятие о методах динамического программирования и “разделяй и властвуй”. Алгоритм Штрассена умножения матриц. Задача о рюкзаке. Графы с ограниченным параметром treewidth и алгоритмы для них. 8. Основы теории сложности вычислений. Детерминированные и недетерминированные машины Тьюринга. Понятие о классах Р и NР. NP-полные задачи. Теорема Кука-Карпа-Левина. NP-полнота задач “3-выполнимость”, “Клика”, “Гамильтонов цикл”. Списки наиболее известных NР-полных задач. 9. Алгоритмы с гарантированной оценкой точности. Понятие о гарантированной оценке точности алгоритма. Задача упаковки. Задача о максимальном разрезе. Задача о вершинном покрытии. Задача о коммивояжере с неравенством треугольника, О существовании алгоритма с гарантированной оценкой точности для общей задачи коммивояжера. 10. Основные алгоритмические стратегии. Эвристики и метаэвристики. Алгоритмы локального поиска, поиска с запретами. Генетические алгоритмы, алгоритмы имитации отжига. Алгоритмы полного перебора, метод ветвей и границ. 11. Задачи линейного и целочисленного линейного программирования. Понятие о задачах линейного и целочисленного линейного программирования. Формулировки основных задач дискретной оптимизации как задач целочисленного линейного программирования. Программные пакеты для решения задачи целочисленного линейного программирования. Формат MPS. 12. Алгоритмы для работы с матрицами. Решение систем линейных уравнений. LU-разложение. Обращение матриц. 13. Элементы криптографии. Криптосистемы с открытым ключом, цифровая подпись. Криптосистема RSA. Алгоритмы проверки чисел на простоту. 14. Алгоритмы сжатия информации. Коды Хаффмана, алгоритм Хаффмана. 15. Нейронные сети. Понятие о нейронной сети. Типы нейронных сетей. Обучение нейронных сетей. 16. Алгоритмы для параллельных вычислений. 4. Информационная часть Литература Основная
Дополнительная
|
Добавить документ в свой блог или на сайт
Похожие:
- История биологии Типовая учебная программа для высших учебных заведений по специальности
- Аналитическая геометрия Типовая учебная программа для высших учебных заведений по специальности
Первый проректор Государственного учреждения образования «Республиканский институт высшей школы» - Зоология беспозвоночных Типовая учебная программа для высших учебных заведений по специальностям
Первый проректор Государственного учреждения образования «Республиканский институт высшей школы» - Эволюция национальных аудиовизуальных сми типовая учебная программа для высших учебных заведений
Ректор Государственного учреждения образования «Республиканский институт высшей школы» - Нормальная физиология Типовая учебная программа для высших учебных заведений по специальности 1-79
Учреждения образования «Белорусский государственный медицинский университет», доктор - История зарубежной журналистики типовая учебная программа для высших учебных заведений по специальности
Первый проректор Государственного учреждения образования «Республиканский институт высшей школы» - Функциональный анализ и интегральные уравнения Типовая учебная программа для высших учебных заведений
Председатель Учебно-методического объединения вузов Республики Беларусь по естественнонаучному образованию - История южных и западных славян типовая учебная программа для высших учебных заведений по специальности
Первый проректор Государственного учреждения образования «Республиканский институт высшей школы» - Историческая геология типовая учебная программа для высших учебных заведений по специальности
Начальник Управления высшего и среднего специального образования Министерства образования Республики Беларусь - Экономическая и социальная география страны (стран) изучаемого восточного языка Типовая учебная программа
Председатель учебно-методического объединения вузов Республики Беларусь по гуманитарному образованию, профессор
База данных защищена авторским правом ©cat.convdocs.org 2012
обратиться к администрации
cat.convdocs.org
обратиться к администрации
cat.convdocs.org