COMPUTER LINEAR ALGEBRA SYSTEM
The aim of the project is to design a basic linear algebra system
as a very simplified analogy of usual computer algebra systems,
like REDUCE, Maple, Axiom, etc.
It should include algorithms for matrix multiplication,
for inverting matrices, computing determinants, computing
the rank of a matrix and producing a maximal subset of linear
independent vectors, solving systems of linear equations.
The algorithms for solving these problems could be straightforward
classic ones, like Gauss algorithm.
Once this is done, an attempt should be made to implement more
advanced (and more efficient) algorithms.
The system should have a convenient interactive interface with
an ability to extend by adding new commands.
Existing systems could be used as examples,
but all programming is supposed to be original.
Background: some modest knowledge of mathematics
Computer: BUCS computers
Documentation: see NNV
PROGRAM FOR SOLVING TWO-PERSON GAMES
The aim is to design an application for finding
optimal strategies in finite two-person games.
Such games are called bimatrix. They include
all possible situations in which two parties
have finite number of possible ways to act
(strategies) and the outcomes lead to payoffs
depending on the pair of chosen strategies.
Chess is an example, though hardly tractable,
stone-paper-scissors is another, very
simple to solve. The application should
be able to accept any pair of pay-off matrices
as an input and to output optimal mixed
strategies. For games usually defined in the
positional form an appropriate universal representation
of the input should be designed.
The project includes the stage of learning the
background game-theoretical material including the
existing algorithms for solving bimatrix games.
Background: some modest knowledge of mathematics
Computer: BUCS computers
Documentation: see NNV
PROGRAM FOR TEACHING GAME THEORY
The aim of the project is to design a program which
will help to explain and illustrate the basic concepts
of the theory of games.
When the number of strategies of one of the players
in a matrix game is small (say, two or three) then
the optimal strategies can be found by drawing
certain two- or three-dimensional pictures.
The program will draw such pictures and explain
interactively some elements of the theory.
Background: very modest knowledge of mathematics
Computer: BUCS computers
Documentation: see NNV
ROBOT MOTION PLANNING
The aim is to design a graphical application
for robot motion planning on the plane
in the presence of polygonal obstacles.
In one version of the problem the robot is
considered as a point and we are looking for
a shortest piece-wise linear path connecting
"start" and "finish".
In another version the robot is a polygon,
and the aim is to decide whether it is possible
for him to pass through a corridor of a complex
form, and if yes, to plane the move.
Background: very modest knowledge of mathematics
Computer: BUCS computers
Documentation: see NNV
DOMINO PARTNERS
The game of domino is usually played between two teams of two
players in each. Since it might be hard to find enough partners
willing to play, it's desirable to have a computer program
which can model one, two or three players, breaking them in
teams, as required. The project consists of designing such a
program together with a graphic interface to show moves.
Background: non special
Computer: BUCS
Documentation: none