AS Computer Science: 4.0 Theory of Computation

Describe problem-solving in the context of computer science.

Developing solutions to logic problems and checking their correctness.

What does following and writing algorithms involve?

Understanding algorithms, expressing solutions using pseudocode with standard constructs, hand-tracing algorithms, and converting pseudocode to program code.

Define abstraction in the context of computations.

The concept of simplifying a representation by removing unnecessary details or grouping by common characteristics.

How is information hiding relevant in computer science?

It involves concealing non-essential details of an object to focus on its essential characteristics.

What are the standard constructs used in expressing algorithms in pseudocode?

Sequence, assignment, selection, and iteration.

Describe procedural abstraction.

Procedural abstraction represents a computational method.

What is functional abstraction?

Functional abstraction hides the particular computation method.

Define data abstraction.

Data abstraction hides the details of how data are represented, allowing construction of new data objects from existing types.

How is problem abstraction/reduction achieved?

Details are removed until the problem is simplified to a solvable form, often by reducing it to a previously solved problem.

Do you know what decomposition involves?

Procedural decomposition breaks a problem into sub-problems, each accomplishing a specific task that may be further subdivided.

Describe composition in the context of abstraction.

Composition involves combining procedures to create compound procedures and combining data objects to form compound data structures like a tree.

How is automation related to abstraction?

Automation involves implementing models (abstractions of real-world objects) to solve problems by creating algorithms, coding them, implementing data structures, and executing the code.

Describe problem solving in the context of finding a solution to a difficult issue.

Problem solving involves the process of finding a solution to a challenging or complex problem.

Do exam questions often involve providing a series of statements for students to draw conclusions from?

Yes, exam questions may present a series of statements from which students have to derive conclusions.

Define the process of forming a reasonable conclusion in problem solving.

The process involves analyzing the given information to draw logical inferences or conclusions.

How does the example with George and chocolate illustrate drawing conclusions from statements?

The example shows how conclusions can be made based on the given statements about George being a student and all students liking chocolate.

Describe the scenario with Alice, Bob, and Charlie and the hat colors.

Alice, Bob, and Charlie, wearing hats of unknown colors, can see each other's hats but not their own. Charlie deduces his hat is yellow. The question is about Bob's hat color.

Describe the process of assignment in pseudocode.

Assignment in pseudocode involves giving a value to a variable or constant, represented by an arrow pointing towards the variable or constant.

Define an algorithm.

An algorithm is a sequence of steps that can be followed to complete a task, always terminating rather than looping indefinitely.

How can pseudocode aid communication among programmers?

Pseudocode allows programmers, even if they use different programming languages, to describe algorithms in a language-independent way, facilitating communication.

Do algorithms have to terminate?

Yes, algorithms always terminate rather than running indefinitely in a loop.

Describe the concept of sequence in pseudocode.

Sequence in pseudocode refers to instructions that follow on from one another, executed in the order they appear.

How did Charlie determine the color of her hat in the given scenario?

Charlie deduced the color of her hat by realizing that her hat is the color that Alice and Bob's hats are not, leading her to conclude her hat is yellow.

Describe abstraction in problem-solving.

Abstraction is the process of omitting unnecessary details from a problem to simplify it and make finding a solution easier.

What is representational abstraction?

Representational abstraction involves arriving at a problem's representation by removing unnecessary details.

Define information hiding in programming.

Information hiding is the process of hiding non-essential details of an object to focus on its essential characteristics.

How does procedural abstraction work in modeling?

Procedural abstraction involves breaking down a complex model into reusable procedures, abstracting away actual values used in computations.

Explain abstraction by generalization/categorization.

Abstraction by generalization/categorization involves grouping by common characteristics to establish a hierarchical relationship.

What is functional abstraction in problem-solving?

Functional abstraction involves disregarding the particular method of a procedure and focusing on the resulting function.

Describe data abstraction.

Data abstraction involves abstracting away specific details of data representation to create new data structures based on previously defined ones.

Define problem abstraction/reduction.

Problem abstraction involves removing details from a problem until it is simplified and solvable, often by making it similar to a problem that has already been solved.

How does decomposition work in problem-solving?

Decomposition involves dividing a problem into smaller sub-problems that can be solved individually or further divided until the original problem is fully solved.

What is the purpose of composition in dealing with complex problems?

Composition is used to combine procedures to form a larger system, particularly in abstract data types where complex types are built from simpler ones.

Explain the concept of automation in problem-solving.

Automation involves putting abstractions of real-world phenomena into action through algorithms implemented in code, utilizing models in data structures, and executing the code on the data structures.

Describe the purpose of Finite State Machines (FSMs) without output.

FSMs without output are used to model systems where the focus is on the sequence of states rather than the output produced by each state transition.

Define Finite State Machines (FSMs) without output.

FSMs without output are mathematical models used to represent systems where the output is not dependent on the current state, focusing solely on the sequence of states.

Describe a finite state machine (FSM)

A computational model with a fixed number of states that changes state based on input data and transition rules.

What is the purpose of state transition diagrams in computer science?

To visually represent a finite state machine with states, transitions, start state, and accepting state.

Define accepting state in the context of finite state machines

A state where the machine terminates if the input data is valid.

How are transition rules used in finite state machines?

To determine the next state of the machine based on the current state and input data.

Do finite state machines accept all input data?

No, they only accept input data that satisfies specific criteria defined by the transition rules.

Describe a state transition table in the context of a finite state machine.

A state transition table in a finite state machine includes columns for current state, input, and next state, detailing the transitions between states based on inputs.

Define the transition function in the context of a finite state machine.

The transition function in a finite state machine specifies how the machine transitions from one state to another based on the current state and input.

How can transition functions be represented more formally in a finite state machine?

Transition functions in a finite state machine can be represented more formally using a state transition table, outlining the current state, input, and next state for each transition.

Do state transition tables provide a structured way to define the behavior of a finite state machine?

Yes, state transition tables offer a structured format to define and understand the behavior of a finite state machine by specifying the transitions between states based on inputs.

Describe the example of a parking machine using a state transition diagram.

The example of a parking machine involves a finite state machine where customers pay coins worth 10p or more to reach an accepting state of 50p, with transitions between states based on the coins inserted.

Describe the type of parity represented by this finite state machine.

Odd parity, where only numbers with an odd total of 1s will be accepted.

Define the number of states in this finite state machine.

Two states: one start state and one accepting state.

How many transition functions are there in this finite state machine?

There are four transition functions.

Do accepted input strings include numbers with an even total of 1s?

No, only numbers with an odd total of 1s are accepted.

Describe the behavior of the machine for rejected input strings.

Rejected input strings do not have an odd total of 1s and are not accepted by the machine.