Ру
En
数字之谜被揭开：库兹巴斯国立技术大学学生成为全俄竞赛优胜者
发布时间：2026-04-13 09:02 来源：库兹巴斯国立技术大学
全俄科研、设计与创意作品竞赛 “获得的一代” 在莫斯科落下帷幕。信息技术、机械制造与汽车工程学院二年级学生 玛丽亚·韦季谢娃 参加了比赛，并在 “数学与信息技术”方向 获得 第一名。
“我已不是第一次参加这个竞赛了——去年我也获得了一等奖证书。因此本季组织者直接邀请我参加了函授阶段。”——玛丽亚指出。
这位学生展示了题为 “塔内吉问题的计算复杂度分析及数算术表示搜索算法开发” 的作品，该作品是在数学系副教授安娜·佳吉列娃的指导下完成的。
塔内吉问题是一个著名的数学难题：使用从1到9的严格有序数字序列和基本运算，通过算术表达式来表示自然数。对于大多数数字，已经找到了这样的表示，但对于10958这个数字，至今仍未找到解法。这表明搜索空间的非平凡性以及问题计算复杂度缺乏形式化分类。
玛丽亚设定了一个基础科学任务：确定该问题的计算复杂度。她证明，表达式合成问题属于NP困难问题类别，即除非P≠NP，否则不存在通用的快速算法。这是一个重要的理论成果。
实践部分包括用Python开发一个软件包，采用带优化的递归完全枚举算法（中间结果记忆化、剪除不相关搜索分支）。对0到500的数字进行了计算实验，构建了一个“复杂度图谱”，可视化显示哪些数字容易求解，哪些需要大量计算资源。
“塔内吉问题看起来像是个玩具问题，但其背后隐藏着关于计算复杂度本质的深刻问题。我的研究表明，即使一个漂亮的谜题也可能是NP困难的。而所开发的算法可用于测试符号计算方法以及解决其他组合问题。”——这位学生讲述道。
祝贺玛丽亚获胜，并祝愿她取得新的科学成就！
背景资料
竞赛的组织者为“集成”国家系统。从事科学或研究活动的14至35岁的高中生和大学生均可参加。竞赛分三个阶段进行：首先是地区选拔赛，成功通过者将材料送交评审，并在全俄函授阶段的论文集中发表摘要。最后阶段是全俄面审阶段，以会议形式在首都举行。