Algorithmic Problem Solving
Stc
ComputingScienceColloquium
Date: October 15
Time:
10:00 - 11:30
Room:
BBL room 420
Title: Algorithmic Problem Solving
Abstract
The modern world is critically
dependent on the reliable functioning of computer software. The sheer
scale of software systems makes their design and implementation a
highly demanding intellectual activity.
The level of rigour, accuracy and effectiveness required in reasoning
about
software is unprecedented, even when compared with reasoning in
mathematics.
Computing scientists (particularly in the Netherlands) have responded
to
this challenge by developing novel reasoning techniques for designing
efficient computer algorithms. These "correct-by-construction"
techniques emphasise the process of algorithm design, rather than the
result. That is, they are about the problem-solving skills that are
used in extracting, from an initial, informal, set of requirements, a
formal program specification, which is then transformed by a series of
design steps to a working, provably correct implementation of the
specification. Reliability of the process is ensured by emphasising
calculational skills.
The insight that has been gained has the potential of causing a
revolution in the art of effective reasoning, with immense benefits
for the way that problem solving is taught in schools and
universities.
This talk is about how I am trying to introduce first-year
undergraduates to these skills in a module entitled "Algorithmic
Problem Solving" at the University of Nottingham
http://www.cs.nott.ac.uk/~rcb/G5AAPS/G5AAPS.html.
The problems I have chosen to present in the module are typically
challenging but easily understood, and involve some sort of
construction. I use, for example, simple two-person games, where what
is to be constructed is a winning strategy. The problems are
deliberately non-mathematical in the sense that they are expressed in
natural language, without the aid of mathematical formulae.
Nevertheless, my goal is to demonstrate how the use of the mathematics
of
algorithm design is truly effective in their solution. The problems
are not new ---a Dutch audience will recognize many as having
appeared in the "Vierkant Voor Wiskunde" calendars in 1999 and 2000---
but the focus is.
The talk uses an overview of the module as a basis for a discussion of
good and bad problem-solving skills, and how they can be taught. I
will draw on my own experience (including as a student of mathematics)
and offer some views on how to make radical improvements in
mathematics education.
