CmpE 59T Sp.Tp. Kolmogorov Complexity 2017 Fall

Instructor: 

Course Schedule: 

TTT 235 BM A5 | BM A5 | BM A5

Course Program: 

Topics (subject to change): Definitions of algorithmic complexity. The invariance theorem. Incompressibility. Resource-bounded complexity. Physics, information, and computation.

Textbook: 

Ming Li and Paul Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, 3rd ed. Springer, 2008.

Grading: 

Two midterms and a final exam of equal weight

Notes: 

Topics (Section headings from the book):

1 Preliminaries 

1.1 A Brief Introduction 

1.2 Prerequisites and Notation 

1.7 Basics of Computability Theory 

1.11 Information Theory and Coding 

2 Algorithmic Complexity 

2.1 The Invariance Theorem

2.2 Incompressibility

2.8 Algorithmic Information Theory 

3 Algorithmic Prefix Complexity 

3.1 The Invariance Theorem 

3.3 Incompressibility 

3.4 K as an Integer Function 

3.8 *Complexity of Complexity 

3.9 *Symmetry of Algorithmic Information

7 Resource-Bounded Complexity 

7.1 Mathematical Theory 

7.2 Language Compression

8 Physics, Information, and Computation

8.1 Information Theory 

8.3 Information Distance 

8.4 Normalized Information Distance 

8.5 Thermodynamics 

8.6 Entropy Revisited 

Contact us

Department of Computer Engineering, Boğaziçi University,
34342 Bebek, Istanbul, Turkey

  • Phone: +90 212 359 45 23/24
  • Fax: +90 212 2872461
 

Connect with us

We're on Social Networks. Follow us & get in touch.