IC(Integrated Circuit)技术飞速发展，目前己处于GSI阶段，正向SOC(System On a Chip)发展，IC的应用范围极广。关于IC的设计、测试、模拟、仿真已形成实用化的集成工具，如VHDL语言。但是，在IC的发展过程中遇到了很多理论与技术问题。本文正是从理论研究角度入手，结合计算复杂性理论，对EDA中的两个重要环节，高层次综合和逻辑综合中的时序处理，做了深入研究，给出了两个理论结果和两个算法。 正如文中所指出的那样，绝大多数组合与时序优化问题，实际上都是NP-完全问题，因而试图给出现实可行的一劳永逸的通用算法在目前是办不到的。所以，大多数研究者均是从自身的角度出发，研究各种各样的启发式算法，然而算法效果如何，针对EDA中各个环节目前尚无人提出统一标准来做判断分析。 本文在继承前人工作的基础上，将最基本也是最重要的图灵机模型及其依据于此的计算复杂性理论的若干重要概念与思想引入到EDA中的高层次综合和逻辑综合环节中。文中在讨论了P与NP问题、近似算法性能指标等概念的基础上，对高层次综合中的问题，将其归结为基本组合问题，并进行了描述。针对高层次综合中部分有代表性的问题，指出其近似求解的无限逼近最优性。 本文对高层次综合中的互连单元分配算法进行了研究，对互连单元分配进行了论述。在着重分析数据通路连接图的表示模型的基础上，对数据通路连接图的标准型给出了一系列定义，然后提出了IU-Allocation算法。利用该算法对线性预测系统的自相关数字电路进行了实验，并对算法的时间复杂性做了分析。 本文介绍了演化计算的概念及应用。提出了一种基于演化程序的数据通路综合算法。该算法将演化程序与已知的启发式算法相结合，可对较大的设计空间进行智能化搜索。同时，以减少硬件资源成本和缩短总的执行时间为目标，讨论了应用该方法对典型的微分方程电路实施调度、分配和数据通路综合的整体优化过程，并做了仿真实验，证明可以有效地提高高层次综合设哈尔滨工程大学博士学位论文计的质量。 对时序逻辑综合领域的两种重要理论，布尔过程论与时变布尔函数，在定时特性方面进行了重点比较。这两种理论均是在考虑布尔变量的同时，将时间特性加入其中，以期系统地处理逻辑与时序问题。其重要的不同点是，布尔过程借助实数的运算，而时变布尔函数依然采用布尔运算。研究了布尔过程在计算通路敏化时的计算复杂性，指出按其算法进行通路敏化求解是指数时间算法。 最后本文对逻辑综合领域的最新进展进行了综述，介绍了OBDD的来源、发展，以及目前的状态。论述了确切BDD算法、启发式BDD算法、快速BDD最小化、使用无关集的启发式BDD最小化等相关概念和算法。关键词:高层次综合算法;布尔过程论;时变布尔函数;顺序二叉判决图