Search academic texts

Information × Registration Number 0824U001332, PhD dissertation Status Доктор філософії Date 06-03-2024 popup.evolution o Title SIMULATION OF COMPUTATION PROBLEMS AND COMPUTATION OF TOPOLOGIES ON A FINITE SET Author Anna V. Skryabina, popup.head Polina G. Steganpeva popup.opponent Serhiy I. Maksimenko popup.opponent Taras O. Banakh popup.review Igor V. Kozin popup.review Nataliya K. Maksyshko Description Дослідження топологічної структури на скінченній множині передбачає розв’язання задач підрахунку та перерахування топологій. Для цього топології моделюють графами, матрицями, булевими функціями, впорядкованими наборами невід’ємних цілих чисел, які визначають мінімальні околи елементів заданої скінченної множини - векторами топологій. Теорія топологій на скінченних множинах має багато застосувань. В теорії графів задача перерахування топологій на скінченних множинах еквівалентна задачі перерахування транзитивних орієнтованих графів, в алгебраїчній топології вона зводиться до перерахування гомотопічних типів скінченних множин. В хімії топологічну структуру на скінченних множинах використовують для аналізу молекулярних структур, в теорії розпізнавання образів – для цифрової обробки зображень на основі скінченних наборів спостережень з метою отримання інформації про вміст зображення на основі поняття близькості точок. Питання про загальну кількість негомеоморфних топологій, а також про кількість всіх топологій на n-елементній множині залишається відкритим. При розв’язанні задач перерахування та підрахунку топологій виключну роль відіграють To-топології. За умови, що топологія має m відкритих множин, говорять, що вона належить до m-класу (або має вагу m). Використання вектора топології дозволило дослідити всі To-топології з вагою m>2^(n-1), які називаються близькими до дискретної топології. В дисертаційній роботі використовується представлення топології вектором, а також зв’язок між топологіями на n-елементній та (n-1)-елементній множинах, який описано за допомогою відношення узгодженності топологій. Перераховано вектори всіх To-топологій з вагою 2^(n-2)<m≤2^(n-1) на n-елементній множині, які є узгодженими з близькими до дискретної топологіями на (n-1)-елементній множині. Серед них To-топології з вагою 2^(n-2)<m<5⋅2^(n-4) досліджено вперше. У роботах Stanley 1971 р. і Kolli 2007 р. та 2014 р. знайдено кількість To-топологій на n-елементій множині з вагою k≥7⋅2^(n-4), k≥3⋅2^(n-3) та k≥5⋅2^(n-4). Порівняння отриманих в дисертації результатів із зазначеними вище результатами дало можливість перерахувати класи топологій, в яких всі топології є узгодженими з близькими до дискретної топологіями, а також довести існування класів топологій з вагою m∈[5⋅2^(n-4),13⋅2^(n-5)), які не вичерпуються To-топологіями, узгодженими з близькими до дискретної на (n-1)-елементній множині, та двоїстими до них. Досліджено структуру топологій на n-елементній множині, які не узгоджені з топологіями, близькими до дискретної на (n-1)-елементній множині, та знайдено вектори таких топологій. При моделюванні топологій булевими функціями кожній To-топології ставиться у відповідність кон’юнктивна нормальна форма спеціального вигляду. В дисертаційній роботі введено нове поняття – максимальної 2-КНФ булевої функції, яка визначає топологію на скінченній множині. Доведено існування бієкції між множиною топологій на n-елементній множині та множиною максимальних 2-КНФ від n змінних. Розроблено метод розпізнавання взаємно двоїстих та самодвоїстих To-топологій, що важливо для підрахунку кількості To-топологій із заданою вагою. Розділ 1 присвячено аналізу публікацій, пов’язаних з темою дисертації. Зазначено, що задача перерахування та підрахунку топологій на скінченній множині виникла як задача теорії графів і що перші результати дослідження цієї задачі пов’язані з використанням графів. Вказано на те, що дослідження топологій на скінченній множині має особливості, оскільки така топологічна структура є дискретною, і що дослідження цієї структури тісно пов’язане з теоріями частково впорядкованих множин, булевих функцій, гомотопічної топології. В цьому ж розділі відзначена особлива роль To-топологій для задачі підрахунку всіх топологій на довільній скінченній множині. У розділі 2 проаналізовано опубліковані результати, пов’язані з темою дисертаційного дослідження, а також представлені результати, отримані в дисертації. Особлива увага приділена опису методів та моделей для представлення топологій, оцінці їх переваг та недоліків... Registration Date 2024-03-22 popup.nrat_date 2024-03-22 Close