Difference between revisions of "User:Jeffj/CS6723/Syllabus"
From A-State Computer Science Wiki
< User:Jeffj | CS6723
| Line 27: | Line 27: | ||
<tr><td align=center valign=top>1</td> | <tr><td align=center valign=top>1</td> | ||
<td></td> | <td></td> | ||
| − | <td valign=top>Chapter | + | <td valign=top>Chapter 9: Turing Machines</td><td valign=top></td></tr> |
<tr><td align=center valign=top>2</td> | <tr><td align=center valign=top>2</td> | ||
<td></td> | <td></td> | ||
| − | <td valign=top>Chapter | + | <td valign=top>Chapter 10: Other Models of Turing Machines</td><td valign=top></td></tr> |
<tr><td align=center valign=top>3</td> | <tr><td align=center valign=top>3</td> | ||
<td></td> | <td></td> | ||
| − | <td valign=top>Chapter | + | <td valign=top>Chapter 11:.A Hierarchy of Formal Languages and Automata</td><td valign=top></td></tr> |
<tr><td align=center valign=top>4</td> | <tr><td align=center valign=top>4</td> | ||
<td></td> | <td></td> | ||
| − | <td valign=top>Chapter | + | <td valign=top>Chapter 12: Limits of Algorithmic Computation</td><td valign=top></td></tr> |
<tr><td align=center valign=top>5</td> | <tr><td align=center valign=top>5</td> | ||
<td></td> | <td></td> | ||
Revision as of 08:20, 10 July 2019
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
An Introduction to Formal Languages and Automata, 6th ed. (ISBN: 978-12840772470), by Peter Linz. Jones & Bartlett Learning, 2016. (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
