当前位置：文档之家 › 计算机科学与技术专业集合论与图论

计算机科学与技术专业集合论与图论

  • 格式：pdf
  • 大小：722.48 KB
  • 文档页数：28

周 晓 聪 (中山大学计算机科学系)
离散数学基础·集合论与图论
2008 9
年 月9日
7 / 12
子集关系及集合相等举例
证明(A − B) − C ⊆ A − (B − C )，这两者什么时候相等？ 证明子集关系的思路：利用基本恒等式A − B = A∩ ∼B
(A − B) − C = (A∩ ∼B)∩ ∼C A − (B − C ) = A∩ ∼(B∩ ∼C ) = A ∩ (∼B ∪ C ) = (A∩ ∼B) ∪ (A ∩ C )
从而：
(A∩ ∼B)∩ ∼C ⊆ A∩ ∼B ⊆ (A∩ ∼B) ∪ (A ∩ C )
周 晓 聪 (中山大学计算机科学系)
离散数学基础·集合论与图论
2008 9
年 月9日
7 / 12
子集关系及集合相等举例
证明(A − B) − C ⊆ A − (B − C )，这两者什么时候相等？ 这两者什么时候相等？
周 晓 聪 (中山大学计算机科学系)
离散数学基础·集合论与图论
2008 9
年 月9日
3 / 12
德摩尔根律
A − (B ∪ C ) = (A − B) ∩ (A − C )
A B C B
A C B
A C
A−B
∩
A−C
=
A − (B ∪ C )
周 晓 聪 (中山大学计算机科学系)
离散数学基础·集合论与图论
周 晓 聪 (中山大学计算机科学系)
离散数学基础·集合论与图论
2008 9
年 月9日
8 / 12
子集关系及集合相等举例
证明(A ∩ C ) ⊆ (B ∩ C )且(A∩ ∼C ) ⊆ (B∩ ∼C )蕴含A ⊆ B 两种思路：元素法和性质法
周 晓 聪 (中山大学计算机科学系)
离散数学基础·集合论与图论
2008 9
证明(A − B) − C ⊆ A − (B − C )，这两者什么时候相等？
周 晓 聪 (中山大学计算机科学系)
离散数学基础·集合论与图论
2008 9
年 月9日
7 / 12
子集关系及集合相等举例
证明(A − B) − C ⊆ A − (B − C )，这两者什么时候相等？ 证明子集关系的思路：利用基本恒等式A − B = A∩ ∼B
，
是全集
且 且 当且仅当 当且仅当
且
，则
，
及
当且仅当
周 晓 聪 (中山大学计算机科学系)
离散数学基础·集合论与图论
2008 9
年 月9日
4 / 12
子集关系及集合相等举例
子集关系及集合相等举例
设A, B是集合，证明A − B = A当且仅当A ∩ B = ∅ 设A, B, C 是集合，证明(A − B) − C ⊆ A − (B − C )，什么时候这两 者相等？ 设A, B, C 是集合，若(A ∩ C ) ⊆ (B ∩ C )且(A∩ ∼C ) ⊆ (B∩ ∼C )，证 明A ⊆ B 设A, B, C 是集合，证明
2008 9
年 月9日
3 / 12
德摩尔根律
A − (B ∩ C ) = (A − B) ∪ (A − C )
A B C B
A C B
A C
A
−
B∩C
= (A − B) ∪ (A − C )
周 晓 聪 (中山大学计算机科学系)
离散数学基础·集合论与图论
2008 9
年 月9日
3 / 12
德摩尔根律
从 出发
(A∩ ∼B) ∪ (A ∩ C ) ⊆ (A∩ ∼B)∩ ∼C ⇐⇒ (A∩ ∼B) ⊆ (A∩ ∼B)∩ ∼C ⇐⇒
− (A − B) − C = (A∩ ∼B)∩ ∼C , A − (B − C ) = (A∩ ∼B) ∪ (A ∩ C ) − (A∩ ∼B) ∪ (A ∩ C ) ⊆ (A∩ ∼B)∩ ∼C
进一步
且 (A ∩ C ) ⊆ (A∩ ∼B)∩ ∼C (A∩ ∼B) ⊆∼C 且 (A ∩ C ) ⊆ (A∩ ∼B) 且 (A ∩ C ) ⊆∼C
− A ∩ C ⊆∼C − A∩C =∅ − A∩C =∅
◦
因此，(A − B) − C = A − (B − C )当且仅当A ∩ C = ∅
周 晓 聪 (中山大学计算机科学系) 离散数学基础·集合论与图论
从 出发
− (A − B) − C = (A∩ ∼B)∩ ∼C , A − (B − C ) = (A∩ ∼B) ∪ (A ∩ C ) − (A∩ ∼B) ∪ (A ∩ C ) ⊆ (A∩ ∼B)∩ ∼C
周 晓 聪 (中山大学计算机科学系)
离散数学基础·集合论与图论
2008 9
年 月9日
7 / 12
计算机科学与技术专业·集合论与图论
第一讲第三次课 子集关系与集合相等
中山大学计算机科学系软件工程实验室
2008 9 9
周晓聪
年月日
/∼ zxc isszxc@
周 晓 聪 (中山大学计算机科学系)
离散数学基础·集合论与图论
子集关系及集合相等举例
证明(A − B) − C ⊆ A − (B − C )，这两者什么时候相等？ 这两者什么时候相等？
从 出发
(A∩ ∼B) ∪ (A ∩ C ) ⊆ (A∩ ∼B)∩ ∼C ⇐⇒ ⇐⇒ (A∩ ∼B) ⊆ (A∩ ∼B)∩ ∼C
− (A − B) − C = (A∩ ∼B)∩ ∼C , A − (B − C ) = (A∩ ∼B) ∪ (A ∩ C ) − (A∩ ∼B) ∪ (A ∩ C ) ⊆ (A∩ ∼B)∩ ∼C
周 晓 聪 (中山大学计算机科学系)
离散数学基础·集合论与图论
2008 9
年 月9日
7 / 12
子集关系及集合相等举例
证明(A − B) − C ⊆ A − (B − C )，这两者什么时候相等？ 证明子集关系的思路：利用基本恒等式A − B = A∩ ∼B
(A − B) − C = (A∩ ∼B)∩ ∼C A − (B − C ) = A∩ ∼(B∩ ∼C ) = A ∩ (∼B ∪ C ) = (A∩ ∼B) ∪ (A ∩ C )
进一步
且 (A ∩ C ) ⊆ (A∩ ∼B)∩ ∼C (A∩ ∼B) ⊆∼C 且 (A ∩ C ) ⊆ (A∩ ∼B) 且 (A ∩ C ) ⊆∼C
− A ∩ C ⊆∼C − A∩C =∅ − A∩C =∅
◦
再由(A∩ ∼B) ⊆ A得A ∩ C = ∅也蕴含(A∩ ∼B) ⊆∼C
离散数学基础·集合论与图论
首先，假定A − B = A成立，证明A ∩ B = ∅ 然后，假定A ∩ B = ∅成立，证明A − B = A
周 晓 聪 (中山大学计算机科学系)
离散数学基础·集合论与图论
2008 9
年 月9日
6 / 12
子集关系及集合相等举例
基本思路
证明A − B = A当且仅当A ∩ B = ∅
首先，假定A − B = A成立，证明A ∩ B = ∅ 然后，假定A ∩ B = ∅成立，证明A − B = A
2008 9
年 月9日
1 / 12
集合相等 基本恒等式
−
◦ ∪ ◦
与命题逻辑中的等值演算非常类似
集合等式的证明方法
−
◦ A=B ◦
−
注意德摩尔根律的绝对形式和相对形式，差与交之间的转换等集合等式 根据集合相等的定义进行证明 利用基本恒等式进行证明
当且仅当∀x (x ∈A ↔ x ∈B) 对任意的x ，首先以x ∈A作为附加前提推导x ∈B，然后以x ∈B为附加前提推 导x ∈ A
证明A ∩ B = ∅蕴含A − B = A
− −
假定A ∩ B = ∅，证明A − B ⊆ A及A ⊆ A − B
对任意的x ∈A，由于A ∩ B = ∅，因此x ∈ B，因此x ∈A − B
周 晓 聪 (中山大学计算机科学系)
离散数学基础·集合论与图论
2008 9
年 月9日
6 / 12
子集关系及集合相等举例
设A ∩ B = ∅，即存在x∈A ∩ B，即x∈A且x∈B，由A − B的定义 得x ∈ A − B，但x∈A，这与A − B = A矛盾！
证明A − B = A蕴含A ∩ B = ∅
−
假定A − B = A成立，反证法证明A ∩ B = ∅
周 晓 聪 (中山大学计算机科学系)
离散数学基础·集合论与图论
且 (A ∩ C ) ⊆ (A∩ ∼B)∩ ∼C (A∩ ∼B) ⊆∼C 且 (A ∩ C ) ⊆ (A∩ ∼B) 且 (A ∩ C ) ⊆∼C
周 晓 聪 (中山大学计算机科学系)
离散数学基础·集合论与图论
2008 9
年 月9日
7 / 12
子集关系及集合相等举例
证明(A − B) − C ⊆ A − (B − C )，这两者什么时候相等？ 这两者什么时候相等？
2008 9
年 月9日
8 / 12
子集关系及集合相等举例
证明(A ∩ C ) ⊆ (B ∩ C )且(A∩ ∼C ) ⊆ (B∩ ∼C )蕴含A ⊆ B 元素法，思路：对任意x ∈A，假设x ∈A，需要推导x ∈B
−
分两种情况：x∈C 和x ∈ C
周 晓 聪 (中山大学计算机科学系)
离散数学基础·集合论与图论
从 出发
(A∩ ∼B) ∪ (A ∩ C ) ⊆ (A∩ ∼B)∩ ∼C ⇐⇒ (A∩ ∼B) ⊆ (A∩ ∼B)∩ ∼C ⇐⇒
− (A − B) − C = (A∩ ∼B)∩ ∼C , A − (B − C ) = (A∩ ∼B) ∪ (A ∩ C ) − (A∩ ∼B) ∪ (A ∩ C ) ⊆ (A∩ ∼B)∩ ∼C

合集下载

计算机科学与技术专业主要课程简介

计算机科学与技术专业主要课程简介

计算机科学与技术专业主要课程简介计算机科学与技术专业是当今社会备受瞩目的高端学科之一，其创造了各种各样的机会和挑战。

在迅速发展的信息技术领域中，计算机科学与技术专业的学生被要求掌握广泛的计算机知识和技能。

本文将简要介绍计算机科学与技术专业的主要课程，以帮助读者了解该专业的学习内容和发展方向。

1. 离散数学离散数学是计算机科学与技术专业中基础且必不可少的课程之一。

它涵盖了数理逻辑、集合论、图论、代数结构等内容，培养了学生分析和解决实际问题的能力。

离散数学的学习也有助于培养学生的抽象思维和逻辑推理能力。

2. 数据结构与算法数据结构与算法是计算机科学与技术专业中最重要的课程之一。

学生将学习不同的数据结构，如数组、链表、栈和队列等，并了解它们之间的联系和应用。

同时，学生还将了解常用的算法，如排序、搜索和图算法等。

数据结构与算法的学习帮助学生开发高效的程序设计能力和解决实际问题的能力。

3. 编程语言及编程基础计算机科学与技术专业要求学生精通至少一种编程语言。

常见的编程语言包括C++、Java和Python等。

学生将学习编程语言的语法、面向对象编程、软件开发流程等，并完成一系列编程实践项目。

通过编程语言的学习，学生能够熟练掌握程序设计的方法和技巧，为以后的实际应用打下坚实的基础。

4. 操作系统操作系统课程旨在帮助学生理解计算机系统的组成和工作原理。

学生将学习操作系统的各种概念和机制，如进程管理、内存管理、文件系统等。

此外，学生还将进行实践，如编写简单的操作系统模拟程序，以更深入地理解操作系统的运行机制。

5. 计算机网络计算机网络是现代社会的基础设施，也是计算机科学与技术专业中不可或缺的一门课程。

学生将学习计算机网络的基本原理、协议和技术。

课程内容包括网络体系结构、数据传输、网络安全等。

通过计算机网络课程的学习，学生能够理解和应用各种网络技术，确保计算机系统的高效和安全运行。

6. 数据库数据库管理系统是现代信息系统中重要的组成部分。

图论第01讲

图论第01讲


•
两个问题：
（1）经过每个顶点一次且仅一次； （2）代价最小的Hamilton回路。
(目前无有效的方法求解)
•
货郎问题（Traveling Salesman Problem）
一个货郎到各村去卖货，要求每个村子 至少去一次，最后返回出发点，为其设计一 种销售路线，使总耗时最短。
求解方法：把路线全排列，求其中最小的。
1930年，波兰数学家库拉托父斯基 (Kuratowski)证明了平面图可以画在平面上；
•
里程碑：1936年，匈牙利数学家寇尼希 (D.Konig)发表名著《有限图和无限图理论》 ，使得图论成为一门独立的数学学科；
蓬勃发展：1946年，随着世界上第一台计算机 的问世，使图论的发展突飞猛进。 其后，图论在现代数学、计算机科学、工程技 术、优化管理等领域有大用而得以大力发展。
图论第01讲
•
课程简介
▪ 《图论》是计算机科学与技术专业、信息 安全专业的选修课程。 通过本课程的学习，使学生对图论的 历史背景、研究内容、相关技术及其发展 有一个较为全面地了解，从而将所学知识 和技术运用于实际应用领域奠定基础。
•
▪ 本课程所介绍的内容包括：
图论的发展历程和经典问题； 图的基本概念； 有关树和图的算法； 网络流问题； 匹配问题、色数问题；
•如何才能在所有桥都恰巧只走一遍的前提下，回到原出发点?
•
不少数学家都尝试去解析这个事例。而 这些解析，最后发展成为了数学中的图论。
莱昂哈德·欧拉(Leonhard Euler)在1736 年圆满地解决了这一问题，证明这种方法并 不存在。他在圣彼得堡科学院发表了图论史 上第一篇重要文献。欧拉把实际的问题抽象 简化为平面上的点与线组合，每一座桥视为 一条线，桥所连接的地区视为点。这样若从 某点出发后最后再回到这点，则这一点的线 数必须是偶数。
计算机科学与技术专业主要课程简介

计算机科学与技术专业主要课程简介

计算机科学与技术专业主要课程简介1H10306计算机导论学分：2.5 Introduction to Computer Science预修课程：无内容简介：本课程是计算机科学与技术、信息与计算科学专业的重要入门课程，系统而全面地向学生介绍信息技术的基础知识，引导学生进入计算机科学技术的大门，让学生了解和掌握本专业要学习基本内容和特征。

主要内容包括：信息化社会特点、计算机的基本知识、计算机系统及其组成、软件基础；计算机网络及其应用技术基础；计算机法规与知识产权保护、计算机病毒防治等基础知识；计算机的基本操作、中英文输入法、Office等办公软件的操作使用方法。

推荐教材：《计算机科学技术导论》（专业版·第二版），陶树平主编，高等教育出版社，2004年主要参考书：《计算机系统导论》，许洪杰主编，南开大学出版社，2003年《Computer Concepts》(4thEdition), June Jamrich Parsons，机械工业出版社，2002年《计算机科学技术导论实践教程》，丁岳伟主编，高等教育出版社，2004年1H12046程序设计基础（C）学分：3.5C Programming预修课程：计算机导论内容简介：本课程是计算机及相关专业的一门重要的基础课，通过C语言的学习，以及程序设计基础能力的培养，使学生掌握初步的计算机编程能力。

主要内容包括C语言程序设计方法概述、数据类型、运算符与表达式、输入输出语句、控制语句、数组、函数、指针、结构体等。

推荐教材：《C语言程序设计》，刘玉英等主编，中国水利水电出版社，2002年主要参考书：《C语言学习指南与题解》，刘玉英等主编，中国水利水电出版社，2002年《C程序设计语言》（影印版·第二版），Brian W. Kernighan 、Dennis M. Ritche，清华大学出版社，1997年1H11756程序设计基础（C＋＋）学分：3.5 C＋＋Programming预修课程：计算机导论、程序设计基础（C）内容简介：本课程是计算机及相关专业的一门十分重要的基础课，通过从C到C++语言程序设计的学习，让学生进一步掌握程序设计基础，掌握基于对象的程序设计，了解面向对象的设计方法，重点培养学生的计算机编程能力。

计算机科学与技术专业大一课程

计算机科学与技术专业大一课程

计算机科学与技术专业大一课程计算机科学与技术专业是现代高等教育体系中的一门应用学科，它主要研究计算机系统的原理、方法、技术和应用，是现代信息技术的基础与核心学科之一、在大一阶段，学生将学习一系列基础课程来帮助他们对这门学科有一个全面的了解和基础的技能。

以下是一些常见的大一课程，它们可能会因学校和课程设置而有所不同：1.计算机导论：这门课程主要介绍计算机科学与技术的基本概念、发展历程、相关技术和学科发展趋势。

学生将了解计算机科学与技术的基础知识，如计算机硬件、软件、计算机网络等。

2. 程序设计与算法：这门课程主要介绍计算机程序设计的基本原理和方法，以及算法设计与分析。

学生将学习一种或多种编程语言，如C、C++、Java等，并学习如何用程序解决实际问题。

3.数据结构与算法：这门课程主要介绍各种数据结构和算法的基本概念、特点和实现方法。

学生将学习如何选择和设计适合特定问题的数据结构和算法，并通过编程实现和应用。

4.计算机组成原理：这门课程主要介绍计算机硬件系统的组成和工作原理。

学生将学习计算机的运算原理、存储器层次结构、指令系统、中央处理器等相关知识。

5.操作系统原理：这门课程主要介绍操作系统的基本原理和功能。

学生将学习操作系统的概念、进程管理、内存管理、文件系统等内容，并通过实践了解操作系统的实现和应用。

6.数据库原理与应用：这门课程主要介绍数据库的基本原理和应用。

学生将学习数据库的概念、数据模型、设计和管理等知识，并通过实践掌握数据库系统的应用技术。

7.离散数学：这门课程主要介绍离散数学的基本概念和应用。

学生将学习集合论、图论、逻辑等相关理论和方法，为计算机科学与技术的理论基础打下基础。

8.网络技术与应用：这门课程主要介绍计算机网络的基本原理和应用。

学生将学习网络体系结构、协议、网络安全等知识，并通过实践了解网络技术的实现和应用。

在大一阶段，学生将通过这些课程建立起计算机科学与技术的基础，并培养计算思维、问题解决和团队合作能力。