MIT Electrical Engineering and Computer Science Spring 2003 Catalogue Supplement

6.291 Systems, Information and Computer Science: The View from Above (G)

L TR2:30-4, Room 36-153
Profs. Sanjoy Mitter with assistance from Profs. Madhu Sudan, David Karger and John Tsitsiklis
Prereq.: 6.001, 6.041, 6.042J (or the equivalents), knowledge of linear algebra and calculus (18.014)
3-0-9

Recent developments in scientific and technological problems in the fields of Information and Communication, Systems and Control, Computer Science and AI clearly demonstrate that a more unified and conceptual view of the foundations of these fields is required. This course attempts to give such a conceptual, high-level view. It is, however, not meant to be a survey course. It uses the language of mathematics in a rigorous way to illuminate and sharpen concepts in the same way that the laws of Physics are embodied in Mathematics. The need for rigor is however quite essential here since the analogue of laws in Physics is usually not available.

COURSE OUTLINE

Prologue: The Physical World and the Perceptual World and their linkages. Perception and Action. The role of Information Transmission and Processing, Computation and Control in the study of Interconnected Systems, natural and technological. The need for a Synthesis. The Problématique of AI. Deep Blue vs. Speech and Vision. Languages, formal and natural.

A. Models 1. Signals Deterministic and Probabilistic Models. Continuous and Discrete Models of signals depending on time and space-time. Fourier Transforms and the Sampling Theorem. Discrete Fourier Transform on groups. Computation of the Discrete Fourier Transform.

2. Models to Data Quantization. Why Digital? Shannon's Source Coding Theorem. Huffman Coding. Lempel-Ziv Algorithm for Data Compression. Learning from Data.

3. Models of Dynamical Systems. Systems as Behaviors and the Notion of Controllability. Linear Dynamical Systems and Codes. The Concept of State. Input-Output State Representations. Stability. Languages as Behaviors. Operations on Languages. The Chomsky Hierarchy. Finite State Automata and Regular Languages. Nerode & Myhill Equivalence, Semi-group of a Machine. Discrete-Continuous Models

B. Inference From Noisy Data Graphical Models and Hidden Markov Models. Inference for Graphical Models. Recursive Inference and the Kalman Filter. Construction of Models from Data and the Minimium Description Length Principle. Applications to Speech Recognition and Image Analysis.

C. Principles of Control The Idea of Control through Interconnection of Dynamical Systems. Feedback and Reduction of Complexity. Robustness against Uncertainty.

D. Principles of Communication Mutual Information, Capacity and the Noisy Channel Coding Theorem. Turbo Coding, Decoding. Communication over a Network.

E. Principles of Computer Science 1. Digital computation. Universal computers. Its power and its problems 2. Computational problems vs. algorithms vs. instances. Comparing algorithms: worst-case complexity, big-Oh notation. Efficient computations: P, EXP, NP and PSPACE. 3. Challenges to Church Turing thesis: Randomness. Quantum effects. 4. The Computational Lens: Information vs. Knowledge Randomness vs. Pseudorandomness Theorems vs. Proofs

F. Optimization, Algorithms and Design Linear Programming and Duality; Economic Interpretations. Simplex Algorithm. Integer Programming & Relaxation. Nonlinear Programming and the Kuhn-Tucker Theorem. Min-Max Theorem; Cooperative and Non-cooperative Games and Nash Equilibrium. Adam Smith's Invisible hand. Basic Algorithmic Techniques for Devising Efficient Algorithms: amortization, divide and conquer, random sampling, randomized incremental constructions.

G. Decision Making under Uncertainty Dynamic Programming. Stochastic Control and Markov Decision Processes. Reinforcement Learning and Neuro-Dynamic Programming.

H. Algorithmic Complexity Hard computation problems: Undecidability, Time and Space Hierarchy. Comparing efficiency: Search problems vs. decision problem: Reductions between problems. NP and NP-completeness.

Epilogue: Do Systems, Information and Computer Science have a role to play in Systems Biology?

Prerequisites: 6.001, 6.003, 6.041, 6.042J (or their equivalents); good knowledge of Linear Algebra and Calculus (18.014).

Grading: Homework assignments: given out once every two weeks. Take-home final examination.