AS and A-level Computer Science Specification Specifications for first teaching in 2015
PDF | 1.31 MB
Content | Additional information |
---|---|
Be able to develop solutions to simple logic problems. | |
Be able to check solutions to simple logic problems. |
Content | Additional information |
---|---|
Understand the term algorithm. | A sequence of steps that can be followed to complete a task and that always terminates. |
Be able to express the solution to a simple problem as an algorithm using pseudo-code, with the standard constructs:
| |
Be able to hand-trace algorithms. | |
Be able to convert an algorithm from pseudo-code into high level language program code. | |
Be able to articulate how a program works, arguing for its correctness and its efficiency using logical reasoning, test data and user feedback. |
Content | Additional information |
---|---|
Be familiar with the concept of abstraction as used in computations and know that:
|
Content | Additional information |
---|---|
Be familiar with the process of hiding all details of an object that do not contribute to its essential characteristics. |
Content | Additional information |
---|---|
Know that procedural abstraction represents a computational method. | The result of abstracting away the actual values used in any particular computation is a computational pattern or computational method - a procedure. |
Content | Additional information |
---|---|
Know that for functional abstraction the particular computation method is hidden. | The result of a procedural abstraction is a procedure, not a function. To get a function requires yet another abstraction, which disregards the particular computation method. This is functional abstraction. |
Content | Additional information |
---|---|
Know that details of how data are actually represented are hidden, allowing new kinds of data objects to be constructed from previously defined types of data objects. | Data abstraction is a methodology that enables us to isolate how a compound data object is used from the details of how it is constructed. For example, a stack could be implemented as an array and a pointer for top of stack. |
Content | Additional information |
---|---|
Know that details are removed until the problem is represented in a way that is possible to solve, because the problem reduces to one that has already been solved. |
Content | Additional information |
---|---|
Know that procedural decomposition means breaking a problem into a number of sub-problems, so that each sub-problem accomplishes an identifiable task, which might itself be further subdivided. |
Content | Additional information |
---|---|
Know how to build a composition abstraction by combining procedures to form compound procedures. | |
Know how to build data abstractions by combining data objects to form compound data, for example tree data structure. |
Content | Additional information |
---|---|
Understand that automation requires putting models (abstraction of real world objects/phenomena) into action to solve problems. This is achieved by:
| Computer science is about building clean abstract models (abstractions) of messy, noisy, real world objects or phenomena. Computer scientists have to choose what to include in models and what to discard, to determine the minimum amount of detail necessary to model in order to solve a given problem to the required degree of accuracy. Computer science deals with putting the models into action to solve problems. This involves creating algorithms for performing actions on, and with, the data that has been modelled. |
Content | Additional information |
---|---|
Be able to draw and interpret simple state transition diagrams and state transition tables for FSMs with no output and with output (Mealy machines only). |
Content | Additional information |
---|---|
Be familiar with the concept of a set and the following notations for specifying a set: A = {1, 2, 3, 4, 5 } or set comprehension: A = {x | x ∈ ℕ ∧ x ≥ 1 } where A is the set consisting of those objects x such that x ∈ ℕ and x ≥ 1 is true. Know that the empty set, {}, is the set with no elements. Know that an alternative symbol for the empty set is Ø. | A set is an unordered collection of values in which each value occurs at most once. Several languages support set construction. In Python, for example, use of curly braces constructs a set: {1, 2, 3 }. | means such that. x ∈ ℕ means that x is a member of the set ℕ consisting of the natural numbers, ie {0, 1, 2, 3, 4, … }. The symbol ∧ means AND. The term ∧ x > = 1 means AND x is greater than or equal to 1. In Python, {2 ∗ x for x in {1, 2, 3 }} constructs {2, 4, 6 }. This is said to be a set comprehension over the set {1, 2, 3 } . |
Be familiar with the compact representation of a set, for example, the set {0n 1n | n ≥ 1}. This set contains all strings with an equal number of 0 s and 1s. | For example, {0n 1n | n ≥ 1} = {01, 0011, 000111, 00001111, … } |
Be familiar with the concept of:
| A finite set is one whose elements can be counted off by natural numbers up to a particular number, for example as: 1st element, 2nd element, …, 20th (and final) element. The set of natural numbers, ℕ and the set of real numbers, ℝ are examples of infinite sets. A countably infinite set is one that can be counted off by the natural numbers. The set of real numbers is not countable. The cardinality of a finite set is the number of elements in a set. Cartesian product of two sets, X and Y, written X x Y and read 'X cross Y', is the set of all ordered pairs ( a, b ) where a is a member of A and b is a member of B. |
Be familiar with the meaning of the term:
| {0, 1 , 2 } ⊂ ℕ where ⊂ means proper subset of, that is ℕ contains everything in {0, 1, 2 } but there is at least one element in ℕ that is not in {0, 1, 2 }. {0, 1 , 2 } ⊆ {0, 1, 2, 3 } where ⊆ means subset of. ⊆ includes both ⊂ and =, for example {0, 1, 2, 3 } ⊆ {0, 1, 2, 3 } is also true, because {0, 1, 2, 3 } = {0, 1, 2, 3 }. A countable set is a set with the same cardinality (number of elements) as some subset of natural numbers. |
Be familiar with the set operations:
| The set difference A\B (or alternatively A-B) is defined by A\B = {x : x ∈ A and x ∉ B} |
Content | Additional information |
---|---|
Know that a regular expression is simply a way of describing a set and that regular expressions allow particular types of languages to be described in a convenient shorthand notation. | For example, the regular expression a ( a | b )* generates the set of strings { a, aa, ab, aaa, aab, aba , …}. |
Be able to form and use simple regular expressions for string manipulation and matching. | Students should be familiar with the metacharacters:
|
Be able to describe the relationship between regular expressions and FSMs. | Regular expressions and FSMs are equivalent ways of defining a regular language. |
Be able to write a regular expression to recognise the same language as a given FSM and vice versa. | A student's ability to write very simple regular expressions and FSMs will be assessed. |
Content | Additional information |
---|---|
Know that a language is called regular if it can be represented by a regular expression. | Also, a regular language is any language that a FSM will accept. |
Content | Additional information |
---|---|
Be able to check language syntax by referring to BNF or syntax diagrams and formulate simple production rules. | |
Be able to explain why BNF can represent some languages that cannot be represented using regular expressions. |
Content | Additional information |
---|---|
Understand that algorithms can be compared by expressing their complexity as a function relative to the size of the problem. Understand that the size of the problem is the key issue. | |
Understand that some algorithms are more efficient:
| Efficiently implementing automated abstractions means designing data models and algorithms to run quickly while taking up the minimal amount of resources such as memory. |
Content | Additional information |
---|---|
Be familiar with the mathematical concept of a function as a mapping from one set of values, the domain, to another set of values, drawn from the co-domain, for example ℕ → ℕ. | |
Be familiar with the concept of:
| |
Be familiar with the notion of permutation of a set of objects or values, for example, the letters of a word and that the number of permutation s of n distinct objects is n factorial ( n !). | n ! is the product of all positive integers less than or equal to n . |
Content | Additional information |
---|---|
Be familiar with Big-O notation to express time complexity and be able to apply it to cases where the running time requirements of the algorithm grow in:
| |
Be able to derive the time complexity of an algorithm. |
Content | Additional information |
---|---|
Be aware that algorithmic complexity and hardware impose limits on what can be computed. |
Content | Additional information |
---|---|
Know that algorithms may be classified as being either:
| Heuristic methods are often used when tackling intractable problems. |
Content | Additional information |
---|---|
Be aware that some problems cannot be solved algorithmically. |
Content | Additional information |
---|---|
Describe the Halting problem (but not prove it), that is the unsolvable problem of determining whether any program will eventually stop if given particular input. | |
Understand the significance of the Halting problem for computation. | The Halting problem demonstrates that there are some problems that cannot be solved by a computer. |
Content | Additional information |
---|---|
Be familiar with the structure and use of Turing machines that perform simple computations. | |
Know that a Turing machine can be viewed as a computer with a single fixed program, expressed using:
One of the states is called a start state and states that have no outgoing transitions are called halting states. | Exam questions will only be asked about Turing machines that have one tape that is infinite in one direction. |
Understand the equivalence between a transition function and a state transition diagram. | |
Be able to:
| |
Be able to explain the importance of Turing machines and the Universal Turing machine to the subject of computation. | Turing machines provide a (general/formal) model of computation and provide a definition of what is computable. |