Across
- 1. A visual representation of a FSM that uses circles to represent states and arrows to indicate transitions between states.
- 3. A way of describing sets and the elements present within it using strings of characters.
- 5. The number of elements in the set.
- 7. A function that determines how a Turing Machine moves from one state to the other. It is equivalent to a state transition diagram.
- 9. A formal model of computation that consists of a finite state machine that controls one or more tapes, where at least one tape is of unbounded length (i.e., infinitely long).
- 11. An interpreter that can simulate any Turing machine by reading the description of any arbitrary Turing Machine and faithfully executing operations on data precisely as the machine would.
- 13. An operator that produces a set containing only the elements present in both initial operand sets.
- 15. A measure of the amount of memory space needed by an algorithm to solve a particular problem of a given input size.
- 16. The process of looking at a program's entire code or code extract and running through the instructions as though you are the computer.
- 18. A set that is fully contained in another set, and the other set contains elements that are not present in the proper subset.
- 22. The result of abstracting away the actual values used in any particular computation is a computational pattern or computational method.
- 25. Simplifying a problem by breaking it down into a series of procedures or subroutines that are generalised with variable parameters. Knowledge of the implementation of each procedure is irrelevant.
- 26. A set with the same cardinality as some subset of natural numbers.
- 30. A Turing Machine's initial starting state.
- 31. An operator that produces a set containing all the elements from both initial operand sets.
- 35. The process of combining data objects to form compound data.
- 45. A sequence of steps that can be followed to complete a task and that always terminates.
- 46. The storage and representation of data in a computer system along with its logical description and interaction with operators. This allows the construction of new compound data objects from existing ones.
- 48. An optional state of a FSM that indicates whether or not an input has been accepted by the FSM.
- 49. A set that is not finite.
- 51. A tabular representation of a FSM that contains the current state, inputs and their consequent successor state.
- 52. The reverse process of decomposition where a complex system of compound procedures is built from its smaller, simpler procedures.
- 53. A set whose elements can be counted off by natural numbers up to a particular number.
- 54. A measure of the amount of time needed by an algorithm to solve a particular problem of a given input size.
- 55. The repeated removal of unnecessary details from a problem until an underlying problem representation is reached which is identical to a previously solved problem.
Down
- 2. The process of creating algorithms and implementing them as data structures and models of real-life situations that run without a significant need for human intervention.
- 4. A set with no elements. Represented by {} or Ø.
- 6. The use of a set of facts (axioms) to draw conclusions and determine whether new information is true or false.
- 8. A model of computation for a machine that is always in one of a fixed number of states.
- 10. Simplifying a problem by grouping together common characteristics of a problem to arrive at a hierarchical relationship.
- 12. The set of all ordered pairs (a, b) where a is a member of the first set, A, and b is a member of the second set, B.
- 14. A human-readable method of writing the steps of an algorithm without any particular programming language.
- 17. The process of breaking down a problem into a number of sub-problems, so that each sub-problem accomplishes an identifiable task, which might itself be further subdivided.
- 19. Simplifying a problem by only taking into consideration the necessary details required to obtain a solution, leaving a representation without any unnecessary details.
- 20. Problems that cannot be solved algorithmically.
- 21. The process of hiding all details of an object that do not contribute to its essential characteristics.
- 23. Problems that have a polynomial (or less) time solution.
- 24. An operator that produces a set containing all the elements present in either of the initial operand sets, but not both.
- 27. The property of an element being within a set.
- 28. A mapping from one set of values, the domain, to another set of values, drawn from the co-domain.
- 29. A notation technique to express syntax of languages in computing.
- 30. A set such that all its elements are present in the other set being considered.
- 32. A state with no outgoing transitions that halts a Turing Machine.
- 33. A set that can be counted off by the natural numbers.
- 34. Problems that can be solved algorithmically.
- 36. A language that can be represented by a regular expression.
- 37. The creation of a set by mathematically defining the elements that qualify to be in the set, rather than listing out all its elements.
- 38. Problems that have no polynomial (or less) time solution.
- 39. Simplifying a problem by breaking it down into a series of reusable functions which disregard the particular computational method.
- 40. A property of an algorithm that is related to the amount of resources (memory space and time in particular) that an algorithm uses in its execution.
- 41. An algorithm is said to be correct when it is consistent with the specification and produces the expected output for any given input.
- 42. The unsolvable problem of determining whether any program will eventually stop if given particular input.
- 43. A finite state machine that determines its outputs from the present state and from the inputs.
- 44. Data abstractions that hide details of how data are actually represented from the user.
- 47. An arrangement of objects such that their ordering matters.
- 50. An unordered collection of values in which each value occurs at most once.