2012秋季学期(Fall Semester, 2012)
公告(Announcement)
- The classroom of Section-02 has been changed to Shang Yuan 110 (2班教室改至上院110)
- Welcome to the class. Have fun! The important information will be announced here. Please check this webpage often.
基本信息(General Information)
- Level: Undergraduates (Freshmen)
- Time & Place:
- 8:00am – 9:40am, Monday (Class 05), Shang Yuan 206 (上院206)
- 2:00pm – 3:40pm, Monday (Class 02), Shang Yuan 110 (上院110)
- Instructor:
- Name: Xiaofeng Gao (高晓沨)
- Email: gao-xf(at)cs.sjtu.edu.cn
- Office: Telecom Building 3-543
- Phone: 021-34207407
- Teaching Assistant:
- Class-05 (Morning Class)
- Name: Fei Yang (杨非)
- Email: iamyf(at)sjtu.edu.cn
- Office: Telecom Building 3-329
- Phone: 021-34205060
- Office Hour: By appointment
- Class-02 (Afternoon Class)
- Name: Tao Chen (陈涛)
- Email: taotaochan(at)126.com
- Office: Telecom Building 3-328
- Phone: N/A
- Office Hour: By appointment
课堂时间(Course Schedule)
|
September 2012 |
|
October 2012 |
|
November 2012 |
||||||||||||||||||
week |
S |
M |
T |
W |
T |
F |
S |
week |
S |
M |
T |
W |
T |
F |
S |
week |
S |
M |
T |
W |
T |
F |
S |
|
|
|
|
|
|
|
1 |
(4) |
|
1 |
2 |
3 |
4 |
5 |
6 |
(8) |
|
|
|
|
1 |
2 |
3 |
|
2 |
3 |
4 |
5 |
6 |
7 |
8 |
(5) |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
(9) |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
(1) |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
(6) |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
(10) |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
(2) |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
(7) |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
(11) |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
(3) |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
(8) |
28 |
29 |
30 |
31 |
|
|
|
(12) |
25 |
26 |
27 |
28 |
29 |
30 |
|
(4) |
30 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
December 2012 |
|
January 2013 |
|
Total: 18 weeks, 16 classes |
||||||||||||||||||
week |
S |
M |
T |
W |
T |
F |
S |
week |
S |
M |
T |
W |
T |
F |
S |
|
|
|
|
|
|
|
|
(12) |
|
|
|
|
|
|
1 |
(17) |
|
|
1 |
2 |
3 |
4 |
5 |
|
|
|
Class Day |
||||
(13) |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
(18) |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
|
|
|
|
|
|
|
(14) |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
13 |
14 |
15 |
16 |
17 |
18 |
19 |
|
|
· |
Holiday (1st, Oct/Jan) |
||||
(15) |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
|
20 |
21 |
22 |
23 |
24 |
25 |
26 |
|
|
|
|||||
(16) |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
|
27 |
28 |
29 |
30 |
31 |
|
|
|
|
· |
Final Exam Week |
||||
(17) |
30 |
31 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
计划日程(Syllabus)
Week |
Date |
Lecture Topic |
Event |
第一部分、数理逻辑 (Part 1: Mathematical Logic) |
|||
1 |
Sep.10 |
School Opening |
|
2 |
Sep.17 |
离散数学简介与命题逻辑的基本概念（1） Basic Concepts of Propositional Logic (1) |
Lab-01 |
3 |
Sep.24 |
命题逻辑的基本概念（2） Basic Concepts of Propositional Logic (2) |
Lab-02 |
Sep.29 |
命题逻辑的等值与推理（1） Propositional Equivalences and Inference (1) |
Lab-03 |
|
4 |
Oct.01 |
National Holiday. |
|
5 |
Oct.08 |
命题逻辑的等值与推理（2） Propositional Equivalences and Inference (2) |
Lab-04 |
6 |
Oct.15 |
命题逻辑的等值与推理（3） Propositional Equivalences and Inference (3) |
Lab-05 |
7 |
Oct.22 |
谓词逻辑的基本概念（1） Basic Concepts of Predicate Logic (1) |
Lab-06 |
8 |
Oct.29 |
谓词逻辑的基本概念（2） Basic Concepts of Predicate Logic (2) |
Lab-07 |
9 |
Nov.05 |
谓词逻辑的等值和推理演算（1） Equivalences and Deductions in Predicate Logic (1) |
Lab-08 |
10 |
Nov.12 |
谓词逻辑的等值和推理演算（2） Equivalences and Deductions in Predicate Logic (2) |
Lab-09 |
第二部分、图论 (Part 2: Graph Theory) |
|||
11 |
Nov.19 |
图论基本概念 Basic Concepts |
Lab-10 |
12 |
Nov.26 |
道路与回路（1） Euler and Hamilton Paths (1) |
Lab-11 |
13 |
Dec.03 |
道路与回路（2） Euler and Hamilton Paths (2) |
Lab-12 |
14 |
Dec.10 |
树（1） Introductions to Trees (1) |
Lab-13 |
15 |
Dec.17 |
树（2） Introductions to Trees (2) |
Lab-14 |
16 |
Dec.24 |
复习与习题练习 Review. Exercises. Tutoring. |
Lab-15 |
17-18 |
TBD |
Final Exam |
Final |
作业与课后阅读(Assignments and Readings)
Lecture 1: 离散数学简介(Introduction to Discrete Mathematics)
- 阅读材料(Reading Materials)
- 计划日程与评分标准(Syllabus & Grading Policy): Syllabus-DiscreteMathematics.pdf
- 离散数学概述(Notes)： Slide01-Introduction.pdf
- 阅读命题逻辑的基本概念(From Textbooks)
- Lab01: Self-Introduction (Due: 10:00pm, 10/08/2012)
- Join google group: http://groups.google.com/group/MA115at206 (Class 05)
http://groups.google.com/group/MA115at208 (Class 02) - Complete self-introduction: http://www.sojump.com/jq/1828783.aspx
- Join google group: http://groups.google.com/group/MA115at206 (Class 05)
Lecture 2: 命题逻辑的基本概念(Basic Concepts of Propositional Logic)
- 阅读材料(Reading Materials)
- 命题逻辑的基本概念(Notes)： Slide02-PropositionalLogic.pdf
- 阅读命题逻辑的基本概念(From Textbooks)
- Lab02: 命题逻辑的基本概念(Due: 10/08/2012, Class05--9:45am; Class02--3:45pm)
- 习题: Lab02-PropositionalLogic.pdf
- Latex源码: Lab02-PropositionalLogic.tex （供Latex爱好者使用）
Lecture 3: 命题逻辑的等值和推理演算(Propositional Equivalences and Calculus)
- 阅读材料(Reading Materials)
- 命题逻辑的等值和推理演算(Notes)： Slide03-PropositionalEquivalence.pdf
- Lab03: 命题逻辑的等值和推理演算(Due: 10/08/2012, Class05--9:45am; Class02--3:45pm)
- 习题: Lab03-PropositionalEquivalence.pdf
- Latex源码: Lab03-PropositionalEquivalence.tex （供Latex爱好者使用）
Lecture 4: 对偶式、范式、推理形式(Dual Form, Normal Form, and Inference)
- 阅读材料(Reading Materials)
- 对偶式、范式、推理形式(Notes)： Slide04-NormalForm.pdf
- Lab04: 对偶式、范式、推理形式(Due: 10/15/2012, Class05--9:45am; Class02--3:45pm)
- 习题: Lab04-NormalForm.pdf
- Latex源码: Lab04-NormalForm.tex （供Latex爱好者使用）
Lecture 5: 推理演算与归结推理法(Deduction and Resolution)
- 阅读材料(Reading Materials)
- 推理演算与归结推理法(Notes)： Slide05-Deduction&Resolution.pdf
- Lab05: 推理演算与归结推理法(Due: 10/22/2012, Class05--9:45am; Class02--3:45pm)
- 习题: Lab05-Inference.pdf
- Latex源码: Lab05-Inference.tex （供Latex爱好者使用）
Review 1: 命题逻辑 (Propositional Logic)
- 概念一览(CheckList)
- 命题逻辑的基本概念、等值与演算：CheckList01-PropositionalLogic.pdf
- 题型训练(QuestionList)
- 命题逻辑部分习题训练: QuestionList01-PropositionalLogic.pdf
Lecture 6: 谓词逻辑的基本概念(Basic Concepts of Predicate Logic)
- 阅读材料(Reading Materials)
- 推理演算与归结推理法(Notes)： Slide06-PredicateLogic.pdf
- Lab06: 谓词逻辑的基本概念(Due: 10/29/2012, Class05--9:45am; Class02--3:45pm)
- 习题: Lab06-Predicate.pdf
- Latex源码: Lab06-Predicate.tex （供Latex爱好者使用）
Lecture 7: 判定问题和等值公式(Decision Problem and Equivalence)
- 阅读材料(Reading Materials)
- 谓词逻辑的等值和推理演算(Notes)： Slide07-EquivalenceWithQuantifiers.pdf
- Lab07: 谓词逻辑表示、判定与等值(Due: 11/05/2012, Class05--9:45am; Class02--3:45pm)
- 习题: Lab07-Decision.pdf
- Latex源码: Lab07-Quantifiers.tex （供Latex爱好者使用）
Lecture 8: 谓词逻辑的等值和推理演算(Equivalences and Calculus with Quantifiers)
- 阅读材料(Reading Materials)
- 谓词逻辑的范式与推理公式(Notes)： Slide08-NormalForm&Deduction.pdf
- Lab08: 谓词逻辑的范式与推理公式(Due: 11/12/2012, Class05--9:45am; Class02--3:45pm)
- 习题: Lab08-Deduction.pdf
- Latex源码: Lab08-Deduction.tex （供Latex爱好者使用）
Lecture 9: 谓词逻辑的归结推理法 (Resolution with Quantifiers)
- 阅读材料(Reading Materials)
- 谓词逻辑的归结推理法(Notes)： Slide09-ResolutionWithQuantifiers.pdf
- Lab09: 谓词逻辑的范式与推理公式(Due: 11/19/2012, Class05--9:45am; Class02--3:45pm)
- 习题: Lab09-Resolution.pdf
- Latex源码: Lab09-Resolution.tex （供Latex爱好者使用）
Review 2: 谓词逻辑 (Predicate Logic)
- 概念一览(CheckList)
- 谓词逻辑的基本概念、等值与演算：CheckList02-PredicateLogic.pdf
- 题型训练(QuestionList)
- 谓词逻辑部分习题训练: QuestionList02-PredicateLogic.pdf
Lecture 10: 图论的基本概念 (Basic Concepts for Graph Theory)
- 阅读材料(Reading Materials)
- 图论的基本概念(Notes)： Slide10-GraphTheory.pdf
- Lab10: 图论的基本概念(Due: 11/26/2012, Class05--9:45am; Class02--3:45pm)
- 习题: Lab10-GraphTheory.pdf
- Latex源码: Lab10-GraphTheory.tex, Fig-Isomorphic.eps （两个文件需一起编译）
Lecture 11: 道路与回路 (Path and Circuit)
- 阅读材料(Reading Materials)
- 道路与回路(Notes)： Slide11-Path&Circuit.pdf
- Lab11: 道路(Due: 12/03/2012, Class05--9:45am; Class02--3:45pm)
- 习题: Lab11-Path.pdf
- Latex源码: Lab11-Path.tex（供Latex爱好者使用）
Lecture 12: 欧拉路与哈密顿路 (Euler and Hamilton Path)
- 阅读材料(Reading Materials)
- 道路与回路(Notes)： Slide12-Euler&HamiltonPath.pdf
- Lab12: 道路与回路(Due: 12/10/2012, Class05--9:45am; Class02--3:45pm)
- 习题: Lab12-Path&Circuit.pdf
- 勘误1: Q1的G(S)应改为G-S。
- 勘误2: Q4的最后一句应是“证明G中存在包含任意q条互不相邻边的哈密顿回路”。
- Latex源码: Lab12-Path&Circuit.tex, Fig-Room.eps（供Latex爱好者使用）
Lecture 13: 树 (Tree)
- 阅读材料(Reading Materials)
- 树(Notes)： Slide13-Tree.pdf
- Lab13: 树 (Due: 12/17/2012, Class05--9:45am; Class02--3:45pm)
- 习题: Lab13-Tree.pdf
- Latex源码: Lab13-Tree.tex（供Latex爱好者使用）
Lecture 14: 生成树 (Spanning Tree)
- 阅读材料(Reading Materials)
- 生成树(Notes)： Slide14-SpanningTree.pdf
- Lab14: 树 (Due: 12/24/2012, Class05--9:45am; Class02--3:45pm)
- 习题: Lab14-SpanningTree.pdf
- Latex源码: Lab14-SpanningTree.tex，Fig-MST.eps （供Latex爱好者使用）
Lecture 15: 补充内容 (Supplementary Materials)
- 阅读材料(Reading Materials)
- 期末说明与补充内容(Notes)： Slide15-Supplement.pdf
Review 3: 图论 (Graph Theory)
- 概念一览(CheckList)
- 题型训练(QuestionList)
- 图论部分习题训练: QuestionList03-GraphTheory.pdf
Roster and Events
Roster for Class 02
Click rouster02.htmlRoster for Class 05
Check roster05.html
References
- 数理逻辑(Mathematical Logic)
- 《数理逻辑与集合论》（第二版）： MathematicalLogic-Scan.pdf, MathematicalLogic-Print.pdf
- 《数理逻辑与集合论》（精要与习题）： MathematicalLogic-Exercise.pdf
- 《数理逻辑》莫少揆等著： MathematicalLogic-MoShaokui.pdf
- 图论(Graph Theory)
- 《图论与代数结构》： GraphTheory.pdz, GraphTheory.pdf
- PDZ文件需超星阅读器： SSReader.exe
- 离散数学(Discrete Mathematics)
- 《离散数学及其应用》（第六版）： DiscreteMathematics.pdf