Скачать 129.23 Kb.
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Нижегородский государственный университет им. Н.И. Лобачевского» Радиофизический факультет Кафедра математики УТВЕРЖДАЮ Декан радиофизического факультета ____________________Якимов А.В. «18» мая 2011 г. Учебная программа Дисциплины Б3.Б4 «Алгоритмы и анализ сложности» по направлению 010300 «Фундаментальная информатика и информационные технологии» Нижний Новгород 2011 г. 1. Цели и задачи дисциплины Содержание дисциплины «Алгоритмы и анализ сложности» направлено на ознакомление студентов с основами теории сложности и некоторыми методами анализа сложности алгоритмов, основными приемами построения и анализа эффективности алгоритмов, которые используются при решении классических задач информационных технологий и математического моделирования. 2. Место дисциплины в структуре программы бакалавра Дисциплина «Алгоритмы и анализ сложности» относится к дисциплинам базовой части профессионального цикла основной образовательной программы по направлению 010300 «Фундаментальная информатика и информационные технологии», преподается в 4 семестре. Преподавание курса строится с учетом знаний, полученных студентами при изучении дисциплин «Дискретная математика», «Основы программирования», «Языки программирования». Знания, приобретённые в процессе изучения дисциплины «Алгоритмы и анализ сложности» используются при изучении дисциплин «Операционные системы», «Программная инженерия», а также других дисциплин профессионального цикла, преподавание которых требует рассмотрения вопросов, связанных с анализом сложности и эффективности алгоритмов. 3. Требования к уровню освоения содержания дисциплины В результате освоения дисциплины формируются следующие компетенции:
В результате изучения студенты должны:
4. Объём дисциплины и виды учебной работы Общая трудоемкость дисциплины составляет 4 зачетные единицы, 144 часа.
5. Содержание дисциплины 5.1. Разделы дисциплины и виды занятий
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. Лабораторный практикум
7. Учебно-методическое обеспечение дисциплины 7.1. Рекомендуемая литература. а) основная литература:
б) дополнительная литература:
8. Вопросы для контроля
9. Критерии оценок
10. Примерная тематика курсовых работ и критерии их оценки Не предусмотрены. Программа составлена в соответствии с Федеральным государственным образовательным стандартом высшего профессионального образования по направлению 010300 «Фундаментальная информатика и информационные технологии» Автор программы ___________ Лапинова С.А. Программа рассмотрена на заседании кафедры 18 марта 2011 г. протокол № 10-11-04 Заведующий кафедрой _________________ Дубков А.А. Программа одобрена методической комиссией факультета 11 апреля 2011 года протокол № 05/10 Председатель методической комиссии_________________ Мануилов В.Н. |
Радиофизический факультет Дисциплины 02 «Полупроводниковые лазеры в оптической связи и измерительных системах» | Радиофизический факультет Дисциплины р12 «Взаимодействие электронных потоков с электромагнитными полями» | ||
Радиофизический факультет Данная дисциплина относится к общепрофессиональным дисциплинам федерального компонента, преподается в 9 семестре | Радиофизический факультет Данная дисциплина относится к дисциплинам специализации федерального компонента, преподается в 6 и 7 семестрах | ||
Радиофизический факультет ... | Радиофизический факультет Цель курса – сформировать у студентов представления о квантовомеханических закономерностях, лежащих в основе современной физики и... | ||
Радиофизический факультет Целью преподавания дисциплины «Дискретная математика» является подготовка специалистов к деятельности в сфере разработки, исследования... | Радиофизический факультет Содержание дисциплины направлено на расширение знаний электродинамики плазменных процессов, обусловленных ионизационной нелинейностью... | ||
Радиофизический факультет Цель изучения дисциплины состоит в освоении студентами методологии и технологии моделирования (в первую очередь компьютерного) информационных... | Радиофизический факультет Содержание дисциплины направлено на углубленное изучение методов физики твердого тела, знакомство с некоторыми современными проблемами... | ||
Программа по формированию навыков безопасного поведения на дорогах... Факультет русской филологии и журналистики. Факультет истории и юриспруденции. Факультет татарской и сопоставительной филологии.... | Радиофизический факультет Дисциплина базируется на знаниях студентов, приобретенных в курсах общей физики, полупроводниковой электроники, электродинамики и... | ||
Радиофизический факультет Большое внимание в курсе уделено сопутствующему математическому описанию указанных процессов и их использованию для расчета основных... | Радиофизический факультет Дисциплина «Физическая электроника» относится к дисциплинам базовой части профессионального цикла основной образовательной программы... | ||
Радиофизический факультет Основное внимание при чтении лекций уделяется приближенным методам решения задач распространения и рассеяния скалярных волн в средах... | Радиофизический факультет Содержание дисциплины направлено на изучение разделов аналитической геометрии и высшей алгебры, необходимых для понимания других... |