2.11 - Abstraction and Automation

What is meant by representational abstraction?

• A representation arrived at by removing unnecessary details from a real-world problem

• Only the details relevant to the purpose of the model are kept

• e.g. A bouncing ball program may ignore air resistance, surface texture and spin if they are unnecessary for the simulation

• Trade-off: the more details removed, the simpler the model, but the less accurately it mimics reality

What is meant by abstraction by generalisation?

• Grouping by common characteristics to arrive at a hierarchical relationship of the "is a kind of" type

• A specific problem is recognised as a particular instance of a more general problem

• Solving the general case makes the solution applicable to many similar problems

• e.g. Euler abstracted Königsberg's bridge problem into graph theory - applicable to any city with any number of bridges

• Common in OOP - a Dog is a kind of Animal, sharing common attributes defined in the parent class

What is meant by procedural abstraction?

• Using a procedure to carry out a sequence of steps for achieving a task, without the caller needing to know how it works internally

• Separates the physical reality (how it is done) from the logical view (what it does)

• The programmer only needs to know:

  • The procedure interface - the procedure's name, what arguments are required, and what data type each argument is

What is meant by functional abstraction?

A mapping of one set of values to another, e.g. x = sqrt(17)

What is meant by data abstraction?

The details of how data is actually represented internally are hidden from the programmer.
This allows the creation of abstract data types (ADTs) - logical descriptions of how data is viewed and what operations can be performed on it - such as queues, stacks and trees.

What is meant by information hiding?

Data is not directly accessible to the programmer, and can only be accessed through defined procedures/functions.

What is meant by decomposition?

Breaking down a complex problem into a number of sub-problems, each of which performs an identifiable task.

What is meant by composition?

Combing procedures to from compound procedures.

What is meant by problem abstraction?

• Removing details from a problem until it is represented in a way that can be solved, because it reduces to a problem that has already been solved

• This process is called reduction

• e.g. The knight chessboard problem - by numbering squares and representing moves as edges between nodes, it reduces to a graph unfolding problem, for which a solution already exists