Sumários
Asymptotic Equipartition and Markovian Sources
30 outubro 2014, 17:30 • Mário Alexandre Teles de Figueiredo
Asymptotic equipartition and its implications and interpretations; typical sets and coding. Markovian discrete sources; entropy rate and conditional entropy rate, and their equality in the case of stationarity.
Introduction to Information Theory
28 outubro 2014, 17:30 • Mário Alexandre Teles de Figueiredo
Introduction to Shannon's Information Theory. The information axioms and entropy. Other information theoretic quantities and their relationship (conditional entropy, joint entropy, Kullback-Leibler divergence, and mutual information). Inequalities: information, data processing, and Fano's.
Complexity - probabilistic classes and relativization
23 outubro 2014, 17:30 • Paulo Alexandre Carreira Mateus
Bounded probabilistic polynomial time (BPP). BPP vs BQP. Derandomization and pseudo-random generators. Relativization of P and NP.
Complexity - bounded quantum polynomial time
21 outubro 2014, 17:30 • Paulo Alexandre Carreira Mateus
Quantum circuits. Universal quantum gates. Bounded quantum polynomial time. Quantum Turing machines with deterministic control (dcQTM). Equivalence between quantum circuits and dcQTM.
Complexity - Efficient universality
16 outubro 2014, 17:30 • Paulo Alexandre Carreira Mateus
Lectured by David Henriques. Existence of universal Turing machine with polynomial overhead.