时间无关的膜系统下若干数学问题的研究

摘要

膜计算是生物计算的一个重要分支，其本质是通过研究细胞（包括组织细胞，脑细胞等器官细胞以及细菌等）的结构和功能然后从中抽象出计算模型。自膜计算被提出后，一系列关于膜计算的期刊、书籍不断出现，越来越多的团队开始从事膜计算的研究。许多研究者在探索如何利用膜系统在多项式时间（甚至线性时间）内求解计算困难问题，以及如何改进已有的结果，如构造半统一形式的解和统一形式的解。
　　在传统的脉冲神经膜系统中，当一个神经元发射脉冲后，该脉冲会立即离开源神经元并到达目标神经元，也就是说每个规则的执行时间都是一个时间单元。这个特点与实际的生化反应过程并不相符，事实上，化学反应或者复杂的生物反应通常需要一定的反应时间。因此，本文引入了计时的脉冲神经膜系统，在该系统中，每个规则都有相对应的执行时间。但规则的反应时间容易受到环境因素（温度、湿度等）的影响，因此本文构建了一种计算结果不会受到规则执行时间长短影响的脉冲神经膜系统，即时间无关的脉冲神经膜系统，并对其计算能力进行了研究。同时，本文也构建了时间无关的带分裂规则的组织膜系统并对其解决判定问题的计算能力进行了研究。具体工作有:
　　1.基于计时的带分裂组织膜系统，本文首次给出了求解判定形式的多维0-1背包问题和QSAT问题的时间无关的统一形式解，所构造的系统结构和规则都比较简单，易于理解。
　　2.基于计时的脉冲神经膜系统，本文首次给出了针对判定形式大数分解问题的时间无关的统一形式解，并构造了可以对任何自然数进行计算的时间无关的基础四则运算单元，并对以往的输入编码方式进行了简化。
　　本文通过研究时间无关的组织膜系统和神经脉冲膜系统求解若干数学问题的计算能力，再次证明由于可以在多项式时间内生成指数计算空间以及信息处理的极大并行性，膜计算系统模型和算法方面的研究在解决计算困难问题方面上具有重大的理论意义。

目录

声明

摘要

符号一览表

1．绪论

1．1．课题的背景和意义

1．2．膜计算模型介绍

1．2．1．脉冲神经膜系统

1．2．2．带分裂规则的组织膜系统

1．3．研究内容与创新点

2．时间无关的脉冲神经膜系统和组织膜系统研究

2．1． 时间无关的脉冲神经膜系统研究

2．1．1． 标准脉冲神经膜系统

2．1．2． 计时的脉冲神经膜系统

2．1．3．基于脉冲神经膜系统的时间无关解

2．1．4．脉冲神经膜系统的应用

2．2． 时间无关的带分裂规则的组织膜系统研究

2．2．1．带分裂规则的组织膜系统

2．2．2．计时的组织膜系统

2．2．3．基于组织膜系统的时间无关解

2．3．本章小结

3．时间无关的脉冲神经膜系统框架下的数学问题求解

3．1．基于时间无关的脉冲神经膜系统的大数分解问题求解

3．1．1．大数分解问题

3．1．2．求解大数分解问题的统一形式解

3．1．3．统一形式的时间无关解证明

3．1．4．大数分解问题的解讨论

3．2．时间无关的脉冲神经膜系统构建四则运算单元

3．2．1．加法系统

3．2．2．减法系统

3．2．3．乘法系统

3．2．4．除法系统

3．2．5．统一形式的时间无关解证明

3．2．6．四则运算单元的解讨论

3．3．本章小结

4．基于时间无关的组织膜系统的若干组合优化问题求解

4．1．时间无关的组织膜系统求解多维0-1背包问题

4．1．1．背包问题及多维0-1背包问题

4．1．2．求解多维0-1背包问题的统一形式解

4．1．3．统一形式的时间无关解证明

4．1．4．多维0-1背包问题的解讨论

4．2．时间无关的组织膜系统求解QSAT问题

4．2．1．SAT问题及QSAT问题

4．2．2．QSAT问题的时间无关的统一形式解

4．2．3．统一形式的时间无关解证明

4．2．4．QSAT问题的解讨论

4．3．本章小结

5．总结与展望

5．1．全文总结

5．2．展望

参考文献

攻读硕士学位期间发表论文及科研情况

致谢