集合论与图论SetTheoryandGraphTheory要点.ppt

集合论与图论Set Theory and Graph Theory 集合论与图论是数学的一部分 “对于大自然这本奥秘无穷的书，我读不懂”。 ──莎士比亚《安东尼和克里奥帕特拉》（1564—1616） “如果不理解它的语言，没有人能读懂宇宙这本伟大的书，它的语言就是数学”。 ──伽里略（1564—1642） “在任何特定的理论中，只有其中包含数学的部分才是真正的科学” ──康德（1724—1804） 集合论与图论是数学的一部分 “一门科学，只有当它能够运用数学时，才算真正发展了。” ──马克思（1818—1883） 数学不专属自然科学，也不专属社会科学，更不专属于文学艺术。它是一种宇宙语言，为一切文明生物共有、共享。 教学目的 该课程的设置主要是为了培养学生的抽象思维和逻辑推理能力，提高学生分析问题和解决问题的能力，提高学生的数学修养及计算机科学素质。 本课程为后继的专业基础课及专业课提供必要的数学工具，为描述离散模型提供数学语言。 要想用计算机解决问题就要为它建立数学模型，即描述研究对象及对象与对象之间的联系，并通过事物之间的联系找出事物的运动规律。 集合论与图论为此提供了强有力的描述工具与推理理论。 基本思想 我们从“集合”这个基本概念开始建立集合理论。就某种观点来看，“集合”与“性质”是同义词，是基本概念之一。 集合用来描述事物的性质—我们的研究对象，映射用来描述事物之间的联系—运算、关系，从而为集合建立了结构。于是，为建立系统的数学模型提供了数学描述语言—工具，代数系统就是引入运算以后的集合。 基本思想 集合论又提供了研究数学模型的性质，发现新联系的推理方法，从而找出事物的运动规律。 图论是上述思想的一个具体应用，事实上，图论为任何一个包含了一种二元关系的系统提供了一个数学模型；部分地，也因为使用了图解式表示方法，图就具有一种直观的和符合美学的外形。 在图论中，许多结果是初等的，但也有大量的十分复杂的问题可以难倒最老练的数学家。 在计算机专业中的意义 能形式化就能自动化。 对计算机专业而言，形式化尤为重要。利用形式化描述给程序设计提供了方便，从而实现了自动化。 在计算机专业中的意义 集合论可以看成一种通用语言，一切必要的数据结构都可以由集合这个原始的数据结构而构造出来。 实际上，数学发展的历史可以看成是一个煞费苦心或精心制成的数据结构。首先，我们有整数，然后有有理数、代数数，在经过一阵斗争以后，我们有实数、复数、函数的一般概念等等。最后，人们终于明白开头所说的思想，计算机科学家或许可以利用这个经历。 其次，19世纪后半期，数学家把函数定义为笛儿乘积的子集，从而把函数视为集合，这是严格的。但对计算机科学家是不合适宜的，他们更喜欢用规则来定义函数。 在计算机专业中的意义 集合论是数学的基础，也是计算机科学的基础。集合论和图论是算法与数据结构、形式语言与自动机、数据库原理、计算的复杂性理论等课的先修课。而图论的基本知识则将始终陪伴我们，直到……。 数学要教会人如何进行逻辑推理，如何进行正确的抽象思维，如何在纷繁的事物中抓住主要的联系，并如何使用明确的概念，等等。这对计算机技术及应用也是至关重要的，在其他任何领域同样重要。 本课程的特点 自给自足，不需要预先的知识准备。学习本课的前提实在仅仅是不可捉摸的所谓“数学上的成熟”。 概念多，但都有实在的具体的实物背景，最后要落实到抽象的定义上，概念是第一位的。 本课程的特点 作为一门数学课，与以往不同的是以证明为主而不是以计算为主。因此，要学会证明技术，学会分析问题和解决问题的思想方法。它能培养你诚实！ 与计算机科学/技术联系紧密，是最常用、最有用的数学内容之一。 没有什么公式要你背。需要的仅是智力上的成熟并乐意进行独立思考！ 教学要求——考试要求 题型 选择、填空、判断、简答、证明、论述、设计、计算等 重点和难点 会在各章的开始点明 考试权重 作业占10% 期末考试占90% 考前答疑 考试前两天 教学方法 “只有学生能理解的定义才是令人满意的。” —Poincaré于1909年 讲清概念的背景，最好先从具体的实例出发，直观地给出实在的东西，然后推广或抽出本质得到抽象概念。没有抽象就没有科学！ “从具体到抽象是数学发展的一条重要大道，因此具体例子往往是抽象概念的源泉，而所用的方法也往往是高深数学里所用的方法的依据。 仅仅熟读了抽象的定义和方法而不知道他们具体来源(从抽象回到具体)的数学工作者是没有发展前途的，这样的人要搞深刻研究是可能会遇到无法克服的