1 Mathematical Preliminaries

Chapter 1 Recurrent Problems
1.1 The Tower of Hanoi Let‟s look first at a neat little puzzle called the Tower of Hanoi. We are given a tower of eight disks, initially stacked in decreasing size on one of three pegs:
Preface
• 具体数学(Concrete Mathematics)，从字面上它和传统 的“抽象数学”对立。名字其实是连续(CONtinuous)和离 散(disCRETE)的融合。不过名字不重要，内容主要是说在 计算机科学领域内遇到的问题和传统数学常常不太合拍， 传统数学的方法和理念往往不容易用来解决计算机问题。 具体数学主要致力如何解决计算机科学中的问题，为计算 机算法奠定一个数学基础，或者说给出一些可用的数学手 段／方法。具体数学最早是上个世纪70年代，由Donald E. Knuth在斯坦福开设的一门课，这本书可以说是这门课的 讲义之延伸。 书写的很有意思，第一章讲recurrence，用了几个经 典问题，写的还是挺吸引人的。最后那个约瑟夫环问题， 我看了后，的确是佩服的很。一般来说这个问题的程序的 写法是模拟求解，复杂度是O(n*n)，我自己推导过一个递 推的方法，可以把复杂度降到O(n)，而这本书里直接给出 了这个问题的解公式，强悍。
Chapter 1 Recurrent Problems
• The recurrence only gives indirect, local information. • A solution to the recurrence would make us much happier. With a closed form, we can understand what Tn really is. • So how do we solve a recurrence? 1. One way is to guess the correct solution, then to prove that our guess is correct.

答 疑 与 交 流
通过网络
− − − 清华网络学堂（师生讨论版） 电子邮件
金明 软件学院
面对面
时间预约 第 2 – 8 周上班时间（节假日除外） 地点
School of Software 8
电子信箱 jinm09@
2010-09-18 School of Software
课 程 性 质
Computer Software Basic Course
− − 上世纪 60 年代末、70年代初，研究的高峰 之后，向应用领域渗透，研究生课程
A study of abstract models of computers and computation.
− Why theory, when computer field is so practical? −Theory provides concepts and principles, for both hardware and software that help us understand the general nature of the field.
2010-09-18 School of Software 21
John E. Hopcroft is the IBM Professor of Engineering and Applied Mathematics in Computer Science at Cornell University. From January 1994 until June 2001, he was the Joseph Silbert Dean of Engineering. After receiving both his M.S. (1962) and Ph.D. (1964) in electrical engineering from Stanford University. He served as chairman of the Department of Computer . Hopcroft’s research centers on theoretical aspects of computing, especially analysis of algorithms, automata theory, and graph algorithms. He has coauthored four books on formal languages and algorithms with Jeffrey D. Ullman and Alfred V. Aho. His most recent work is on the study of information capture and access. He was honored with the A. M. Turing Award in 1986. He is a member of the National Academy of Sciences (NAS), the National Academy of Engineering (NAE) and a fellow of the American Academy of Arts and Sciences (AAAS), the American Association for the Advancement of Science, the Institute of Electrical and Electronics Engineers (IEEE), and the Association of Computing Machinery (ACM). In 1992, he was appointed by President Bush to the National Science Board (NSB), which oversees the National Science Foundation (NSF), and served through May 1998.

抽象代数⼀、课程⽬的与教学基本要求本课程是在学⽣已学习⼤学⼀年级“⼏何与代数”必修课的基础上，进⼀步学习群、环、域三个基本的抽象的代数结构。

要求学⽣牢固掌握关于这三种抽象的代数结构的基本事实、结果、例⼦。

对这三种代数结构在别的相关学科，如数论、物理学等的应⽤有⼀般了解。

⼆、课程内容第1章准备知识（Things Familiar and Less Familiar）10课时复习集合论、集合间映射及数学归纳法知识，通过学习集合间映射为继续学习群论打基础。

1、⼏个注记(A Few Preliminary Remarks)2、集论(Set Theory)3、映射(Mappings)4、A（S）(The Set of 1-1 Mappings of S onto Itself)5、整数(The Integers)6、数学归纳法(Mathematical Induction)7、复数(Complex Numbers)第2章群(Groups) 22课时建⽴关于群、⼦群、商群及直积的基本概念及基本性质；通过实例帮助建⽴抽象概念，掌握群同态定理及其应⽤；了解有限阿贝尔群的结构。

1、群的定义和例⼦(Definitions and Examples of Groups)2、⼀些简单注记(Some Simple Remarks)3、⼦群(Subgroups)4、拉格朗⽇定理(Lagrange’s Theorem)5、同态与正规⼦群(Homomorphisms and Normal Subgroups)6、商群(Factor Groups)7、同态定理(The Homomorphism Theorems)8、柯西定理(Cauchy’s Theorem)9、直积(Direct Products)10、有限阿贝尔群(Finite Abelian Groups) （选讲）11、共轭与西罗定理(Conjugacy and Sylow’s Theorem)(选讲)第3章对称群(The Symmetric Group) 8课时掌握对称群的结构定理，了解单群的概念及例⼦。

第一章
6
關於集合(set)
complementation: The complement of a set S consists of all elements not in S. S Universal set U: 代表所有可能的元素。
S {x : x U , x S}
空集合Φ或,empty set 或 null set：就是不 包含任何元素的集合。 S = S - = S, S=
第一章 8
關於集合(set)
有限集合 finite sets，元素個數為有限者； 其他的為 infinite sets 無限集合。 集合 S 的元素個數記成 |S|。 冪集合 powerset: 所有子集合所形成的集 合稱為冪集合。令 2S 為 S 的 powerset， 其元素個數為 2|S| 。 S = {a, b, c} 2S = {, {a}, {b}, {c}, {a,b}, {b, c}, {c, a}, {a, b, c} }.
自動機 (Automata)
Time:
1:10~2:00 Monday: homework practice, quiz 2:10~4:00 Wednesday: lecture

Textbook: (new!)

An Introduction to Formal Languages and Automata, 3rd Edition, Peter Linz

15% for 上課筆記
No lecture slides 上課要抄筆記，學期間會抽查三次算分數

第一章 2
1 Introduction to the theory of computation