Алгоритмы и модели вычисления

Эта книга написана по мотивам материалов одноименного курса кафедры МФТИ. Курс вел Сергей Тарасов, и он же придумал концепцию, сильно отличающую «Алгоритмы и модели вычисления» от других аналогичных курсов. Стандартный курс по алгоритмам — обзор основных алгоритмов (быстрая сортировка, поиск медианы, обходы графов) и структур данных, необходимых каждому программисту. Нетрудно видеть, что почти все эти основные алгоритмы возникли во время решения некоторых математических задач.

Читая «Алгоритмы и модели вычисления», Сергей в первую очередь стремился продемонстрировать связь алгоритмов и математики, какие алгоритмы и как позволяют решать математические задачи (из самых разных областей, будь то теория чисел или топология) и какая математика лежит в основе тех или иных алгоритмов. Теория алгоритмов возникла естественным образом из вычислительных задач в разных областях математики и по сей день остается живой областью, в которой некоторые тривиально сформулированные вопросы до сих пор открыты.

В этой книжке мы расскажем математическим языком об основных алгоритмах сортировки, алгебры, теории чисел и теории графов. Многие школьники изучают алгоритмы, готовясь к олимпиадам по программированию. Возможно, что эта книга поможет математикам-олимпиадникам, не занимавшимся алгоритмами, заинтересоваться олимпиадным программированием, а может быть — и теорией алгоритмов.