Разделяемый алгоритм перебора разбиений конечного множества на подмножества заданной мощности

Standard

Разделяемый алгоритм перебора разбиений конечного множества на подмножества заданной мощности. / Ковшов, А.М.

In: ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ, Vol. 16, No. 1, 03.2020, p. 50-61.

Research output: Contribution to journal › Article › peer-review

Author

Ковшов, А.М. / Разделяемый алгоритм перебора разбиений конечного множества на подмножества заданной мощности. In: ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ. 2020 ; Vol. 16, No. 1. pp. 50-61.

BibTeX

@article{f4a988f67a064cbdb9c81385284a2021,

title = "Разделяемый алгоритм перебора разбиений конечного множества на подмножества заданной мощности",

abstract = "Представлен итерационный алгоритм перебора разбиений конечного множества, состоящего из различимых элементов, на подмножества заданной мощности. Мощности некоторых подмножеств могут совпадать. Весь алгоритм состоит из двух независимых алгоритмов. Первый алгоритм определяет, в подмножество какой мощности при разбиении попадет каждый элемент исходного множества. Для этого подмножества одинаковой мощности объединяются в составные подмножества. Производится распределение элементов исходного множества по составным подмножествам. Разбиения описываются индексным массивом, указывающим, в какое составное подмножество распределяется каждый элемент исходного множества. Перебор разбиений исходного множества по составным подмножествам сводится к перебору всех перестановок индексов в массиве. Второй алгоритм распределяет элементы внутри каждого составного подмножества по равномощным подмножествам. При этом для каждого составного подмножества создается свой индексный массив, описывающий, в какое подмножество попадает каждый элемент составного подмножества. Перебор всех разбиений составного подмножества по равномощным подмножествам сводится к частичному перебору перестановок индексов. Перестановки всех индексных массивов перебираются в лексикографическом порядке. Такое построение алгоритма позволяет разбить весь перебор на независимые части и использовать параллельные вычисления. Рассмотрен пример, показывающий состоятельность алгоритма и ускорение получения результата при применении параллельных вычислений.",

keywords = "параллельные вычисления, алгоритмы перебора, разделяемые алгоритмы, exhaustive search algorithms, parallel computing, PERMUTATIONS, GENERATION, Parallel computing, Exhaustive search algorithms",

author = "А.М. Ковшов",

note = "Ковшов А. М. Разделяемый алгоритм перебора разбиений конечного множества на подмножества заданной мощности // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. 2020. Т. 16. Вып. 1. С. 50–61. https://doi.org/10.21638/11702/spbu10.2020.105",

year = "2020",

month = mar,

doi = "10.21638/11702/spbu10.2020.105",

language = "русский",

volume = "16",

pages = "50--61",

journal = " ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ",

issn = "1811-9905",

publisher = "Издательство Санкт-Петербургского университета",

number = "1",

}

RIS

TY - JOUR

T1 - Разделяемый алгоритм перебора разбиений конечного множества на подмножества заданной мощности

AU - Ковшов, А.М.

N1 - Ковшов А. М. Разделяемый алгоритм перебора разбиений конечного множества на подмножества заданной мощности // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. 2020. Т. 16. Вып. 1. С. 50–61. https://doi.org/10.21638/11702/spbu10.2020.105

PY - 2020/3

Y1 - 2020/3

N2 - Представлен итерационный алгоритм перебора разбиений конечного множества, состоящего из различимых элементов, на подмножества заданной мощности. Мощности некоторых подмножеств могут совпадать. Весь алгоритм состоит из двух независимых алгоритмов. Первый алгоритм определяет, в подмножество какой мощности при разбиении попадет каждый элемент исходного множества. Для этого подмножества одинаковой мощности объединяются в составные подмножества. Производится распределение элементов исходного множества по составным подмножествам. Разбиения описываются индексным массивом, указывающим, в какое составное подмножество распределяется каждый элемент исходного множества. Перебор разбиений исходного множества по составным подмножествам сводится к перебору всех перестановок индексов в массиве. Второй алгоритм распределяет элементы внутри каждого составного подмножества по равномощным подмножествам. При этом для каждого составного подмножества создается свой индексный массив, описывающий, в какое подмножество попадает каждый элемент составного подмножества. Перебор всех разбиений составного подмножества по равномощным подмножествам сводится к частичному перебору перестановок индексов. Перестановки всех индексных массивов перебираются в лексикографическом порядке. Такое построение алгоритма позволяет разбить весь перебор на независимые части и использовать параллельные вычисления. Рассмотрен пример, показывающий состоятельность алгоритма и ускорение получения результата при применении параллельных вычислений.

AB - Представлен итерационный алгоритм перебора разбиений конечного множества, состоящего из различимых элементов, на подмножества заданной мощности. Мощности некоторых подмножеств могут совпадать. Весь алгоритм состоит из двух независимых алгоритмов. Первый алгоритм определяет, в подмножество какой мощности при разбиении попадет каждый элемент исходного множества. Для этого подмножества одинаковой мощности объединяются в составные подмножества. Производится распределение элементов исходного множества по составным подмножествам. Разбиения описываются индексным массивом, указывающим, в какое составное подмножество распределяется каждый элемент исходного множества. Перебор разбиений исходного множества по составным подмножествам сводится к перебору всех перестановок индексов в массиве. Второй алгоритм распределяет элементы внутри каждого составного подмножества по равномощным подмножествам. При этом для каждого составного подмножества создается свой индексный массив, описывающий, в какое подмножество попадает каждый элемент составного подмножества. Перебор всех разбиений составного подмножества по равномощным подмножествам сводится к частичному перебору перестановок индексов. Перестановки всех индексных массивов перебираются в лексикографическом порядке. Такое построение алгоритма позволяет разбить весь перебор на независимые части и использовать параллельные вычисления. Рассмотрен пример, показывающий состоятельность алгоритма и ускорение получения результата при применении параллельных вычислений.

KW - параллельные вычисления

KW - алгоритмы перебора

KW - разделяемые алгоритмы

KW - exhaustive search algorithms

KW - parallel computing

KW - PERMUTATIONS

KW - GENERATION

KW - Parallel computing

KW - Exhaustive search algorithms

UR - http://www.scopus.com/inward/record.url?scp=85090160601&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/e000323b-01c6-3e64-9271-2c56f5bc9dbb/

U2 - 10.21638/11702/spbu10.2020.105

DO - 10.21638/11702/spbu10.2020.105

M3 - статья

VL - 16

SP - 50

EP - 61

JO - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ

JF - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ

SN - 1811-9905

IS - 1

ER -

ID: 53724390