4.4 Theory of computation Flashcards
Define decomposition
Deomposition is the process of breaking down large complex tasks or processes down into smaller more manageable tasks
Abstraction techniques will also be used in order to decompose the system requirements
What is logical reasoning?
The process of using a given set of facts to determine whether new facts are true or false
What is an algorithm?
A sequence of steps that can be followed to complete a task & that always terminates
What are the standard constructs of any algorithm?
- Sequence (statements ordered sequentially)
- Assignment (variables used to temporarily store information in memory to be refferenced later)
- Iteration (loops)
- Selection (statements used to make a decision/ decide whether to execute the next statement or not)
How do we think critically about designing algorithms?
What questions do we ask ourselves when designing algorithms?
- Does the algorithm solve the problem?
For this we use:
- Logical reasoning (look and analyse)
- Test data (valid, invalid, boudary) to see if works as expected
- User feedback (does the result satisfy the intended user?) - Does the algorithm solve the problem efficiently (use time-complexity analysis Big O’ notation)
What is abstraction?
The concept of picking out common concepts from a problem in order to reduce it to its essential defining features, ignoring less significant details.
There are 6 types (2 main ones)
What are the 2 main types of abstraction
Representational abstraction:
- The process of removing unnecessary detail so only the necessary details needed to solve the problem remain e.g. a map
Abstraction by generalisation/categorisation:
- The process of grouping common aspects of a problem into broader categories to arrive at a hierachal relationship e.g. inheritance concept in OOP. Involves recognising common characteristics of representations so that more general representations can be developed.
What are the other 4 types of abstraction related to computing?
- Procedural Abstraction - all solutions can be broken down into a series of procedures and subroutines. Enables the programmer to identify the main processes needed to be copleted and to contain these in procedures e.g. top-down approach to programming
- Functional abstraction - reusable functions can be created to solve common sub-tasks in a problem / breaking down or solving a complex problem by using a series of reusable functions
- Data abstraction - hiding the details of how data is truly represented so that it is easier for the programmer to create new data objects from previously defined objects e.g. encapsulation
- Problem abstraction - breaking down and removing details of a problem so that it can be represented in a way that can be solved by a solution that already exists to a similar problem
What is information hiding?
Process of providing a definition or interface of a system or object, whilst keeping the inner workings hidden.
What is procedural decomposition?
The process at looking at a system as a whole, then breaking it down into a series of procedures or subroutines needed to complete a task
Why do we use procedural decomposition?
We use procedural decomposition so that subtasks can be further subdivided until the** programmer reaches a level of detail** that is sufficient to start building the system.
If you leave the problem too large, you have messier code at the end.
What is composition?
The process of building up a whole system from smaller units (opposite of composition)
What is procedural composition?
The process of creating a working system from the abstraction. It involves
1. Writing procedures and linking them together to make compound procedures
2. Creating data structures and combining them to form compound data structures
What is automation
Creating a computer model of a real-life situation and putting it into action.
Most computer algorithms are created to solve some sort of real-world problem.
One objective of creating computer systems is to create elegant solutions to difficult problems.
What are the steps to automation?
- Identify and understand the problem
- Create suitable algorithms (using pseudocode)
- Build algorithms into program code
- Use suitable data to test the solution to solve the problem
