Difference between revisions of "User:Jeffj/CS6723/Syllabus"
From A-State Computer Science Wiki
< User:Jeffj | CS6723
Line 44: | Line 44: | ||
=== Textbook === | === Textbook === | ||
:{{Template:Textbook | :{{Template:Textbook | ||
+ | |title=Introduction to the Theory of Computation | ||
+ | |edition=3rd | ||
+ | |author=Michael Sipser | ||
+ | |ISBN=978-1133187790 | ||
+ | |publisher=Course Technology | ||
+ | |year=2012 | ||
+ | |Amazon=http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X | ||
+ | }} | ||
+ | <!-- | ||
+ | {{Template:Textbook | ||
|title={{link|marquee=An Introduction to Formal Languages and Automata|protocol=https://|address=www.jblearning.com/catalog/productdetails/9781284077247}} | |title={{link|marquee=An Introduction to Formal Languages and Automata|protocol=https://|address=www.jblearning.com/catalog/productdetails/9781284077247}} | ||
|edition=6th | |edition=6th | ||
Line 52: | Line 62: | ||
|Amazon=https://www.amazon.com/Introduction-Formal-Languages-Automata/dp/1284077241 | |Amazon=https://www.amazon.com/Introduction-Formal-Languages-Automata/dp/1284077241 | ||
}} | }} | ||
+ | --> | ||
=== Resources === | === Resources === |
Revision as of 09:19, 30 May 2020
CS 6723 Computability
Summer 2019, Section 001, MTWRF 8:10am-10:00am, CSM 211 (3 credits)
Instructor
Dr. Jeff Jenness | |||
Office | CSM 132 | Office Hours | TR 11:00am-12:00pm and MW 11:00pm-12:00pm |
Phone | 870-972-3978 ext. 8117 | jeffj@astate.edu |
Course Description
- CS 6723. Computability Theory
- Turing machines and equivalent models of computation. The universal Turing machine and unsolvability results. Study of computable functions. Problem classification and hierarchy. Prerequisites: CS 5723 or permission of professor. Spring even.
Program Specific Outcomes
- (Reinforced) M.S. Computer Science graduate students should have a deeper understanding of the theory and application of algorithms, programming languages, and computer processes.
Course Outcomes
- Understand Turing machine model, and variants of Turing machines and Church-Turing Thesis.
- Understand and could apply important concepts of computability theory and complexity theory.
- Understand the limits of algorithmic solvability (computability): what is solvable and what is not solvable.
- Understand the issues of complexity: even when a problem is computationally solvable in principle.
Grading
Grades are assigned on a standard scale with the following weights:
Tests (2) 60% Final 40%
Note: excessive unexcused absences will result in a 10% reduction in your overall grade.
Schedule
(subject to change)
Week | Topic | Reading | Assignment |
---|---|---|---|
1 | Chapter 9: Turing Machines | ||
2 | Chapter 10: Other Models of Turing Machines | ||
3 | Chapter 11:.A Hierarchy of Formal Languages and Automata | ||
4 | Chapter 12: Limits of Algorithmic Computation | ||
5 | Review for Final |
Textbook
Introduction to the Theory of Computation, 3rd ed. (ISBN: 978-1133187790), by Michael Sipser. Course Technology, 2012. (Amazon)
Resources
- Go to the online repository
Software Downloads
- JFLAP is software for exploring and experimenting with automata, machines and grammars.
Course Policies
See Department Policies which will be adhered to within the course.
See Also
- Mathematical Induction en.wikipedia.org/wiki/Mathematical_induction Wikipedia article