4.4 Theory of Computation Flashcards
(37 cards)
What is an Algorithm?
A sequence of steps that can be followed to complete a task and that always terminates
Algorithms are fundamental in computer science and programming.
Define Pseudo-code.
A way of expressing an algorithm in the style of a program, but without worrying about language-specific syntax
Pseudo-code is written for humans to understand.
What does Pseudo-code show?
The structure of any planned program using the standard constructs:
* Sequence
* Assignment
* Selection
* Iteration
These constructs help in visualizing the flow of the algorithm.
What is Sequence in programming?
A series of instructions that are executed in order
Sequence is the simplest form of control flow.
What does Assignment refer to in programming?
A value being assigned to a placeholder (variable)
Assignment is a fundamental operation in most programming languages.
Define Selection in programming.
Running instructions only if a condition is met (if)
Selection allows for decision-making in algorithms.
What is Iteration?
Repeatedly running instructions depending on a condition (for, while)
Iteration is essential for tasks that require repetition.
What is a Hand-trace?
Manually stepping through an algorithm line by line, adding to a table of placeholders (variables) each time a value is assigned to one
Hand-tracing helps in debugging and understanding algorithms.
In a Hand-trace, when is a new row used?
Each time the code loops, or a value is replaced
This helps to keep track of changes in variable states.
What is procedural decomposition?
Breaking down problems into sub-problems that accomplish identifiable tasks
Each sub-problem can also be decomposed into smaller sub-problems.
What is abstraction in problem-solving?
Removing details until the problem is represented in a solvable way
This can involve representational abstraction, generalisation, or procedural abstraction.
What is representational abstraction?
A representation arrived at by removing unnecessary details
Example: The London Underground map, which shows connections without geographical accuracy.
What does abstraction by generalisation or categorisation involve?
Grouping by common characteristics to define concepts
Example: Defining a cat as a kind of mammal, which is a kind of animal.
What is procedural abstraction?
Abstracting away actual values used in a computation to create a procedure
Example: Finding the mean average of numbers by outlining the procedure rather than using specific values.
What is functional abstraction?
Hiding the procedure used to achieve a result and presenting a function
Example: A mean() function that calculates the mean without exposing its internal workings.
What is data abstraction?
Hiding the real data structure to present a simpler, compound data structure
Example: A stack created using an array and a pointer, abstracting the details of data storage.
What does composition abstraction entail?
Combining procedures to form compound procedures
Example: Creating a mean average procedure by combining sum and divide procedures.
What is automation in problem-solving?
Putting models into action to solve problems
This involves creating algorithms, implementing them in code, and executing the code.
What are models in the context of automation?
Clean, abstract versions of real-world objects or phenomena
The challenge is deciding what details to include or discard for accuracy.
True or False: Procedural decomposition can lead to smaller sub-problems.
True
Each sub-problem can be further decomposed.
What is a set?
An unordered collection of unique values
How is set notation represented for a set A containing values 1 to 5?
A = {1, 2, 3, 4, 5}
What does set A = {x | x ∈ Natural Numbers, x ≥ 1} represent?
Set A consists of those objects, x, such that x is a member of the Natural Numbers set and x is greater than or equal to 1
What does the notation A = {0^n 1^n | n ≥ 1} indicate?
Set A consists of all strings consisting of n 0s and n 1s where n is greater than or equal to 1
