Exact Real Arithmetics

Lecturer:

Petr Kůrka (gar.)

Tutor:

Petr Kůrka (gar.)

Supervisor:

Department of Computer Science

Synopsis:

Common properties of number systems and corresponding arithmetic algorithms, theory of algorithms in continuous domains and their computational complexity, algorithms and data structures for infinite words.

Requirements:

Syllabus of lectures:

1. Cantor space and symbolic representation of compact metric spaces.

2.Symbolic dynamics: subshifts and cellular automata.

3.Number systems: positional number systems, continued fractions, Moebius systems.

4.Redundancy, convergence speed and approximation in number systems.

5.Constructive analysis: constructive (algorithmic) real numbers and constructive real functions.

6.Complexity of real functions, power series and Gauss continued fractions.

7.Domain theory: ordering and lattices, monotone functions and their fixed points, recursive definitions.

8.Arithmetic algorithms: integer arithmetics, interval arithmetics, algorithms for redundant number systems.

9.Parallelism in arithmetic algorithms.

10.Computational complexity in arithmetic algorithms.

11.Modular and p-adic arithmetics.

Syllabus of tutorials:

Study Objective:

To teach students arithmetic and numerical algorithms for real and complex numbers that compute with any guaranteed precision.

Study materials:

P.Kurka: Topological and symbolic dynamics, Société Mathématique de France, 2003, ISBN 2856291430.

M.B.Pour-El, J.I.Richards: Computability in analysis and physics, Springer-Verlag 1989, ISBN 0387500359.

Ker-I Ko: Complexity theory of real functions, Birkhauser 1991, ISBN 3764335866.

P.Kurka, A.Kazda: Moebius number systems based on interval covers, Nonlinearity 2010.

S.Abramsky, A.Jung: Domain theory, Handbook of Logic in Computer Science vol. 3, Clarendon Press 1994, ISBN 0198537816.

Note:

Time-table for winter semester 2011/2012:

Time-table is not available yet

Time-table for summer semester 2011/2012:

Time-table is not available yet

The course is a part of the following study plans:

• Informatics (VO)