算法方法实验室是在 俄罗斯科学院斯捷克洛夫数学研究所圣彼得堡分所 (PDMI RAS) 在教授 费奥多尔·弗拉基米罗维奇·福明 (Fedor Fomin) 的指导下，并获得 俄罗斯联邦教育与科学部 的支持（第220号法令，“巨额资助”项目）。
算法解决方案被应用于处理支撑互联网搜索引擎、计算机图形学和生物信息学等技术成就的基础数据。实验室工作人员正在开发设计与分析算法以及研究计算任务复杂性的新方法。
项目名称： 构建新型高效算法并证明计算任务的难度
目标与任务
研究方向： 算法与复杂性理论
项目目标： 解决现代数学和计算机科学的基础问题：研究计算任务的复杂性
研究的实际意义
组织与基础设施变革：
实验室基础上成立了一个非营利性科研教育中心，每年开设约20门关于理论计算机科学和编程的公开课程。课程由现职科学家和执业专家授课。所有课程的视频记录和材料均在计算机科学俱乐部（Computer Science Club）网站上公开。
算法解决方案被应用于处理支撑互联网搜索引擎、计算机图形学和生物信息学等技术成就的基础数据。实验室工作人员正在开发设计与分析算法以及研究计算任务复杂性的新方法。
项目名称： 构建新型高效算法并证明计算任务的难度
目标与任务
研究方向： 算法与复杂性理论
项目目标： 解决现代数学和计算机科学的基础问题：研究计算任务的复杂性
研究的实际意义
其他成果
- 组织了多场关于算法和复杂性理论的大型国际会议：2015年第三届圣彼得堡逻辑与可计算性日、2016年第11届俄罗斯国际计算机科学研讨会、2016年第15届实验算法国际研讨会、2017年弱算术研讨会、“2017年圣彼得堡机器学习与算法分析”。200多位算法理论和计算机科学领域的俄罗斯及国际顶尖专家访问了该研究所。
- 实验室工作人员负责管理10多个获得资助的项目，其中包括俄罗斯基础研究基金会、俄罗斯科学基金会、俄罗斯联邦总统资助委员会以及其他预算和商业机构的资助。
- 实验室员工每年与Yandex、三星研究中心、华为等机构签署开展研究和编写讲座课程的商业合同。
- 研究团队成员定期在全球各地的国际研讨会和会议上发表报告。
科学成果
- 改进了布尔电路规模的下限估计。该评估不仅刷新了此类电路规模的世界纪录，也是自1984年以来，针对最基础计算模型之一的已知下限的首次改进。
- 解决了图同态和子图计算复杂性的基础问题。寻找这些问题的精确渐近复杂性估计曾是指数算法领域的核心开放性问题之一。
- 获得了最短公共超串问题的首批参数化算法，该问题是基因组组装问题的数学模型。
- 开发了一种通过分布模拟时间层次结构来证明启发式计算时间层次定理的方法。时间层次定理是用于解决复杂性理论中核心问题——区分复杂性类的主要工具。
组织与基础设施变革：
实验室基础上成立了一个非营利性科研教育中心，每年开设约20门关于理论计算机科学和编程的公开课程。课程由现职科学家和执业专家授课。所有课程的视频记录和材料均在计算机科学俱乐部（Computer Science Club）网站上公开。
教育与人才再培训
- 举办了3场国际学生学校：2014年算法与复杂性理论学生科学学校（80名参与者），以及2017年（70名参与者）和2018年（50名参与者）的两场“算法最新进展”学生学校。
- 答辩情况：1篇博士论文，4篇相关研究方向的副博士论文。
- 实验室每年招收1-2名新研究生，他们在科学团队成员的指导下在俄罗斯科学院斯捷克洛夫数学研究所圣彼得堡分所（POMI RAN）学习。目前，实验室成员包括5名研究生和7名副博士。在5名博士中，有一位是俄罗斯科学院院士，一位是俄罗斯科学院通讯院士。
- 为本科、硕士和博士项目开发并讲授了12门理论计算机科学课程，以及针对年轻专家的进修课程。硕士课程包括：“布尔函数分析”、“高效算法”、“证明复杂性理论”、“参数化算法”、“密码学的复杂性理论基础”、“专业环境下的实践编程与数据分析”、“信息论”。本科课程包括：“数理逻辑与算法理论”、“算法理论”、“离散数学与数理逻辑基础”。进修课程包括：“流数据处理算法”、“NP难问题算法”。课程在俄罗斯科学院纳米技术科研教育中心、俄罗斯科学院圣彼得堡国立研究大学、喀山联邦大学、POMI RAN科研教育中心、高等经济学院和圣彼得堡国立大学开展。
- 组织了算法和理论计算机科学领域专家的定期讲座，以提高科学团队以及圣彼得堡其他机构学生、研究生和员工的专业水平。每学期在POMI RAN基础上开设约10门公开讲座课程（讲座视频发布在计算机科学俱乐部网站上）。
合作伙伴
- 卑尔根大学（挪威）、钦奈数学科学研究所（印度）、华沙大学（波兰）、加州大学圣地亚哥分校（美国）、图尔库大学（芬兰）、库朗数学科学研究所（美国）：开展联合研究并发表学术论文。
- 钦奈研究所（印度）、卑尔根大学（挪威）：开发了解决图和字符串难题的新型高效算法。
- 华沙大学：获得了图嵌入问题的新条件性下界估计。
- 加州大学圣地亚哥分校：在Coursera国际平台上录制了两个在线专业课程，目前全球已有超过20万名学员报名学习。
网站： https://algo.pdmi.ras.ru/
联系人： Fedor Vladimirovich Fomin
地址： 丰坦卡河滨河路 27 号
电话： +7 (812) 312-40-58
电子邮箱： admin@pdmi.ras.ru
联系人： Fedor Vladimirovich Fomin
地址： 丰坦卡河滨河路 27 号
电话： +7 (812) 312-40-58
电子邮箱： admin@pdmi.ras.ru
相关创新技术基础设施对象