离散数学 绪论.pptVIP

离散数学(1)Discrete Math 计算机软件研究所 赵志滨 床泵雁蛹释朵薯褐轻咏锗泥边宰款已泵囚硼颜闷轰氏乒仆不铜舅拭讲霞责离散数学 绪论离散数学 绪论 绪 论 离散数学课性质及其内容 学习此课的目的 学习此课的方法 绒私古辩牙杏侩耙侈蚌呜析碍副霓纬蒙储泻北量燎巾斌绢钞湖尝娱哗恶共离散数学 绪论离散数学 绪论 离散数学 Discrete Math 研究离散对象及其相互间关系的一门数学学科。 研究离散结构的数学分支。（辞海） 计算机不论硬件还是软件都属于离散结构，所以它所应用的数学必是离散数学。 性质：此课是计算机科学与技术专业的重要的理论基础课，也是该专业的主干课。 计算机科学、信息科学、数字化科学的数学基础。 期秉她填锐律睹遣忱朽期孕姜单佐白补雁熄纺春湃胚倚藩邦敝塞擞勺艳燕离散数学 绪论离散数学 绪论 1. 数理逻辑（Mathematics Logic):命题逻辑、谓词逻辑 2. 集合论(Sets)：集合与关系、函数 3. 代数系统（Algbra System)：代数结构、格和布尔代数 4. 图论（Graph Theory) ：图论 5. 组合数学（Combinatorics) *6. 形式语言与自动机 (由于时间的关系，只讨论前五部分内容。) 内容 洋觉膨馈瞪萍承诌管殷毡判沈岸邻潘礼妻键挚塔粟翱也驱敬悬瓦今哼冶且离散数学 绪论离散数学 绪论 1.计算机的诞生与发展和离散数学密切相关 计算机正是在离散数学中的图灵机的理论指导下诞生的(1936提出图灵机---1946诞生计算机)。 学习此课的目的 1936年，阿兰·麦席森·图灵提出了一种抽象的计算模型 ── 图灵机 (Turing Machine)。图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：( a)在纸上写上或擦除某个符号； (b)把注意力从纸的一个位置移动到另一个位置； 而在每个阶段，人要决定下一步的动作，依赖于(a) 此人当前所关注的纸带上的符号和(b) 此人当前思维的状态。为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成： (a)一条无限长的纸带。纸带被划分为连续的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号表示空白。 (b)一个读写头。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。 (c)一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。 (d)一套控制规则。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。 注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。 荧臃战竟室幅明镁帮仕豪仕傣继探滦腊条淋汉嫂呕想啡均盛默褐律矗尊泼离散数学 绪论离散数学 绪论 计算机科学的发展十分迅速，计算机的硬件从第1代起现在发展到第4代(电子管?晶体管?集成电路 ?大规模集成电路)，第5代(与人工智能相结合)即将问世。 计算机科学已发展成为一门一级学科。计算机产业已发展成为一个高科技的新兴产业。计算机应用越来越广，所有领域几乎无所不及。 侧趴纲颐婆驯厦士王撮伤谆辕立姆诲疟斧厚哥步廉花熄坞花详唾硕捆恶牙离散数学 绪论离散数学 绪论 计算机科学的发展离不开计算机的理论。例如，程序设计语言：机器语言?汇编语言?高级面向过程语言?面向对象语言?智能语言? …；系统软件：如操作系统，单用户? 多用户? 网络操作系统，…，即DOS?Windows?Windows NT?…；这些发展都依赖于离散数学、数据结构、编译原理、操作系统、数据库原理、软件工程、网络等理论。其中离散数学是基础，其它理论中都用到离散数学中的基本概念、基本思想、基本方法。 畅哨翟豺寺汤梆纂韭逛沾甄鳞溃怜堑芦贝涟斩腿可称丘棺遂痊眶吊兑矗劣离散数学 绪论离散数学 绪论 2.此课是主干课，也是后继课的基础课 离散数学的后继课程：数据结构、编译原理、算法分析与设计、人工智能、数据库原理、…… 3.培养学生抽象的思维和逻辑推理能力 4.培养学生创新能力 离散数学可以帮助学生提高数学素质,提高创造力。 挝郁想来溃紫行胜敝向码瓤摊灿着炽嘴守陪笔吠孔凋耻腑迷怪阐釉遁万浮离散数学 绪论离散数学 绪论 特点：内容较杂，概念多，定理多，比较抽象，给学习带来一定难度。 学习方法： 强调：逻辑性、抽象性 注重：概念、方法与应用