Федеральное государственное автономное образовательное учреждение высшего профессионального образования
"Национальный исследовательский университет
"Высшая школа экономики"
Московский институт электроники и математики
Департамент прикладной математики
Рабочая программа дисциплины
«Алгоритмы и анализ сложности алгоритмов»
для образовательной программы «Фундаментальная информатика и информационные
технологии»
направления подготовки 02.03.02 «Фундаментальная информатика и информационные
технологии»
уровень бакалавр
Разработчик программы
, Phd, к. ф.-м. н., *****@***ru, *****@***com
Одобрена на заседании департамента прикладной математики
«___»____________ 2015 г.
Руководитель департамента ________ [подпись]
Рекомендована Академическим советом образовательной программы
«___»____________ 2015 г., № протокола_________________
Утверждена «___»____________ 2015 г.
Академический руководитель образовательной программы
_________________ [подпись]
Москва, 2015
Настоящая программа не может быть использована другими подразделениями университета и другими вузами без разрешения подразделения-разработчика программы.
1. Область применения и нормативные ссылки
Настоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности.
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010300.62 «Фундаментальные информатика и информационные технологии», изучающих дисциплину «Алгоритмы и анализ сложности».
Программа разработана в соответствии с:
· ФГОС 010300 Фундаментальные информатика и информационные технологии 62 бакалавр.
· Рабочим учебным планом университета по направлению подготовки 010300.62 Фундаментальные информатика и информационные технологии, утвержденным в 2015 г.
2. Цели освоения дисциплины «Алгоритмы и анализ сложности»
Цель настоящего курса − дать студентам систематизированные сведения об основах теории алгоритмов, структуре и опыте применения наиболее распространённых базовых алгоритмов обработки данных, стратегиях алгоритмов, оценках сложности алгоритмов и издержек при их реализации, а также ознакомить с основами построения распределённых алгоритмов.
Определённая часть курса посвящена изложению основных сведений о тенденциях развития вычислительных сред и перспективных областей применения численных методов и численного эксперимента.
3. Компетенции обучающегося, формируемые в результате освоения дисциплины
В результате освоения дисциплины студент должен:
· Знать основные положения теории алгоритмов, структуру и возможности основных алгоритмов обработки данных, часто употребляемые стратегии алгоритмов, принятые на практике оценки сложности алгоритмов, основные представления о распределённых алгоритмах.
· Уметь обоснованно выбирать алгоритмы и стратегии алгоритмов для решения конкретных задач с учётом оценок сложности, затратности и целесообразности издержек для решения практических задач.
· Иметь навыки применения алгоритмов, выбора стратегий алгоритмов, оценки приемлемости затрат и оценки ресурсных ограничений, иметь основные представления о программировании параллельных систем обработки данных.
В результате освоения дисциплины студент осваивает следующие компетенции:
Компетенция | Код по ФГОС/ НИУ | Дескрипторы – основные признаки освоения (показатели достижения результата) | Формы и методы обучения, способствующие формированию и развитию компетенции |
Способность приобретать новые знания с использованием научной методологии и современных образовательных и информационных технологий | ОНК-6 | Дает правильные определения основных понятий, формулировки теорем, воспроизводит их доказательства, правильно применяет изученные методы | Лекции, практические занятия, самостоятельная работа |
Способность демонстрации общенаучных базовых знаний естественных наук, математики и информатики, понимание основных фактов, концепций, принципов теорий, связанных с прикладной математикой и информатикой | ПК-1 | Демонстрирует понимание алгоритмов и методы их анализа | Лекции, практические занятия, самостоятельная работа |
Способность понимать и применять в исследовательской и прикладной деятельности современный математический анализ | ПК-2 | Правильно применяет изученные ранее методы математического анализа и методы данной дисциплины | Практические занятия, самостоятельная работа |
Способность решать задачи производственной и технологической деятельности на профессиональном уровне, включая разработку математических моделей, алгоритмических и программных решений | ПК-8 | Разрабатывает алгоритмические и программные решения для реализации изученных методов | Практические занятия, самостоятельная работа |
Способность применять в профессиональной деятельности современные языки программирования и языки баз данных, операционные системы, электронные библиотеки и пакеты программ, сетевые технологии и т. п. | ПК-9 | Использует языки программирования для реализации изученных алгоритмов | Практические занятия, самостоятельная работа |
4. Место дисциплины в структуре образовательной программы
Настоящая дисциплина относится к базовой (общепрофессиональной) части профессионального цикла.
Изучение данной дисциплины базируется на следующих дисциплинах:
· Основы программирования.
· Объектно-ориентированное программирование.
5. Тематический план учебной дисциплины
№ | Название раздела | Всего часов | Аудиторные часы | Самостоятельная работа | ||
Лекции | Семинары | Практические занятия | ||||
1 | Основы теории алгоритмов | 24 | 4 | 4 | 16 | |
2 | Основы анализа алгоритмов | 24 | 4 | 4 | 16 | |
3 | Основные алгоритмы обработки информации | 42 | 6 | 6 | 30 | |
4 | Стратегии алгоритмов | 24 | 4 | 4 | 16 | |
5 | Распределенные алгоритмы | 10 | 2 | 2 | 6 | |
6 | Основы анализа вычислимости | 10 | 2 | 2 | 6 | |
Всего | 134 | 22 | 22 | 90 |
6. Формы контроля знаний студентов
Тип контроля | Форма контроля | 1 год | Параметры ** |
3 модуль | |||
Итоговый | Экзамен | X | Устный экзамен включает от 3 до 5 вопросов и 1-2 задач по всем темам курса различного уровня сложности. |
7. Содержание дисциплины
Раздел 1. Основы теории алгоритмов
- Машина Поста и машина Тьюринга.
- Основные положения теории автоматов.
- Рекурсивные функции.
- Основные положения теории формальных грамматик
Раздел 2 Основы анализа алгоритмов
- Асимптотический анализ верхней и средней оценок сложности алгоритмов, сравнение наилучших, средних и наихудших оценок;
- O-, o-, ω- и θ-нотации; стандартные классы сложности; эмпирические измерения эффективности алгоритмов;
- Накладные расходы алгоритмов по времени и памяти; рекуррентные соотношения и анализ рекурсивных алгоритмов
Раздел 3. Основные алгоритмы обработки информации
- Алгоритмы последовательного и бинарного поиска;
- Алгоритмы сортировки сложности O(N*N) и O(N*logN);
- Хеш-функции и методы исключения коллизий;
- Деревья бинарного поиска; поиск в глубину и поиск в ширину;
- Алгоритмы поиска кратчайших путей (алгоритмы Дейкстры и Флойда);
Раздел 4. Стратегии алгоритмов
- Полный перебор; метод «разделяй и властвуй»;
- «Жадные» алгоритмы; бэктрекинг (перебор с возвратами);
- Метод ветвей и границ; эвристический поиск;
- Поиск по образцу, алгоритмы обработки строк;
- Генетические алгоритмы;
- Алгоритмы построения минимального покрывающего дерева (алгоритмы Прима и Крускала);
Раздел 5. Распределённые алгоритмы
- Модель параллельного выполнения программы с общей памятью и модель с разделённой памятью.
- Модель потока данных.
- Модель самоопределяемых данных;
Раздел 6. Основы теории вычислимости
- Сложностные классы задач.
- Определение и взаимосвязь классов P и NP.
- Определение и примеры NP-полных задач.
8. Образовательные технологии
Работа на практических занятиях предполагает разработку программ, реализующих алгоритмы, их экспериментальное исследование и сравнение результатов с теоретическими оценками алгоритмов. Практическая работа предполагает самостоятельный анализ ресурсной эффективности двух-трех выбранных алгоритмов решения определённой задачи и сравнительный анализ этих алгоритмов с целью формулировки рекомендаций по их применению в зависимости от особенностей проблемной области применения.
9. Оценочные средства для текущего контроля и аттестации студента
Вопросы для оценки качества освоения дисциплины
1. Основные свойства алгоритмов. Требования к алгоритмам.
2. Понятие вычислительной сложности алгоритма. Комплексные оценки качества алгоритмов и их компоненты.
3. Классификации алгоритмов.
4. Трудоёмкость в худшем, среднем и лучшем случае как функция длины входа.
5. Сравнительный анализ алгоритмов по трудоёмкости.
6. Основы анализа эффективности алгоритмов. Оценка размера входных данных, время выполнения.
7. Математический анализ нерекурсивных алгоритмов.
8. Математический анализ рекурсивных алгоритмов
9. Генераторы случайных чисел. Методы анализа.
10. Сортировка посредством выбора. Усовершенствованный простой выбор.
11. Метод декомпозиции, основные алгоритмы
12. Сортировка методом слияния, методом естественного двухпутевого слияния, быстрая сортировка, Сортировка вставкой.
13. Бинарный поиск. Однородный бинарный поиск. Обход бинарного дерева.
14. Умножение больших целых чисел. Алгоритм Штрассена.
15. Задача о паре ближайших точек.
16. Метод уменьшения размера задачи, основные алгоритмы.
17. Поиск в ширину. Поиск в глубину.
18. Алгоритмы генерации комбинаторных объектов.
19. Основная теорема о рекуррентных соотношениях.
20. Оценка вычислительной сложности рекурсивных алгоритмов.
21. Метод динамического программирования.
22. Основные сложностные классы задач. NP-полные задачи и особенности решающих их алгоритмов.
10. Порядок формирования оценок по дисциплине
По всем видам работ выставляется 10-балльная оценка. Оценивается практические работы студентов Оаудиторная, сдача практической работы включает опрос, как устной форме, так и в форме компьютерного тестирования. Оценки за работу на практических занятиях выставляются в рабочую ведомость.
Накопленная оценка формируется из оценок за практические работы и оценки за контрольную работу:
Онакопленная= 0,4 * ОКР + 0,2 * Опр1 + + 0,2 * Опр2+ 0,2 * Опр3
Способ округления — арифметический.
Оценка итогового контроля во втором модуле в форме зачета определяется соотношением:
Оитоговая = 0,5 * Онакопленная + 0,5 *·Оэкзамен
Оценка округляется вверх. Перевод в 5-балльную шкалу осуществляется по правилу:
· 0 ≤ К ≤ 3 - неудовлетворительно,
· 4 ≤ К ≤ 5 - удовлетворительно,
· 6 ≤ К ≤ 7 - хорошо,
· 8 ≤ К ≤10 - отлично.
11. Учебно-методическое и информационное обеспечение дисциплины
11.1 Базовый учебник отсутствует
11.2 Основная литература
1. Алгоритмы: построение и анализ, 2-е издание. — Пер. с англ. — М.; СПб.; Киев: Издательский дом «Вильямс», 2011. — 1296 с.
2. Ульянов -эффективные компьютерные алгоритмы: разработка и анализ. — М.: ФИЗМАТЛИТ, 2008. — 304 с.
3. Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы: Пер. с англ.: - М.: Издательский дом «Вильямс», 2001 г. -384 с., ил.
11.3 Дополнительная литература
1. Аляев математика и математическая логика. — М.: Финансы и статистика, 2006. — 368 с.
2. Макконнел Дж. Анализ алгоритмов. Вводный курс. - М.: Техносфера, 2002 г. -304 с.
3. Карпов автоматов - СПб.: Питер, 2002 г. - 224с., ил.
4. Седжвик, Р. Фундаментальные алгоритмы на С. СПб. ДиаСофтЮП, 2003. - 1127 с.
5. Искусство программирования. Тома 1, 2, 3. 3-е изд. Пер. с англ. : Уч. пос. - М.: Изд. дом "Вильямс", 2001 г.
11.4 Справочники, словари, энциклопедии
· http://algs4.cs. princeton. edu/
· http://calgo. acm. org/
· htpp://www-cs-faculty. stanford. edu
· htpp://
11.5 Программные средства
Практические занятия проводятся в компьютерном классе с выходом в Интернет и доступом к ресурсам электронной библиотеки НИУ ВШЭ.
Для успешного освоения дисциплины, студент использует следующие программные средства:
· Microsoft Office Professional 2007-2010;
· Microsoft Visual Studio 2008-2010.
12. Материально-техническое обеспечение дисциплины
Проектор для лекций и семинаров, классы для семинаров с компьютерами, на которых установлена инструментальная среда Microsoft Visual Studio 2010.
