Difference between revisions of "User:Jeffj/CS6723/Syllabus"

From A-State Computer Science Wiki
Jump to: navigation, search
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 3: The Church-Turing Thesis</td><td valign=top></td></tr>
+
     <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 4: Decidability</td><td valign=top></td></tr>
+
     <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 5:.Reducibility</td><td valign=top></td></tr>
+
     <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 6: Advanced Topics in Computability Theory</td><td valign=top></td></tr>
+
     <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
OfficeCSM 132Office HoursTR 11:00am-12:00pm and MW 11:00pm-12:00pm
Phone870-972-3978 ext. 8117Emailjeffj@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%
Final40%

Note: excessive unexcused absences will result in a 10% reduction in your overall grade.

Schedule

(subject to change)

Week  TopicReadingAssignment
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

create PDF version