1. SCSIT
  2. Всі випуски
  3. Випуск 694, 2011
  4. Пошук оптимальних комбінаторних структур методом розподілених обчислень

Пошук оптимальних комбінаторних структур методом розподілених обчислень

SCSIT.
2011;
Випуск 694
: cc. 62 - 66
Authors: 

Ю. Цимбал, О. Пазюк

Національний університет «Львівська політехніка», кафедра автоматизованих систем управління

Розглядається проблема пошуку оптимальних комбінаторних структур на прикладі дерев Ліча. Узагальнено критерії оптимальності для таких дерев. Запропоновано застосувати для пошуку систему розподілених обчислень на основі методу повного перебору. Наведено можливі варіанти алгоритмів пошуку, вказано їхні переваги та недоліки.

The problem of the search for optimal combinatorial designs on the example of Leech trees has been considered. Criteria of optimality for these trees have been generalized. The application of a system of distributed computing to the search on the basis of exhaustive method has been suggested. Variants of search algorithms have been presented; their advantages and disadvantages have been stated.

комбінаторна структура
дерева Ліча
розподілені обчислення
оптимальні лінійки Ґоломба
масиви Костаса
алгоритм
кладність обчислень
  1. Colbourn C.J., Dinitz J.H. Handbook of Combinatorial Designs (2 ed.). – Chapman & Hall - CRC, 2007. – 1018 p.
  2. Bloom G.S., Golomb S.W. Applications of Numbered Undirected Graphs // Proceedings of the IEEE. – 1977. – Vol. 65, No. 4, pp. 562-570.
  3. Bloom G.S., Golomb S.W. Numbered Complete Graphs, Unusual Rulers, and Assorted Applications // Theory and Applications of Graphs. – Springer, 1978, pp. 53-65.
  4. Різник В.В. Синтез оптимальних комбінаторних систем. – Львів: Вища школа. Вид-во при Львів. ун-ті, 1989. – 168 с.
  5. Наукова школа професора Володимира Різника http://iknit.lp.edu.ua/riznyk.
  6. Golomb Ruler http://mathworld.wolfram.com/GolombRuler.html.
  7. Линейка Голомба http://ru.wikipedia.org/wiki/Линейка_Голомба.
  8. Luschny P. Perfect And Optimal Rulers http://www.luschny.de/math/rulers/introe.html.
  9. Costas J.P. A Study of a Class of Detection Waveforms Having Nearly Ideal Range-Doppler Ambiguity Properties // Proceedings of the IEEE. – 1984. – Vol. 72, No. 8, pp. 996-1009.
  10. Leech J. Another Tree Labelling Problem // The American Mathematical Monthly. – 1975. – Vol. 82, No. 9, pp. 923-925.
  11. distributed.net: Project OGRhttp://www.distributed.net/ogr/.
  12. Dimitromanolakis A. Analysis of the Golomb Ruler and the Sidon Set Problems, and Determination of Large, Near-Optimal Golomb Rulers. – Thesis. Department of Electronic and Computer Engineering. Technical University of Crete, June 2002. – 118 p.
  13. Drakakis K. A Review of the Available Construction Methods for Golomb Rulers // Advances in Mathematics of Communications. – 2009. – Vol. 3, No. 3, pp. 235-250.
  14. Wichmann B. A Note on Restricted Difference Bases // Journal of the London Mathematical Society. – 1963.– Vol. 38, pp. 465-466.
  15. Rosen K.H. (ed.). Handbook of Discrete and Combinatorial Mathematics. – CRC Press, 2000. – 1183 p.
  16. Knuth D.E. The Art of Computer Programming. Volume 4 Fascicle 3, Generating All Combinations and Partitions. – Addison-Wesley, 2005. – 156 p.
  17.  Atkinson M.D., Santoro N., Urrutia J. Integer Sets with Distinct Sums and Differences and Carrier Frequency Assignments for Nonlinear Repeaters // IEEE Transactions on Communications. – 1986. – Vol. COM-34, No. 6, pp. 614-617.
  18. Пазюк О.В., Цимбал Ю.В. Система розподілених обчислень для пошуку оптимальних числових лінійок // Комп’ютерні науки та інформаційні технології: Матеріали 4-ї Міжнародної науково-технічної конференції CSIT-2009. – Львів: Вид-во ПП «Вежа і КО», 2009. – с. 214-216.
  19. Ruskey F. Combinatorial Generation http://www.1stworks.com/ref/RuskeyCombGen.pdf.
  20. Kreher D.L., Stinson D.R. Combinatorial Algorithms. Generation, Enumeration, and Search. CRC Press, 1999. – 340 p.
  21. Skiena S.S. The Algorithm Design Manual, 2nd Edition. – Springer, 2008. – 739 p. 22. Проект hxGrid http://www.deep- shadows.com/hax/hxgrid.htm