|
Instructor
Dr. Elise De Doncker
Department of Computer Science
College of Engineering and Applied Sciences
B-240 Parkview Campus
Kalamazoo, MI-49008
Phone: (269) 276-3102 (office), 276-3101 (Dept. office) 276-3122 (fax)
e-mail: elise[dot]dedoncker[at]wmich.edu
Office hours
MW 13:15 - 14:00,
or by appointment
Texts
(best to get the most recent version)
Required:
Quantum Computing for Computer Scientists, Noson S. Yanofsky and Mirco A. Manucci, Cambridge University Press 2008 (ISBN: 978-0-521-87996-5) or ebook,
Amazon link
Programming Quantum Computers, Eric R. Johnston, Nic Harrigan and Mercedes Gimeno-Segovia, O'Reilly Media, Inc.,
ISBN: 9781492039686,
O'Reilly
Recommended:
Automata, Computability, and Complexity: Theory and Applications, Elaine A. Rich, Pearson Prentice Hall 2008 (ISBN: 0-13-228806-0; ISBN: 978-0-13-228806-4)
Languages and Machines, Thomas A. Sudkamp, 3rd edition, Addison Wesley
Introduction to Automata Theory, Languages and Computation,
John E. Hopcroft,
Rajeev Motwani and Jeffrey D. Ullman, 2nd edition, Addison Wesley 2001 (ISBN: 0-201-44124-1); former edition by John E. Hopcroft and Jeffrey D. Ullman
(ISBN: 0-201-02988-X)
Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak, Cambridge University Press 2009 (ISBN: 978-0-521-42426-4)
2006 (ISBN: 0-321-32221-5)
Catalog description
Definition of grammars and languages, recursive and recursively enumerable sets, decidability, and the Chomsky hierarchy of languages and their relation to models of automata.
The course will include topics from
Main topic this semester: Quantum computing, theory and systems;
Stochastic machines, quantum automata (security revisited);
Review of languages, grammars and machines, Chomsky hierarchy, decidability;
The theory of recursive and partial recursive functions;
Models of computation such as Turing machines, Markov algorithms,
Post systems, recursive functions, lambda-calculus;
Markov models, Hidden Markov Models (HMM);
Computability: what problems can be solved? Problem as a 'property'/membership in
a language ('computable' sets), Universal language (Lu), diagonalization language (Ld), 'properties' of r.e. languages, non-re languages, Rice's theorems;
Computational complexity, relations among complexity measures, DTIME, NTIME, DSPACE, NSPACE, hierarchy theorems;
Intractable problems, Polynomial time and space, NP-complete, PSPACE-complete, complements of complexity classes;
Topics in formal languages: properties of FSA and regular languages, FSA with output, Myhill-Nerode theorem, DCFL, normal forms of CFG, ambiguity of CFG, closure properties of (full) trios,
LL(k) grammars, LR(k) grammars;
Self-modifying machines, cellular automata models (Wolfram), viruses, computer security;
Applications of automata theory in coding, secure communication protocols, cryptography;
Alternative (natural) models of computation: neural networks, genetic algorithms, swarm technologies.
Evaluation
Tests,
Assignments, project, presentations and miscellaneous,
using the following grading scale:
A: 92.0 - 100.0,
BA: 88.0 - 91.9,
B: 82.0 - 87.9,
CB: 78.0 - 81.9,
C: 72.0 - 77.9,
DC: 68.0 - 71.9,
D: 60.0 - 67.9,
E: below 60.0.
Problems with attendance may lead to a failing grade.
Academic Integrity Policies
You are responsible for making yourself aware of and for understanding the
policies and procedures in the Undergraduate Catalog that
pertain to Academic Integrity. These policies include cheating, fabrication,
falsification and forgery, multiple submission, plagiarism, complicity
and computer misuse. If there is reason to believe you have been involve in academic dishonesty, you will be referred to the Office of Student
Judicial Affairs. You will be given the opportunity to review the charge(s).
If you believe you are not responsible, you will have the opportunity
for a hearing. You should consult with me if you are uncertain about an
issue of academic honesty prior to the submission of an assignment or
test.
Additional instructor's notes: The above policy includes cheating by submitting tests, programming assignments or projects where the work (even in part) has been downloaded from the internet; this also applies to text in assignments and project reports. Cooperation among students on submitted work is not allowed. If you are caught there will be consequences.
Useful links
https://en.wikipedia.org/wiki/IBM_Quantum_Experience IBM Quantum Experience
https://www.ibm.com/topics/quantum-computing IBM Quantum
http://www.cs.utexas.edu/~ear/cs341/automatabook/ Homepage of the book by Elaine Rich
http://www.cs.princeton.edu/theory/complexity/ Draft of the book by Arora and Barak
http://www.stanford.edu/~ullman/ialc.html Homepage of the book by Hopcroft, Motwani and Ullman
http://infomesh.net/2001/swintro/ Introduction to the Semantic Web
|