低度图的点覆盖和独立集问题下界改进

给出了一种提高低度图点覆盖和独立集问题下界的精确算法.通过分析如何有效地减少图中的顶点来打破原问题的NP Hard结构建立起搜索递推关系;得出3度图的最小点覆盖问题的解决时间为 O(1 1033n),参数化的3度图点覆盖问题的解决时间为O(kn+1 2174k);将此算法应用到 3 度图的最大独立集问题上,可以得到运行时间为O(1 1033n)的解.以上3结果均打破原有最佳下界.

紧急输送策略的线性规划模型

以美国南弗洛里达州递避飓风袭击为例建立了紧急输送情况下的线性规划模型。其中具体建立了以SCEPD(美国南弗洛里达州紧急情况预防部门)提出的公路反向，地区分块撤离，使用小路等三个最受人们关注的策略的模型。模型的灵敏度分析能很好地解释建立更多的临时避难所、限制车辆等策略对撤离的影响。在相近的环境下，文中模型解得的结果很接近官方预测的结果，并且本文的模型能对更广泛的情况进行分析．可给SCEPD提供一定参考。

有理Bézier曲线权因子的有效形式

给出了确定 n 次有理 Bézier 曲线权因子的权系数极大化方法和幂指数型权因子方法。这些方法根据 Bernstein 基函数及其系数来选取权因子。系数极大化方法表示的曲线是一种确定的适合于任意次数的有理 Bézier 曲线,它可以比 Bézier 曲线更好地保持其控制多边形的形状。幂指数型权因子方法给出了有理 Bézier 曲线权因子的有效形式。它既保持了一般有理权因子的局部可调性,又能使形状调整的效果更明显。

三次有理Bézier曲线的形状调整方法

给出了两类调整三次有理Bézier曲线形状的方法。一类方法是使曲线通过给定的插值点,从而实现曲线的形状调整。另一类方法是将曲线上的点作为控制多边形两边连线段上的分点,通过调整分线段的比例,实现对曲线的形状调整。针对不同情况,分别给出了权因子的计算公式。计算方法简单,使用方便,并使三次有理Bézier曲线的形状调整更加具体和明确。同时,由计算结果得到了任意三次有理Bézier曲线不相交的充分必要条件。

解整数规划问题的目标收敛法

提出基于目标收敛法的整数规划求解方法 .该求解方法从整系数目标函数值一定为整数这一性质出发 ,对目标函数值进行逐步约束 ,使得每一步迭代均在上一步问题的可行域中割去一块不包含原规划问题整数可行解的区域 ,从而使可行域逐步缩小最终得到整数最优解 .目标收敛法还可与割平面法、分枝估界等方法结合起来使用 ,从而加速求解过程 .

基于C／S模式的远程维护系统的设计与实现

针对网络机房维护工作的实际问题,提出了一套高效的基于C/S模式的纯软件解决方案。分析了维护系统所需的功能结构、系统设计、关键技术研究及其程序实现。

一道IMO题与一道CMO题的等价性

本文谈谈第26届IMO第5题与1997年CMO第4题的等价性。 题目1 (CMO1997-4)四边形ABCD内接于圆,其边AB与DC的延长线交于点P,AD与BC的延长线交于点Q,由Q作该圆的两条切线QE和QF,切点分别为E、F,则P、E、F三点共线。 题目2 (IMO-26-5)⊙O过△ABC顶点A、C,且与AB、BC交于K、N(K与N不同),△ABC外接圆和△BKN外接圆相交于B和M.求证:

二次均匀B样条方法的扩展及其应用

以经典的二次B样条曲线结构构造了一种带两个形状参数的可调三次多项式曲线.曲线在两个参数变化下最少保证一阶连续,在形状参数取某些特殊值时曲线可以生成二次均匀B样条曲线,插值各控制点的插值样条曲线等等.还可以通过改变形状参数的取值,调整曲线接近控制多边形的程度,也可以调整曲线从两侧逼近二次均匀B样条曲线.还分析了曲线端点位置和切矢的性质以及形状参数变化下对它们的影响,给曲线的形状调整带来一定的指导.最后给出了一些曲线曲面生成及调整的实例.

濒临灭绝蜥蜴种群模型

本文以有灭绝危险的佛罗里达丛林蜥蜴为例，给出基于Leslie矩阵的种群保护模型，讨论了非迁移状态及迁移状态下，对丛林蜥蜴生活环境产生影响的因素，然后设计了对它的保护方案，最后在实例中对此方案进行应用和检验，取得了良好的结果。

带有多折扣选项的滑雪租赁问题的在线和离线算法

研究了带有多折扣选项的滑雪租赁问题(ski-rental problem with multiple discount options,简称多折扣租赁问题)的离线和在线算法.多折扣租赁问题是经典的滑雪租赁问题的一个自然扩展,在现实生活中有着非常广泛的应用.在多折扣租赁问题中,除了租借一次装备和购买滑雪装备的选项以外,还存在多次租借装备的选项,这种多次租借可以得到折扣.一次租借次数越多,折扣就越大.规则价格子问题则是多折扣租赁问题中要求各选项的价格成倍数关系的一类子问题.证明了多折扣租赁问题的离线问题是NP难的,但对于规则价格子问题的离线问题,给出了一种线性时间算法.基于对离线问题的算法分析,给出了规则价格子问题的一个2倍竞争比的在线策略,同时证明了该问题的最优竞争比是2.基于规则价格子问题的在线策略,又给出了多折扣租赁问题的一个新的4倍竞争比的在线策略,该竞争比同样达到了最优.最后,通过对现实生活中的数据和随机数据进行实验,说明所给出的在线算法具有实际应用价值.

负参数Bézier曲线的性质及其应用

1引言 从便于形状处理、形状信息传递与数据交换的角度来看,形状的数据描述应满足如下要求[1,2]:1.唯一性;2.同一形式性;3.几何不变性;4.易于定界性.在实际应用中往往难以做到的是3、4条.Bezier曲线则利用了Bernstein基函数和等于1来满足几何不变性,再又利用各基函数非负来达到凸包性.易于定界不一定要是凸包的,文[2]中就负权因子分析了这种丧失了凸包性的有理二次Bezier曲线的一些性质,得出用不同的负权因子来生成椭圆弧、抛物线弧和双曲线弧的应用.……

无向图中子集反馈顶点集问题的精确算法

子集反馈顶点集问题是一个经典的NP难问题,该问题是指在一个无向图中删除最少的顶点使得图中某些给定的顶点不在任何圈中.子集反馈顶点集问题包含了经典的最小反馈顶点集、多路割等重要特例问题,并且可应用于电路测试、操作系统解死锁等领域.子集反馈顶点集问题也是精确算法中的一个重要问题,该问题存在一个运行时间为O~*(2~n)的简单暴力搜索算法,其中n为图中顶点数.直到2011年Fomin等人给出一个运行时间为O~*(1.8638n)的算法,这个运行时间界才被打破.文中将该运行时间上界进一步改进到O~*(1.7743n).文中的算法是一个分支搜索算法,为了改进该问题的运行时间界,文中对问题的结构性质进行了深入的分析,挖掘出若干有效的规约和分支规则,再采用测量治之方法对算法的运行时间进行分析,最终将运行时间上界给予改进.

带权混合支配问题的近似算法研究

图G=(V,E)上的混合支配集D是由图G中的顶点和边组成的集合,因此对于图G中的任意一条边或一个顶点,若其不在D中,则其必须与D中某条边或某个顶点相邻。混合支配问题是在一个图中找到一个基数最小的混合支配集。混合支配问题是图顶点支配问题和边支配问题的混合,在实际生活中有着许多应用,最近在算法中也备受关注。混合支配问题在一般图上是NP完全的。带权混合支配问题则是混合支配问题的一个自然推广,其将图中的点和边以不同权重进行区分。令图中所有点的权重均为w_v,所有边的权重均为w_e,带权混合支配问题则要求寻找一个混合支配集使得其点和边的权重之和达到最小。尽管针对混合支配问题已存在一个简单2倍近似算法,但是对带权混合支配问题的近似算法的研究进展却非常缓慢。在点的权重不大于边的权重的情况下,文中给出了带权混合支配问题的一个3倍近似算法。

Paw图–边删除问题的线性顶点核心化算法

图边删除问题中一类重要问题是研究是否可以删除图中不超过k条边之后使得剩余的图不存在某个子图结构H,而子图H为顶点个数不超过4的连通图的情况被研究得最为广泛.本文主要考虑H为Paw图(三角形其中一个顶点再邻接一条边)的情况,称为Paw图–边删除问题,并为该问题设计了一个32k个顶点的问题核.这是该问题的第1个线性顶点大小的问题核.文中主要的技术是结合两个新的皇冠分解的变体来分析图的结构从而对图进行简化.

新工科建设背景下“互联网＋”复合型精英人才培养模式的探索与实践

除了加快设置新兴专业,新工科建设的当务之急是改变传统的工科专业过窄过细的弊端,积极探索学科专业之间的交叉融合,培养更多工程实践能力强、创新能力强,具备国际竞争力的高素质复合型人才。本文以电子科技大学"互联网+"复合型精英人才培养计划为例,提出了新工科建设的一种新模式:面向"互联网+"国家重大战略需求,依托学校在电子信息领域的学科优势,整合工科、理科、经济、管理等多个专业的优质教学资源,采用"2+2"和"双学位"的培养模式,培养既掌握扎实的"互联网+"核心知识,又敢于跨界融合并具有集成创新能力的复合型新工科精英人才。