The Theory of Computing--A Summary
Introduction goes here.
Defining Computer Science
Give the definition of computer science.
- Describe what a problem is.
- Describe what a problem instance is.
- Describe what a solution is.
- Discuss why answers to a problem cannot be computed once and provided in a table.
Give an example of a problem for part 1 and then using that problem give further examples or discussion for parts 2, 3, and 4.
Discuss what a decision problem is.
Give an example of a general problem and a decision problem based on the general problem.
Discuss the reasons for focusing on decision problems when studying the theory of computing.
Regular Languages
A Simple Model of Computation: The Finite State Automaton as a Recognizer of Regular Languages
The theory of computing generally starts out with a description of models of computation.
Give an example of an interesting problem and a finite state automaton that solves it. Use the FSA applet in the theory hypertextbook to generate the FSA, take a screen shot of it, size it properly, and include it in this page as an image. Include this image (and all others) in a file with the name
imagesYourLastName
Give an exampleof an interesting problem and a nondeterministic finite state automaton that solves it that possibly more intuitive than an equivalent deterministic finite state automaton that solves the same problem. Use the FSA applet as before.
Discuss why nondeterminism is of interest in the study of models of computation.
Discuss what it means for a nondeterministic FSA to accept a string.
A Simple Paradigm for Representing Regular Languages: Regular Expressions