基本情况
- 主题:
计算理论,计算复杂性和生物信息学
Topic:
Theory of Computation, Computational Complexity and Computational Biology
- 时间:
2002年7月10日至18日
- 地点:
杭州莫干山
- 主办单位:
中国自然科学基金委员会,上海交通大学计算机科学与工程系
组织
报告人及内容
- 朱洪: 计算机算法的预备知识、概要
Abstract: Hong Zhu will
arrange a pre-requisite course for those students who do not have
such back ground, such as: Design and Analysis of Algorithms (big-O,
solve recursive equations, (nlogn) for sorting, O(n) for median,
network flow and graph matching algorithms).
- Osamu Watanabe (Tokyo Institute of Technology):
Computational Complexity
Abstract:
1. Overview of Complexity
Theory; Models of Computation; Turing Machines; Reductions,
NP-completeness; Time and Space Hierarchy Theorems.
2. Nondeterminstic space and deterministic space; Savitch's theorem;
Immerman-Szelepcsenyi theorem.
3. Randomized Complexity
Classes; Universal Hash Functions; Probabilistic Amplifications;
Sipser-Lautemann Theorem.
4. Sparse sets and P/poly; BPP in
P/poly; Karp-Lipton Theorem; Mahaney's Theorem;
5. Hartmanis
Conjectures; NC hierarchies; Cai-Sivakumar Theorem.
6. Interactive Proof Systems; Arthur-Merlin Games; LFKN
protocol.
7. IP=PSPACE.
8. Pseudorandom generators;
Goldreich-Levin hardcore bits.
9. Constant Depth Circuits;
Razborov-Smolensky Proof.
10. The Switching Lemmas of
Furst-Saxe-Sipser, Yao, Cai, and Hastad.
- Jiang Tao (University of California, Riverside):
Computational Biology
- Deng
Xiaotie (City University of Hong Kong): Computational Economics
and Finance
Abstract: pre-requisite and require students to full
comprehend before my course:
1. Linear programming (duality
theorem)
2. NP-completeness (proof techniques for 3SAT, set
cover, integer programming)
3. Design and Analysis of Algorithms
( big-O, solve recursive equations, (nlogn) for sorting, O(n) for
median, network flow and graph matching algorithms).
- Teng
Shao-hua (Boston University): Smoothed Analysis on Linear
Programming and Optimization
Abstract:
1. Introduction to
Smoothed Analysis (1 hour) a. Worse-case analysis b. Average-case
analysis c. Randomization d. Models of Smoothed analysis
2. Why the simplex method usually takes polynomial time (2 hours)
a. Introduction to Linear Programming b. The simplex method c. Pivot
Rules d. Shadow vertex-rule e. Geometric Characterization of optimal
solution g. Smoothed analysis
3. Smoothed Analysis of Growth
Factor and Gaussian Elimination (2 hours) a. Introduction to
Scientific Computing b. Gaussian elimination c. Precision and Growth
factor d. Partial-pivoting e. Smoothed Analysis f. Symmetric
Case
精彩剪辑:课上和活动