DOI: https://doi.org/10.18523/2617-70802201924-32

Неперервнi частковi вiдображення на блок-схемах

Yevgeniya Kochubinska, Hanna Chelnokova

Анотація


У роботi розглядаються неповнi збалансованi блок-схеми – системи k-елементних пiдмножин (блокiв) деякої скiнченної множини елементiв, таких, що кожний елемент мiститься в r блоках та кожна пара елементiв мiститься в λ блоках. Блок-схеми були введенi для планування статистичних дослiджень та згодом отримали багато iнших використань. На блок-схемi можна визначити частковi неперервнi вiдображення, тобто такi частковi вiдображення, при яких прообразом кожного блоку є блок або пуста множина. Наведено основнi вiдомi властивостi часткових неперервних вiдображень на блок-схемах. Однiєю з важливих властивостей, що, зокрема, дає необхiдну умову iснування неперервних часткових вiдображень на данiй блок-схемi, є лема однорiдностi: для непустого неперервного часткового вiдображення на блок-схемi кiлькiсть елементiв у (непустому) прообразi кожного елемента фiксована i дорiвнює числу d, що дiлить розмiр блокiв k. Дуальна гiпотеза однорiдностi припускає, що кожен блок, що є прообразом якогось iншого блоку, має бути прообразом фiксованого числа блокiв. Виконання цiєї гiпотези дозволило б отримати не менш важливу властивiсть блок-схем i неперервних вiдображень на них та отримати новий спосiб побудови блок-схем, як образiв блок-схем при неперервних вiдображеннях. Основним новим результатом роботи є контрприклад до дуальної гiпотези однорiдностi, який був побудований як складена блок-схема – блок-схема, множина блокiв якої розбивається на групи блокiв, кожна з яких утворює блоксхему на тiй самiй множинi елементiв. В останньому роздiлi отримано двi необхiднi умови складеностi блок-схеми. Також у роботi наводиться спосiб зведення задачi пошуку блок-схеми з заданими параметрами до задачi булевої або псевдобулевої виконуваностi. Наведено явний алгоритм побудови систем булевих або псевдобулевих виразiв еквiвалентних задачi пошуку блок-схеми та продемонстровано результати застосування до вiдповiдних задач iснуючих програм для їх розв’язку.

Ключові слова


блок-схеми; частково неперервнi вiдображення

Повний текст:

PDF

Посилання


S. W. Margolis, and J. H. Dinitz, Translational hulls and block designs (Springer, 1983).

M. Hall, Combinatorial theory, second edition (Wiley-interscience, 1986).

L.N. Shevrin (originator), “Translations of semi-groups”, Encyclopedia of Mathematics. Retrieved from http://www.encyclopediaofmath.org/index.php?title=Translations_of_semi-groups&oldid=18842.

M. Hall, Construction of Block Designs, in: A Survey of Combinatorial Theory (Elsevier, 2014).

K. Takeuchi, “A Table of Difference Sets Generating Balanced Incomplete Block Designs”, Review of the International Statistical Institute. 30 (3), 361–366 (1962). doi: https://doi.org/10.2307/1401745

Jane di Paola, Jennifer Seberry Wallis and W. D. Wallis, “A list of balanced incomplete block designs for r < 30”, Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium. 8, 249–258 (1973).

Marshall Hall Jr., Richard Lane and David Wales, “Designs Derived from Permutation Groups”, Journal of Combinatorial Theory. 8, 12–22 (1970). doi: https://doi.org/10.1016/s0021-9800(70)80004-7

David C. Clark, Dissertation, Applications of finite geometries to designs and code, Michigan Technological University, 2011. Retrieved from http://digitalcommons.mtu.edu/etds/199.

Haim Hanani, “On Balanced Incomplete Block Designs with Blocks Having Five Elements”, Journal of Combinatorial Theory (A). 12, 184–201 (1972). doi: https://doi.org/10.1016/0097-3165(72)90035-0

Petteri Kaski and Patric R.J. Osterg ̊ard, ̈ Classification Algorithms for Codes and Designs (Springer, 2006).

Charles J. Colbourn and Jeffrey H. Dinitz, Handbook of Combinatorial Designs, second edition (Chapman and Hall/CRC, 2006).

Douglas R. Stinson, Combinatorial Designs: Construction and Analysis (Springer, 2004).

Mate Soos and Andrew V. Jones. CryptoMiniSAT, 2019, GitHub repository. Retrieved from https://github.com/msoos/cryptominisat.

Jan Elffers, RoundingSAT, 2019, GitHub repository. Retrieved from https://github.com/elffersj/roundingsat.






Copyright (c) 2019 Kochubinska Yevgeniya, Hanna Chelnokova

Creative Commons License
Ця робота ліцензована Creative Commons Attribution 4.0 International License.