Department of Computer Science and Engineering



Yüklə 370,5 Kb.
səhifə8/16
tarix08.08.2018
ölçüsü370,5 Kb.
#61766
1   ...   4   5   6   7   8   9   10   11   ...   16


Module 1 (14 Hours)


Review of Linear Algebra. The postulates of quantum mechanics. Review of Theory of Finite Dimensional Hilbert Spaces and Tensor Products
Module 2 (14 Hours)

Complexity classes. Models for Quantum Computation. Qubits. Single and multiple qubit gates. Quantum circuits. Bell states. Single qubit operations. Controlled operations and measurement. Universal quantum gates. Quantum Complexity classes and relationship with classical complexity classes


Module 3 (14 Hours)

Quantum Algorithms – Quantum search algorithm - geometric visualization and performance. Quantum search as a

quantum simulation. Speeding up the solution of NP Complete problems. Quantum search as an

unstructured database. Grover’s and Shor’s Algorithms.


Module 4 (14 Hours)

Introduction to Quantum Coding Theory. Quantum error correction. The Shor code. Discretization of errors, Independent error models, Degenerate Codes. The quantum Hamming bound. Constructing quantum codes – Classical linear codes, Shannon entropy and Von Neuman Entropy.


References:

1. Nielsen, Michael A., and Isaac L. Chuang, Quantum Computation and Quantum Information. Cambridge, UK, Cambridge University Press, 2002.

2. Gruska, J. Quantum Computing, McGraw Hill, 1999.

3. Halmos, P. R. Finite Dimensional Vector Spaces, Van Nostrand, 1958.

4. Peres, Asher. Quantum Theory: Concepts and Methods. Springer, 1993.
CS4029 TOPICS IN THEORY OF COMPUTATION

Pre-requisite: CS3001 Theory of Computation




L

T

P

C

4

0

0

4

Total Hours: 56 Hrs  


Module 1 (14 Hours)


Recursion, The primitive recursive functions, Turing machines, Arithmetization, Coding functions , The normal form theorem, The basic equivalence and Church’s thesis, Canonical coding of finite sets, Computable and computably enumerable sets, Diagonalization, Computably enumerable sets , Undecidable sets , Uniformity, Many-one reducibility, The recursion theorem, Proof for Godel’s Incompleteness Theorem based on Recursion theorem.
Module 2 (14 Hours)

The arithmetical hierarchy, Computing levels in the arithmetical hierarchy , Relativized computation and Turing degrees, Turing reducibility , Limit computable sets, Incomparable degrees


Module 3 (14 Hours)

The priority method, Diagonalization, Turing incomparable sets , Undecidability , Constructivism, randomness and Kolmogorov complexity, Compressibility and randomness, Undecidability


Module 4 (14 Hours)

Scheme, programming and computability theory based on a term-rewriting, "substitution" model of computation by Scheme programs with side-effects; computation as algebraic manipulation: Scheme evaluation as algebraic manipulation and term rewriting theory.


References:

  1. R. I. Soare, Recursively enumerable sets and degrees, Springer-Verlag, 1987.

  2. G. E. Sacks, Higher recursion theory, Springer Verlag, 1990.

  3. M. Li and P. Vitányi, An introduction to Kolmogorov complexity and its applications, Springer-Verlag, 1993.

  4. Dexter C. Kozen, Automata and Computability, Springer-Verlag, 1997.

  5. S. C. Kleene, Introduction to Metamathematics, Van Nostrand, 1950.

  6. MIT OpenCourseWare on Computability Theory of and with Scheme at http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-844-computability-theory-of-and-with-scheme-spring-2003/ Accessed on 26/11/2010


CS4030 COMPUTATIONAL COMPLEXITY

Pre-requisite: Nil



L

T

P

C

4

0

0

4

Total Hours: 56 Hrs  


Module 1 (14 Hours)


Review of Complexity Classes, NP and NP Completeness, Space Complexity, Hierarchies, Circuit satisfiability, Savitch and Immerman theorems, Karp Lipton Theorem.
Module 2 (14 Hours)

Randomized Complexity classes, Adleman's theorem, Sipser Gacs theorem, Randomized Reductions, Counting Complexity, Permanent’s and Valiant’s Theorem


Module 3 (14 Hours)

Parallel complexity, P-completeness, Sup-liner space classes, Renegold's theorem, Polynomial hierarchy and Toda's theorem


Module 4 (14 Hours)

Arthur Merlin games, Graph Isomorphism problem, Goldwasser-Sipser theorem, Interactive Proofs, Shamir's theorem.


References:

  1. S. Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

  2. Papadimtriou C. H.., Computational Complexity, Addison Wesley, 1993.

  3. Motwani R, Randomized Algorithms, Cambridge University Press, 1995.

  4. Vazirani V., Approximation Algorithms, Springer, 2004.



CS4031 COMPUTATIONAL ALGEBRA

Pre-requisite: Nil




L

T

P

C

3

0

2

4

Total Hours: 70 Hrs  

Yüklə 370,5 Kb.

Dostları ilə paylaş:
1   ...   4   5   6   7   8   9   10   11   ...   16




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2024
rəhbərliyinə müraciət

    Ana səhifə