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

Simple item page
dc.contributor.authorКочубiнська, Євгенія
dc.contributor.authorЧелнокова, Ганна
dc.date.accessioned2019-12-09T23:37:06Z
dc.date.available2019-12-09T23:37:06Z
dc.date.issued2019
dc.description.abstractУ робот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снуючих програм для їх розв’язку.uk_UA
dc.description.abstractThis paper studies the properties of balanced incomplete block designs – the systems of k-element subsets (blocks) of some finite set of elements, such that every element is included in r blocks, and every pair of elements is included in λ blocks. The block designs were introduced for the planning of statistical experiments, and since then they have found lots of other uses. One can define a continuous partial map on a block design as a partial map for which the preimage of every block is either a block or an empty set. The paper lists the main known properties of continuous partial maps on block designs are listed. One of the important properties which, in particular, provides a necessary condition for existence of continuous partial maps on a given block design, is the homogeneous lemma: for a nonempty continuous map on a block design the number of the elements in a (nonempty) preimage of every element is fixed and equals to a number d, a divisor of the block size k. The dual homogeneous hypothesis conjectures that every block which is a preimage of some other block has to be a preimage of a fixed number of blocks. If this hypothesis holds, one would get a property for the block designs and the continuous maps on them, which is as important as the homogeneous lemma, and it would be able to build new block designs by taking continuous map images of other block designs. The main new result of this work is a counterexample to the dual homogeneous hypothesis built as a composite block design – block design whose set of blocks can be partitioned into groups, each one making a block design on the same element set. In the last section two necessary conditions for a block design to be composite are provided. Also a way of reduction of the search for a block designs with given parameters to the Boolean satisfiability problem and to the pseudo-Boolean satisfiability problem is given. The paper provides an explicit algorithm that builds a system of Boolean or pseudo-Boolean expressions equivalent to the problem of search for a block designs is provided. Finally, it demonstrates the results of application of existing solvers to the obtained problems.en_US
dc.identifier.citationКочубiнська Є. А. Неперервнi частковi вiдображення на блок-схемах / Кочубiнська Є. А., Челнокова Г. О. // Могилянський математичний журнал. - 2019. - Т. 2. - С. 24-32.uk_UA
dc.identifier.urihttps://ekmair.ukma.edu.ua/handle/123456789/16774
dc.language.isoukuk_UA
dc.relation.sourceМогилянський математичний журналuk_UA
dc.statusfirst publisheduk_UA
dc.subjectблок-схемиuk_UA
dc.subjectчастково неперервнi вiдображенняuk_UA
dc.subjectстаттяuk_UA
dc.subjectblock designsen_US
dc.subjectcontinuous partial mapsen_US
dc.subjectarticleen_US
dc.titleНеперервнi частковi вiдображення на блок-схемахuk_UA
dc.title.alternativeContinuous partial maps on block designsen_US
dc.typeArticleuk_UA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Kochubinska,Chelnokova_Neperervni_chastkovi_vidobrazhennia_na_blok-skhemakh.pdf
Size:
620.62 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
7.54 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Том 2