Алгоритмы и анализ сложности

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Саратовский государственный университет имени

Факультет компьютерных наук и информационных технологий

УТВЕРЖДАЮ

___________________________

"__" __________________20__ г.

Рабочая программа дисциплины

АЛГОРИТМЫ И АНАЛИЗ СЛОЖНОСТИ

Направление подготовки

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

Профиль подготовки

Информатика и компьютерные науки

Квалификация (степень) выпускника

Бакалавр

Форма обучения

Очная

Саратов,

2011 год

Цели освоения дисциплины

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

2.Место дисциплины в структуре ООП бакалавриата

Данная учебная дисциплина входит в раздел «Профессиональный цикл. Базовая часть» ФГОС-3.

Для изучения дисциплины необходимы компетенции, сформированные у обучающихся в результате изучения дисциплин «Теоретическая информатика» и «Дискретная математика».

3 Компетенции обучающегося, формируемые в результате освоения дисциплины

Данная дисциплина способствует формированию следующих компетенций:

- способность понимать и применять в исследовательской и прикладной деятельности современный математический аппарат, фундаментальные концепции и системные методологии, международные и профессиональные стандарты в области информационных технологий, способность использовать современные инструментальные и вычислительные средства (в соответствии с профилем подготовки) (ПК-4);

- детальное знание методов и базовых алгоритмов обработки информационных структур, методов анализа сложности алгоритмов (ПК-17)

- уверенное знание теоретических и методических основ, понимание функциональных возможностей, следующих предметных областей: Разработка информационных систем; Моделирование и анализ программного обеспечения; Технологии мультимедиа; Архитектура и организация компьютеров; Конфигурирование и использование операционных систем; Разработка и принципы сетевых технологий; Человеко-машинное взаимодействие; Приложения и использование баз данных; Социальные и этические вопросы ИТ; Анализ технических требований; Графика и визуализация; Интеллектуальные системы; Теория баз данных; (ПК-25)

- способность решать задачи производственной и технологической деятельности на высоком профессиональном уровне, включая: разработку математических, информационных и имитационных моделей по тематике выполняемых опытно-конструкторских работ и проектов; создание информационных ресурсов глобальных сетей, образовательного контента, прикладных баз данных; разработку тестов и средств тестирования систем и средств на соответствие стандартам и исходным требованиям; разработку эргономичных человеко-машинных интерфейсов в соответствии с профилизацией (ПК-28).

В результате освоения дисциплины обучающийся должен:

Знать:

· методы и базовые алгоритмы обработки информационных структур;

· методы анализа сложности алгоритмов;

· теоретические основы моделирования и анализа программного обеспечения;

· классы сложности программ;

Уметь:

· использовать современный математический аппарат для анализа сложности программного обеспечения;

· разрабатывать алгоритмические и программные решения в различных областях программирования;

Владеть

· навыками анализа программного обеспечения;

· навыками использования современных инструментальных и вычислительных средств;

4. Структура и содержание дисциплины

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

№ п/п	Раздел дисциплины	Семестр	Неделя семестра	Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах)	Формы текущего контроля успеваемости (по неделям семестра) Формы промежуточной аттестации (по семестрам)
1	Основы анализа алгоритмов.	3	1-7	Л:14	СР:8	Пр:2	Тест №1 на 7 неделе.
2	Стратегии алгоритмов.	3	8-9	Л:4	СР:6	Пр:4	Тест №2 на 9 неделе.
3	Основные алгоритмы обработки информации.	3	10	Л:2	СР:10	Пр:18	Контрольная работа №1 на 12 неделе.
4	Распределенные алгоритмы.	3	11-14	Л:8	СР:4	Пр:4	Тест №3 на 14 неделе.
5	Основы теории вычислимости.	3	15-18	Л:8	СР:8	Пр:8	Контрольная работа №2 на 18 неделе.
	Текущая аттестация		Экзамен
	ИТОГО	36	36	36	36

Раздел «Основы анализа алгоритмов». Асимптотический анализ верхней и средней оценок сложности алгоритмов; сравнение наилучших, средних и наихудших оценок; O-, o-, ω- и θ-нотации; стандартные классы сложности; эмпирические измерения эффективности алгоритмов; накладные расходы алгоритмов по времени и памяти; рекуррентные соотношения и анализ рекурсивных алгоритмов.

Раздел «Стратегии алгоритмов». Полный перебор; метод «разделяй и властвуй»; «жадные» алгоритмы; бэктрекинг (перебор с возвратами); метод ветвей и границ; эвристический поиск; поиск по образцу, алгоритмы обработки строк; алгоритмы аппроксимации числовых функций.

Раздел «Основные алгоритмы обработки информации». Основные алгоритмы над числами; алгоритмы последовательного и бинарного поиска; алгоритмы сортировки сложности O(N*N) и O(N*logN); хеш-функции и методы исключения коллизий; деревья бинарного поиска;

Раздел «Распределенные алгоритмы». Модель параллельного выполнения программы с общей памятью и модель передачи сообщений: организация параллельных вычислений на принципе консенсуса и на основе выбора; методы определения завершения параллельных вычислений.

Раздел «Основы теории вычислимости». Конечные автоматы; контекстно-свободные грамматики; разрешимые и неразрешимые проблемы; невычислимые функции; проблема останова; применение невычислимости.

5. Образовательные технологии

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

6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины.

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

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

1.  Алгоритмы. Построение и анализ = Introduction to Algorithms / Т. Кормен [и др.] ; пер. с англ. , , ; под ред. . - 2-е изд. - М. ; СПб. ; Киев: Вильямс, 2005.
Князева : от алгоритма к программе: учеб. пособие / . - М. : КУДИЦ-ОБРАЗ, 2006.

2.  Макконелл Дж. Основы современных алгоритмов: учеб. пособие по направлению подготовки специалистов "Информатика и вычислительная техника" / Дж. Макконелл. - 2-е доп. изд. - М. : Техносфера, 2004.
Макконелл, Дж. Основы современных алгоритмов: учеб. пособие / Дж. Макконелл ; пер. с англ. под ред. . - 2-е изд., доп. - М. : Техносфера, 2006.

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

1.  Введение в распределенные алгоритмы = Introduction to Distributed Algorithms / Ж. Тель; пер. с англ. . - М.: Изд-во МЦНМО, 2009.

2.  Гергель и практика параллельных вычислений : учеб. пособие / . - М.: Интернет-Ун-т Информ. Технологий: БИНОМ. Лаб. знаний, 2007.

3.  Структуры данных и алгоритмы = Data Structures and Algorithms : учеб. пособие / , Дж. Э. Хопкрофт, Дж. Д. Ульман ; пер. с англ. и ред. . - М. ; СПб. ; Киев : Вильямс, 2007.

в) программное обеспечение и Интернет-ресурсы:

Не требуется

8. Материально-техническое обеспечение дисциплины

Мультимедийная лекционная аудитория (наличие проектора и проекционного экрана).

Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по направлению и профилю подготовки «Информатика и компьютерные науки»

Автор:

зав. кафедрой МКиКН .

Программа одобрена на заседании кафедры Математической кибернетики и компьютерных наук от «22» февраля 2011 г., протокол

Зав. кафедрой МКиКН .

Декан факультет .