受限SIMD PRAM模型上的高效并行图算法

在限定处理机个数的 CREW PRAM并行计算模型上,给出了图论中一些基本问题的并行算法.所给并行算法的费用c(n)=p(n)*t(n)是目前已知的最好结果,其中p(n),t(n)分别是对一具有n个顶点图实施并行算法所用处理机的个数和最坏情况下的时间复杂性。     

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 元组开始计算的特点.     

一类限制树问题的复杂性及其近似算法

多层印刷线路板布线中如何减少金属导孔是一个重要问题。本文将这个问题化为在2—部超图G[S、V、E]中寻找一类限制树问题。证明了该问题为Np—Complete,并给出它的多项式时间heuristric算法。     

动态规划问题的高效并行算法

在具有p(1≤p≤n)个处理机的CREW PRAM并型计算模型上,对一类动态规划问题给出了一处理机利用率为E(n)=0(1),并行加速比为S(n)=0(p)的并行算法(n表示问题的尺寸);计算了问题求解的最少费用,并同时给出了问题求解的方法。     

一类背包问题的可解性

本文的主要结果是,对K背包问题给出了时间、空间复杂性为O(nM~k)的拟多项式算法;证明了若P≠NP,则该问题不存在完全多项式时间ε近似算法;对动态背包问题给出了时间复杂性为O(nM~k)的拟多项式算法。     

基于竞争的联想存储器学习算法

提出两种基于竞争的神经网络联想存储器学习算法—CC算法和ACC算法 ,并证明算法得到的神经网络对任一输入模式的竞争收敛性 ,由CC算法得到的网络 ,利用 p n个神经元存储p个n维样本模式 ;每个样本点都是吸引中心 ,不存在假吸引中心 ;对任一输入模式 ,总被吸引到与之海明距离最小的样本点上 ;不产生拒识点 .ACC算法是CC算法的改进形式 ,所得网络可在自适应学习中收敛 ,竞争次数较CC算法大大降低 本文算法得到的网络在存储容量、容错能力方面好于Hopfield联想存储器及作为联想存储器使用的BP网络 .