Abstract

Content

Introduction
1. Theme urgency
2. Goal and tasks of the research
3. A review of research and development
3.1 Overview of national sources
3.2 Overview of local sources
3.3 Overview of national sources
Conclusion
References

Introduction

The scientific work of students considered topics related to the geometric analysis of machine-gun media, graphs and other discrete structures. One of the objectives of this subject is the problem of describing the structure of the object based on information obtained during traversal of a graph on its boundary. Similar problems arise in robotics, and molecular physics: model maps of the environment, the object model. A number of papers devoted to the structure of the object recognition problem, which considered the case of solving such problems using a single machine (the agent). In this paper we propose an algorithm for solving the problem of recognition with the two agents. As an object model used an undirected graph. The first agent-investigator (AI) moves the original count and the transfer of information to the agent-second experimenter (AE). The second agent received information describes the structure of the graph.

1. Theme urgency

Topic was relevant back in the 50s of last century, when the first articles began to appear Shannon K., which is actually considered the problem of finding an automaton-mouse specific purpose in the labyrinth, which largely determined the subject areas for the coming years. After 60 years, the topic remains relevant and is often used in the creation of games, software and other products.

2. Goal and tasks of the research

Developing a new algorithm for the graph consisting of several strongly connected subgraphs connected by bridges. Need to develop such algorithms AI agent movement on the original graph G with the transfer of information about it, and restore the graph of AE agent from the data obtained in the form of a formula that the AI in a finite number of steps regardless of the initial placement of bypass of the internal vertices of G are all boundary vertices, step by passing the information on which the AE after a finite number of steps will describe the graph of P, is isomorphic to the original graph G.

The main objectives of the study:
Develop an algorithm for AI and AE, to circumvent and recognition of the graph.
Create a program to implement these algorithms.

Object of research: automatic analysis of graphs

Subject of research: methods and algorithms for reconstructing the structure of graphs consisting of a strongly-connected subgraphs, connected by bridges

As part of the master plan to get the actual scientific results in the following areas:

Development of an efficient algorithm for graph traversal mosaic structure consisting of strongly connected subgraphs connected by bridges.

Development of an efficient algorithm for the restoration of the graph.

Create cross-platform program to bypass the graph.

For the experimental evaluation of the theoretical results and the formation of the foundation of further research, as the practical results will be cross-platform development, customized and functional system to work with the graph:

Using a cross-platform class library Qt. Writing code in C + +. Ability to manage the process of recognition. Ability to save and restore the file.

3. An approach to the unification of synthesis of Moore FSM on FPGA

My supervisor Shatokhina Natalia, published a work entitled Recognition of the mosaic structure of the graph collective of agents, which describes how to work with a graph of the mosaic structure of a special type of strongly connected graph.

Recognition of the graph

The recognition process consists of two algorithms. The first algorithm, Bypass describes the movement of the AI for an unknown graph G, and generate information for the AE. The second algorithm, "Recovery," presents an analysis of the information received, on the basis of which creates a symbolic description of the graph F is isomorphic to the original G.

Algorithm, Bypass of AI.

It is assumed that an agent at random can be placed at any vertex of the graph, so the algorithm consists of two stages. In the first stage, if you want the AI goes to the border, and the second phase of the AI avoids Count counter-clockwise along the boundary edges as long as no return to the top to the boundary. AI algorithm to the boundary. The agent placed in an arbitrary vertex v, determine its extent, if it is an internal vertex, ie deg (v) = 6, then moves on diametrically opposite edge relative to the first encountered edge until the next summit. This procedure repeats until it finds a boundary vertex, select the first boundary edge by turning counterclockwise, which marks the marker. Graph traversal algorithm for boundary vertices. Further movement of the agent is on the boundary of the graph in a counterclockwise direction, starting from the found vertices and edges. The agent moves to the next vertex of the selected edge, capturing a letter-direction of their movement. Further, the AI checks whether the selected marker labeled edge. If it is not marked, he sends a letter AE and continues to move, otherwise the AI completes its work. Algorithm, "Bypass" consists of two parts. The first part can be absent. Lemma 1. If the tile graph of n vertices, the maximum path on the internal vertices of the graph in this direction does not exceed l = (n-1) / 3. Lemma 2. Any route to the internal vertices of the graph in the selected direction of movement is not closed. Original graph G can be more complicated than the basic structure, which satisfies the following. Lemma 3. The route p along the boundary vertices of G When calculating the time complexity of the case: to enter the border of the graph according to Lemma 1 takes time (n-1) / 3, ie O (n); by Lemma 3 bypass on the boundary does not exceed 2n, then estimated as O (n) steps. Capacitive complexity of E (n) is absent, because the agent did not want to keep.

Picture 1. - Principle of operation AI(to the boundary and a further detour)

Algorithm Restoration of the AE.

The algorithm analyzes a string of directions generated and transmitted to the AI. Initially, searches for points of inflection. If the points are then determined by the identifier of the inverse base structure containing the next inflection point, as the second top of the route. Produced string conversion, building counters Sch_vv internal and boundary vertices Sch_gv, joining this structure to the graph, which is reflected in the formula by adding the sign - corresponding to the fragment. If there are no such points, then re-viewed, first string to search for identifiers of base structures. Whenever there is such an identifier is removed from the string matching substring, and decrease the value Sch_vv Sch_gv, Department of the structure of the graph, and adding to the formula with the sign + corresponding to the fragment. The algorithm of recognition by two views of a string. If there is at least one point of inflection, then added to the graph corresponding to the basic structure of the number of vertices and sets an implicit enumeration u: V(G∪G)→V(H∪G), where G 'of graph included. The numbering of u (v) = Sch_vv or u (v) = Sch_gv, for all v∈G'. This numbering is a bijection, since addition of basic structures is performed one to one according to their IDs. When performing the separation in a graph H creates an implicit enumeration d: V(G')→V(H) of vertices of G into the vertices of a graph H, the vertices that are contained in a detachable base structure. The equality d (v) = t, where t = or t = Sch_vv Sch_gv. This numbering is also a bijection, since removal of basic structures is performed one to one according to their IDs. This proves the following towers. Theorem 1. Performing recognition algorithms, the agents recognize any graph G up to isomorphism. When calculating the time complexity of algorithm AE is taken into account that the recognition of the structure of the graph is performed by two-time view of the string whose length can not exceed 2n letters, ie, time complexity is estimated as follows. The accession process of the underlying structures is performed no more than the possible number of inflection points, and it is no more than n / 2 steps. The process of cutting off the underlying structures is performed no more than the possible number of corners in the graph, ie no more than n / 2 steps. The second line runs show no more than 2n steps. Consequently, the total time complexity is estimated as T (n) = O (n). Thus, the joint work of the AI and AE is estimated as O (n). Capacitive complexity of E (n) is determined by the complexity of list row direction S, the set of boundary vertices V'⊂V, and a string of formulas F, the complexity is determined by the values of O (n), O (n), O (n). Due to limitations on the amount of detailed descriptions of the algorithms are omitted.

3.1 Overview of national sources

Kapitonova Y., A. Letichevsky "The mathematical theory of design of computer systems"
The fundamentals of mathematical tools and modern methods of data conversion system design: hardware computers, software and software systems, control systems and data processing, based on the use of computer tehniki. Pervaya part provides an overview of the basic mathematical models of computing systems. The second part contains an account of the practical methods of designing different types of systems — the hardware of computers, serial and parallel programs, a component of a system-wide matematiki.Dlya mathematicians and engineers - developers of hardware and software, as well as undergraduate and graduate students in computer science and computer engineering.

V. Kudryavtsev, S. Ushchumlich, G. Kilibarda. "The behavior of automata in labyrinths"
A survey of more than 80 works made over the past 20 years, the behavior of systems of automata in labyrinths. Stand the basic concepts, problems, achievements, problem-solving methods and open problems. The main assertion in some cases are in a stronger form in comparison with that of the authors. The article also contains new results on the problem of traversing labyrinths by automata.

3.2 Overview of local sources

In the Donetsk National Technical University has a publication entitled "Recognition of the graph of the mosaic structure of a group of agents," the authors: Shatokhina N., Shatokhin P.
The problem of analysis of discrete structures, represented by a graph of special form. In particular, we consider the problem of describing the structure of the graph based on information obtained during its traversal of the boundary. An algorithm for solving the problem, it gives an estimate of time and space complexity.

3.3 Overview of national sources

Topics of graph theory in national sources is virtually no information, but our people are very interested in this topic, often publishing new articles, algorithms, developments and solutions.

Conclusion

In the course of this work, we calculated were used for matrix multiplication and other mathematical operations. The algorithm of reconstructing the structure of the graph as a formula that reflects the composition of the original graph as a combination of basic structures.

Sergey Kobernyuk

Faculty institute of informatics and artificial intelligence

Department Intelligent Software Systems

Speciality Software Systems

Recognition of a group of agents of the graph of the mosaic structure consisting of highly-connected subgraphs, connected by bridges

Scientific adviser: Ph.D., Docent Shatohina Natalia