Оптимизирующие преобразования потоковых программ
Finite state transducers over semigroups can be regarded as a formal model of sequential reactive programs. In this paper we introduce a uniform tech- nique for checking eectively functionality, k-valuedness, equivalence and inclusion for this model of computation in the case when a semigroup these transducers op- erate over is embeddable in a decidable group.
We consider single machine scheduling problems. N jobs that must be processed on the machine are given. Machine is ready to star processing since time 0 and can handle only one job at a time. Preemptions are not allowed. Each job $j$ is characterized by processing time $p_j$, due date $d_j$, and release date $r_j$. Our goal is to construct a schedule of processing that minimizes total tardiness of the jobs. We propose a new approach to construct approximate solutions with guaranteed absolute error for the problem. The approach consists in finding an instance of the problem, closest to a given instance in certain metric and using its optimal schedule as an approximate solution for the given instance. The approach can be generalized to scheduling problems with other objective functions.
The textbook contains necessary information about universal and classical algebras, systems of axioms for the basic algebraic structures (groupoid, monoid, semi-groups, groups, partial orders, rings, fields). The basic cryptographic algorithms are described. Error-correcting codes - linear, cyclic, BCH are considered. Algorithms for designing of such codes are given. Many examples are shown. It is put in a basis of the book long-term experience of teaching by authors the discipline «Discrete mathematics» at the business informatics faculty, at the computer science faculty of National research university Higher school of economics, and at the automatics and computer technique faculty of National research university Moscow power engineering institute. The book is intended for the students of a bachelor degree, trained at the computer science faculties in the directions 09.03.01 Informatics and computational technique, 09.03.02 Informational systems and technologies, 09.03.03 Applied informatics, 09.03.04 Software Engineering, and also for IT experts and developers of software products.