Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Introduction to Information Transmission and Processing - NTIX100

Title:	Základy přenosu a zpracování informace
Guaranteed by:	Student Affairs Department (32-STUD)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2022
Semester:	summer
E-Credits:	5
Hours per week, examination:	summer s.:2/1, C+Ex [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	cancelled
Language:	Czech
Teaching methods:	full-time
Teaching methods:	full-time
Is provided by:	NTIN100

Guarantor:	prof. Mgr. Michal Koucký, Ph.D.
Pre-requisite :	{NXXX036, NXXX037}
Incompatibility :	NTIN100
Interchangeability :	NTIN100

Opinion survey results Examination dates Schedule Noticeboard

Annotation -

Last update: IUUK (27.04.2015)

The course covers the fundamental concepts of information theory, error-correcting codes and communication complexity.

Course completion requirements -

Last update: prof. Mgr. Michal Koucký, Ph.D. (10.06.2019)

The credit from tutorials is given based on the number of points obtained from the homework assignments. To get the credit one has to get at least 70% of the total number of points

from the assignments.

There are no make-up homeworks.

The exam is oral.

Literature -

Last update: IUUK (27.01.2015)

· T.M. Cover, J.A. Thomas, Elements of Information Theory. John Wiley & Sons, 2nd edition, 2006.

· F.J. MacWilliams, N.J.A. Sloane, The theory of error correcting codes. North-Holland, Amsterdam, 1981.

· E. Kushilevitz, N. Nisan, Communication Complexity. Cambridge University Press, 1997.

· J.H. van Lint, Introduction to coding theory. Springer, 3rd edition, 1998.

Requirements to the exam -

Last update: prof. Mgr. Michal Koucký, Ph.D. (10.06.2019)

The exam is oral from the material covered by the lectures. Each student gets reasonable time (at most three hours) for preparation upon receiving the questions.

Study materials (lecture notes, text books, etc.), computers and other electronic devices are not allowed during the exam.

Syllabus -

Last update: IUUK (27.04.2015)

Information Theory

· Information, entropy, mutual information

· Relative information and its properties

· Data compression - Shannon-Fano code, Huffman code

· Kolmogorov complexity, Kolmogorov information, symmetry of Kolmogorov information

Error-Correcting Codes

· Data transmission over a noisy channel, channel capacity, Shannon's theorems

· Non-explicit codes

· Hamming codes

· Reed-Solomon codes, Berlekamp-Welch algorithm

Communication Complexity

· Model of communication complexity

· Deterministic complexity, combinatorial rectangles, examples

· Probabilistic protocols, public and private random bits

· Non-deterministic protocols

· Application: analysis of data structures