Алгоритмы и структуры данных

Магистратура 2019/2020

Лучший по критерию «Полезность курса для Вашей будущей карьеры»

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

Статус: Курс адаптационный (Анализ больших данных в бизнесе, экономике и обществе)

Направление: 01.04.02. Прикладная математика и информатика

Кто читает: Департамент информатики

Где читается: Санкт-Петербургская школа физико-математических и компьютерных наук

Когда читается: 1-й курс, 1 модуль

Формат изучения: с онлайн-курсом

Преподаватели: Копелиович Сергей Владимирович, Сироткин Александр Владимирович

Прогр. обучения: Анализ больших данных в бизнесе, экономике и обществе

Язык: русский

Кредиты: 3

Контактные часы: 4

Полная версия программы учебной дисциплины

Аннотация

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

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

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

Планируемые результаты обучения

Способен давать оценку сложности поставленной задачи и оценивать вычислительную сложность алгоритмов решения задачи. Способен выбирать оптимальный алгоритм.
Способен выбирать оптимальный алгоритм. Способен проводить сортировку алгоритмов. Изучил: представление графов в виде списков смежности и матрицы смежности; в ориентированных и неориентированных графах; двунаправленный поиск путей в графах; поиск кратчайших путей во взвешенном графе, алгоритмы Беллмана – Форда, Флойда – Уоршелла.
Изучил понятие жадные алгоритмы, в том числе основные принципы и примеры алгоритмов. Способен осуществлять поиск кратчайших путей в графе при помощи алгоритма Дейкстры. Владеет понятием минимальные остовные деревья: алгоритмы Прима и Крускала. Способен составить расписания для взвешенных интервалов, выравнивать текст по ширине, выравнивать последовательности.
Владеет понятиями: линейные структуры данных; амортизационный анализ; двоичные и биномиальные кучи; система непересекающихся множеств. Изучил всевозможные варианты задачи поиска подстроки в строке. Изучил понятие об алгоритме поиска реального времени; алгоритм Кнута-Морриса-Пратта, префикс-функция; алгоритм построения префикс-функции; линейность времени его работы.

Содержание учебной дисциплины

Введение. Числовые алгоритмы. Рекуррентные соотношения. Вычислительная сложность.
Алгоритмы сортировки. Декомпозиция графов. Пути в графах.
Жадные алгоритмы. Динамическое программирование.
Структуры данных: список, массив, стек, очередь, хеш-таблица, очередь с приоритетами. Алгоритмы на строках: поиск подстроки.

Элементы контроля

Работа на семинарах
Контрольная работа
Итоговый контроль

Промежуточная аттестация

Промежуточная аттестация (1 модуль)
0.5 * Итоговый контроль + 0.25 * Контрольная работа + 0.25 * Работа на семинарах

Программа дисциплины