Алгоритмика

Программа курса

• Понятие алгоритма. Скользящее среднее. Метод двух указателей.
  • Введение в алгоритмы
    • Понятие сложности алгоритма. O-нотация. Оценка времени
    • Исполнения программы. Уроки про алгоритмические собеседования.
• Основные структуры данных
  • Массив, связный список, стек, очередь. Сложность операций
  • вставки, поиска и удаления. Представление данных в памяти.
  • Пространственная сложность алгоритма.
• Рекурсия
  • Квадратичные сортировки. Сортировка слиянием. Быстрая
  • сортировка. Линейная сортировка подсчётом.
• Хеш-функции и хеш-таблицы
  • Абстракция отображения. Понятие и свойства хеш-функции,
  • примеры. Структура данных хеш-таблица. Коллизии и способы
  • их разрешения.
• Деревья
  • Структура данных дерево. Сбалансированные деревья поиска.
  • Структура данных куча. Пирамидальная сортировка.
• Графы
  • Определение графа, способы представления в памяти. Обход графа
  • в глубину и в ширину. Компоненты связности. Алгоритмы поиска
  • кратчайшего пути. Минимальное остовное дерево.
• Жадные алгоритмы
  • Понятие жадного алгоритма, область применения. Примеры,
  • доказательство корректности алгоритма.
• Динамическое программирование
  • Определение, одномерная и двумерная динамика, доказательство 

  • по индукции и классические задачи.
• Практика решения задач