The descriptions are for modules currently being taught. They should be viewed as an example of the modules we provide. All modules are subject to change for later academic years.

Non-Standard Computation (NSTC) 2013/4

Workload - Private Study - Assessment - Description - Aims - Learning Outcomes - Content - Teaching Materials - Recommended Books

Module Code COM00011H
Lecturers Susan Stepney
Taken By CS 3, CS/Math 3, CSESE 3, CSSE 3, MEng CSAI 3, MEng CSBES 3, MEng CSESE 3, MEng CSSE 3, MMath 3
Number of Credits 20
Open Assessments Assessment 1 [20%]
9th Oct → 4th Dec
Feedback: 29th Jan
Assessment 2 [80%]
9th Oct → 14th May
Feedback: 11th Jun
Reassessment [100%] TBA

Module Prerequisites

Prerequisite knowledge

None.

Workload

  • Lectures: 9 x 2hrs
  • Software Labs: 7 x 2hrs
  • Practicals: 6 x 2hrs
  • Private Study: 36hrs
  • Assessment: 20hrs
  • Assessment 2: 100hrs

Lectures: 9 x 2 hours
Software lab practicals: 7 x 2 hours
Practicals (discussion seminars): 6 x 2 hours
Assessment 1: 20 hours (open assessment, autumn term)
Assessment 2: 100 hours (open assessments, spring/summer term)
Private Study: 36 hours

Private Study

The assessments require a significant amount of private study: this has been accounted for in the workload.

Further private study time is allocated for general background reading, and for preparatory reading for the software labs and the discussion seminar sessions

Assessment

Open Assessments

Assessment will be in two parts, both of which will be given out at the beginning of the module.

Assessment 1 will run over the autumn term. The student will submit a report (no longer than 5pp) on the set problem. Credit will be given for appropriate use of the literature, for imaginative and appropriate use of material covered in the autumn term, and from other non-standard techniques discovered during private study/background reading. 20/100 marks

Assessment 2 will run over spring/summer terms. The student will submit a report (no longer than 20pp) on the set problem. Credit will be given for appropriate use of the literature, for imaginative and appropriate use of material throughout the module, and from other non-standard techniques discovered during private study/background reading. 80/100 marks

Formative Feedback

Feedback is provided by the lecturer and peers in interactive seminars.

Assessment 1 feedback is provided before Assessment 2 is tackled.

Description

This module introduces Non-Standard Computation, including nature-inspired computation paradigms, and the importance of the physical embodiment of computation, as demonstrated by quantum computing. The underlying themes of chaos, self-organisation, and emergence in many of these areas will be drawn out.

Aims

The aim of this module is to introduce Non-Standard Computation, including nature-inspired computation paradigms, and the importance of the physical embodiment of computation, as demonstrated by quantum computing. The underlying themes of chaos, self-organisation, and emergence in many of these areas will be drawn out.

Learning Outcomes

On completion of this module, students should

  • have a grounding in a range of nature-inspired computing techniques, including similarities and essential differences, and their applicability
  • have an understanding of the underlying principles of complex systems, including self-organisation and emergence
  • be aware of the issues and capabilities of quantum computing
  • be able to apply these techniques and concepts to the investigation of a novel problem

Content

Lectures:

Autumn term
1. Introduction: fitness landscapes, No Free Lunch theorem, representations
2. local search : hill climbing, tabu search, simulated annealing
3. EAs 1: biological and historical background
4. EAs 2: genetic algorithms, schema theorem, genetic programming
5. Swarms, ants and termites (JT)
6. Artificial immune systems (JT)
7. A generic population-based search model
8. Growth and development: L-systems
9. Analogue computing
10. DNA, cell, membrane computing (SOK)

Spring term
11. quantum computation, entanglement (guest)
12. quantum communication: cryptography, teleportation (guest)
13. Hypercomputation
14. fractals: percolation, iterated function systems
15. cellular automata: 1D and 2D, Wolfram's classification
16. chaos, strange attractors and dynamical systems, reconstructing the attractor
17. complexity, emergence: NK landscapes, complex adaptive systems, self-organising criticality
18. nanotechnology and the grey goo problem

Seminars
The Seminars will be 2 hour long group discussions where more general points raised in the lectures can be explored in a more informal setting.

Autumn term
1. Assumptions of standard (classical) computation
2. Representations and Cost functions
3. Analogue computing: scaling issues

Spring term
4. Quantum issues
5. Embodiment
6. Wrap: Assumptions of non-standard computation

The lectures/seminars will be timetabled together, in two 2-hour slots every other week: 15 such slots (a slot is 2 lectures, or one seminar), over the Aut/Spr term. Seminars will be interwoven with lectures in these slots, to allow them to occur in the right places.

Practicals
These are sw lab based. The students will get to investigate and "play" with the following

Autumn term
1. Simulated annealing (Python)
2. Evolutionary algorithms (Python)
3. L-Systems (via L-Studio)

Spring term
4. Quantum computing (Python)
5. Iterated Function Systems (Python, and via existing applet)
6. Cellular Automata (Python, and via Golly)
7. Reconstructing the attractor

These will be timetabled every other week.

All teaching (lectures, seminars, sw labs) occurs in the even weeks of term; there is no contact time in the odd weeks of term.

Teaching Materials

Copies of slides used during lectures will be made available. Links on the module web page will point to on-line research papers/tutorials/software.

There is no one book that covers all the module material. Suitable books for parts of the material are indicated. Some of the later material does not yet have good book. Review papers, and research papers, will be suggested - some will be discussed in the seminar sessions.

Recommended Books

Rating Author Title Publisher Year
++ Eric W. Bonabeau, Marco Dorigo, Guy Theraulaz. Swarm Intelligence: from natural to artificial systems. OUP 1999
++ Jonathan Timmis, Leandro N. de Castro. Artificial Immune Systems: a new computational intelligence approach. Springer 2000
++ Melanie Mitchell. An Introduction to Genetic Algorithms. MIT Press 1996
++ Wolfgang Banzhaf, Peter Nordin, Robert E. Keller, Frank D. Francone Genetic Programming, An Introduction Morgan Kaufmann 1998
+ Christopher G. Langton, ed Artificial Life: an Overview MIT Press 1995
+ Colin P. Williams, Scott H. Clearwater Ultimate Zero and One: computing at the quantum frontier Springer 1992
+ Heinz-Otto Peitgen, Hartmut Jurgens, Dietmar Saupe Fractals for the Classroom, Parts 1 and 2. Springer 1992
+ Peter J. Bentley, ed Evolutionary Design by Computers Morgan Kaufmann 1999
+ Przemyslaw Prusinkiewicz, Aristid Lindenmayer The Algorithmic Beauty of Plants Springer 1990
Back to top

Last updated: 29th November 2013