Том 2

Permanent URI for this collection

https://ekmair.ukma.edu.ua/handle/123456789/16769

Browse

Browsing Том 2 by Subject "continuous partial maps"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Неперервнi частковi вiдображення на блок-схемах
    (2019) Кочуб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снуючих програм для їх розв’язку.