报告时间：2025年6月9日14:00-15:30

报告地点：大连海事大学船电楼A306

报告摘要：当前电子计算机难以有效求解所谓的“组合爆炸”问题。这类问题的显著特点是随着问题规模的增加，所需的计算量会呈指数级增长。它们属于NP完全问题，例如资源分配、逻辑电路设计、路径规划、蛋白质结构预测、密码破译等等。幸运的是，所有NP完全问题本质上是等价的。这意味着，我们只需深入研究其中一类NP完全问题，便能将所得结论推广至其他所有NP完全问题。围绕图着色这一典型的NP完全问题，报告人将从图的结构与构造、相关算法设计，到对计算模型的探索展开汇报。在计算模型方面，介绍了并行型DNA计算模型，基于该模型，团队完成了61个顶点图着色问题的求解实验，使生物计算的搜索规模达到了359，为迄今国际上最大规模的生物实验。受DNA计算模型及其硬件实现的启发，报告人提出了一种底层并行计算的9-元组计算模型，称为探针机。其数据是多维的，“探针”是类比生物技术中的概念，用于寻找特定数据，并把它们关联起来的“粘合剂”。然后介绍了基于生物和电子技术的两类探针计算机模型。其中，阻断非解探针计算系统成功应用于求解114个顶点的图着色问题，展现了生物计算在复杂问题求解中的潜力。基于FPGA卡的电子探针计算机具有高并行性、可扩展性以及对NP完全问题的通用求解能力，为高效计算提供了新的思路。

报告人简介：

许进，北京大学教授，北京工商大学计算机与人工智能学院院长，博士生导师。理学、工学双博士。主要从事理论计算机与算法研究。出版学术专著7部、译著1部，发表学术论文300余篇。作为第一完成人，获国家自然科学二等奖1项、教育部自然科学一等奖2项、湖北省自然科学一等奖1项。先后主持国家自然科学基金重点项目、重大国际合作项目、专项基金项目、重大仪器专项、863项目、国家重大工程、国家重点研发计划共超十项。现任中国电路与系统学会副主任委员、中国通信学会云计算与大数据委员会副主任委员、中国网络空间安全协会理事、中国电子学会电路与系统分会生物计算与生物信息处理专委会理事长；《Artificial Intelligence Review》与《电子与信息学报》副主编，《电子学报》、《计算机学报》与《软件学报》编委；曾任军委科学技术委领域专家、电子学会图论与系统优化专委会理事长、湖北省运筹学会理事长、北京市运筹学会副理事长、教育部网络空间安全教咨委委员；第一、二、四、五、七、八届国际生物计算机大会主席。