Sumários
Asymptotic Equipartition and Markovian Sources
5 novembro 2015, 14:00 • 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
3 novembro 2015, 14:00 • 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
22 outubro 2015, 14:00 • 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
20 outubro 2015, 14:00 • 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
15 outubro 2015, 14:00 • Paulo Alexandre Carreira Mateus
Existence of universal Turing machine with polynomial overhead.