🔥 На прошлой неделе закончился цикл лекций, который для учеников математического профиля провели кандидат физико-математических наук, старший научный сотрудник Математического института им. В.А. Стеклова РАН Станислав Олегович Сперанский и доктор физико-математических наук, ведущий научный сотрудник Математического института им. В.А. Стеклова РАН Степан Львович Кузнецов. С.О. Сперанский прочитал второшкольникам две лекции на тему “Открытие алгоритмической неразрешимости”. Формализация понятия вычислимой функции и появление естественных примеров алгоритмически неразрешимых проблем — яркие события в истории современной математики и информатики, связанные с пионерскими работами Алана Тьюринга. Лекции были посвящены стоящему за этими событиями математическому аппарату и его применениям. В частности, была приведена схема доказательства неразрешимости небезызвестной «проблемы остановки». Также была обсуждена (не)разрешимость алгоритмических проблем в области алгебры. С. Л. Кузнецов посвятил свои две лекции теме “Алгоритмическая сложность”. Помимо абстрактной алгоритмической разрешимости интерес обычно представляет сложность алгоритмических задач, измеряемая прежде всего как время работы соответствующего алгоритма. «Эффективно» разрешимыми принято считать задачи, для которых существует алгоритм, время работы которого ограничено некоторым многочленом от размера входных данных. Такого рода задачи относятся к классу P (полиномиально разрешимые). Есть также более высокий класс сложности NP, в который входят задачи, решаемые перебором объектов полиномиальной длины. На лекциях было рассказано о проблеме равенства классов P и NP. В случае, если они не равны, «самые сложные» задачи в классе NP (так называемые NP-полные) не являются полиномиально разрешимыми. Были приведены примеры таких задач из логики и теории графов. Мы благодарим наших гостей из Математического института им. В. А. Стеклова РАН за содержательные занятия с второшкольниками и надеемся на дальнейшее сотрудничество!