Правительство Российской Федерации

Нижегородский филиал

Федерального государственного автономного образовательного учреждения высшего профессионального образования
"Национальный исследовательский университет
"Высшая школа экономики"

Факультет бизнес-информатики и прикладной математики

Программа дисциплины «Алгоритмы и структуры данных»

для направления 010400.62 «Прикладная математика и информатика»

подготовки бакалавра

Автор программы: преподаватель , *****@***ru

Одобрена на заседании кафедры ПМИ «___»____________ 2011 г.

Зав. кафедрой _______________________

Рекомендована секцией УМС «Прикладная математика» «___»________ 2011 г.

Председатель _______________________

Утверждена УМС НИУ ВШЭ – Нижний Новгород «___»_____________2011 г.

Председатель ________________________

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

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

2  Область применения и нормативные ссылки

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

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

Программа разработана в соответствии с:

·  ОС ГОБУ ВПО ГУ-ВШЭ по направлению 010400.62 «Прикладная математика и информатика»;

НЕ нашли? Не то? Что вы ищете?

·  Образовательной программой 010400.62 «Прикладная математика и информатика».

·  Рабочим учебным планом университета по направлению подготовки 010400.62 «Прикладная математика и информатика», утвержденным в 2011г.

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

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

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

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

·  Знать основные структуры данных и способы их применения

·  Уметь применять на практике изученные структуры данных

·  Приобрести опыт реализации основных структур данных и алгоритмов, использующих эти структуры

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

Компетенция

Код по ФГОС/ НИУ

Дескрипторы – основные признаки освоения (показатели достижения результата)

Формы и методы обучения, способствующие формированию и развитию компетенции

Готовность выявить естественнонаучную сущность проблем,

возникающих в ходе

профессиональной деятельности, привлечь их

для решения соответствующий физико-математический аппарат

ОНК-5

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

Чтение лекций, проведение практических занятий, самостоятельная работа

Способность понимать и применять в исследовательской и прикладной деятельности современный математический аппарат

ПК-2

Студент способен применять в

исследовательской и приклад-

ной деятельности современный

математический аппарат

Чтение лекций, проведение практических занятий, самостоятельная работа

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

ПК-8

Студент применяет знания из

области теории графов для разработки математических моделей, алгоритмических и программных решений

Чтение лекций, проведение практических занятий, самостоятельная работа

5  Место дисциплины в структуре образовательной программы

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

Изучение данной дисциплины базируется на дисциплине «Дискретная математика».

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

·  Владеть одним из объектно-ориентированных языков программирования (например, C++).

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

·  «Дискретные модели и сложность алгоритмов»

·  «Прикладная теория графов»

6  Тематический план учебной дисциплины

№

Название раздела

Всего часов

Аудиторные часы

Самостоя­тельная работа

Лекции

Семинары

Практические занятия

1

Концепция структур данных и анализ алгоритмов

10

4

2

4

2

Базовые структуры данных

74

14

16

44

3

Основные алгоритмы

52

8

8

36

4

Более сложные структуры данных

80

16

16

48

ИТОГО

216

42

42

132

7  Формы контроля знаний студентов

Тип контроля

Форма контроля

1 год

Параметры

3

4

Текущий

(неделя)

Контрольная работа

6

Написание программы

5

Написание программы

Домашнее задание

9

Написание программы

Промежуточный

Зачет

*

Тест

Итоговый

Экзамен

*

Устно-письменная работа

7.1  Критерии оценки знаний, навыков

При выполнении контрольных работ и домашнего задания студент должен реализовать предложенные структуры данных и алгоритмы. Программа оценивается по корректности реализации и качеству кода. При ответе на экзамене студент должен демонстрировать знание изученных структур данных и понимание работы соответствующих алгоритмов. Оценки по всем формам текущего контроля выставляются по 10-ти балльной шкале.

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

1.  Концепция структур данных и анализ алгоритмов. Тип данных: множество значений и набор операций. Абстрактный тип данных. Структуры представления данных. Виды асимптотических оценок алгоритмов. , ,-символика. Затраты по объему памяти и времени.

Формы и методы проведения занятий по разделу: чтение лекций, проведение практических занятий. Литература по разделу: [1] (глава 3), [2] (лекция 1), [3].

2.  Базовые структуры данных. Стеки. Очереди. Списки. Хеш-таблицы. Хеш-функции. Способы разрешения коллизий в хеш-таблицах. Двоичные деревья. Графы и способы их представления. Примеры использования этих структур.

Формы и методы проведения занятий по разделу: чтение лекций, проведение практических занятий. Литература по разделу: [1] (главы 10-12).

3.  Основные алгоритмы. Алгоритмы поиска: линейный, бинарный. Алгоритмы сортировки: пузырьковая, вставкой, слиянием, быстрая, цифровая. Алгоритмы обхода графа: поиск в ширину, поиск в глубину. Оценки трудоемкости.

Формы и методы проведения занятий по разделу: чтение лекций, проведение практичских занятий. Литература по разделу: [1] (главы 7, 8, 22).

4.  Более сложные структуры данных. Разделенные множества. Реализация разделенных множеств при помощи списков. Реализация разделенных множеств с помощью деревьев. Приоритетные очереди. Реализация приоритетной очереди на основе d-арных деревьев. Красно-черные деревья и их свойства. АВЛ-деревья и их свойства. Примеры использования этих структур.

Формы и методы проведения занятий по разделу: чтение лекций, проведение практических занятий. Литература по разделу: [1] (главы 13, 21), [2] (лекции 3,4), [3].

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

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

10  Оценочные средства для текущего контроля и аттестации студента

10.1  Тематика заданий текущего контроля

Примерные задания для контрольных работ и домашнего задания:

1.  Реализовать структуру данных стек. С использованием этой структуры реализовать синтаксический анализатор арифметических выражений.

2.  Реализовать три алгоритма сортировки, провести сравнительные тесты и изобразить график времени работы предложенных алгоритмов.

3.  Реализовать структуру данных кольцевой список. С использованием этой структуры реализовать систему для арифметических действий над многочленами от нескольких переменных.

10.2  Вопросы для оценки качества освоения дисциплины

Примерный перечень вопросов к экзамену по всему курсу.

1.  Понятие об абстрактных типах данных и структурах данных для их реализации в памяти прямого доступа. Примеры абстрактных типов данных.

2.  Виды асимптотических оценок алгоритмов. , ,-символика.

3.  Стек. Его реализация и примеры использования.

4.  Очередь. Её реализация и примеры использования.

5.  Различные виды списков. Примеры применения.

6.  Реализация кольцевого списка. Оценки трудоемкости операций.

7.  Хеш-таблица. Хэш-функции. Способы разрешения коллизий.

8.  Реализаций хеш-таблицы с разрешением коллизий с помощью цепочек. Оценки трудоемкости операций.

9.  Реализаций хеш-таблицы с разрешением коллизий с помощью открытой адресации. Оценки трудоемкости операций.

10.  Двоичные деревья и их применение.

11.  Графы и способы их представления.

12.  Алгоритмы сортировок с оценками трудоемкости.

13.  Быстрая сортировка. Оценка трудоемкости.

14.  Цифровая сортировка. Оценка трудоемкости.

15.  Алгоритмы обхода графа. Поиск в глубину. Поиск в ширину.

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

17.  Реализация разделенных множеств с помощью списков, оценки трудоемкости операций.

18.  Реализация разделенных множеств с помощью деревьев, оценки трудоемкости операций.

19.  Свойства d-арных деревьев. Оценка высоты d-кучи, состоящей из n элементов.

20.  Реализация приоритетной очереди на основе d-кучи. Оценки трудоемкости операций.

21.  Написать псевдокод операции всплытия в d-куче. Оценить трудоемкость этой операции.

22.  Написать псевдокод операции погружения в d-куче. Оценить трудоемкость этой операции.

23.  Написать псевдокод операции окучивания массива. Оценить трудоемкость этой операции.

24.  Написать псевдокод операции изъятия элемента с минимальным ключом из d-кучи. Оценить трудоемкость этой операции.

25.  Красно-черные деревья и их свойства.

26.  АВЛ-деревья и их свойства. Оценки трудоемкости операций.

11  Порядок формирования оценок по дисциплине

Преподаватель оценивает самостоятельную работу студентов по правильности выполнения домашних работ, задания для которых выдаются на практических занятиях. Оценки за самостоятельную работу студента преподаватель выставляет в рабочую ведомость. Накопленная оценка по 10-ти балльной шкале за самостоятельную работу определяется перед промежуточным и итоговым контролем – Осам. работа.

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

Отекущий = 0.5*Ок/р1 + 0.5*Одом;

Результирующая оценка за промежуточный контроль в форме зачета выставляется по следующей формуле, где Озачет – оценка за работу непосредственно на зачете:

Опромежуточный = 0.2*Отекущий + 0.2*Осам. работа + 0.6*Озачет;

Результирующая оценка за итоговый контроль в форме экзамена выставляется по следующей формуле, где Оэкзамен – оценка за работу непосредственно на экзамене:

Оитоговый = 0.2*Ок/р2 + 0.2*Осам. работа + 0.6*Оэкзамен;

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

Одисциплина = 0.5*Опромежуточный + 0.5*Оитоговый

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

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

12.1  Базовый учебник

[1].  Алгоритмы: построение и анализ. – М.; СПб.; Киев: Вильямс, 2011. – 1290 с.

12.2  Дополнительная литература

[2].  , Таланов данных и модели вычислений http://www. *****/department/algorithms/dscm/

[3].  , . Графы и алгоритмы. Структуры данных. Модели вычислений. – Бином. Лаборатория знаний. 2009.

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

Для выполнения и демонстрации лабораторных работ предполагается использовать ресурсы вычислительного кластера НИУ ВШЭ – Нижний Новгород.

Автор программы