要重视计算机算法研究

【期数】：1997年03期

【作者】：朱洪

【摘要】： 笔者于1996年6月17～19日应邀参加了在香港大学召开的第2次计算和组合算法国际会议。会议涉及到组合学的某些成果,但主要内容在计算机算法方面,例如算法的平均复杂性分析,NP-难问题的近似算法的存在性和不可能存在性,多处理的分布式计算调度问题,密码设计和复杂度分析,等等。下面略作介绍。 MIT的论文是多机作业均衡负载的在线调度问题,它的应用背景有分布式数据库存取频度和机器人劳动强度均衡分配问题等。论文首次提出了在常数(6.8285)重分派因子条件下,极大负载和即时负载之比小于3.5981的在线算法。依利诺斯大学的论文探讨了有关超大规