CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2023/2024

# Algebraic structures in theoretical informatics

Code Completion Credits Range Language
01ALTI ZK 3 1+1 Czech
Garant předmětu:
Edita Pelantová, Severin Pošta
Lecturer:
Severin Pošta, Milena Svobodová
Tutor:
Severin Pošta, Milena Svobodová
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] Jean-Michel 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:
Time-table for winter semester 2023/2024:
Time-table is not available yet
Time-table for summer semester 2023/2024:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2024-08-08
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet3947206.html