Automation and Finite State Machines

Overview

Recall questions on what automation is and the four steps by which it is achieved, and on finite state machines with and without output.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is automation?

   Model answer

   Automation is putting models — abstractions of real-world objects or phenomena — into action to solve problems. Building the model is abstraction; making the computer actually use the model to produce answers is automation.

2. 2

   By what four steps is automation achieved?

   Model answer

   Creating algorithms; implementing the algorithms in program code, that is in instructions; implementing the models in data structures; and executing the code.

3. 3

   Why is creating algorithms the first step in automating a model?

   Model answer

   A model is only a description of the parts of the real world that were kept; by itself it does nothing at all. Automating it means writing algorithms that act on the modelled data and do something with it — the sequences of steps that turn what has been stored into the answer the problem actually calls for. Until those steps have been set down in algorithmic form there is nothing for the computer to execute; implementing them as programs is what completes the automation.

4. 4

   What does 'implementing the models in data structures' mean, and why is the choice of data structure part of automation rather than an afterthought?

   Model answer

   It means deciding how the modelled information will actually be stored so a program can work with it: a road network held as an adjacency list or adjacency matrix, a queue of jobs held as an array with front and rear pointers, a set of records held in a hash table. It is part of automation because the algorithms operate on these structures, and the structure chosen fixes what those algorithms can do quickly. Holding a network as a matrix makes 'is A joined to B?' immediate but wastes memory when there are few roads; holding it as a list saves the memory but makes the same test slower.

5. 5

   Take a supermarket checkout queue and describe how the four steps of automation would be applied to it.

   Model answer

   First the model: an abstraction of the real queue keeping only the arrival time and the number of items per customer and discarding everything else about the shoppers. Then create the algorithm: repeatedly take the customer at the front, work out the service time from the item count, advance the clock and record the waiting time. Then implement the model in a data structure: hold the waiting customers in a queue and each customer as a record of arrival time and item count. Then implement the algorithm in program code and execute it, so the simulation runs and reports the average wait — which is the answer that was wanted.

6. 6

   What does 'efficiently implementing automated abstractions' involve?

   Model answer

   Designing the data models and the algorithms together so the program runs fast on as little memory as possible. The two often pull against each other, so it involves a judgement: storing extra pre-computed values makes the program faster but uses more memory, while recomputing them each time saves memory but costs time.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.