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

Санкт-Петербург, осень 2017

Описание

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

Содержание

Методы

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

Структуры данных

Базовые структуры (массивы, списки, стеки, очереди); очереди с приоритетами; системы непересекающихся множеств; хеш-таблицы; сбалансированные деревья

Алгоритмы на графах

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

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

Поиск образца в строке, суффиксное дерево, суффиксный массив, преобразование Барроуза–Уиллера

Алгоритмы и теория сложности

Потоки в сетях, линейное программирование, NP-полные задачи, алгоритмы для NP-полных задач

Оценка за курс

Оценка будет складываться из:

  • Обратная связь по онлайн-курсу (10%)
  • Теоретические задачи (45%)
  • Задачи на программирование (45%)

Для получения оценки отлично необходимо будет набрать хотя бы 80%, хорошо — хотя бы 70%, удовлетворительно — хотя бы 60% (данные проходные баллы могут слегка поменяться).

Преподаватели