Основы анализа алгоритмов. Алгоритмы и анализ сложности

Алгоритмы и анализ сложности

Содержание курса (с1)

Введение в теорию алгоритмов. Основы теории вычислимости.

История возникновения теории алгоритмов. Определение понятия "Алгоритм", основные требования, предъявляемые к алгоритму. Классификации алгоритмических моделей. Машина Поста. Машина Тьюринга. Описание, способы задания, особенности программирования машин Тьюринга (МТ). Основные операции над МТ, доказательство теоремы о существовании универсальной МТ.

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

Нормальные алгоритмы Маркова.

Определение вычислимости. Разрешимые и неразрешимые проблемы. Невычислимые функции, проблема останова. Применение невычислимости.

Введение в теорию конечных автоматов (КА). Формальное определение КА, способы задания, примеры. Свойства и варианты конечных автоматов (КА). Контекстно-свободные грамматики. Определение понятия формального языка, грамматика языка, язык грамматики. Классификация формальных грамматик по Хомскому.

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

Асимптотический анализ верхней и средней оценок сложности алгоритмов; сравнение наилучших, средних и наихудших оценок; O-, o-, ω- и θ-нотации; стандартные классы сложности; эмпирические измерения эффективности алгоритмов; накладные расходы алгоритмов по времени и памяти; рекуррентные соотношения и анализ рекурсивных алгоритмов.