Description
Definition of information (classical state, message source): unit of information (bit) and other units of information, measures (Shannon entropy), Graph theory, Conditional probability, Bayes theorem; Random and pseudorandom sequences: importance of randomness to security; Introduction to coding: types of codes, Humming codes, compression (lossy and lossless), Shannon?s Theorem; Communication channels: lossless channels, lossy channels, types of information noises, Error correction procedures; Basic definitions of information theory: algorithm, algebra, language, grammar; Computational complexity theory: classes of problems, polynomial problems (P), non-deterministic polynomial problems (NP), NP-complete problems, Context of asymmetrical cryptography; Computational models: state machines (Turing machine, DFA, NFA), Church-Turing Thesis; Boolean algebra and classical logical circuits theory: logical gates, universality, non-reversibility of binary information in Boolean algebra, implementations of algorithms; Probabilistic computational model: NBP problem class, extended Church-Turing Theorem; Quantum computational model: NQP problem class, Quantum circuits theory, Fundamental weakness of asymmetrical cryptography (Fourier transform, Shor?s algorithm for factorization, Quantum Fourier transform by Kitaev, discrete logarithm problem, modulo algebra problem, hidden subgroup)