Give a solid foundation in the theory of computation. Establish the relevance of computation theory to software development. Ensure a fair and accurate measurement of student performance.
Late homework assignments will not be accepted.
Rules of ethical conduct will be respected.
Hard versus easy.
Computability theory: some basic problems cannot be solved by computers.
Solvable versus not solvable.
Automata theory: models of computation. Finite automaton, context-free grammar.
Sequence: list of objects in some order.
Tuple: a sequence with k elements is a k-tuple.
Function: input-output relationship.
Infix notation: a + b
Prefix notation: add(a, b)
Predicate (property): function whose range is {T, F}.
Relation: property whose domain is a set of k-tuples.
If R is a binary relation: "aRb" means aRb = T.
Graph: set of points with lines connecting, vertices and edges.
Directed graph: arrows.
String: a finite sequence of symbols from an alphabet. The empty string epsilon has length zero.
Language: a set of strings.
Boolean Logic: conjunction, disjunction, negation, XOR, equality (also called biconditional), implication.
To disprove a statement, you need only a single counterexample.
For existence proof, demonstrate how to construct the object.
Contradiction
Example: assume sqr(2) is rational: sqr(2) = m / n.
Reduce m / n so that both cannot be even.
Multiply by n: n * sqr(2) = m.
Square: 2 * n ^ 2 = m ^ 2.
Because m ^ 2 is twice n ^ 2, m ^ 2 is even.
Therefore, m is even (square of an odd number is odd).
We can write m = 2 * k.
Therefore 2 * n ^ 2 = (2 * k) ^ 2 = 4 * k ^ 2.
Divide by 2: n ^ 2 = 2 * k ^ 2.
Therefore n is even, a contradiction.
Induction
Used to show that all elements of an infinite set have a specified property.
Chapter 0:
Exercises 0.1, 0.2, 0.6.
Problems 0.10, 0.13.
Email: Richard dot J dot Wagner at gmail dot com
notes00b.htm, this hand crafted HTML file created August 31, 1998.
Last updated May 14, 2011, by
Rick Wagner. Copyright © 1998-2011, all rights reserved.