Flashcards in Unit 1 - CH 1 Deck (33):
The act or process of calculating something by mathematical, logical, or interactive methods.
A measure of what can and cannot be computed.
The study of natural and artificial information processes
Define Artificial Intelligence
A branch of computing that studies the use of computers to perform computational processes normally associated with the human intellect.
A description (independent of any programming language) of a process that achieves some task. A step-by-step procedure for solving a problem.
(Solving a problem) without guessing a solution.
What is the purpose of an algorithm?
To effectively communicate a computation to humans (not computers).
A description of a process in a programming language that achieves some useful result.
A given (initial solution) where it is not immediately obvious how to reach the goal (desired outcome).
What are the four components about a well-defined problem?
- Resources & Constraints
- A Goal,
Define Defining Boundaries
Establishing the limits or rules about what can and can't be done when solving a problem. These limits are a type of constraint.
Define Lateral Thinking
Thinking, which challenges assumptions, establishes facts/rules, and defines boundaries of problem solving
A self-contained entity that results when a problem is divided into subproblems (each module corresponds to a subproblems).
Define Top-down design
The process of breaking a problem into smaller problems that are easier to work on.
Define Stepwise refinement
The process of breaking a problem down through successive steps into smaller problems.
Define Structure Table
An indented, numbered list of steps produced by stepwise refinement.
What is a finite state machine?
A machine that consists of a fixed set of possible states with a set of allowable inputs that change the state and a set of possible outputs.
What is a state transition diagram?
A way of describing an FSM graphically. Each state is represented by a circle and each transition by an arrow labelled with an input that causes the transition plus an output resulting from the transition.
What do you call a Finite State machine that has no outputs?
A Finite State Automation (FSA)
What is a Mealy machine?
A FSM with an initial state (arrow labelled with 'start') and outputs but usually no accepting/goal state.
What is a state transition table?
One that shows the effect on the current state of a FSM due to particular inputs, and corresponding outputs.
What is a decision table?
One that shows the outcome of a given logical condition.
Consecutive (groups of) steps process one after another in the order they arise.
A decision-making step
A step or sequence of steps that are repeated until some condition is satisfied or while a condition is satisfied.
Four major steps of computer-based problem solving:
- Identify the problem inputs
- Identify the problem outputs
- Determine the variables
- Derive the algorithm which transforms inputs into outputs
An operation that assigns a value to a variable
Define Structured English
A very restricted subset of the English language
Code that resembles a programming language but uses less strict syntax to express an algorithm and is independent of any real programming language.
What is a dry run/hand trace/desk check?
A careful step-by-step simulation on paper of how an algorithm would be executed by a computer.
What are the two main principals of computation?
1. Abstraction (how to communicate compex ideas simply and decompose problems logically)
2. Automation (automating algorithms)
When planning a solution, you should consider:
1. Strategies you will apply
2. Resources you will use
3. How these will be used
4. What order they will be used in
5. Whether they are adequate for the task