Учебная программа Дисциплины б4 «Алгоритмы и анализ сложности» по направлению 010300 «Фундаментальная информатика и информационные технологии» Нижний Новгород 2011 г

скачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Нижегородский государственный университет им. Н.И. Лобачевского»

Радиофизический факультет

Кафедра математики

УТВЕРЖДАЮ

Декан радиофизического факультета

____________________Якимов А.В.

«18» мая 2011 г.

Учебная программа

Дисциплины Б3.Б4 «Алгоритмы и анализ сложности»

по направлению 010300 «Фундаментальная информатика и информационные технологии»

Нижний Новгород

2011 г.

1. ^ Цели и задачи дисциплины

Содержание дисциплины «Алгоритмы и анализ сложности» направлено на ознакомление студентов с основами теории сложности и некоторыми методами анализа сложности алгоритмов, основными приемами построения и анализа эффективности алгоритмов, которые используются при решении классических задач информационных технологий и математического моделирования.

2.^ Место дисциплины в структуре программы бакалавр��

Дисциплина «Алгоритмы и анализ сложности» относится к дисциплинам базовой части профессионального цикла основной образовательной программы по направлению 010300 «Фундаментальная информатика и информационные технологии», преподается в 4 семестре.

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

Знания, приобретённые в процессе изучения дисциплины «Алгоритмы и анализ сложности» используются при изучении дисциплин «Операционные системы», «Программная инженерия», а также других дисциплин профессионального цикла, преподавание которых требует рассмотрения вопросов, связанных с анализом сложности и эффективности алгоритмов.

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

В результате освоения дисциплины формируются следующие компетенции:

способность понимать сущность и значение информации в развитии современного информационного общества (ОК–11);
способность применять в профессиональной деятельности современные языки программирования методологии системной инженерии, системы автоматизации проектирования, электронные библиотеки и коллекции, библиотеки и пакеты программ, современные профессиональные стандарты информационных технологий (ПК–1, ПК–27);
способность в составе научно-исследовательского и производственного коллектива решать задачи профессиональной деятельности (в соответствии с профилем подготовки) (ПК-5);
понимание концепций, синтаксической и семантической организации, методов использования современных языков программирования (ПК–19);
понимание концепций, базовых алгоритмов, принципов разработки и функционирования современных операционных систем (ПК–20);
знание международных стандартов в области разработки программного обеспечения, понимание процессного подхода, методов управления жизненным циклом и качеством программного обеспечения (ПК 21).

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

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

4. ^ Объём дисциплины и виды учебной работы

Общая трудоемкость дисциплины составляет 4 зачетные единицы, 144 часа.

Виды учебной работы	Всего часов	Семестры
^ Общая трудоемкость дисциплины	144	4
Аудиторные занятия	68	68
Лекции	34	34
Практические занятия (ПЗ)	–	–
Семинары (С)	–	–
Лабораторные работы (ЛР)	34	34
Другие виды аудиторных занятий	–	–
Самостоятельная работа	40	40
Курсовой проект (работа)	–	–
Расчетно-графическая работа	–	–
Реферат	–	–
Другие виды самостоятельной работы	–	–
Вид итогового контроля (зачет, экзамен)	экзамен (36)	экзамен (36)

5. Содержание дисциплины

5.1. Разделы дисциплины и виды занятий

№ п/п	Раздел дисциплины	Лекции	ПЗ (или С)	ЛР
1	Основы анализа эффективности алгоритмов	6	-	6
2	Сложность в худшем случае	2	-	4
3	Сложность в среднем	4	-	6
4	Методы построения алгоритмов	8	-	6
5	Распределенные алгоритмы	8	-	4
6	Основы теории вычислимости	6	-	4

5.2. Содержание разделов дисциплины

Раздел 1. Основы анализа эффективности алгоритмов.

1.1. Основы анализа.

Оценка размера входных данных. Единицы измерения времени выполнения алгоритма. Порядок роста. Основные классы эффективности. Соотношения, используемые при анализе алгоритмов.

1.2. Математический анализ нерекурсивных алгоритмов.

План анализа нерекурсивных алгоритмов. Анализ алгоритма поиска наибольшего элемента в списке. Алгоритм проверки единственности элементов в списке. Произведение двух матриц.

^ 1.3. Математический анализ рекурсивных алгоритмов.

Понятие рекурсии. План анализа рекуррентных алгоритмов. Методики решения рекурсивных отношений. Задача Ханойской башни. Алгоритм подсчета количества разрядов в двоичном представлении числа. Числа Фибоначчи.

1.4. Эмпирический анализ алгоритмов.

План эмпирического анализа алгоритмов. Профилирование. Графическое представление данных. Генератор случайных чисел.

Раздел 2. Сложность в худшем случае.

2.1. Затраты алгоритма на входе.

Сортировка простыми вставками. Последовательный поиск. Поиск подстроки. Поиск пары ближайших точек. Простое построение выпуклой оболочки. Решение задачи коммивояжера.

Раздел 3. Сложность в среднем.

3.1. Понятие о сложности в среднем.

Основные определения. Асимптотический закон распределения простых чисел. Сортировка и конечные вероятностные пространства. Применение формул полного математического ожидания.

3.2. Примеры алгоритмов.

Быстрая сортировка. Сортировка слиянием. Бинарный поиск. Обход бинарного дерева. Алгоритм умножения больших чисел. Алгоритм умножения матриц Штрассена.

Раздел 4. Методы построения алгоритмов.

4.1.Метод декомпозиции .

Основные принципы метода. Решение задачи о паре ближайших точек методом декомпозиции. Решение задачи о построении выпуклой оболочки методом декомпозиции.

4.2.Метод уменьшения размера задачи.

Уменьшение на постоянную величину. Сортировка вставкой. Поиск в глубину. Поиск в ширину. Топологическая сортировка. Алгоритмы генерации комбинаторных объектов. Уменьшение на постоянный множитель.

Умножение по-русски. Задача о поиске фальшивой монеты. Задача Иосифа. Алгоритмы с переменным уменьшением размера. Вычисление медианы. Интерполяционный поиск. Поиск и вставка в бинарное дерево.

4.3.Метод преобразования.

Основные принципы метода: упрощение экземпляра, изменение представления, приведение задачи. Предварительная сортировка. Методы решения линейных систем.

4.4.Структуры хранения данных.

Сбалансированные деревья поиска. AVL-деревья. Повороты. Вставка элемента в дерево. Удаление элемента из дерева. 2-3- деревья. Пирамиды. Алгоритм построения пирамиды. Пирамидальная сортировка.

4.5.Линейное программирование.

Классы экстремальных задач. Графический метод решения. Симплексный метод решения. Транспортная задача. Метод потенциалов решения транспортной задачи. Задача о рюкзаке.

4.6.Линейное программирование.

Классы экстремальных задач. Графический метод решения. Симплексный метод решения. Транспортная задача. Метод потенциалов решения транспортной задачи. Задача о рюкзаке.

4.7.Пространственно-временной компромисс.

Сортировка подсчетом. Алгоритм Хорспула. Хеш-функции. Открытое хеширование. Закрытое хеширование. В-деревья.

4.8.Динамическое программирование.

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

4.8.Жадные алгоритмы.

Алгоритм Крускала. Алгоритм Дейкстры. Деревья Хаффмана.

Раздел 5. Распределенные алгоритмы.

5.1.Основные принципы параллельного программирования .

Задачи параллельного программирования. Процессы и потоки. Модели программ с общей памятью. Модель передачи сообщений. Организация параллельных вычислений на принципе консенсуса. Невытесняющие алгоритмы планирования. Вытесняющие алгоритмы планирования.

5.2.Инструменты анализа эффективности параллельного программирования .

Библиотека MPI. Библиотека OpenMP.

Раздел 6. Основы теории вычислимости.

6.1.Ограничения мощности алгоритма.

Нижняя граница. Тривиальная нижняя граница. Информационно-теоретическая нижняя граница. Метод противника. Легкие и сложные задачи.

6.1.Конечные автоматы.

Определение. Основные свойства. Контекстно-свободные грамматики.

6.2. Разрешимые и неразрешимые проблемы.

P- задачи. NP и NP-полные задачи. Задача останова.

6. Лабораторный практикум

№ п/п	№ раздела дисциплины	Наименование лабораторной работы
1	1	Алгоритмы построения генераторов случайных чисел. Методы анализа генераторов.
2	2-3	Алгоритмы сортировки, поиска
3	4	Алгоритмы, основанные на методе декомпозиции, анализ алгоритмов
4	4-6	Алгоритмы по созданию структур хранения данных. Хэш-функции

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

7.1. Рекомендуемая литература.

а) основная литература:

Абрамов С.А. Лекции о сложности алгоритмов. - М.: МЦНМО, 2009.
Левитин Ананий В. Алгоритмы: введение в разработку и анализ. - М.: Издательский дом «Вильямс», 2006.
Ху Т.Ч., Шинг М.Т. Комбинаторные алгоритмы. –Н.Новгород: Изд-во Нижегородского государственного университета, 2004.

б) дополнительная литература:

Дональд Э. Кнут. Искусство программирования. Том 1. -М. Издательский дом «Вильямс», 2005.
Дональд Э. Кнут. Искусство программирования. Том 2. -М. Издательский дом «Вильямс», 2005.
Дональд Э. Кнут. Искусство программирования. Том 3. -М. Издательский дом «Вильямс», 2005.
Красиков И.В., Красикова И.Е. Алгоритмы: как дважды два. - М.: Эксмо, 2006.

8. Вопросы для контроля

Основы анализа эффективности алгоритмов. Оценка размера входных данных, время выполнения.
Порядок роста. Основные классы эффективности.
Асимптотические представления, О- символика.
Формула Эйлера. Применение формулы Эйлера для оценки разложения логарифма
Применение формулы Эйлера для оценки формулы Стирлинга.
Математический анализ нерекурсивных алгоритмов.
Математический анализ рекурсивных алгоритмов.
Числа Фибоначчи.
Эмпирический анализ алгоритмов.
Генераторы случайных чисел. Методы анализа.
Метод грубой силы. Анализ алгоритма на примере алгоритма поиска максимума.
Сортировка посредством выбора. Усовершенствованный простой выбор.
Последовательный поиск.
Исчерпывающий перебор.
Метод декомпозиции, основные алгоритмы
Сортировка методом слияния.
Сортировка методом естественного двухпутевого слияния.
Быстрая сортировка.
Метод Шелла
Бинарный поиск. Однородный бинарный поиск.
Обход бинарного дерева.
Умножение больших целых чисел. Алгоритм Штрассена.
Задача о паре ближайших точек.
Построение выпуклой оболочки.
Метод уменьшения размера задачи, основные алгоритмы.
Сортировка вставкой.
Поиск в ширину.
Поиск в глубину.
Топологическая сортировка.
Алгоритмы генерации комбинаторных объектов.
Целочисленная функция и ее свойства, перестановки, сочетания. Основные свойства биномиальных коэффициентов.
Инверсии, Мультимножества, Серии.
Алгоритмы, использующие уменьшение на постоянный множитель: задача поиска фальшивой монеты; задача Иосифа; умножение по-русски.
Алгоритмы, использующие переменное уменьшение на постоянный множитель: вычисление медианы; задача выбора; интерполяционный поиск.
Метод преобразования. Предварительная сортировка: проверка единственности элементов в массиве; вычисление моды.
Метод Гаусса.
AVL-деревья.
2-3- деревья.
Пирамиды. Пирамидальная сортировка.
Схема Горнера.
Подсчет путей в графе.
Линейное программирование. Симплексный метод решения.
Транспортная задача. Метод потенциалов.
Пространственно-временной компромисс, основные алгоритмы.
Сортировка посредством подсчета (два вида).
Алгоритм Хорспула.
Алгоритм Бойера-Мура.
Поиск по дереву с вставкой.
Цифровой поиск. Хеш-функции. Открытое и закрытое хеширование.
В-деревья.
Динамическое программирование. Алгоритм Воршалла. Алгоритм Флойда.
Оптимальные бинарные деревья поиска.
Жадные методы, алгоритм Прима.
Алгоритм Крускала.
Алгоритм Дейкстры поиска кратчайшего пути
Функции с запоминанием. Задача о рюкзаке.
Деревья Хаффмана
P- задачи. NP и NP-полные задачи. Задача останова.
Задача об упаковке. NF – алгоритм. FF – алгоритм. BF – алгоритм.
On line алгоритмы. Правило первого подходящего. Правило наилучшего подходящего.
Правило Яо.
Задача о составлении расписания.
Расписание "без простоев": увеличение числа машин, ослабление ограничений, уменьшение времени выполнения работ.
Задача о расписание с древесным ограничением.
Нижняя граница. Тривиальная нижняя граница. Информационно-теоретическая нижняя граница. Метод противника. Легкие и сложные задачи.
Конечные автоматы. Определение. Основные свойства. Контекстно-свободные грамматики.
Задачи параллельного программирования. Процессы и потоки. Модели программ с общей памятью. Модель передачи сообщений. Организация параллельных вычислений на принципе консенсуса. Невытесняющие алгоритмы планирования. Вытесняющие алгоритмы планирования.

9. ^ Критерии оценок

Превосходно	Превосходная подготовка с очень незначительными погрешностями
Отлично	Подготовка, уровень которой существенно выше среднего с некоторыми ошибками
Очень хорошо	^ В целом хорошая подготовка с рядом заметных ошибок
Хорошо	Хорошая подготовка, но со значительными ошибками
Удовлетворительно	Подготовка, удовлетворяющая минимальным требованиям
Неудовлетворительно	Необходима дополнительная подготовка для успешного прохождения испытания
Плохо	^ Подготовка совершенно недостаточная

10. Примерная тематика курсовых работ и критерии их оценки

Не предусмотрены.

Программа составлена в соответствии с Федеральным государственным образовательным стандартом высшего профессионального образования по направлению 010300 «Фундаментальная информатика и информационные технологии»

Автор программы ___________ Лапинова С.А.

Программа рассмотрена на заседании кафедры 18 марта 2011 г. протокол № 10-11-04

Заведующий кафедрой _________________ Дубков А.А.

Программа одобрена методической комиссией факультета 11 апреля 2011 года

протокол № 05/10

Председатель методической комиссии_________________ Мануилов В.Н.

Скачать 131,38 Kb.

оставить комментарий