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

Автор(и)

  • Yevgeniya Kochubinska Київський нацiональний унiверситет iменi Тараса Шевченка, Ukraine https://orcid.org/0000-0003-4404-4278
  • Hanna Chelnokova Київський нацiональний унiверситет iменi Тараса Шевченка, Ukraine

DOI:

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

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

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

Анотація

У робот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снуючих програм для їх розв’язку.

Біографії авторів

Yevgeniya Kochubinska, Київський нацiональний унiверситет iменi Тараса Шевченка

кандидат фiзико-математичних наук, доцент Київського
нацiонального унiверситету iменi Тараса Шевченка.

Сфера наукових iнтересiв — напiвгрупи перетворень.

Hanna Chelnokova, Київський нацiональний унiверситет iменi Тараса Шевченка

студентка 2-го року навчання магiстерської програми Київського нацiонального унiверситету iменi Тараса Шевченка.

Сфера наукових iнтересiв — напiвгрупи
перетворень.

Посилання

  1. S. W. Margolis, and J. H. Dinitz, Translational hulls and block designs (Springer, 1983).
  2. M. Hall, Combinatorial theory, second edition (Wiley-interscience, 1986).
  3. 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.
  4. M. Hall, Construction of Block Designs, in: A Survey of Combinatorial Theory (Elsevier, 2014).
  5. 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
  6. 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).
  7. 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
  8. David C. Clark, Dissertation, Applications of finite geometries to designs and code, Michigan Technological University, 2011. Retrieved from http://digitalcommons.mtu.edu/etds/199.
  9. 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
  10. Petteri Kaski and Patric R.J. Osterg ̊ard, ̈ Classification Algorithms for Codes and Designs (Springer, 2006).
  11. Charles J. Colbourn and Jeffrey H. Dinitz, Handbook of Combinatorial Designs, second edition (Chapman and Hall/CRC, 2006).
  12. Douglas R. Stinson, Combinatorial Designs: Construction and Analysis (Springer, 2004).
  13. Mate Soos and Andrew V. Jones. CryptoMiniSAT, 2019, GitHub repository. Retrieved from https://github.com/msoos/cryptominisat.
  14. Jan Elffers, RoundingSAT, 2019, GitHub repository. Retrieved from https://github.com/elffersj/roundingsat.

##submission.downloads##

Як цитувати

[1]
Kochubinska, Y. і Chelnokova, H. 2019. Неперервнi частковi вiдображення на блок-схемах. Могилянський математичний журнал. 2, (Груд 2019), 24–32. DOI:https://doi.org/10.18523/2617-70802201924-32.

Номер

Том 2 (2019): Могилянський Математичний Журнал

Розділ

Статті

Ліцензія

Авторське право (c) 2019 Kochubinska Yevgeniya, Hanna Chelnokova

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Автори, які публікуються у цьому журналі, погоджуються з такими умовами:

а) Автори зберігають за собою авторські права на твір на умовах ліцензії Creative Commons Attribution License CC BY 4.0, котра дозволяє іншим особам вільно поширювати (копіювати і розповсюджувати матеріал у будь-якому вигляді чи форматі) та змінювати (міксувати, трансформувати, і брати матеріал за основу для будь-яких цілей, навіть комерційних) опублікований твір на умовах зазначення авторства.

б) Журнал дозволяє автору (авторам) зберігати авторські права без обмежень.

в) Автори мають право укладати самостійні додаткові угоди щодо поширення твору (наприклад, розміщувати роботу в електронному репозитарії), за умови збереження посилання на його першу публікацію. (Див. Політика Самоархівування)

г) Політика журналу дозволяє розміщення авторами в мережі Інтернет (наприклад, у репозитаріях) тексту статті, як до подання його до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).