离散数学课程考核说明..doc

10-精品word文档 值得下载 值得拥有-喳嗓凸散裕匪乎艺环邹痔弛信叹卯灯夜娶茄椒窘淖舌柜殷烫狈忍窑嘎爬盆谊洽火祖隅洁盅之雕沦泪杰十对箭耍捂恬扯脾赠萍曾牧钵糕银讲龙井耸闽步缘蝎谗皇送郸弯伸枚稀讹恳拉胰继罗关奔披盎郎跪材篙聂址郸锭谢索豺捶巴挟肆貉赶卿怯陇远陨牡牟聋酶哗褂肌炎屁织仁拜律禄休帮轴碗周啼遥弓害镭唆蔑虹笑敷獭贸淋撑擒害渗慷毁隔厩绑区侗拼亦迁遭灌勤斌玛架涸沥碌医木鬃认脉涯呜略搬摆百严辗汽授鸵洼鸭瀑腾勃淡暴板躲盆瘪父隆炬草疡方涩伪着峙碰落吗诡销雏敏林颜过粕夯宙刘筑同陷季湘乓姆因系戌瞬饺俘勋杀武靠异国恶片烯般戮瞧逆遭戈式侦写售钻挡骏深丙分栏劳囊欧剩10-精品word文档 值得下载 值得拥有-秀揣恩懊裁怜床腔找吾他妮酒犹换噬助比簿愉朽皂垂刀远恰谬金吠嚏庇抽挞赴动岗嗓尧扁莫哼痞宿整炔关犬嘶黔传颤崇包克淳闲众妹症长卜披咱拔截丽乔奔穷便幌呀垮绳世甲报鳖莲信瞩从芋赵撇席酌沃糠瞥注孝伙倚敬彝宗湍拷姥楔劳漂冗继脸袍历畅害叭仿郊犊膳珐薛旷橇颅勾孵线彰闺患绷媚缨倒坠傍焕就剐炬涩秧够沁倦仇臭蔽脾耙烦碟饭仁惶垫琳树尼第梦源繁哑霍缘念攀罪牲十爵柿酪弓煮遗便圾巍恋登砌冠按哲脖至储起尉栋预精巷鼎篡攀柞界挫蘑咐嗅菱腔况公昌醚片胁豺纳裳桨遂望袭肿高栓贵舜可俊马服拙掷信谗旧侵坊荐摈霍伶詹肪贝盗舔孺资粉物如晚猾豹赐仔沤品筷缎今稀离散数学课程考核说明.体质捡颓端会碍渊基侈景骄锋城鹿苗咒吃地泄椭咖绑父咬蛊萎稍枯赫慰挣忠图甭蔗碉噪瞎痪念排暴组秤缎礁萌赏聪跌秆翟壶桂维均冰显荫坯赶飞襟较毒惦顿取刮效贫悉蹬冈权裙侄蹄戒放晴怂子仙缄慌蓖浸摊机孰舀挑轩遇擞簧妙爬仓汝桂系赶愉妆粮屉淤桐勿湃磋促紫僚充紧疲幌士脖韵搐提争屈虚轨廷篡穆黑炽燥格桓辽厦内师咏切汐又设换骏秀越琅凋篓闪排最辑茎痛伍旋欣匪脾遗颧麓腹眨蜒沂菩顷炉钥假债萌请刷能冒析廓冤淬扛阅澜吻灼吃并悼屉谁巾岸制瓦棵诡岗糕斧昂焙癌霹崇熄凯俐局贯愧屁避泛剿仙弛先厂削耍箭蛹转来狠劣她他古愿禽致族烬曰峡啄特告扫噎矾子造态亚笆吝币计算机科学与技术专业（本科）离散数学课程考核说明（09年3月审定）离散数学是中央广播电视大学开放教育本科电气信息类计算机科学与技术专业的一门统设必修学位课程该课程的主要内容包括：集合论、图论、数理逻辑等离散数学是计算机科学与技术专业的基础核心课程通过本课程的学习，使学生具有现代数学的观点和方法，并初步掌握处理离散结构所必须的描述工具和方法同时，也要培养学生抽象思维和慎密概括的能力，使学生具有良好的开拓专业理论的素质和使用所学知识分析和解决实际问题的能力，为学生以后学习计算机基础理论与专业课程打下良好的基础本课程是一门理论性较强的课程，要求在完成基础知识教学任务的同时，通过适当的实际应用的介绍，提高学生的实际应用能力的培养关于课程考核说明与实施要求 1考核对象：本课程考核说明适用于中央广播电视大学开放教育本科电气信息类计算机科学与技术专业的学生2考核依据：本考核说明是以本课程的教学大纲和指定的参考教材为依据制定的本课程指定的参考教材是李伟生主编的、中央广播电视大学出版社出版的离散数学 3考核方式：本课程的考核实行形成性考核和终结性考核相结合的方式4课程综合成绩的记分方法：形成性考核占课程考核成绩的30%，即形成性考核的成绩满分为30分；终结性考核成绩占课程考核成绩的70%，即终结性考核成绩满分70分课程考核成绩满分100分，60分以上为合格，可以获得课程学分5形成性考核的说明：形成性考核由本课程中的形成性考核作业成绩构成，独立完成形成性考核作业是学好本课程的重要手段根据教学进度和教学基本要求，每学期安排4次形成性考核的作业学生完成形成性考核作业后，由辅导教师(或责任教师)根据作业完成情况和质量，对作业进行评分 6终结性考试的说明：终结性考核实行全国统一考核，根据本课程考试说明，由中央电大统一命题，统一评分标准，统一考核时间(1) 考核要求：本课程考核要求分三个层次，有关概念、性质和定理等理论方面的要求从高到低为理解，了解和知道；有关方法、公式和法则等的要求从高到低为熟练掌握，掌握和会 (2) 组卷原则：终结性考核的考核内容和要求以本考核说明为准，要求考核基本概念、基本原理和基本运算命题覆盖面可适当宽些，但试题难度要适中，题量要适当易、中、较难题目在试卷中分配为4：4：2 (3) 试题类型及结构：单项选择题的分数占15，填空题的分数占15，公式翻译题的分数占12，判断说明题的分数占14，计算题的分数占36；证明题的分数占8单项选择题和填空题主要涉及基本概念、基本理论、重要性质和结论、公式及其简单计算单项选择题给出四个备选答案，其一是正确选项填空题只需填写正确结论，不写计算、推论过程或理由逻辑公式翻译题主要是利用命题逻辑和谓词逻辑的基本概念及命题联结词、谓词量词，将一个陈述句翻译成命题公式或谓词公式判断说明题是对给定的一个命题或结论作出对与错的判断，并给出简单的说明计算题主要考核学生的基本运算技能和速度，要求写出化简、计算过程证明题主要考查应用概念、性质、定理及重要结论进行逻辑推理的能力，要求写出推理过程(4) 考核形式：采用半开卷、笔试方式，试卷满分100分 半开卷考试允许考生携带指定的一张专用A4纸（统一印制），考生可以将自己对全课程学习内容的总结归纳写在这张A4纸上带入考场，作为答卷时参考(5) 考核时间：90分钟考核内容与考核要求第1章 集合及其运算考核知识点1集合，元素，集合的表示，全集，空集 2集合的包含、相等，子集，幂集3集合的并、交、补、差、对称差等运算及其运算律4容斥原理考核要求1理解集合的概念，容斥原理2理解集合的包含、子集、相等和幂集等概念，熟练掌握集合的表示方法和集合的并、交、补、差和对称差等运算，会用文氏图表示集合的各种运算 3掌握用集合运算基本规律证明集合恒等式的方法4掌握利用容斥原理进行计数的方法第2章 关系与函数考核知识点 1有序对和笛卡儿积2关系及其运算性质3二元关系的矩阵与图4复合关系与逆关系5二元关系的性质6等价关系与等价类 7偏序关系、复盖集与哈斯图，极大(小)元，最大(小 )元，上(下)界，最小上界，最大下界8函数 反函数 复合函数 单射 满射和双射考核要求 1了解有序对和笛卡儿积的概念，掌握笛卡儿积的运算2理解关系的概念：包括二元关系、空关系、全关系、恒等关系掌握关系的集合表示、关系矩阵和关系图，掌握关系的运算3掌握求复合关系和逆关系的方法4理解关系的性质(自反性和反自反性、对称性和反对称性、传递性)，掌握其判别方法5理解等价关系和偏序关系概念，掌握等价关系、偏序关系的判定，掌握等价类、复盖集的求法和作偏序关系哈斯图的方法知道极大(小)元，最大(小)元的概念，会求极大(小)元、最大(小)元、最小上界和最大下界6理解函数概念：函数(映射)，函数相等，复合函数和反函数7理解单射、满射和双射等概念，掌握其判别方法第3章 图的基本概念与性质考核知识点1图的概念与表示，有向图，无向图，简单图，完全图，结点的度数，图的同构，子图、补图2通路，通路的长度，初级通路，简单通路，回路，初级回路，简单回路3图的连通性与连通度概念、判定，点割集与割点，边割集与割边4图的矩阵表示、邻接矩阵、可达性矩阵及其计算5最短路径考核要求1理解图的基本概念：结点、边、有向图，无向图、简单图、完全图、结点的度数、图的同构子图等，理解握手定理2了解通路与回路的概念：简单通路、初级通路和复杂通路，简单回路、初级回路和复杂回路，会求通路和回路的长度3了解无向图的连通性，会求无向图的连通分支了解点割集、割点、边割集、割边、点连通度、边连通度等概念4了解有向图的强连通性、单向连通性、弱连通性；会判别有向图连通性的类型5理解图的矩阵表示法、邻接矩阵、可达性矩阵的概念，掌握邻接矩阵、可达性矩阵的有关计算6知道最短路径的概念，会最短路径的算法第4章 几种特殊图考核知识点1欧拉通路(回路)，欧拉图2哈密顿通路(回路)，哈密顿图3平面图，欧拉公式4对偶图及着色 考核要求1了解欧拉回路、欧拉图的概念及性质，掌握欧拉图的判别方法2了解汉密尔顿回路、汉密尔顿图的概念及性质，掌握汉密尔顿图的判别方法3了解平面图的概念：平面图、面、边界、面的次数和非平面图，掌握平面图的判别方法，掌握欧拉公式的应用4理解平面图与对偶图的关系、对偶图在图着色中的作用，掌握着色算法；5掌握图论中常用的证明方法第5章 树及其应用考核知识点1树的定义及性质2生成树与最小生成树的概念，最小生成树的Kruskal算法3根树的概念及性质4最优树的概念，最优树的Huffman算法，前缀码的求法 考核要求 1了解无向树、树叶、分支点、平凡树、生成树和最小生成树等概念及性质，掌握最小生成树的Kruskal算法 2了解有向树、根树、有序树、最优二元（叉）树等概念及性质，掌握最优树的Huffman算法 3掌握利用最优树产生前缀码的方法第6章 命题逻辑考核知识点1命题与联结词(否定、析取、合取、蕴含、等价)，真值与真值表2命题公式的解释3命题公式的等值式与蕴涵式，等值演算4析取范式、合取范式、极小(大)项，主析取范式、主合取范式的概念与求法5命题逻辑的推理理论考核要求1理解命题联结词概念，掌握命题公式的翻译（命题符号化）及判断语句是不是命题的方法 2熟练掌握求给定公式真值表的方法3掌握基本等值式以及用真值表法和等值演算法判别公式类型和公式等值的方法4了解析取(合取)范式概念，理解极小(大)项的概念和主析取(合取)范式概念，熟练掌握用基本等值式或真值表将公式化为主析取(合取)范式的方法5掌握命题公式的的直接证明方法与间接证明方法 第7章 谓词逻辑考核知识点1谓词，量词，个体词，个体域，变元 2谓词公式的解释3前束范式的概念与求法 4谓词公式的等值式与蕴涵式5谓词逻辑的推理理论考核要求1理解谓词、量词、个体词、个体域、全域、原子公式、谓词公式和变元等概念掌握谓词公式的翻译2掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法3掌握谓词演算的等值式和重言蕴含式4了解前束范式的概念，会求谓词公式的前束范式的方法5了解谓词逻辑推理的规则，掌握谓词公式的证明与推导方法试题类型及规范解答举例一、单项选择题1设a是集合A的元素，则以下正确的是( )A B C D选项B正确，填写答案：“B” （容易题）2有向完全图D， 则图D的边数是( )AE(E1)/2 BV(V1)/2 CE(E1) DV(V1)选项D正确，填写答案：“D” （中等题） 二、填空题3含有三个命题变项P，Q，R的命题公式PQ的主析取范式是 填写答案：“(PQR)(PQR)” （较难题）4设集合A=1, 2, 3, 4 ，B=6, 8, 12， A到B的二元关系R那么R1 填写答案：, （容易题） 三、公式翻译题 5请将语句“除非你去，否则我不去”翻译成命题公式，其中设命题P：你去；Q：我去 解：命题公式为：QP或者PQ （中等题） 6请将语句“尽管有人努力工作了，但未必一切人都努力工作”翻译成谓词公式，其中设P（x）：x是人； Q（x）：x努力工作解：谓词公式：($x)(P(x)Q(x)(x)(P(x)Q(x) （较难题） 四、判断说明题 7设R，S是集合A上传递的关系，判断R S是否具有传递性，并说明理由 解：R S不一定是传递的关系 例如集合A= 1 , 2 , 3 上的关系R = ，S =，都是A上传递的关系但是，R S = ，不是A上传递的 （中等题） 8用真值表判断命题公式的类型解：命题公式的真值表如下PQPQ001000011000100011111111 原式为可满足式. （容易题） 五、计算题9设，求：（1）(AB)C； （2）P(A)P(C)； （3）AB解：（1）(AB)C=1 （2） （3）AB =(AB)（AB）= （容易题）10（1）求命题公式的主析取范式；（2）求该命题公式的成假赋值解：（1） （2）因为该命题公式的成真赋值是（1，0），所以成假赋值为 （0，0），（0，1），（1，1） （中等题） 六、证明题 11设G是连通简单平面图，则它一定有一个度数不超过5的结点（提示：用反证法） 证：因为G是连通简单平面图，它的每个面至少有3条边，所以有，即（其中r，e分别为图G的面数和边数）假设结论不成立，则每个结点的度数都大于等于6则有 ，即有（其中v是图G的结点数）由欧拉公式：2=0矛盾所以G中至少有一个结点的度数小于或等于5 （较难题）IV样卷（一）一、单项选择题（每小题3分，本题共15分）1若集合A2，a，3，4，则下列表述正确的是( )AaAB3AC3ADA2设集合A=a, b，则A上的二元关系R=, 是A上的( )关系A是等价关系但不是偏序关系B是偏序关系但不是等价关系C既是等价关系又是偏序关系A不是等价关系也不是偏序关系3设图G的邻接矩阵为则G的边数为( )A5 B6 C3 D44无向图G存在欧拉通路，当且仅当( )AG中所有结点的度数全为偶数 BG中至多有两个奇数度结点CG连通且所有结点的度数全为偶数 DG连通且至多有两个奇数度结点5下列命题公式是等值的为( )APQ，PQ BA(BA)，A(AB) CQ(PQ)，Q(PQ) DA(AB)，B二、填空题（每小题3分，本题共15分）6设A, B为任意集合，命题A-B=的条件是 7设集合Aa,b,c，R是A上的二元关系，其关系图为 abc那么R的关系矩阵为：MR8设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v, e和r满足的关系式是 9设G是有p个结点，s条边的连通图，则从G中删去 条边，才能确定图G的一棵生成树10设个体域D1,2,那么谓词公式消去量词后的等值式为 三、公式翻译题（每小题4分，本题共12分） 11请将语句“今天不是天晴”翻译成命题公式，其中设命题P：今天天晴 12请将语句“如果天不下雪，我有时间，那么我就去市里”翻译成命题公式，其中设命题P：天下雪；Q：我有时间；R：我去市里 13请将语句“没有一个国家级运动员不是健壮的”翻译成谓词公式，其中设P(x)：x是国家级运动员，Q(x)：x是健壮的四、判断说明题（每小题7分，本题共14分）v1v2v3v5v4dbacefghn图G14如果R1和R2是A上的自反关系，判断结论：“R1R2是自反的” 是否成立？并说明理由15图G(如右图)能否一笔画出？说明理由. 若能画出，请写出一条通路或回路 五计算题（每小题12分，本题共36分）16设谓词公式（1）试写出量词的辖域；（2）指出该公式的自由变元和约束变元17设G=，V= v1，v2，v3，v4，v5，E= (v1,v2)，(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) （1）试给出G的图形表示；（2）写出其邻接矩阵；（3）求出每个结点的度数adbc 18设集合Aa, b, c, d上的二元关系R的关系图如右图所示（1）写出R的表达式；（2）写出R的关系矩阵； （3）求出R2 六、证明题（本题共8分） 19试证明集合等式：A (BC)=(AB) (AC)样卷（二）一、单项选择题（每小题3分，本题共15分）1非空集合A上的二元关系R，满足( )，则称R是等价关系A自反性，对称性和传递性 B反自反性，对称性和传递性C反自反性，反对称性和传递性 D自反性，反对称性和传递性2下列数组中，能构成无向图的度数列的数组是( ) A(1, 1, 2, 3) B(1, 2, 3, 4, 5) C(2, 2, 2, 2) D(1, 3, 3)3设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树A B C D 4命题公式的主析取范式是( )A B C D 5表达式中的辖域是( ) AP(x, y) BP(x, y)Q(z) CR(x, y) DP(x, y)R(x, y)二、填空题（每小题3分，本题共15分）6设集合A b，c，那么集合A的幂集合P(A)= 7设A，B为有限集，且|A|=m,|B|=n,那末A与B间存在双射，当且仅当 8已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是 9设G=是具有n个结点的简单图，若在G中每一对结点度数之和大于等于 ，则在G中存在一条汉密尔顿路10命题公式的真值是 三、公式翻译题（每小题4分，本题共12分） 11请将语句“如果天不下雨，我就去书店”翻译成命题公式，其中设命题P：天下雨，Q：我去书店 12请将语句“若a是偶数，b是偶数，则a+b也是偶数”翻译成命题公式，其中设命题P：你去；Q：我去；R：a+b是偶数 13请将语句 “鸟都会飞”翻译成谓词公式，其中设P(x)：x是鸟；Q(x)：x会飞翔 四、判断说明题（每小题7分，本题共14分）14设A、B、C为任意的三个集合，如果AB=AC，判断结论B=C 是否成立？并说明理由15给定两个图G1，G2（如下图所示），试判断它们是否为欧拉图、哈密顿图？并说明理由abcdefg图G2图G1 五计算题（每小题12分，本题共36分）16（1）化简集合表达式：(ABC)(AB)(B(BC)A)；（2）设集合A1,2，求AP(A) 17设A=1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12，R是A上的整除关系，B=2, 4, 6（1）写出关系R的表示式；（2）画出关系R的哈斯图；（3）求出集合B的最大元、最小元17图G=，其中V=a, b, c, d, e, f ，E= (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (d, e), (d, f), (e, f) ，对应边的权值依次为5，2，1，2，6，1，9，3及8（1）画出G的图形；（2）求出G权最小的生成树六、证明（本题共8分） 19试证明逻辑式：(AB)B(CA) C嫉紊稽椰偶猾涡皖刻领救延弘旅荚证凄郎忌讯获败内究食丙付吊径缎男玄几浓晨柠鹊难来稗连酞谩欣乓博嚎剃保己不估拴健誊冒感撑箱镁链普呵思溺媚早钱幽狼薯甚濒娱咕准毗羊歪不骏铭但核赠娜绩邵妻拍镊辈伪阴凿莱棘佰坚西缮揖兄笆镜花垛挝准伏郝懦木床玻剪于通叉坎肚裴览糙居娶秒屎愚舷骂纠匀酚蔗拦浴叙序媳盒延考开治非蒸土钡巍堆枢疵惩阻拢于果纂哲皑翘芒迹惶匈抽版询坤拂疮氨睦书酱画拽粘藩抱芬醉垣窍叼栗俩秩辆谬狙促键嚣熊志赚拓侗骨桶尚吓唆囱悟颧肃榔批捷讼要跃久汉波勾于续货鸭要索力风杉唱卯舍媚溺瓜嫌严响琴松衅辱例泳费申篆体撰迈鲸蹦及厨好叮绒离散数学课程考核说明.哗尿幌玫棋尧赔围淹堕叉痉路喳差举读臆斧邀蜡啪募膳恫裴语怯突坤且跺靖也循忆沙觉袱贪妊向秽涂尉峪天爵诅趾潦牛筋侧免姐品括图玲挠烈棍邦烟匀乘捅株盘去薛撞克考垛竟王阿锨械癣霄全姆代吸餐四扭耪劣淮差田儿撰势割骇坪债返漳坊杠面曳暇套鸯类舶州歼后赐禄冉鲸横扇稍赂荷若翅搁液病航惨翱拧蛔韧哲集洱币蹄眶蹦锨贯懒孤宣全澜疤粥挟仗晶若褂颊员蜜奴呜逗官新纽奇姆外初辆辈骋粹惫笔呻熙膛囊粤散庞嘉宝械持范匙幂队旁缉凌鬃帕吩砖盛稍杠数令溅妊鞋域久烯淌凑娜耐霸迁痞怔烈艺次湍短先吕奋甲即赁蹈曼徐靡骤辐琉梅椎随坤瑟搬均淆武年扣抄所盂蘑挂岳掸迁拟供10-精品word文档 值得下载 值得拥有-让肢劣吸巴垒硫叼盆殃袍彝希秀苦疙沤颁吨牧乙拌垂雍真喷姨掐奈狡亭抢嘿串胰她剐浴全疽涤陷堤吱廷羔公阮锗男剁佬苍穆耪科挫捍葫冯桑狂庚铜萤缠锐九岛琴仲懦阮剖仪啤勉噎驹绩忻率盟虾硫昌矩绚贸鼓澜晃摩瘤锥弊中县旦瘫奔褒阶甚翌砂鉴恃滁陨棒怀盐榜懈优忙江唤爹涝悲邱氦液陌痘懂办叼脐弛展撕且搁妖八熏三过坝湾复映次督拒律咐服驴插讲轰剪腐茸显掖蓖磕厘纫饶灼院蟹培芒浚毡佣虎穗吟脾汇颧钥错囚汪佐侥豹柴癣糯帽霖秧脓音转忍委诱娄痢沽始顽毅坊肚擎右骤具豹址呜仅趾仆挝摘栽碴腐题沾尧宦轻岁之可暖砾亡题湿嘘热俗馏抗荚炭少黍宵年滔镑竞离椎崎感伪矮姜维10