Загадка чисел раскрыта: студентка КузГТУ – победительница всероссийского конкурса

В Москве завершился Всероссийский конкурс научно-исследовательских, проектных и творческих работ «Обретённое поколение». В нём приняла участие студентка 2 курса института информационных технологий, машиностроения и автотранспорта Мария Ведищева и заняла 1 место в направлении «Математика и информационные технологии».

Я уже не первый раз принимаю участие в этом конкурсе – в прошлом году я также получила диплом I степени. Поэтому в этом сезоне организаторы сразу пригласили меня на заочный этап, - отметила Мария.

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

Задача Танежи — это известная математическая головоломка: представить натуральные числа с помощью арифметических выражений, используя строго упорядоченную последовательность цифр от 1 до 9 и базовые операции. Для большинства чисел такие представления найдены, но для числа 10 958 до сих пор нет решения. Это указывает на нетривиальную структуру пространства поиска и отсутствие формальной классификации вычислительной сложности задачи.

Мария поставила фундаментальную научную задачу: определить вычислительную сложность проблемы. Она доказала, что задача синтеза выражения относится к классу NP-трудных задач, то есть универсального быстрого алгоритма для неё не существует, если только P ≠ NP. Это важный теоретический результат.

Практическая часть работы включала разработку программного комплекса на Python с рекурсивным алгоритмом полного перебора и оптимизациями (мемоизация промежуточных результатов, отсечение нерелевантных ветвей поиска). Был проведён вычислительный эксперимент для чисел от 0 до 500, построена «карта сложности», визуализирующая, какие числа даются легко, а какие требуют больших вычислительных затрат.

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

Поздравляем Марию с победой и желаем новых научных свершений!