Unit 1 - CH 1 Flashcards Preview

Computer Science > Unit 1 - CH 1 > Flashcards

Flashcards in Unit 1 - CH 1 Deck (33):

Define Computation

The act or process of calculating something by mathematical, logical, or interactive methods.


Define Computability

A measure of what can and cannot be computed.


Define Computing

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.


Define Algorithm

A description (independent of any programming language) of a process that achieves some task. A step-by-step procedure for solving a problem.


Define Deterministically

(Solving a problem) without guessing a solution.


What is the purpose of an algorithm?

To effectively communicate a computation to humans (not computers).


Define Program

A description of a process in a programming language that achieves some useful result.


Define Problem

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?

- Givens
- Resources & Constraints
- A Goal,
- Ownership


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


Define Module

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.


Define Sequence

Consecutive (groups of) steps process one after another in the order they arise.


Define Selection

A decision-making step


Define Repetition/Iteration

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


Define Assignment

An operation that assigns a value to a variable


Define Structured English

A very restricted subset of the English language


Define Pseudocode

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


What are the 3 constructs that may be used to create an algorithm?

1. Sequence
2. Selection
3. Iteration/Repetition