本课程主要为对数学和计算机科学/工程有兴趣的学生介绍数学逻辑与图论的原理。主要内容分为两部分：数理逻辑和图论。第一部分主要介绍数学语言的定义（命题和谓词逻辑）、递归概念和关系理论。第二部分讨论图论的主要结论并介绍本课程所涉及的方法和术语。图的数学理论是重点。涉及的主题有：顶点、边、度、平面图、有向图、偶图、连通性、路径、欧拉回路、哈密顿回路、树、独立集、平面化和着色等。着重强调了现代数理逻辑与图论中已经被证明是非常有成效的各种方法。
This course is an introduction to the theory of mathematical logic and graphs intended for students interested in mathematics and computer science/engineering theory. The content of this course is divided into two parts: mathematical logic and graph theory. The first part gives will meet precise definitions of the language of mathematics (propositional and predicate logic), and basic notions of recursion and relation theory. The second part discusses some of the major results of graph theory, and provides an introduction to the methods and terminology of the subject. Emphasis will be given to mathematical theory of graphs. The topics include: vertex, edge, degrees, planar graphs, directed graphs, bipartite graphs, connectivity, paths, Eulerian tours, Hamiltonian cycles, trees, independent sets, planarity, and colorings, etc. Special emphasis is on various approaches that has proved fruitful in modern mathematical logic and graph theory.
《离散数学及其应用（原书第8版）本科教学版》（美）Kenneth H. Rosen 著，徐六通 杨娟 吴斌 译，机械工业出版社
《离散数学及其应用》（原书第8版）（美）Kenneth H. Rosen 著，徐六通 杨娟 吴斌 译，机械工业出版社（
pdf文件下载）
《Discrete Mathematics and its Application (Eighth Edition)》 Kenneth H. Rosen 著，机械工业出版社
（原版教材主页：http://www.mhhe.com/rosen）
《离散数学教程》耿素云 屈婉玲 王焊贫 著，北京大学出版社
学时：40学时（1-10周），32学时上课，6学时习题课、复习和答疑，2学时考试
课后作业：每周二放至教室最后一排，等助教来收取，下周二前发回
评分标准：
期末考试：60分
课后作业：32分，共8次作业，每次满分4分
平时表现：8分
注意：抄作业，该次作业按0分计；迟交作业，该次作业满分2分
重要通知比如考试和习题课安排会及时放在主页上，请同学们多多关注！
第一周第一次作业：1.1节（13，19，35，43），1.2节（11，29，39）；
第一周第二次作业：1.3节（19，29，33，45，55）；
第二周第一次作业：1.4节（7，27，63）；1.5节（7，11，21，35）；1.6节（11，23，29，35）；
（注意：1.6.23题论证第一行的析取应为合取；1.6.35题倒数第二句应为“如果超人存在，则他既不是无能的也不是恶意的。”）
第二周第二次作业：1.7节（15，19，41）；1.8节（5，13，27，51）；
第三周第一次作业：2.1节（11，27，41，43，49）；2.2节（19，35，47）；
第三周第二次作业：2.3节（3，21，37）；2.4节（27）；2.5节（11，17，31）；
第四周第一次作业：3.1节（41，53，77）；3.2节（13，15，25，49）；3.3节（23，31）；
第四周第二次作业：4.1节（17，27，29，35）；4.5节（17）；4.6节（15，17）；
（注意：4.1.35题，J(n)是指最后生存者的编号；4.5.17题，题目应为“有多少个以3个数字987开始，或者在第5和
第6位包含数字45，或者最后3位是123？”；4.6.15题，100封信应对应100个不同的信袋。）
第六周第一次作业：5.1节（5，9，49，57）；5.2节（23）；
第六周第二次作业：5.3节（15，31）；5.4节（13，23，29）；
第七周第一次作业：5.5节（7，21，47，59，63）；
第八周第一次作业：5.6节（3，33，43，49，67）；6.1节（11，13，29）；
第九周第一次作业：6.2节（5，27，33，47，51，63）；6.3节（21，33，47，49，59）；
第九周第二次作业：6.4节（15，23，37，45，47，53）；
第十周第一次作业：6.5节（9，23，45，47，67）；
第十周第二次作业：6.6节（3，27，31）；
第十一周第一次作业：6.7节（9，17，19，25，29）；6.8节（15，19，25，35，37）；
重要通知
通知：2023年10月19日星期四上习题课！
通知：2023年10月26日星期四课程暂停一次，后续课程顺延，不专门补课！
第一章（2023.9.4更新）
第一章.pdf
第二章（2023.9.6更新）第二章.pdf
第三章、第四章（2023.9.6更新）第三章、第四章.pdf
第五章（2023.9.6更新）第五章.pdf
第六章（2023.9.6更新）第六章.pdf
第七章（2023.9.6更新）第七章.pdf
复习纲要（2023.9.6更新）复习纲要.pdf
刘斌老师：flowice@ustc.edu.cn（邮箱）
科技实验楼西楼1711（办公室）
0551-63606597 （电话）
助教 邓杰：gutendzx@mail.ustc.edu.cn
助教 丰逸飞：eastwind@mail.ustc.edu.cn
助教 张芷苒：minerva_z@mail.ustc.edu.cn
信息论起源于两个重要的问题：如何压缩地表示信息以及如何在有噪声时可靠地传输信息。本课程的教学目的就是通过对通信系统中信息理论的介绍，使学生们更深入地了解信息的概念和本质，掌握熵、相对熵、互信息等重要概念。本课程以香农信息论为基础，着重介绍了信源编码、信道编码和率失真的理论基础。还介绍了信息论中的一些其他概念，如渐近均分性、熵率、微分熵等等。最后，课程引入信息论在解决信息安全领域一些问题中的应用，从而拓宽学生的相关知识面，为其之后的学术研究工作指引方向。
Information theory arises from two important problems: How to represent information compactly, and how to transmit information reliably in the presence of noise. The purpose of the course is to offer students a deeper understanding of the essence of information and some fundamental concepts such as entropy, relative entropy, and mutual information, by introducing information theories in the communication system. Based on the Shannon theory, the course mainly introduces the theories of source coding, channel coding and rate distortion. Other concepts, such as asymptotic equipartition property, entropy rate, and differential entropy, are also introduced. Finally, the course also introduces applications of information theory in dealing with problems in the field of information security. It is helpful to widen the students' eyes and can therefore guide their future research.
《信息论基础》（原书第2版）（美）Thomas M. Cover， Joy A. Thomas 著，阮吉寿 张华 译，机械工业出版社（pdf版本下载）
《信息论基础》（原书第2版）勘误（2023年3月1日更新）（pdf版本下载）
《Elements of Information Theory》（美）Thomas M. Cover， Joy A. Thomas 著，Wiley-InterScience（pdf版本下载）
《信息论与编码》 姜丹 著，中国科技大学出版社
概率论学习资料整理（pdf版本下载）
学时：40学时（1-10周），32学时上课，6学时习题课、复习和答疑，2学时考试
课后作业：每周二放至教室最后一排，等助教来收取，下周二前发回
评分标准：
期末考试：60分
课后作业：32分，共8次作业，每次满分4分
平时表现：8分
注意：抄作业，该次作业按0分计；迟交作业，该次作业满分2分
重要通知比如考试和习题课安排会及时放在主页上，请同学们多多关注！
第二周第一次作业：2.7(a)，2.10(a)，2.18，2.40
第二周第二次作业：2.12，2.23，2.35，2.39
第三周第一次作业：2.15，2.29，2.32，2.42
第三周第二次作业：3.4，3.5，3.9(a)，3.13(a,b)
(注意：3.13题，书上表中的数据有问题，请自己算)
第四周第一次作业：4.7(a)-(d)，4.9，4.18，4.22
第五周第一次作业：5.3，5.8，5.18，5.37
第五周第二次作业：5.4，5.16，5.25，5.32，6.1，6.8
(注意：5.25题，应该是p1>p2)
第六周第一次作业：7.2，7.4，7.7，7.12，7.26
第七周第一次作业：7.1，7.19，7.20，7.31，7.32
(注意：7.32题，可以直接用7.28题的结果)
第八周第一次作业：8.1，8.4
第八周第二次作业：8.3(a,b)，8.8，8.9
第九周第一次作业：9.2，9.3，9.5
(注意：9.2题，公式(9-173)中矩阵K有误，请参照《信息论基础》（原书第2版）勘误)
第九周第二次作业：9.6，9.7，9.14，9.15，9.21
第十周第一次作业：10.2，10.5，10.7
第十一周第一次作业：10.8，10.14，10.18
重要通知
通知：因临时需要出差，3月21日（星期四）的课程暂停一次，不另外补课，后续课程顺延。
通知：因临时需要出差，4月25日（星期四）的课程暂停一次，不另外补课，后续课程顺延。
通知：4月28日（星期日）上5月2日（星期四）的课，上午第1-2节课。
第一章、第二章（2024.3.4更新）第一章&第二章.pdf
第三章（2024.3.4更新）第三章.pdf
第四章（2024.3.4更新）第四章.pdf
第五章、第六章（2024.3.4更新）第五章&第六章.pdf
第七章（2024.3.4更新）第七章.pdf
第八章（2024.3.4更新）第八章.pdf
第九章（2024.3.4更新）第九章.pdf
第十章（2024.3.4更新）第十章.pdf
末章（2024.3.4更新）末章.pdf
复习纲要（2024.3.4更新）复习纲要.pdf
刘斌老师：flowice@ustc.edu.cn（邮箱）
西区科技实验楼西楼1711（办公室）
0551-63606597 （电话）
高新校区一号学科楼A532（办公室）
助教 高源：wazs98@mail.ustc.edu.cn
助教 郭俊荣：gjr13754822885@mail.ustc.edu.cn
助教 王卓丰：wzf0303@mail.ustc.edu.cn
