Introduction to Information Theory (67548)
Spring 2006

Hours and Location

Lecture: Mondays, 10:00 - 11:45, Shprintzak 115
Exercise: Mondays, 16:00 - 17:45, Shprintzak 28

Staff

Teacher:
Prof. Naftali Tishby
Reception hour: Sundays, 14:00-15:00, Ross 214

Teaching Assistant:
Talya Meltzer infot@cs.huji.ac.il
Reception hour: Mondays, 18:00-19:00, Ross 67

Syllabus

  1. Shannon's communication model - the fundamental problems: sources (compression) and channels (error correction).
  2. Measures of information: the uniqueness of Entropy and Mutual Information, chain rules, Jensen & data processing inequalities, Fano inequality.
  3. Asymptotic properties of Entropy, relative Entropy and Information, AEP, Entropy rate and Shannon-McMillen Theorem for stationary stochastic processes.
  4. Lossless data compression. Codes, Kraft inequality, optimal codes, Shannon's first theorem, Huffman codes and questioners.
  5. Universal compression, LZ code, Kolmogorov Complexity and algorithmic randomness.
  6. Joint typicality and AEP for mutual information, differential entropy.
  7. Maximum Entropy and Minimum Mutual Information as Inference methods.
  8. Channel Capacity (with and without cost constraint). BSC, the Gaussian channel and the C(E) function. Block coding and Simple examples of error correcting codes.
  9. Lossy compression: Rate Distortion Theory.
  10. Joint source-channel coding - and optimal cost-distortion tradeoff. MAYBE: Optimal single letter codes.
  11. Information Theory, Statistics and Learning.
  12. Open problems. Connections with other fields (control theory, economy & game-theory, etc.)

Requirements

You have to submit at least 75% of the exercises.
The exercises grade would be 25% of your final grade.

Course Administration