The extremal route problem of permutations under constraints in the form of preceding conditions is investigated. It is supposed that an executer leaves the initial point (the base) after which he visits a system of megalopolises (finite goal sets) and performs some work on each megalopolis. The cost functions for executor permutations and interior works depend on the “visiting moment” that can correspond to the real time or can also correspond to the natural regular succession (the first visiting, the second visiting, and so on). An economic variant of the widely interpreted dynamic programming method (DPM) is constructed. On this basis an optimal computer realized algorithm is constructed. A variant of a greed algorithm is proposed.

We review some methods and approaches to programming discrete problems for Programmable Logic Controllers on the example of constructing PLC-programs for controling a code lock. For these approaches we evaluate the usability of the model checking method for the analysis of program correctness with respect to the automatic verification tool Cadence SMV. Some possible PLC-program vulnerabilities arising at a number approaches to programming of PLC are revealed.

We study the performance of the Trickles protocol which is a transport-layer protocol for the TCP/IP architecture. We have implemented the original model of the Trickles protocol for the ns-2 simulator and defined performance metrics which were measured using ns-2 simulations.

The peculiarities of transforming functional dataflow parallel programs into programs with finite resources are analysed. It is considered how these transformations are affected by the usage of asynchronous lists, the return of delayed lists and the variation of the data arrival pace relative to the time of its processing. These transformations allow us to generate multiple programs with static parallelism based on one and the some functional dataflow parallel program.

In the article we have proved that any countable ideal in the semi-lattice of the De is the intersection of two principal ideals generated by quasi-minimal covers for this ideal.

It is shown that the derived subgroup of the free group is not first-oder definable.

It is considered the minimization of a quadratic polynomial on the set of all points of a multidimensional space, coordinates of which are either zero or one. Some restrictions are imposed on the arrangement of the minimum points when there are many such points.

combinatorial optimization, quadratic programming, empty quadric, polytope, facet

The paper consider a mathematical model of a concurrent system, the special case of which is an asynchronous system. Distributed asynchronous automata are introduced here. It is proved that Petri nets and transition systems with independence can be considered as distributed asynchronous automata. Time distributed asynchronous automata are defined in a standard way by correspondence which relates events with time intervals. It is proved that the time distributed asynchronous automata generalize time Petri nets and asynchronous systems.

We have obtain of some distribution-independent results on the k-neighborliness of random polytopes. They confirm the well-known Gale conjecture for the general case.

We investigate the firmness of code noising to the statistical analysis of the evesdropped messages of repeated repetition. We give a structural description of the model of secured data transmission and construct an information analytical model of the observer. The formula for computing amount of volume, necessary for distinguishing alternative hypothesis with given errors of first and second sorts by sample of codewords is obtained.

The article describes a method of finding business process invariants basing on a given model in eEPC notation. The method uses an original translation process to build a Petri net corresponding to the source eEPC model, to find its invariants and to translate them back into the eEPC notation. An optimized method of finding Petri net invariants is also offered, based on estimating possible values for separate vector elements (and a group of elements) and combining these values with each other to receive a Petri net invariant. The resulting business process invariants may be used to create integration testing scenarios for an implemented automation system.

The classes of graphs closed regarding the set-theoretical operations of union and intersection are considered. Some constructive descriptions of the closed graph classes are set by the element and operational generating basses. Such bases have been constructed for many classes of graphs. The backward problems (when the generating bases are given and it is necessary to define the characteristic properties of corresponding graphs) are solved in the paper. Subsets of element and operational bases of the closed class of all graphs are considered as generating bases.

A formal model of the Russian verse based on the accentual segmentation of its structure is offered and considered. A context-free grammar (in N. Chomsky’s sense) which generates correct rhythmic forms of the presented model is constructed.

We summarize the results of the First Yaroslavl Summer School on Discrete and Computational Geometry and asses its future perspectives.