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 permutations of n distinct objects is n factorial (n!) Be familiar with Big-O notation to express time 4.4.4.3 complexity and be able to apply it to cases where the running time requirements of the algorithm Order grow in: constant time logarithmic time of linear time complexity polynomial time exponential time Be able to derive the time complexity of an algorithm Be aware that algorithmic complexity and computation Limits 4.4.4.4 hardware impose limits on what can be computed of Know that algorithms may be classified as being problems of 4.4.4.5 either: algorithmic tractable problems that have a – Classification polynomial (or less) time solution are called tractable problems intractable problems that have no – polynomial (or less) time solution are called intractable problems Be aware that some problems cannot be solved problems non-computable Computable 4.4.4.6 algorithmically and Describe the Halting problem (but not prove it), problem 4.4.4.7 that is the unsolvable problem of determining whether any program will eventually stop if given particular input Halting Understand the significance of the Halting problem for computation Be familiar with the structure and use of Turing computation 4.4.5 4.4.5.1 machines that perform simple computations Know that a Turing machine can be viewed as a A Turing computer with a single fixed program, expressed model using: a finite set of states in a state transition machine diagram of a finite alphabet of symbols an infinite tape with marked-off squares a sensing head that can travel along the tape, one square at a time.
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 permutations of n distinct objects is n factorial (n!) 4.4.4.3 Order of complexity 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: constant time logarithmic time linear time polynomial time exponential time Be able to derive the time complexity of an algorithm 4.4.4.4 Limits of computation Be aware that algorithmic complexity and hardware impose limits on what can be computed 4.4.4.5 Classification of algorithmic problems Know that algorithms may be classified as being either: tractable – problems that have a polynomial (or less) time solution are called tractable problems intractable – problems that have no polynomial (or less) time solution are called intractable problems 4.4.4.6 Computable and non-computable problems Be aware that some problems cannot be solved algorithmically 4.4.4.7 Halting problem 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 4.4.5 A model of computation 4.4.5.1 Turing machine 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: a finite set of states in a state transition diagram a finite alphabet of symbols an infinite tape with marked-off squares a sensing head that can travel along the tape, one square at a time.
AQA-A-Level-Computer-Science-7517-PLC.docx