有限域上代数方程算法问题研究2013年度报告

该年度围绕关键科学问题"有限域上代数方程求解",结合密码学理论,在求解算法研究及其密码应用方面取得了以下3个方面的进展:(1)在有限域上方程系统求解算法方面,提出了一个二元域上带噪方程系统的求解算法;给出了一种从代数方程到CNF转换的高效算法;(2)在利用代数方程求解算法进行密码分析方面,推进了分组密码KATAN、PRINCE等分析;在多变量密码的分析方面,利用线性化方法分析了MFE改进方案、扩展的多变量公钥密码方案、两层非线性Piece in hand增强方案,用多项式向量的不确定插值方法改进了对SFLASH密码体制的攻击;利用线性化方法或格基约化算法分析了一些基于格及背包问题的密码算法;在代数攻击中自动推理方法的研究方面,利用解方程组的思想,提出了基于字的分组密码算法的不可能差分路径自动化搜索的算法,扩展了Mouha等人基于混合整数线性规划的方法,给出了一种自动化评估比特级分组密码抵抗相关密钥差分攻击安全性的方法;(3)在利用代数方法设计对称密码组件方面,给出了一系列基于线性反馈移位寄存器实现的低代价最优扩散层的构造;否证了C.Carlet于1998年提出的"任何一个AB函数都EA等价于一个置换"的猜想。除以上3个方面之外,针对ALE认证加密算法泄露消息没有受到密钥保护的特点,提出了一种新的伪造攻击方法——泄露状态伪造攻击。

选举中的算法问题

大多数人的记忆中都会有上小学时选班长的情景,再后来,我们也经历过许多不同的选举过程。如何设计公平合理的选举规则是远远超出了数学和算法范畴的复杂问题。本文只讨论在特定规则下如何获得选举结果的相关的算法。一群人按照一人一票的方式(每张选票具有相同权重)在(通常数量很少的)候选人中选出一位“胜出者”(如班长),最简单的规则就是票数最多者当选(假设没有并列)。在没有电子手段之前,最流行的做法就是投票完成后,将候选人名字列在黑板上,随着“唱票”进程,在候选人名字后画“正”字。最后数出每人得票数,即可知谁是当选者。

对算法问题的研究

在新一轮《全日制普通高中数学课程标准》中已明确把“算法”问题列为高中的必修课内容。对大多数高中数学教师来说,算法是一个全新的课题,但算法并不是我们想象的那样高深玄妙,实际上从小学的“先乘除、后加减”起我们就接触过许多算法。

算法审计需求论

算法审计是算法治理体系的重要成员,本文以经典审计理论为基础,提出算法审计需求的一个理论框架。算法的合约类委托代理关系中存在完备合约,监管类委托代理关系中算法相关法律法规发挥了类似完备合约的作用,这两类关系中都不存在算法审计需求。算法的资源类委托代理关系中,由于激励不相容、信息不对称、合约不完备和环境不确定同时存在,必须建构算法治理体系来应对算法代理问题和次优问题,算法审计基于审计固有功能对算法责任履行情况实施鉴证,发现其中存在的代理问题和次优问题,报告给委托人及其他利益相关者并推动整改,从而为算法责任的良好履行提供一定的保障。

查找问题中的算法

教育部颁布的《普通高中信息技术课程标准(2017年版)》在“必修模块1”中用专门的单元谈论了算法,这说明,新课程要求高中信息技术在教学中应当以算法为要旨,强化算法的重要性。本刊从本期起开设“算法园地”专栏,特邀北京大学计算机系原系主任李晓明教授、南京大学计算机系原系主任陈道蓄教授撰写有关算法的文章,为读者提供一些既有思想性又有实用性的材料。专栏的读者定位是对算法问题有兴趣的中小学教师,内容的铺陈将努力做到通俗性、趣味性和严谨性相结合。每月介绍一个算法,每期独立成篇,大体按照以下六个方面展开:应用背景、算法描述、实例模拟、性质分析、思考问题、参考代码。你以前如果学过算法,在这里会看到一种不同的视野;你以前如果没有学过算法,则可以通过对每月一个算法的学习,既领悟到算法思想的精髓,又形成算法实战的能力。

快速蚁群算法求解圆排列问题

圆排列问题属于NP-完全问题,且蚁群算法已成功地解决了许多组合优化的难题。介绍一种基于蚁群算法求解圆排列问题的算法,并对此算法进行优化,提出一种求解圆排列问题的快速蚁群算法。它大大减少了蚁群算法的搜索时间,有效改善了蚁群算法易于过早地收敛于非最优解的缺陷。仿真实验取得了较好的结果。

多股流换热器精确数学控制的反问题算法

在两股流换热器精确数学控制的基础上,提出多股流换热器精确数学控制中的反问题算法,对于其中存在的难以解决的多个待定系数的不适定问题,采用综合法首先将多股流换热器综合成两股流换热器,然后通过对数平均温差法来作为获得辅助流体调节量的反问题算法,最后通过多股流换热器的精确数学控制实验表明,这种控制方法无论从控制精度还是控制速率上都达到了很好的控制效果.

车辆路径问题的禁忌搜索算法研究

简要回顾了车辆路径问题的禁忌搜索算法的发展现状,提出了一种改进的禁忌搜索算法。该算法将路径问题按不同的车辆-顾客分配结构分解成若干子问题,然后用禁忌搜索算法求解每个子问题,最后从所有子问题的最优解中选出全局最优解。理论分析和实验结果表明该算法比以往的算法有以下优点:拓展了搜索空间,提高了最优解的效果;是一种将问题进行空间分解的并行算法,可采用多台计算机同时运算以减少整体运行时间。

基于鱼群算法的多维背包问题研究

将鱼群算法应用于求解多维背包问题,提出一种求解多维背包问题的鱼群算法,MKPAFSA。定义MKPAFSA中的各元素,且引入启发因子和动态因子,并对鱼群算法进行了改进和优化。它减少了人工鱼的搜索时间,有效改善了鱼群算法后期收敛较慢且一般仅能得到满意解域的缺陷。仿真试验取得了较好的结果。

一种求解0-1背包问题的快速蚁群算法

0-1背包问题是典型的NP完全问题,且蚁群算法已成功地解决了许多组合优化的难题。因此,文中介绍一种基于蚁群算法求解0-1背包问题的算法,并对此算法进行优化,提出一种求解0-1背包问题的快速蚁群算法。它大大减少了蚁群算法的搜索时间,有效改善了蚁群算法易于过早地收敛于非最优解的缺陷,当物品数较大时,也取得了较好的求解质量。仿真实验取得了较好的结果。

基于蚁群算法求解最大团问题

最大团问题是一种典型的NP完全问题,是图论中一个经典的组合优化问题。研究将蚁群算法应用于求解最大团问题,提出一种求解最大团问题蚁群算法。通过定义最大团问题蚁群算法中的各元素,并改进了蚂蚁搜索解的方法,有效地改善蚁群算法易于过早地收敛于局部最优解的缺陷。仿真实验表明,图中的顶点数较多时,也取得了较好的结果。

基于蚁群算法的多维0-1背包问题的研究

系统地阐述了蚁群算法,并对它进行改进、优化。将蚁群算法应用于求解多维0-1背包问题,提出一种求解多维0-1背包问题的算法——多维0-1背包问题蚁群算法。它大大减少了蚁群算法的搜索时间,有效改善了蚁群算法易于过早地收敛于非最优解的缺陷。仿真实验取得了较好的结果。

一个关于二次规划问题信赖域中可行下降算法

采用变量消去法化二次规划问题 ,使用一个基于信赖域子问题的内点算法来获得其可行下降方向 ,提出了关于二次规划问题信赖域中可行下降的新算法 ,证明了算法具有全局收敛性 .计算实例表明 。

人数少于任务数的全指派问题的迭代算法

针对人数少于任务数的情况,按每人至少承担一项任务,至多承担L项任务,但每项任务只允许一人承担的指派原则,给出了一种求解这种指派问题的迭代算法,该算法操作简便、易于用计算机运行。构建该算法的方法,用于某些其它指派问题,可以使相应的算法更加便捷。

改进蚁群算法求解圆排列问题

圆排列问题是典型的NP完全问题,且蚁群算法已成功地解决了许多组合优化的难题。介绍了一种求解圆排列问题的蚁群算法,并通过改变概率、下一个元素的选择方式以及采用分段交换,对求解圆排列问题的蚁群算法进行了优化。提出了一种改进的蚁群算法,并将其应用于求解圆排列问题。仿真实验的结果表明,该方法有效地改善了蚁群算法的搜索时间较长,且易于过早地收敛于非最优解的缺陷。

基于遗传算法的高校排课问题的探究

随着高校招生人数的不断扩大,专业和课程的设置不断增多,教师和教室的短缺,使排课工作也越来越复杂。排课具有影响因素多、约束条件复杂以及存在不可预料的情况发生等特点,传统的手动排课既花费了大量的时间和精力,而且又容易出错。因此,利用遗传算法求解排课问题,其搜索过程带有自组织的智能性和并行性,可以更少地依赖于实际问题的情况,实现课表的优化,具有一定的实用价值。

容忍噪音的最大复合问题启发式算法

1.引言 从给定的数据集中发现有用的知识一直是示例学习和数据库知识发现等领域研究的重要内容[1,2].一般地说[3]:规则越简单,归纳概括能力就越强,分类精度越高.因此,近几年来,从给定示例中归纳简单而概括的规则,即最大复合问题的算法研究逐渐成为上述诸领域的一个热点.然而,现有的规则归纳算法多为建立在不含噪音的理想数据基础上的,而在实际的应用领域中不可避免地存在噪音数据[4,5],这样致使现有的算法一直得不到令人满意的结果,甚至很难应用于实际领域,从而给实际领域规则的获取带来了一定难度.噪音数据一般可以分为如下三种形式[6],即个别属性值错误型噪音、未知属性值型噪音和冗余属性值型噪音.规则归纳算法能否有效地解决上述三种情况的噪音、是其能否成功应用于实际领域的关键.

基于差分服务的贪婪流问题解决算法

贪婪流问题是网络拥塞控制范畴的问题 ,泛指不遵从标准TCP拥塞控制机制的流 贪婪流给网络带来不公平性 提出了一种新的甄别算法 ,通过对目标流发送窗口随分组丢弃变化关系的分析 ,对不合规范的流进行检测 算法采用定长列表结构 ,具有实现简单、扩展性强的特点 提出了一种基于差分服务模式的体系结构 ,对传统Internet服务哲学进行了扩展 ,从根本上支持新型流式应用 。

一个求解P_*(κ)线性互补问题的高阶Dikin型仿射尺度算法

对于P*(κ)线性互补问题提出了一个新算法———高阶Dikin型仿射尺度算法.算法的每步迭代,基于线性规划Dikin原始———对偶算法思想来求解一个线性方程组得到迭代方向,再适当选取步长,使算法具有多项式迭代复杂性.

骑士巡游问题的一个遗传算法

用一个遗传算法来求解骑士巡游问题。算法将骑士巡游问题转化为求解无向图的汉密尔顿通路问题,通过对无向图的通路问题进行编码、评估、选择、杂交、变异,求解无向图的一条汉密尔顿通路,即骑士巡游问题的一个解。