Set 10 Flashcards
What is representational abstraction?
A representation arrived at by removing unnecessary details
What is abstraction by generalisation or categorisation?
A grouping by common characteristics to arrive at a hierarchical relationship of the ‘is a kind of’ type.
What is information hiding?
The process of hiding all details of an object that do not contribute to its essential characteristics
What is procedural abstraction?
 Procedural abstraction involves breaking down a complex model into a series of reusable procedures.
 The actual values used in a computation are abstracted away and a computational method is achieved
How is functional abstraction different from procedural abstraction?
 Functional abstraction requires yet another abstraction from procedural abstraction
 While the result of a procedural abstraction is a computational method, the function disregards the particular computation method
What is data abstraction? Give an example
 The process of isolating how a compound data object is used from the details of how it is constructed. Data abstraction forms the basis of abstract data types
 For example, a stack could be implemented as an array and a pointer for the top of the stack
What is problem abstraction/reduction?
The process of removing details until the problem is represented in a way that is possible to solve, because the problem reduces to one that has already been solved
What is (procedural) decomposition?
The process of breaking a problem into a number of subproblems, so that each subproblem accomplishes an identifiable task, which might itself be further subdivided
What is (procedural) composition?
The process of combining procedures to form compound procedures
What is automation? How is it achieved?
The process of putting models (abstractions of real world objects/phenomena) into action to solve problems. This is achieved by:
1. creating algorithms
2. implementing the algorithms in program code
3. implementing the models in data structures
4. executing the code.
When is a problem “computable”?
If there is an algorithm (in principle) that solves the problem
When is a problem “noncomputable”?
If no algorithm can ever exist which solves the problem
What is a intractable problem?
A computable problem for which a polynomial time (or better) algorithm does not exist
How do programmers find “solutions” to intractable problems?
By developing tractable heuristic algorithms and methods, which find approximate (but not necessarily optimal) solutions.
What is the tradeoff that must be considered when developing heuristic algorithms?
speed vs correctness
What is an undecidable problem? Give an example
 A decision problem that is noncomputable
 e.g. the halting problem
What is the halting problem?
The undecidable problem of determining whether any program will eventually halt on given particular input without running the program
What is the significance of the halting problem?
The halting problem demonstrates that some problems are noncomputable, meaning they cannot be solved by a computer
Why can a Universal Turing Machine be considered to be more powerful than any computer that you can purchase?
Because it has an infinite amount of memory
Name one example of a model of computation
Turing machine
Describe the importance of Turing machines
 Turing machines provide a formal model of computation and provide a definition of what is computable
 They can be used to prove that there are problems which cannot be solved by computers
What makes up a Turing machine?
 Finite set of states
 Set of transition rules
 Finite set of symbols
 Infinite tape with marked off squares
 Sensing readwrite head that can travel along the tape, one square at a time
What is a halting state in a Turing machine?
A state with no outgoing transitions
What is meant by a Universal Turing machine?
 A Turing machine that can simulate the behaviour of any other Turing machine, by acting as an interpreter
 It faithfully executes operations on the data precisely as the simulated TM does
 Both the transition rules for the TM as well as the input data would be stored on the tape
What is another way to represent the state transition diagram of a Turing machine?
 Transition function
 δ (current state, input symbol) = (next state, output symbol, movement)
One example of where composition is used
In abstract data types, where a complex abstract data type is formed from smaller and simpler data types
Give three differences between symmetric and asymmetric encryption
S: Uses same key for both encryption and decryption
A: Doesn’t
S: Have to distribute the key without interception
A: Don’t
S: Faster
A: Slower, but provides both confidentiality and authentication
Asymmetric encryption: A
sends to B

A
encrypts the message withB
’s public key 
B
decrypts with their own private key (the only key that can do this)
Asymmetric encryption: A
sends to B
, and B
can verify that A
is the sender

A
encrypts the message withB
’s public key andA
’s private key 
B
will decrypt withB
’s private andA
’s public key
What is the purpose of digital signatures?
To confirm the identity of the sender, and to detect if a message or document has been tampered with
Describe how A
can use a digital signature when sending a document to B

A
hashes the document, creating a message digest 
A
encrypts this message digest with their private key. This encrypted hash is known as the digital signature  The digital signature is appended to the message
 (This may now be encrypted with
B
’s public key, sent toB
, and decrypted byB
using their own private key as normal) 
B
decrypts the digital signature withA
’s public key, to reveal the message digest.B
also hashes recalculates the hash for the document. If the result of these procedures is the same, then the message has not been tampered with and the identity of the sender is authenticated.
Anyone could create a digital signature and claim they are a trusted individual. How do we solve this?
Digital certificates are used to verify the sender’s identity
What is a digital certificate?
 An electronic document that authenticates a message sender or a website
 It contains the sender’s public key as well as some information about them
How can a digital certificate be created for A? What do they contain?
A trusted individual (certificate authority) signs a copy of A’s public key as well as some information about A.
Digital certificates will contain:
 Serial number
 Name (e.g. domain name for website digital certificates)
 Expiration date
 Copy of the certificate holder’s public key
How are digital certificates used by modern web browsers?
 Modern web browsers check the digital certificate of each secure website as a standard security measure.
 If the certificate is suspicious or out of date, the site is blocked.
Why are keyexchange algorithms needed?
In order to distribute the key securely in symmetric encryption systems.
 Asymmetric encryption algorithms are nearly always much more computationally expensive than symmetric ones
 So in many cases it is common to exchange a shared key using a keyexchange algorithm, and then to transmit the data using that key and a symmetric key algorithm.
(e.g. SSH and SSL/TLS)