| 000 | 08197nla2a2200613 4500 | ||
|---|---|---|---|
| 001 | 248087 | ||
| 005 | 20231029212143.0 | ||
| 035 | _a(RuTPU)RU\TPU\book\269755 | ||
| 090 | _a248087 | ||
| 100 | _a20140117d2013 k y0rusy50 ca | ||
| 101 | 0 | _arus | |
| 102 | _aRU | ||
| 135 | _adrnn ---uucaa | ||
| 181 | 0 | _ai | |
| 182 | 0 | _ab | |
| 200 | 1 |
_aИсследование полиномиальности метода вычисления интегрального описателя структуры графа _bЭлектронный ресурс _fВ. К. Погребной, А. В. Погребной |
|
| 203 |
_aТекст _cэлектронный |
||
| 215 | _a1 файл (333 Кб) | ||
| 225 | 1 | _aАлгоритмическое и программное обеспечение | |
| 230 | _aЭлектронные текстовые данные (1 файл : 333 Кб) | ||
| 300 | _aЗаглавие с титульного листа | ||
| 300 | _aЭлектронная версия печатной публикации | ||
| 320 | _a[Библиогр.: с. 151 (3 назв.)] | ||
| 330 | _aАктуальность исследования определяется большой потребностью в разработке эффективных методов инвариантного описания и анализа абстрактных структур графовых моделей. Цель работы заключается в обосновании полиномиальности предложенного авторами метода вычисления интегрального описателя абстрактной структуры графа. Методы исследования основываются на использовании аппарата теории графов и методов свободной и зависимой интеграции кодов структурных различий графов. В результате исследования введено понятие устойчивых групп вершин в графе и сформулированы условия возникновения и существования таких групп в процессе интеграции кодов структурных различий при вычислении интегрального описателя структуры - Integral structure descriptor (ISD). Для устойчивых групп установлен ряд свойств, которые раскрывают правомерность применения основных правил метода ISD и его полиномиальности. На основе выделенных свойств установлено, что условия существования устойчивых групп обусловлены жесткими ограничениями, а вершины разных устойчивых групп не могут порождать новые устойчивые группы. Установлен также фактор полной обособленности устойчивых групп, что в значительной мере предопределило эффективность алгоритма вычисления интегрального описателя структуры графа. Полиномиальность метода показана для наиболее трудного случая, когда графы являются однородными и содержат устойчивые группы. Для экспериментальных исследований метода ISD на языке Java разработано программное средство GraphISD и приведены некоторые результаты его работы. | ||
| 330 | _aThe relevance of the research is caused by the necessity of developing the efficient method of invariant description and analysis of abstract structures of graph models. The aim of the research is to substantiate the polinomiality of the method for computing the integral descriptor of graph abstract structure proposed by the authors. The research techniques are based on application of machinery of graph theory and methods of free and dependent integration of codes of graph structural differences. The authors have introduced the notion of stable group of vertices in graph and stated the conditions of occurrence and existence of such groups at integration of structural differences codes when computing the integral structure descriptor. A number of features which disclose the appropriateness of application of the main rules of the integral structure descriptor and its polinomiality was determined for stable groups. It was ascertained on the basis of the defined features that the conditions for stable group existing are conditioned by hard limits; the vertices of different stable groups can not generate new stable groups. The authors have also defined the factor of full isolation of stable groups that predetermined considerably the efficiency of algorithm for computing the full graph structure descriptor. Polinomiality of the technique is demonstrated for the most complex case when graphs are homogeneous and contain stable groups. The authors developed Java GraphISD software for the experimental investigations of integral structure descriptor technique and introduced the results of its operation. | ||
| 337 | _aAdobe Reader | ||
| 453 |
_tPolynomiality of method for computing graph structure integral descriptor _otranslation from Russian _fV. K. Pogrebnoy, A. V. Pogrebnoy _cTomsk _nTPU Press _d2013 _aPogrebnoy, V. K. |
||
| 461 | 1 |
_0(RuTPU)RU\TPU\book\176237 _tИзвестия Томского политехнического университета [Известия ТПУ] _fТомский политехнический университет (ТПУ) _d2000- |
|
| 463 | 1 |
_0(RuTPU)RU\TPU\book\269043 _x1684-8519 _tТ. 323, № 5 : Управление, вычислительная техника и информатика _v[С. 146-151] _d2013 _p184 с. |
|
| 610 | 1 | _aтруды учёных ТПУ | |
| 610 | 1 | _aэлектронный ресурс | |
| 610 | 1 | _aинтегральный описатель структур | |
| 610 | 1 | _aизоморфизм | |
| 610 | 1 | _aграфы | |
| 610 | 1 | _aабстрактные структуры | |
| 610 | 1 | _aустойчивые группы | |
| 610 | 1 | _aвершины | |
| 610 | 1 | _aинтеграция | |
| 610 | 1 | _aполиномиальные алгоритмы | |
| 610 | 1 | _aкоды | |
| 610 | 1 | _aобласть интеграции | |
| 610 | _aintegral structure descriptor | ||
| 610 | _agraph isomorphism | ||
| 610 | _aabstract graph structure | ||
| 610 | _astable group of vertices | ||
| 610 | _acode integration area | ||
| 610 | _aalgorithm polynomiality | ||
| 700 | 1 |
_aПогребной _bВ. К. _cспециалист в области информатики и вычислительной техники _cпрофессор Томского политехнического университета, доктор технических наук _f1942- _gВладимир Кириллович _2stltpush _3(RuTPU)RU\TPU\pers\19853 _6z01712 |
|
| 701 | 1 |
_aПогребной _bА. В. _gАлександр Владимирович _6z02712 |
|
| 712 | 0 | 2 |
_aНациональный исследовательский Томский политехнический университет (ТПУ) _bИнститут кибернетики (ИК) _bКафедра информатики и проектирования систем (ИПС) _h124 _2stltpush _3(RuTPU)RU\TPU\col\18697 _6z01700 |
| 712 | 0 | 2 |
_aНациональный исследовательский Томский политехнический университет (ТПУ) _c(2009- ) _2stltpush _3(RuTPU)RU\TPU\col\15902 _6z02701 |
| 801 | 2 |
_aRU _b63413507 _c20190520 _gPSBO |
|
| 856 | 4 | _uhttp://earchive.tpu.ru/bitstream/11683/5076/1/bulletin_tpu-2013-323-5-24.pdf | |
| 942 | _cCF | ||