组合逻辑网络故障最小测试集的算法

一、前言逻辑网络故障测试集的算法,是数字系统故障诊断技术中的一个重要问题。近十几年来,随着数字系统应用的日益广泛,国外不少人在这个问题上进行过研究。本文采用布尔差分的概念,应用集合论中的一些方法,提出了组合逻辑网络故障最小测试集或故障近似最小测试集的一套较完整的算法。提出这一算法的基本思想是:     

诊断组合逻辑网络的SDT算法

本文提出诊断组合逻辑网络的一种新算法。其特点是根据组合逻辑网络的结构,将产生测试码与时序测试过程统一起来进行。使算法的复杂性大大降低。这种算法称为S D T(sequential fiagnostic tree)算法。     

赋权图的区间着色和图的着色算法

本文提出了图的区间着色模型,并对相容性图给出了区间着色的多项式算法,同时改进了求图的着色问题的算法。     

智能搜索算法设计和分析

提出了人工智能博弈树搜索ＳＳＳ＊算法的两种改进算法ＢＳ＊和ＤＳ＊算法，给出了ＢＳ＊和ＤＳ＊搜索博弈树端结点的充分必要条件，由此证明了，如果能估计一个合适的上界，则ＢＳ＊算法优于ＳＳＳ＊算法．同时还证明了ＤＳ＊算法优于α－β算法．论述了ＤＳ＊算法搜索深度为奇数的博弈树时，在一般情况下也优于ＳＳＳ＊算法，且这两种算法都降低了存储开销．     

几种特殊的无向网络容量扩充问题

讨论了无向网络容量扩充的4种特殊问题，给出了相应的强多项式算法.     

资源短时占用型作业调度算法

对资源短时占用型作业调度的问题给出了一个数学描述模型 ,并讨论了该问题求解的时间复杂性 .基于该模型提出了对不同情况最佳或近似最佳的实用的联机调度算法 ,并讨论了这些算法在其他类似问题上的应用 .     

K连通图的k分割多项式算法

图G的K分割问题可描述为:输入(Ⅰ)G=(V,E),G为简单无向图,其中|V|=n,|E|= m;(Ⅱ)a_1,a_2,…,a_k k个G中不同的顶点;(Ⅲ)n_1,n_2,…,n_k k个正整数满足 n_1+n_2+…,+n_k= n.输出(V_1,V_2,…,V_k),对1≤i≤k,满足(Ⅰ)a_i∈V_i;(Ⅱ)G[V_i]是连通图;(Ⅲ)|V_i|=n_i.本文给出时间复杂性为O(knm)通用K连通图的k分割多项式算法.     

产生二进制德·布鲁因序列的两个算法

Huang首次利用n元组相邻位的相异数为索引,生成德·布鲁因序列.由前几位产生下一位需4n 位存贮单元,4n 个时间单元.本文,首先改进Huang 的算法,使产生一位需4n 位存贮单元,2n 个时间单元;然后给出一个利用n 元组相异数为索引,生成德·布鲁因序列的新算法,由前n 位产生下一位需4n 位存贮单元,n 个时间单元.新算法与原算法同样具备可从任意n 元组开始计算的特点.