Lecture 16: Data Compression and Shannon’s Noiseless Coding Theorem // TRAIN BRAIN

Lecture 16: Data Compression and Shannon’s Noiseless Coding Theorem

MIT 18.200 Principles of Discrete Applied Mathematics, Spring 2024
Instructor: Ankur Moitra
View the complete course: https://ocw.mit.edu/courses/18-200-principles-of-discrete-applied-mathematics-spring-2024
YouTube Playlist: https://www.youtube.com/playlist?list=PLUl4u3cNGP61p2fXeXjNCrfNHFwyW-bl0
We start with the history of data compression. We define a first-order source, and what it means to compress it. We define entropy. We then state and prove Shannon’s noiseless coding theorem, which gives the optimal compression ratio a first-order source.
License: Creative Commons BY-NC-SA
More information at https://ocw.mit.edu/terms
More courses at https://ocw.mit.edu
Support OCW at http://ow.ly/a1If50zVRlQ
We encourage constructive comments and discussion on OCW’s YouTube and other social media channels. Personal attacks, hate speech, trolling, and inappropriate comments are not allowed and may be removed. More details at https://ocw.mit.edu/comments.

MIT OpenCourseWare

A free and open online publication of educational material from thousands of MIT courses, covering the entire MIT curriculum, ranging from introductory to the most advanced graduate courses. On the OCW website, each course includes a syllabus, instruction...

S7SE Special Episode: Collaborating with Community Colleges

MIT Economist Jon Gruber responds to YouTube comments

3: Deep Learning for Computer Vision – Building Convolutional Neural Networks from Scratch

10: Generative AI – Adapting LLMs with Parameter-Efficient Fine-Tuning

8: Deep Learning for Natural Language – Transformers, Self-Supervised Learning

9: Generative AI – Large Language Models (LLMs) and Retrieval Augmented Generation (RAG)

5: Deep Learning for Natural Language – The Basics

2: Training Deep NNs (cont.); Introduction to Keras/Tensorflow; Application to Tabular Data

4: Deep Learning for Computer Vision – Transfer Learning and Fine-Tuning; Intro to HuggingFace

6: Deep Learning for Natural Language – Embeddings

7: Deep Learning for Natural Language – Transformers

11: Generative AI – Text-to-Image Models

1: Introduction to Neural Networks and Deep Learning; Training Deep NNs

Lecture 16: Data Compression and Shannon’s Noiseless Coding Theorem

Lecture 7: Generating Functions for Catalan Numbers

Lecture 3: Inclusion-Exclusion

Lecture 17: Huffman Coding

Lecture 11: Basic Group Theory

Lecture 20: Reed-Solomon Codes

Lecture 9: Chernoff Bounds

Lecture 13: Duality in Linear Programming

Lecture 18: Transmitting Information Reliably over a Noisy Channel & Shannon’s Noisy Coding Theorem

Lecture 14: Zero-Sum Games

Lecture 15: Max-Flow Min-Cut Theorem

Lecture 2: Independence and Conditioning

Lecture 5: More Counting and Generating Functions

Lecture 6: More on Generating Functions

Lecture 8: Tail Bounds

“Learning for Life: How Curiosity Shapes Well-Being” with Bia Adams

Lecture 20: Building the First Federally (CFTC) Regulated Exchange Dedicated to Trading on Events

Lecture 1, Part III: Bond “Mathematics”

Lecture 13: Portfolio Management

Lecture 14: Stochastic Processes II

Lecture 4: Linear Algebra (cont.); Probability Theory

Lecture 23: Introduction to Machine Learning

Lecture 1, Part I: Introduction of the Class

Lecture 1, Part II: Introduction of Financial Markets, Financial Terms and Concepts

Lecture 21: Black-Scholes Formula, Risk Neutral Valuation

Lecture 2: Linear Algebra

Lecture 8: Regression Analysis (cont.)

Lecture 24: Stochastic Calculus

Lecture 9: Principal Component Analysis in Finance

Lecture 7: Linear Rates, Products, and Models

Lecture 10: Counterparty Risk Optimization

How to Sell Concert Tickets, with MIT Economist Jon Gruber

Can AI fix the economy?

Lecture 11: Contagious Structure in Projection Theory

Lecture 02: Fundamental Methods of Projection Theory

Lecture 13: The Balog-Szemeredi-Gowers Theorem

Lecture 04: The Fourier Method in Euclidean Space

Lecture 09: Reflections on the Szemeredi-Trotter Theorem

Lecture 22: Sharp Projection Theorems, Part 1: Introduction and Beck's Theorem.

Lecture 01: Introduction to Projection Theory

Lecture 23: Sharp Projection Theorems, Part 2: AD Regular Case

Lecture 15: The Bourgain Projection Theorem, Part 2

Lecture 03: Projection Theory in Euclidean Space

Lecture 05: The Large Sieve

Lecture 07: Applications of the Large Sieve to Number Theory

Lecture 20: Homogeneous Dynamics, Part 1

Lecture 10: Sum-Product Theory

Lecture 19: Random Walks on Finite Groups, Part 3

Student Project 2: Ink and Thread: Incorporating Chinese Calligraphy in Fashion

Session 4-1: Networked Geothermal: The European Experience

Session 8-3: Thermal Energy Network Evolution of the Penn South Community in Manhattan

Session 1-3: Health Impacts of Methane ("Natural") Gas Systems

Session 7-3: Techno-Economic Modeling of GENs with HEATNETS Model

Session 5-3: Introduction to Design of GENs

Session 8-2: Framingham, Massachusetts UTEN Pilot Project Overview

Session 6-2: Emerging Code & Standards for Ambient Temperature Loops

Session 5-2: Differences Between Geothermal Heat Pumps and GEN

Session 3-4: Geothermal Energy Networks: Transforming Our Thermal

Session 4-2: Deploying Geothermal Networks At City and Country Scale: Utility Perspective on Scaling

Session 1-2: Carbon Reduction Pathways for Building Stocks

Session 8-1: ATL District Systems Overview

8-4: Intro to the MIT Thermal Energy Networks Plan for Rapid, Cost-Effective Campus Decarbonization

Session 2-1: An Ecological View of the Energy Transition

Session Introduction: Geothermal Energy Networks: Transforming Our Thermal Energy System

Class 15 Video: Encoding Corpora and Voice Leading

Video 7b: Streams as Hierarchies: Types of Containers in music21

Video 6b: Representations of Ontologies: Craig Sapp’s Rosetta Stone