• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Algorithms and Data Structures

2018/2019
Academic Year
RUS
Instruction in Russian
3
ECTS credits
Course type:
Compulsory course
When:
1 year, 2 module

Instructor

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

Аннотация

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

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

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

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

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

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

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

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

  • неблокирующий Аудиторная работа
  • неблокирующий Контрольная работа
  • неблокирующий Экзамен
Промежуточная аттестация

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

  • Промежуточная аттестация (2 модуль)
    0.25 * Аудиторная работа + 0.25 * Контрольная работа + 0.5 * Экзамен
Список литературы

Список литературы

Рекомендуемая основная литература

  • Stephens, R. (2013). Essential Algorithms : A Practical Approach to Computer Algorithms. Indianapolis, IN: Wiley. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=619942

Рекомендуемая дополнительная литература

  • Hetland, M. L. (2010). Python Algorithms : Mastering Basic Algorithms in the Python Language. [New York, N.Y.]: Apress. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=372221