可满足性问题研究

数理逻辑是计算机科学的基础，而逻辑公式的可满足性问题是计算机科学和人工智能领域中的一个著名而又重要的问题。它在计算机科学和人工智能研究中有广泛的应用。本文将重点介绍实际可用的判定算法及其相关技术。 本文的研究分两大方向，分别是命题逻辑的可满足性问题研究和一阶逻辑的可满足性问题研究。命题逻辑的可满足性问题（Satisfiability Problem）是一个历史悠久的问题，一般简称为 SAT问题。SAT 问题的求解算法有两大类，分别是确定性算法和非确定性算法。本文只研究确定性算法的相关内容，尤其是如何进行剪枝。我们充分调研了SAT求解算法和求解工具的相关知识，在此基础上，提出了local Lemma 这个剪枝技术，该技术可以更加充分地挖掘剪枝信息，达到进行更多剪枝的目的。 在一阶逻辑的可满足性问题研究方面，本文采取直接搜索可行的一阶逻辑模型的方法研究有限论域上的一阶逻辑的可满足性问题。该方法本质上就是深度优先的回溯搜索。因此，我们的研究重点就是如何找到问题的更高效的一阶逻辑的表示以及如何采用启发式的方式进行剪枝。在这个问题上，我的主要工作有两个：一个是模型搜索中适用于谓词的同构消去技术，包括Row by Row策略和Ramsey Number 策略两个技术；另一个是 DASH（Decision Assignment Scheme Heuristic），用来在生成有限模型的时候边搜索边消除同构子空间。DASH 能用近乎零代价保证输出的模型都是互不同构的。这两个技术都是基于有限论域中的元素的固有对称性，换言之，就是需要有限论域中的元素是两两可交换的。 在已有的成果的基础上，我们又尝试使用它们去求解一些数学中的实际问题，如拟群拉丁方，有限射影平面，正交拉丁方（组）等。我们给出了在这几个方面的一些尝试和初步结果，包括一个重要的定理和若干效率提高了几个数量级的改进。 值得一提的是，和马菲菲共同提出的横截矩阵（Transversal Matrix）概念是一个新颖的成果，使得正交拉丁方的表示和求解取得了明显的改进。在这个概念的基础上，进一步给出了几个定理，进行了理论上的拓展。实验数据表明，我们的求解途径和技术能有效解决拉丁方相关的问题。

SAT和DSOLS问题的研究

约束可满足性问题（Constraint Satisfaction Problem,CSP）是在人工智能领域被广泛研究的一类问题。对CSP问题的研究有两种重要的思路：一种思路是用统一的模型来表示CSP，然后用针对这个统一模型的通用工具进行求解；另外一种思路是针对不同的CSP问题开发专门工具，设计不同的算法和数据结构来求解。 本文研究了两个CSP问题：SAT(SATisfiability problem)和DSOLS(DoublySelf-Orthogonal Latin Squares)。CSP可以方便的转换为SAT来求解，因此对SAT的研究对很多问题具有重大意义。本文介绍了当前流行的SAT solver的一些技术，也提出一种新的搜索空间裁剪策略Local Lemma。DSOLS是一种具有特定性质的拉丁方，本文对它的研究不仅仅因为它的应用意义。更重要的是它作为一个特定的CSP问题，可以用来比较通用工具和专门工具的优劣。本文尝试了把DSOLS转化为SAT求解，也试过用一般CSP的思路来求解，最后提出了一种针对性的高效算法并开发了一个专门工具DSOLver，用这个工具证明了一个开放问题：DSOLS(10)不存在。

Properly coloured copies and rainbow copies of large graphs with small maximum degree

Let G be a graph on n vertices with maximum degree ?. We use the Lovasz local lemma to show the following two results about colourings ? of the edges of the complete graph Kn. If for each vertex v of Kn the colouring ? assigns each colour to at most (n - 2)/(22.4?2) edges emanating from v, then there is a copy of G in Kn which is properly edge-coloured by ?. This improves on a result of Alon, Jiang, Miller, and Pritikin [Random Struct. Algorithms 23(4), 409433, 2003]. On the other hand, if ? assigns each colour to at most n/(51?2) edges of Kn, then there is a copy of G in Kn such that each edge of G receives a different colour from ?. This proves a conjecture of Frieze and Krivelevich [Electron. J. Comb. 15(1), R59, 2008]. Our proofs rely on a framework developed by Lu and Szekely [Electron. J. Comb. 14(1), R63, 2007] for applying the local lemma to random injections. In order to improve the constants in our results we use a version of the local lemma due to Bissacot, Fernandez, Procacci, and Scoppola [preprint, arXiv:0910.1824]. (c) 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 425436, 2012

Promoting local innovation - a tool for sustainable rural development

Change, be it socio-cultural, political, institutional, technological, economic or ecological motivates local communities and farming families to mobilise and increase their innovation potential in order to create ways of life and production that match their own visions and priorities. In spite of the growing recognition of the potential of local innovations, they are hardly being integrated into development plans and projects; as a consequence, their diffusion within and between communities is limited. therefore interactive and participatory methods for supporting and strengthening the innovative potential of local actors are valuable inputs for sustainable rural development. the article presents an approach to promote local innovations.