Information Theory (F02: Foundations of CS);
情報理論 (F02: Foundations of CS)
2011-12 年（2年後期）

Syllabus; 授業概説
この授業では、 符号理論・通信理論の基礎である、情報量、情報源、符号化、通信、誤り訂正符号、標本化理論、量子化理論、暗号理論を習得する。
Lecturer; 講義担当教員
Lecturer Lab,
Room		 Phone
Extension		 E-mail
Michael Cohen 公園 マイケル 教授 Computer Arts Lab.
327-A		 x3108
(37-2537)		 mcohen

TAs
Shiratori Shun; 白鳥 峻, Saze Shougo; 佐瀬 翔吾, Prabath Weerasinghe; プラバス ウィ―ラシンハ
Office hours
by appointment
Class meeting
Mondays, IInd period; Large Lecture Theater
Class schedule (school calendar, timetable)
Week date Lecture; 内容 chapter keywords video demonstration
1 10/3 確率論の基礎;
Foundations of Probability Theory		 1a sets (and set operations) and probability; communications model; random variables; mean and variance; conditional probability Mathematica
10/10national holiday; Sports Day
2 10/17 1b probability, combinatorics
3 10/24 1c Chebyshev Inequality; Law of Large Numbers "The Law of Large Numbers" (Video Math Festival)
4 10/31 情報源符号化; Source Coding
いろいろな情報源符号;
Various Information Codings		 2a comma, variable-length, instantaneous, and singular codes
coding trees; extensions; Kraft Inequality; code space
5 11/7 midterm exam I (open book, open notes; dictionary and calculator OK)
6 11/14 いろいろな情報源符号;
Various Information Codings		 2b McMillan Inequality; unique decodability; mean length Eames' "Powers of Ten" Towers of Hanoi
7 11/21 情報量とエントロピー;
Information and Entropy		 3a Huffman coding "Homage to Hilbert" (SIGGRAPH Issue 125, #2)
8 11/28 midterm exam II (closed book, closed notes; English dictionary okay, as is a calculator [but you shouldn't need one])
9 12/5 3b compact codes; Markov processes; run-length encoding; ZL coding; arithmetic coding; Gray codes Gray Code counter
10 12/12 エントロピー;
Entropy		 4a logarithms; Kolmogorov complexity; entropy of equiprobable distributions; "The Search for Infinity Teaser" (Arthur C. Clarke's Mandelbrot Set; SIGGRAPH Issue 138, #33)
11 12/19 4b entropy for general distributions
12/23-1/3winter vacation
12 Tuesday, 1/10 4c joint distributions; conditional and relative entropy; chain rule; mutual information
13 1/16 通信路符号化の限界;
Channel Coding		 5, 6a binary symmetric channels, noisy channels; noisy but non-overlapping channels; Hamming distance XOR built from NAND gates (Select Circuits > Combinational Logic > Exclusive OR); Magic Cards; ISBN digit prediction
14 1/23 符号理論;
Limits of Coding Theory符号理論;
Code Spaces		 6b noisy but non-overlapping channels; Hamming distance; modulo operations; parity checks and codes; checksums; triangular and rectangular codes
15 1/31 Final Exam: IInd period, Large Lecture Theater. Coverage: Chapters 1-6.12 plus extra material (open book, open notes, calculator and EJ dictionary OK)

Assignments
assignments
references
reference links
administration
maintained by Michael Cohen