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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

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

УТВЕРЖДАЮ

_______________________

"_____"__________________20___ г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ

Введение в алгоритмы

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

231000 – Программная инженерия

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

Разработка программно-информационных систем

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

Бакалавр

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

Очная

Саратов

2011

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

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

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

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

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

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

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

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

- готовность к использованию методов и инструментальных средств исследования объектов профессиональной деятельности (ПК-3);

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

Знать: основные алгоритмы решения распространенных классов задач и различные структуры данных, используемые в этих алгоритмах, а так же способы представления этих структур в ЭВМ на физическом и логическом уровнях.

Уметь: выбирать наиболее подходящие структуры данных для конкретной задачи и применять различные алгоритмы при решении профессиональных задач повышенной сложности.

Владеть: практическими навыками программной реализации различных алгоритмов и оценкой использования структур данных и алгоритмов их обработки.

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

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

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

«Раздел: Алгоритмы порождения комбинаторных объектов». Генерирование перестановок, генерирование подмножеств множества, генерирование k-элементных подмножеств, биномиальные коэффициенты, генерирование разбиений множества.

«Раздел: Алгоритмы поиска подстрок». Алгоритмы поиска подстроки в строке. Оценка скорости. "Наивный алгоритм". Алгоритм Рабина - Карпа. Алгоритм Кнута - Морриса – Пратта. Алгоритм Бойера – Мура.

«Раздел: Алгоритмы сортировок». Алгоритм двоичного поиска в упорядоченном массиве. Методы оценки алгоритмов сортировок: число сравнений, число перемещений, устойчивость. Сортировка "пузырьком". Сортировки простыми и двоичными вставками, их применимость и оценки. Сортировка Шелла Алгоритм слияния упорядоченных массивов. Сортировка фон Неймана (слиянием). Алгоритм пирамидальной сортировки.

Алгоритм "быстрой" сортировки. Поиск k-го наименьшего (наибольшего) элемента в массиве (поиск альфа-медианы). Сортировка подсчетом. Цифровая сортировка.

«Раздел: Деревья поиска». Двоичное дерево. Рекурсивные алгоритмы для анализа двоичного дерева. Внутренняя итерация двоичного дерева с помощью рекурсивной процедуры. Внешняя итерация узлов двоичного дерева, использующая стек для хранения пути от корня. Внешний итератор для обхода дерева "в ширину", использующий простую очередь. Поиск по ключу. Использование деревьев для поиска. Индексация данных. Алгоритмы поиска и добавления данных в лист и в корень дерева. Сбалансированные по высоте (АВЛ) деревья. Алгоритм "поворота". Добавление нового ключа в сбалансированное по высоте дерево и балансировка получившегося дерева.

Красно-черные деревья. Алгоритм добавления нового ключа в красно-черное дерево. Хранение информации о размере в двоичных деревьях поиска. Решение задач об индексации узлов в дереве. 2-3-деревья: алгоримты вставки и удаления ключей. В-деревья: область применимости и алгоритмы вставки и удаления ключей. Модификация В-дерева - В+-дерево.

«Раздел: Ассоциативный поиск и ассоциативные списки». Хеширование данных и принципы организации хеш-таблиц. Реализация простого словаря, основанного на хешировании, с хранением информации в связанных списках.

«Раздел: Алгоритмы на графах». Циклы, разрезы и задача Эйлера. Гамильтоновы циклы, цепи и задача коммивояжера. Потоки в сетях.

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

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

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

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

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

1.  Макконнелл Дж. Основы современных алгоритмов, 2-е дополненное здание. : Пер. с англ. - М.: Техносфера, 20с.

2.  Кормен Томас X., Лейзерсон Ривест Штайн

Клиффорд. Алгоритмы: построение и анализ, 2-е издание. : Пер. с англ. — М. : Издательский дом "Вильямс", 2005. — 1296 с.

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

1.  Андерсон Дискретная математика и комбинаторика.: Пер. с англ. - М., СПб., Киев : Изд. дом «Вильямс», 20с.

2.  Хусаинов Байрон Сафеевич. Структуры и алгоритмы обработки данных. Примеры на языке Си: учеб. Пособие.: - М. : «Финансы и статистика», 20с.

3.  Кнут Искусство программирования, том 3. Сортировка и поиск, 2-е издание.: Издательский дом "Вильямс", 2008. — 824 с.

4.  Ахо Хопкрофт Ульман Структуры данных и алгоритмы. : Пер. с англ. : Уч. пос. — М. : Издательский дом "Вильямс", 2000. — 384 с.

5.  Комбинаторика для программистов.: Пер. с польского. – М.: «Мир», 1988. – 201с.

6.  Перечислительная комбинаторика.: Пер. с англ. — М.: «Мир», 1990.—440 с.

7.  Теория графов. Алгоритмический подход. : — М.: Мир», 1978.—217 с.

8.  Графы, сети и алгоритмы. : Пер. с англ. — М.: «Мир», 1984.—455 с.

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

1. Операционные системы Windows ХХ или Linux.

2. Компиляторы С++ или Java.

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

Компьютерный класс. Доступ к сети Интернет.

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

Автор:

Старший преподаватель

кафедры МКиКН

Программа одобрена на заседании кафедрв МКиКН

от 22 февраля 2011года, протокол

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

к. ф.-м. н.

Декан факультета КНиИТ

к. ф.-м. н.