Algebraic structures in theoretical informatics
Code  Completion  Credits  Range  Language 

01ALTI  ZK  3  1+1  Czech 
 Garant předmětu:
 Lecturer:
 Tutor:
 Supervisor:
 Department of Mathematics
 Synopsis:

The course is devoted to the applications of some special algebraic structures. The first part of the course is devoted to the Gröbner bases of ideals of polynomial rings and their use for solving of systems of algebraic equations and other applications. The second part of the course is devoted to the ring of integers of algebraic number fields, used to constructions of various representations of numbers utilized in fast effective algorithms for arithmetic operations and evaluations of elementary functions.
 Requirements:

The knowledge of basics of general algebra (01ALGE) and algebraic number theory (01TC).
 Syllabus of lectures:

1) Gröbner bases in rings of polynomials of several variables
2) Ideals of polynomial rings, basis of an ideal
3) Monomial orderings, rewrite rules
4) Buchberger algorithm
5) The solution of systems of algebraic equations, coloring of graphs, automatic theorem proving
6) Unique position representations with integer bases in the ring of integers Z and in the ring of Gaussian integers, NAF representations, arithmetic operations in these systems and finite automata.
7) Redundant representations in real and complex cases, parallel algorithms for addition and substraction and the relation to the redundancy level, online algorithms for multiplication and division.
8) Representations of numbers for shift and add algorithms for the evaluations of elementary functions.
 Syllabus of tutorials:

The first part of the exercises is devoted to the constructions of Gröbner bases of some concretely specified ideals.
The second part of the exercises is devoted to the construction of representations of numbers in various systems, algorithms for arithmetic operations in redundant systems, optimalization of parameters for given basis. Students individually present their solutions of theoretical and practical exercises.
 Study Objective:

The main goal of the course is to learn to manipulate with ideals of rings of polynomials of several variables and to construct their Gröbner bases. The second goal is to learn to manipulate various representations of numbers and to construct the algorithms for effective performing of arithmetic operations and evaluations of elementary functions.
 Study materials:

[1] JeanMichel Muller, Elementary Functions: Algorithms and Implementation, 3rd ed., Birkhauser 2016
[2] Michel Rigo, Formal languages, Automata and Numeration systems, Wiley, 2014
[3] William Adams, Phillippe Loustaunau, An Introduction to Grobner Bases, AMS, 1994
 Note:
 Further information:
 No timetable has been prepared for this course
 The course is a part of the following study plans:

 Matematická informatika (elective course)