问题的提出 1900年 D. Hilbert 在巴黎第二届数学家大会上提出 著名的23个问题. 第10个问题:如何判定整系数多项式是否有整数根? 要求使用“有限次运算的过程” 1970 年证明不存在这样的判定算法, 即这个问题是 不可判定的, 或不可计算的

◼ 确定型有穷自动机(DFA) ◼ 非确定型有穷自动机(NFA) ◼ 带ε转移的NFA(ε-NFA) ◼ 用ε-NFA模拟右线性文法 ◼ 用右线性文法模拟DFA

8.4 平面图 ▪ 平面图与平面嵌入 ▪ 平面图的面、有限面、无限面 ▪ 面的次数 ▪ 极大平面图 ▪ 极小非平面图 ▪ 欧拉公式 ▪ 平面图的对偶图

课程目的和基本要求：·课程性质 技术基础 ·基础知识要求 数学分析(或者高等数学),离散数学 ·主要特点 抽象和形式化 理论证明和构造性 基本模型的建立与性质

树是一类结构较为算单的图途极 泛的散数学模型,特别是 它在许算机科学中用得最多因此在学 习时应很好地棠握好诸如树的充要条件 生成树、最优生成根树、树的各 种法

本章讨论集合论中较为困难的问题一集 合的基数问题;但只限于对基数作一简 单介绍;如学时较少可不讲本章或对本 章作恰当的删减 本章主要概念为:集合的等势、有限集 与无限集、可数集与不可数集及较为常 见的集合的基数

§1集合的概念和表示法 §2集合的运算 §3序偶与笛卡尔积 §4关系及其表示 §5关系的性质 §6复合关系和逆关系 §7关系的闭包运算 §8集合的划分和覆盖 §9等价关系与等价类 §10相容关系 §11序关系

◼ §1 谓词的概念与表示法 ◼ §2 命题函数与量词 ◼ §3 谓词公式与翻译 ◼ §4 变元的约束 ◼ §5 谓词演算的等价式与蕴含式 ◼ §6 前束范式 ◼ §7 谓词演算的推理理论

§1图的基本概念 §2路与回路 §3图的矩阵表示 §4欧拉图和汉密尔顿图 §5平面图 §6树与生成树

定义：设X和Y是任何两个集合，而f是X到 Y的一个关系，如果对于每一个xX，有 唯一的yY，使得f，称关系f为 函数，记作：