Про подібність задач комбінаторної оптимізації та універсальність алгоритмів
Розглянуто властивість подібності, яка має місце в комбінаториці та комбінаторній оптимізації. Виявлено різноманітні ознаки, за якими вона визначається для задач, що відносяться до різних класів. Описано задачі комбінаторної оптимізації, які подібні за аргументом цільової функції, а в комбінаториці...
Saved in:
| Published in: | Системні дослідження та інформаційні технології |
|---|---|
| Date: | 2013 |
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2013
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/85132 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Про подібність задач комбінаторної оптимізації та універсальність алгоритмів / Н.К. Тимофієва // Системні дослідження та інформаційні технології. — 2013. — № 4. — С. 27-37. — Бібліогр.: 11 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862647674189119488 |
|---|---|
| author | Тимофієва, Н.К. |
| author_facet | Тимофієва, Н.К. |
| citation_txt | Про подібність задач комбінаторної оптимізації та універсальність алгоритмів / Н.К. Тимофієва // Системні дослідження та інформаційні технології. — 2013. — № 4. — С. 27-37. — Бібліогр.: 11 назв. — укр. |
| collection | DSpace DC |
| container_title | Системні дослідження та інформаційні технології |
| description | Розглянуто властивість подібності, яка має місце в комбінаториці та комбінаторній оптимізації. Виявлено різноманітні ознаки, за якими вона визначається для задач, що відносяться до різних класів. Описано задачі комбінаторної оптимізації, які подібні за аргументом цільової функції, а в комбінаториці — за способом утворення та упорядкування комбінаторних конфігурацій. Завдяки цій властивості їхні множини генеруються одним і тим же алгоритмом або його модифікацією. Показано, що деякі задачі комбінаторної оптимізації, що відносяться до різних класів, розділяються на подібні підзадачі, які розв’язуються за однією обчислювальною схемою. Властивість подібності, яка характерна для задач цього класу, визначає їхню універсальність, завдяки якій вони розв’язуються за одним і тим же методом. Вивчення та використання цієї властивості в комбінаторній оптимізації в подальшому дозволить зводити нерозв’язні задачі до розв’язних.
Рассмотрено свойство подобия, которое имеет место в комбинаторике и комбинаторной оптимизации. Выявлены различные признаки, по которым оно определяется для задач, относящихся к разным классам. Описаны задачи комбинаторной оптимизации, которые подобны по аргументу целевой функции, а в комбинаторике — по способу образования и упорядочения комбинаторных конфигураций. Благодаря этому свойству их множества генерируются одним и тем же алгоритмом или его модификацией. Показано, что некоторые задачи комбинаторной оптимизации, относящиеся к разным классам, разделяются на подобные подзадачи, решаемые по одной вычислительной схеме. Свойство подобия, которое характерно для задач этого класса, определяет их универсальность, благодаря которой они решаются одним и тем же методом. Изучение и использование этого свойства в комбинаторной оптимизации в дальнейшем позволит сводить неразрешимые задачи к разрешимым.
A property of similarity which takes place in combinatorics and combinatorial optimization is examined. The various signs, after which it is determined for problems, which belong to the different classes, are defined. The problems of combinatorial optimization, which are similar by the argument of objective function, and in combinatorics – by the method of formation and ordering of combinatorial configurations, are described. Due to this property their sets are generated by the same algorithm or its modification. It is shown that some combinatorial optimization problems, which belong to different classes are divided into similar subproblems that are solved by the same calculable scheme. The property of similarity, which is typical for this class of problems, determines their universality by which they are solved by the same method. A study and use of this property in the combinatorial optimization in the future will reduce the insoluble problems to the solvables.
|
| first_indexed | 2025-12-01T13:51:44Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-85132 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1681–6048 |
| language | Ukrainian |
| last_indexed | 2025-12-01T13:51:44Z |
| publishDate | 2013 |
| publisher | Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| record_format | dspace |
| spelling | Тимофієва, Н.К. 2015-07-19T16:32:06Z 2015-07-19T16:32:06Z 2013 Про подібність задач комбінаторної оптимізації та універсальність алгоритмів / Н.К. Тимофієва // Системні дослідження та інформаційні технології. — 2013. — № 4. — С. 27-37. — Бібліогр.: 11 назв. — укр. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/85132 519.816 Розглянуто властивість подібності, яка має місце в комбінаториці та комбінаторній оптимізації. Виявлено різноманітні ознаки, за якими вона визначається для задач, що відносяться до різних класів. Описано задачі комбінаторної оптимізації, які подібні за аргументом цільової функції, а в комбінаториці — за способом утворення та упорядкування комбінаторних конфігурацій. Завдяки цій властивості їхні множини генеруються одним і тим же алгоритмом або його модифікацією. Показано, що деякі задачі комбінаторної оптимізації, що відносяться до різних класів, розділяються на подібні підзадачі, які розв’язуються за однією обчислювальною схемою. Властивість подібності, яка характерна для задач цього класу, визначає їхню універсальність, завдяки якій вони розв’язуються за одним і тим же методом. Вивчення та використання цієї властивості в комбінаторній оптимізації в подальшому дозволить зводити нерозв’язні задачі до розв’язних. Рассмотрено свойство подобия, которое имеет место в комбинаторике и комбинаторной оптимизации. Выявлены различные признаки, по которым оно определяется для задач, относящихся к разным классам. Описаны задачи комбинаторной оптимизации, которые подобны по аргументу целевой функции, а в комбинаторике — по способу образования и упорядочения комбинаторных конфигураций. Благодаря этому свойству их множества генерируются одним и тем же алгоритмом или его модификацией. Показано, что некоторые задачи комбинаторной оптимизации, относящиеся к разным классам, разделяются на подобные подзадачи, решаемые по одной вычислительной схеме. Свойство подобия, которое характерно для задач этого класса, определяет их универсальность, благодаря которой они решаются одним и тем же методом. Изучение и использование этого свойства в комбинаторной оптимизации в дальнейшем позволит сводить неразрешимые задачи к разрешимым. A property of similarity which takes place in combinatorics and combinatorial optimization is examined. The various signs, after which it is determined for problems, which belong to the different classes, are defined. The problems of combinatorial optimization, which are similar by the argument of objective function, and in combinatorics – by the method of formation and ordering of combinatorial configurations, are described. Due to this property their sets are generated by the same algorithm or its modification. It is shown that some combinatorial optimization problems, which belong to different classes are divided into similar subproblems that are solved by the same calculable scheme. The property of similarity, which is typical for this class of problems, determines their universality by which they are solved by the same method. A study and use of this property in the combinatorial optimization in the future will reduce the insoluble problems to the solvables. uk Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Методи оптимізації, оптимальне управління і теорія ігор Про подібність задач комбінаторної оптимізації та універсальність алгоритмів О подобии задач комбинаторной оптимизации и универсальности алгоритмов On the similarity of combinatorial optimization and universality of the algorithms Article published earlier |
| spellingShingle | Про подібність задач комбінаторної оптимізації та універсальність алгоритмів Тимофієва, Н.К. Методи оптимізації, оптимальне управління і теорія ігор |
| title | Про подібність задач комбінаторної оптимізації та універсальність алгоритмів |
| title_alt | О подобии задач комбинаторной оптимизации и универсальности алгоритмов On the similarity of combinatorial optimization and universality of the algorithms |
| title_full | Про подібність задач комбінаторної оптимізації та універсальність алгоритмів |
| title_fullStr | Про подібність задач комбінаторної оптимізації та універсальність алгоритмів |
| title_full_unstemmed | Про подібність задач комбінаторної оптимізації та універсальність алгоритмів |
| title_short | Про подібність задач комбінаторної оптимізації та універсальність алгоритмів |
| title_sort | про подібність задач комбінаторної оптимізації та універсальність алгоритмів |
| topic | Методи оптимізації, оптимальне управління і теорія ігор |
| topic_facet | Методи оптимізації, оптимальне управління і теорія ігор |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/85132 |
| work_keys_str_mv | AT timofíêvank propodíbnístʹzadačkombínatornoíoptimízacíítauníversalʹnístʹalgoritmív AT timofíêvank opodobiizadačkombinatornoioptimizaciiiuniversalʹnostialgoritmov AT timofíêvank onthesimilarityofcombinatorialoptimizationanduniversalityofthealgorithms |