Curriculum M1 MPRI at ENS Paris-Saclay

AFIT: Algorithms for Formal Calculus and Information Theory

Description: The aim of this advanced algorithms course is to teach efficient algorithms related to effective algebra and information theory. More specifically, we will study operations on polynomials and large integers, error-correcting codes, and data compression.

See real-time course progression for up-to-date information, including examination modalities.

Outline:

  1. Introduction to computer algebra, efficient operations on polynomials (rings with and without roots of unity), power series, and large integers (product, inverse, division)
  2. Robust information coding: principles, linear codes, perfect codes, cyclic codes, BCH codes
  3. Data compression: information theory (entropy, mutual information, relative entropy, McMillan's theorem), static coding (Shannon-Fano,Huffman, Shannon-Fano-Elias, arithmetic coding), adaptive coding (adaptive Huffman, Lempel-Ziv), optimality studies


References:

  • Polynomial Algorithms in Computer Algebra. Franz Winkler
  • Algebraic Codes for Data Transmission. Richard E. Blahut
  • Introduction to Data Compression. Khalid Sayood
  • Web site of instructors ...