Powell改进算法是一种()。
A.一维搜索方法
B.处理约束问题的优化方法
C.利用海森矩阵求解的无约束优化方法
D.利用梯度求解的无约束优化方法
A.一维搜索方法
B.处理约束问题的优化方法
C.利用海森矩阵求解的无约束优化方法
D.利用梯度求解的无约束优化方法
第1题
第2题
第4题
第5题
在模式枚举(pattern enumeration)类应用中,需要从主串T中找出所有的模式串P(T|=n,|P|=m),而且有时允许模式串的两次出现位置之间相距不足m个字符。
类似于教材310页图11.3中的实例,比如在“000000”中查找“000”。若限制多次出现的模式串之间至少相距|P|=3个字符,则应找到2处匹配;反之,若不作限制,则将找到4处匹配。
a)试举例说明,若采用后一约定,则教材11.4.3节BM算法的好后缀策略,可能需要Ω(nm)时间;
b)试针对这一缺陷改进好后缀策略,使之即便在采用后一约定时,最坏情况下也只需线性时间。
第6题
对于几乎有序的向量,如教材代码2.26(60页)和代码2.27(60页)所示的起泡排序算法,都显得效率不足,比如,即便乱序元素仅限于A[0,√n)区间,最坏情况下仍需调用bubble()做Ω(√n)次调用,共做Ω(n)次交换操作和Ω(n3/2)次比较操作,因此累计运行Ω(n3/2)时间。
a)试改进原算法,使之在上述情况下仅需o(n)时间;
b)继续改进,使之在如下情况下仅需o(n)时间:乱序元素仅限于A[n-√n,n)区间;
c)综合以上改进,使之在如下情况下仅需o(n)时间:乱序元素仅限于任意的A[m,m+√n]区间。
第8题
在多叉堆(d-heap)中,每个节点至多可拥有d≥3个孩子,且其优先级不低于任一孩子。
a)试证明,多叉堆decrease()接口的效率可改进至O(logdn);(当然,delMax()接口的效率因此会降至O(d-logn))。
b)试证明,若取d=e/n+2,则基于d叉堆实现的Prim算法的时间复杂度可降至O(e·logdn);
c)这种改进策略是否也适用于Dijkstra算法?
第11题
发生药品调配差错的应对原则是:
A.核对一报告一调查一改进措施
B.报告一调查一核对一改进措施
C.报告一调查一改进措施
D.报告一核对一调查一改进措施
E.调查一核对一报告一改进措施