ВЫЧИСЛЕНИЕ ВЕРШИН ПОЛИТОПОВ РАЗБИЕНИЙ ЧИСЕЛ

А. С. Врублевский; В. А. Шлык

ВЫЧИСЛЕНИЕ ВЕРШИН ПОЛИТОПОВ РАЗБИЕНИЙ ЧИСЕЛ

А. С. Врублевский, В. А. Шлык

Полный текст:

PDF (Rus) |

сгенерировать QR код

Аннотация

Описывается метод генерирования вершин политопов разбиений чисел, с помощью которого авторами были вычислены все вершины и опорные вершины политопов разбиений всех n ≤ 105 и все рюкзачные разбиения n ≤ 165. Метод не требует построения всех разбиений n. Вершины определяются с помощью достаточных и необходимых условий, в трудных случаях применяется известная программа Polymake. Подробно излагаются алгоритм проверки критерия, характеризующего разбиения, являющиеся выпуклыми комбинациями двух других; методика применения двух комбинаторных операций, преобразующих известные вершины в новые вершины, и способ применения программы Polymake для распознавания небольшого (для малых n) числа разбиений, являющихся выпуклыми комбинациями трех и более разбиений. Представляются результаты вычислений и формулируются новые проблемы, к которым приводят полученные данные о числах вершин и опорных вершин политопов разбиений чисел.

Список литературы

1. Эндрюс, Г. Теория разбиений / Г. Эндрюс. - М. : Наука, 1982. - 256 с.

2. Эйлер, Л. Введение в анализ бесконечных / Л. Эйлер. - М. : Гос. изд. физ.-мат. лит., 1961. - Т. 1. - 316 с.

3. Dickson, L.E. History of the Theory of Numbers / L.E. Dickson. - Vol. II : Diophantine Analysis. - Washington : Carnegie Inst., 1919. - 520 p.

4. Шлык, В.А. Политопы разбиений чисел / В.А. Шлык // Весці Нац. акад. навук Беларусi. Сер. фiз.-мат. навук. - 1996. - № 3. - С. 89-92.

5. Shlyk, V.A. Polytopes of partitions of numbers / V.A. Shlyk // European J. Combin. - 2005. - Vol. 26, № 8. - P. 1139-1153.

6. Емеличев, В.А. Многогранники, графы, оптимизация (комбинаторная теория многогранников) / В.А. Емеличев, М.М. Ковалев, М.К. Кравцов. - М. : Наука, 1981. - 341 с.

7. Шлык, В.А. Комбинаторные операции порождения вершин политопа разбиений чисел / В.А. Шлык // Докл. Нац. акад. наук Беларуси. - 2009. - Т. 53, № 6. - С. 27-32.

8. Холл, М. Комбинаторика / М. Холл. - М. : Мир, 1970. - 424 с.

9. Gupta, H. Tables of partitions / H. Gupta, C.E. Gwyther, C.P. Winter // Royal society mathematical tables. - Vol. 4. - Cambridge : University Press, 1958. - 132 p.

10. Sloane, N.J.A. a(n) = number of partitions of n (the partition numbers) [Electronic resource] / N.J.A. Sloane. - 2010. - Mode of access : http://oeis.org/A000041. - Date of access : 11.10.2015.

11. Zoghbi, A. Fast algorithms for generating integer partitions / A. Zoghbi, I. Stojmenovic // Intern. J. Computer Math. - 1998. - Vol. 70. - P. 319-332.

12. Рейнгольд, Э. Комбинаторные алгоритмы: теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део. - М. : Мир, 1980. - 476 с.

13. Nijenhius, A. A method and two algorithms on the theory of partitions / A. Nijenhius, H.S. Wilf // J. Comb. Theory A. - 1975. - Vol. 18. - P. 219-222.

14. Riha, W. Efficient algorithms for doubly and multiply restricted partitions / W. Riha, K.R. James // Algorithm 29. Computing. - 1976. - Vol. 16. - P. 163-168.

15. Constant time generation of integer partitions / K. Yamanaka [et al.] // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. - 2007. - Vol. E90-A, № 5. - P. 888-895.

16. Knuth, D.E. Generating all partitions. Pre-fascicle 3B of The Art of Computer Programming. A draft of sections 7.2.1.4-5 [Electronic resource] / D.E. Knuth. - 2004. - Mode of access : http://www.cs.utsa.edu/~wagner/knuth/fasc3b.pdf. - Date of access : 11.10.2015.

17. Kelleher, J. Generating all partitions: a comparison of two encodings [Electronic resource] / J. Kelleher, В. O'Sullivan. - 2009. - Mode of access : http://arxiv.org/pdf/0909.2331v1.pdf. - Date of access : 11.10.2015.

18. Opdyke, J.D. A unified approach to algorithms generating unrestricted and restricted integer compositions and integer partitions / J.D. Opdyke // J. Math. Model. Algor. - 2010. - Vol. 9, № 1. - P. 53-97.

19. Stojmenovic, I. Generating all and random instances of a combinatorial object / I. Stojmenovic // Handbook of applied algorithms: solving scientific, engineering, and practical problem. - Hoboken : John Wiley&Sons, 2008. - P. 1-38.

20. Shlyk, V.A. Number of vertices of the integer partition polytope [Electronic resource] / V.A. Shlyk. - 2012. - Mode of access : http://oeis.org/A203898. - Date of access : 11.10.2015.

21. Shlyk, V.A. Number of support partitions-vertices [Electronic resource] / V.A. Shlyk. - 2012. - Mode of access : http://oeis.org/A203899. - Date of access : 11.10.2015.

22. Ehrenborg, R. Number of knapsack partitions of n [Electronic resource] / R. Ehrenborg. - 2005. - Mode of access : http://oeis.org/A108917. - Date of access : 11.10.2015.

23. Шлык, В.А. Критерий представления разбиений чисел в виде выпуклой комбинации двух разбиений / В.А. Шлык // Вестник БГУ. Сер. 1. - 2009. - № 2. - С. 109-114.

24. Shlyk, V.A. Integer partitions from the polyhedral point of view / V.A. Shlyk // Electron. Notes Discrete Math. - 2013. - Vol. 43. - P. 319-327.

25. Shlyk, V.A. Polyhedral approach to integer partitions / V.A. Shlyk // Journal of Combinatorial Mathematics and Combinatorial Computing. - 2014. - Vol. 89. - P. 113-128.

26. Gawrilow, E. Polymake: a framework for analyzing convex polytopes / E. Gawrilow, E.M. Joswig // Polytopes - combinatorics and computation. - Basel : Birkhäuser, 2000. - P. 43-73.

27. Шлык, В.А. О вершинах политопов разбиений чисел / В.А. Шлык // Докл. Нац. акад. наук Беларуси. - 2008. - Т. 52, № 3. - С. 5-10.

28. Handbook of Mathematical Functions / M. Abramowitz, I.A. Stegun [eds]. - Applied Math. Series 55. - Washington : Government Printing Office, 1972. - 1046 p.

29. Barvinok, A.I. Polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed / A.I. Barvinok // Math. Oper. Res. - 1994. - Vol. 19. - P. 769-779.

30. Effective lattice point counting in rational convex polytopes / J.A. De Loera [et al.] // Journal of Symbolic Computation. - 2004. - Vol. 38, № 4. - P. 1273-1302.

31. Ehrenborg, R. The Möbius function of partitions with restricted block sizes / R. Ehrenborg, M.A. Readdy // Adv. in Appl. Math. - 2007. - Vol. 39, № 3. - P. 283-292.

Для цитирования:

Врублевский А.С., Шлык В.А. ВЫЧИСЛЕНИЕ ВЕРШИН ПОЛИТОПОВ РАЗБИЕНИЙ ЧИСЕЛ. Информатика. 2015;(4):34-48.

For citation:

Vroublevski A.S., Shlyk V.A. COMPUTING VERTICES OF INTEGER PARTITION POLYTOPES. Informatics. 2015;(4):34-48. (In Russ.)

Контент доступен под лицензией Creative Commons Attribution 4.0 License.

ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)

Информатика

ВЫЧИСЛЕНИЕ ВЕРШИН ПОЛИТОПОВ РАЗБИЕНИЙ ЧИСЕЛ

Полный текст:

Аннотация

Об авторах

Список литературы

Рецензия

Для цитирования:

For citation:

Логин
Пароль
	Запомнить меня

Войти

Информатика

ВЫЧИСЛЕНИЕ ВЕРШИН ПОЛИТОПОВ РАЗБИЕНИЙ ЧИСЕЛ

Полный текст:

Аннотация

Об авторах

Список литературы

Рецензия

Для цитирования:

For citation:

Использование куки-файлов