Четыре тысячи лет назад жители Вавилонии изобрели умножение. А в марте этого года математики усовершенствовали его. 18 марта 2019 два исследователя описали самый быстрый из известных методов перемножения двух очень больших чисел. Работа отмечает кульминацию давнишнего поиска наиболее эффективной процедуры выполнения одной из базовых операций математики. «Все думают, что метод умножения, который они учили в школе, наилучший, но на самом деле в этой области идут активные исследования», — говорит Йорис ван дер Хувен, математик из Французского национального центра научных исследований, один из соавторов работы.

В 1936 году советский инженер и учёный Владимир Лукьянов создал вычислительную машину, все математические операции в которой выполняла текущая вода. Гидравлический интегратор Лукьянова — первая в мире вычислительная машина для решения дифференциальных уравнений в частных производных — на протяжении полувека был единственным средством вычислений, связанных с широким кругом задач математической физики.

Математик Александр Шапеев о методах оптимизации, численном оценивании неопределенностей и быстрых алгоритмах решения.

Сколько вещественных корней имеет заданный полином с вещественными коэффициентами? Замечательная теорема Штурма дает исчерпывающее решение этой задачи. “Теорема, имя которой я имею честь носить”, – так говорил об этом результате Штурм, который считал его главным достижением своей жизни. Совместна ли заданная система полиномиальных уравнений и неравенств от нескольких вещественных переменных? Теорема Зайденберга–Тарского, отвечающая на этот вопрос, является грандиозным многомерным обобщением теоремы Штурма. В лекциях будет рассказано новое наглядное решение задачи Штурма. Оно несложно переносится на многомерный случай и приводит к доказательству теоремы Зайденберга–Тарского.

Теория сложности вычислений — бурно развивающаяся область теоретической информатики (theoretical computer science) и охватывает как чисто теоретические вопросы, так и вопросы, непосредственно связанные с практикой. Среди наиболее важных приложений этой теории можно назвать способы построения и анализа эффективных алгоритмов, а также современные криптографические методы. Поэтому знакомство с основами теории сложности, безусловно, полезно любому, кто собирается серьезно заниматься практическим программированием или теоретическими исследованиями.

Возможно ли в линейной алгебре получение новых результатов? Почему в университетах этот курс учат неправильно? Какое матричное разложение является самым важным? Об умножении матрицы на вектор, быстрых алгоритмах и сингулярном разложении. рассказывает доктор физико-математических наук Иван Оселедец.

В вычислительной математике обычно ставится конкретная вычислительная задача, которая затем решается с целью получить результат — в точности как типичный сеанс работы в Mathematica. В чистой математике, напротив, берутся некоторые математические объекты, результаты или структуры, формируются некоторые гипотезы относительно них и потом приводятся доказательства верности выдвинутых гипотез. Большое число чистых математиков продолжает делать всё точно также, как это делалось веками — от руки и на бумаге. Как же эффективно привнести технологии в такой рабочий процесс?

Математики из Университета Техаса в Остине с помощью компьютерных методов решили задачу о булевых пифагоровых тройках. Полная запись решения занимает около 200 терабайт, что делает его самым большим доказательством из существующих. На решение задачи ушло два дня непрерывной работы 800-процессорного суперкомпьютера.

Пожалуй ни одно другое достижение современной теории сложности вычислений не вызывает такого живого интереса и не менее яростных споров как модель квантовых вычислений. Предметом дискуссии, однако, в основном является возможность физической реализации квантового компьютера, чего мы, к счастью, касаться не будем. Вместо этого мы попробуем разобраться в чисто математических аспектах этой модели и, в частности, постараемся пройти столько из нижеследующего, сколько позволит время: Классические и квантовые схемы; Алгоритм Шора быстрого разложения чисел на множители: основные идеи; Квантовые оракулы и задача о скрытой подгруппе; Алгоритм квантового поиска Гровера.

Как грамотно вычислить значение полинома от многих переменных? Можно, конечно, посчитать по отдельности каждый входящий в него моном и результаты сложить, но нельзя ли придумать способ сэкономить на числе используемых операций хотя бы для некоторых наиболее важных и часто встречающихся полиномов? Изучением таких вопросов как раз и занимается теория алгебраической сложности вычислений. Оказывается, что для некоторых классов полиномов ответ отрицателен, для других он положителен, а в подавляющем большинстве случаев ответ неизвестен. Соответствующие вопросы, открытые в течении нескольких десятилетий, по праву числятся среди наиболее важных, интересных и трудных проблем современной теории сложности.

О сложности вычислений и квантовых компьютерах рассказывает Александр Ханиевич Шень — кандидат физико-математических наук, научный сотрудник Института проблем передачи информации РАН (Москва) и LIF CNRS — Лаборатории информатики Национального центра научных исследований Франции (Марсель). Лекция была прочитана 23 апреля 2009 года в Москве, в ФИАНе.