von Neumann Machine Processing Unit: Arithmetic Logical Unit (ALU) and Processor Registers Control Unit: Instruction Register and Program Counter Memory - Stores data and instructions External Mass Storage Input and Output mechanisms (I/O) Data Flow Through a von Neumann Machine
Basic properties of sets Two characteristics of a set There are no repeated occurrences of elements There is no particular order or arrangement of the elements How do you show A is a subset of B? If A and B are sets and every element of A is also an element of B, then A is a subset of B. How do you show A = B? A is a subset of B, and B is a subset of A Operations on sets Union - A union B = set of x s.t. x is an element of A or x is an element of B Intersection - A intersect B = set of x s.t. x is an element of A and x is an element of B Complement Cardinality Inclusion-Exclusion principle | A ∪ B | = | A | + | B | − | A ∩ B |. Inclusion-Exclusion for 3 sets | A ∪ B ∪ C | = | A | + | B | + | C | − | B ∩ C | − | A ∩ B | − | A ∩ C | + | A ∩ B ∩ C | Difference rule | A − B | = | A | − | A ∩ B |.
Basic Properties of: Tuples What are the two characteristics of a tuple? Product rule to count tuples Cartesian product A x B Lists Difference from tuples Strings Languages Relations Language What is the product LM of two languages L and M? If A is an alphabet, what is A*? What is a relation, binary relation --- Regular Expression
Comments
Post a Comment