广义彼得森图意大利控制数

图的罗马控制来源于古罗马帝国的军事防御问题.图的意大利控制是一种泛化的罗马控制.确定图的意大利控制数是NP困难的.一般情况下,很难确定某一类图意大利控制数的精确值,只能给出其上界或下界.通过构造可递推的意大利控制函数,得到了广义彼得森图P(n,k)(k≥4)的意大利控制数紧的上界.结合前人给出的意大利控制数的下界,确定了当k≡2,3(mod 5)且n≡0(mod 5)时,P(n,k)(k≥4)意大利控制数的精确值.     

关于局部扭立方体的反馈数

确定一般网络(或图)的最小反馈点集问题属NP难问题.n维局部扭立方体网络Qltn是n维超立方体网络Qn的变形且是一类重要的互连网络拓扑结构,其拥有的某些性质优于Qn.根据Qltn顶点集合中最后一位字节不同的特点,将其顶点集合划分为两个不相交的子集,通过构造极大无圈子图得到反馈数的上界,并证明了对任意正整数n≥2,存在常数c∈(0,1)使得反馈数为f(n)=2n-1(1-c/(n-1)).     

路径幂图、Flower Snark图及多锥图独立数

图的独立数是图论中的重要参数,令G=(V(G),E(G))是一个简单有限无向图.如果V(G)的子集S中任意两个顶点均不相邻,则S是图G的一个独立集.顶点独立集大小的最大值,称为图G的独立数,记做α(G).研究了路径幂图、Flower Snark及其相关图、多锥图的独立数问题,首先构造出了它们的独立集,得到其独立数的下界,然后证明了该值也是其独立数的上界,并给出了它们独立数的准确值.     

短语结构到依存结构树库转换研究

为基于真实语料进行句法分析,构建了大规模的短语结构树库和依存结构树库,并尝试在两种结构的树库之间进行转换.讨论了宾州中文树库(Penn Chinese Treebank,CTB)中短语结构树库和依存结构树库的关系,并基于现代中文依存文法制定了中心子节点过滤表,依据该表将短语结构的CTB转换为依存结构树库.在CTB中随机抽取200句语料,转换正确率达到了99.50%.基于该转换得到的依存结构树库可以进一步进行中文依存关系解析的研究.     

三色拉姆塞数R3(C8)研究

用r种颜色对图G的所有边着色,记着第i色的边构成的子图为Gi,如果存在一种着色方法使得每一个Gi(1≤i≤r)都不包含图H,则称图G对于H可以r着色.拉姆塞数Rr(H)是使得完全图Kn对于H不可以r着色的最小正整数n.令Cm表示长度为m的圈,Dzido等证明了R3(C2k)≥4k.本文对k=4的情形进行研究,利用计算机,通过大量的计算证明了R3(C8)=16.     

汉语自动分词中中文地名识别

以词语级的中文地名为识别对象，根据地名内部用字的统计信息和地名构成特点产生潜在地名．在汉语自动分词中将可信度较高的潜在地名等同于句子的候选切分词，利用候选切分词本身的可信度和上下文接续关系评价句子的各种切分方案．在确定句子最佳切分时识别句子中的中文地名．对真实语料进行封闭和开放测试，封闭测试结果为召回率93．55％，精确率94．14％，F-1值93．85％；开放测试结果为召回率91．27％，精确率73．48％，F-1值81．42％．取得了比较令人满意的结果．     

三色Ramsey数尺（Cm1，Cm2，Cm3）研究

用r种颜色对图G的所有边着色，记着第i色的边构成的子图为G1,如果存在一种着色方法使得对所有的1≤i≤r都满足Hi￠Gi，则称图G对于（H1，H1，…．Hr）可r着色．Ramsey数尺（H1，H2，…，Hr）是使得完全图Kn对于（H1．H2，…，Hr）不可r着色的最小正整数n，令m1〉m2≥m3，Erdoes等给出了当m1足够大时R（Cm1，Cm2，Cm3）的值．通过对m1不是足够大的情况进行研究，证明了当m≥5时，R（Cm，C3m,C3）=5m=4；并给出了当m1≤7时R（Cm1，Cm2，Cm3）的值．     

盒子中蛇问题回溯算法

研究了盒子中的蛇问题,即求ｎ方体Ｑ＾ｎ中最大导出环Ｓｎ问题;已知｜Ｓ２｜＝４,｜Ｓ３｜＝６,｜Ｓ４｜＝８,｜Ｓ５｜＝１４,｜Ｓ６｜＝２６,通过回溯算法证明了｜Ｓ７｜＝４８,｜Ｓ８｜≥９４,并给出猜想｜Ｓｎ｜≤２｜Ｓｎ－１｜－２（ｎ≥３）。该猜想对３≤ｎ≤７已成立。     

面向对象语言自然类型检查方法

针对面向对象技术中由于多态等机制导致的类型不安全问题,提出一种解决方案－自然类型检查。该方法对面向对象程序设计中的变量进行类型安全检查,发现由多态、强制类型转换等机制引入的不安全因素,保证程序的正确执行。以Java为描述语言,详细介绍了该方法,并与传统的类型检查进行了比较。     

C_(2j+1)∪C_(2k)类与P_n~k类调和图

证明了 Seoud等当 k≥ 3时 C3 与 C2 k的不相交并 C3 ∪ C2 k为调和图的猜想 ,并扩展该结果 ,证明了 C5 ∪ C2 k( k≥ 2 )是调和图 ;给出猜想 C2 j+ 1 ∪ C2 k( j≥ 1,k≥ 2且 ( j,k)≠ ( 1,2 ) )是调和图 .证明了幂图 P4n( 8≤ n≤ 17)与 P5 n( 14≤ n≤ 17)是调和图 ,否定了 Seoud等关于当且仅当 1≤ k≤ 3时 Pkn( 1≤ k≤ n -1)是调和图的猜想 .给出了相反的猜想 :当 n≥ n0 ( k)时 Pkn是调和图 ( n0 ( k)为依赖于 k的足够大的整数 )