Прикладнi можливостi застосування мультимножинного випадку теореми Шпернера та частковi випадки теореми
Вантажиться...
Дата
2021-12
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
У ході даної роботи проведено аналіз доказів простого випадку теореми Шпернера. Запропоновано основні та цікаві способи застосування теореми з використанням різних часткових випадків, які були доведені. Основним і найцікавішим способом застосування теореми була теорія голосування. В основі теорії Голосування лежать сімейства попарно не перетинаних множин, тому оцінка потужності такої сім'ї важлива, а для часткових випадків теореми, які були доведені, ця оцінка отримана. Наступним прикладним застосуванням є балансування системи, яка може бути представлена у вигляді дводольного графа. Спираючись на часткові доведені випадки, можна провести балансування таких систем. Доведені часткові випадки можуть бути використані для створення сильних і слабких груп, які можна використовувати для різних криптографічних проблем, а також для теорії голосування.
Спосіб доведення основної теореми цієї роботи був показаний і використаний у моїй бакалаврській роботі. Цей метод використовує доказ простого випадку теореми та пропонує спосіб повторного використання цього доказу для більш складних випадків. Основним алгоритмом розв’язування системи лінійних рівнянь був метод Гаусса, оскільки він дуже простий і дуже легко програмується, але можна використовувати будь-який алгоритм. Також для кращого розуміння була описана теорія мультимножин.
Доведено різні часткові випадки мультимножин, які задовольняють умовам теореми. Також деякі з описаних тут досліджень були анонсовані на конференції, що відбулася 5 листопада 2021 року під назвою «Modeling, control and information technologies: Proceedings of V International scientific and practical conference».
Опис
Ключові слова
теорема Шпернера, балансування системи графiв, теорiя голосування, сильнi та слабкi групи, Sperner‘s theorem, strong and weak subsets of the multiset, voting theory, balancing the graph system
Бібліографічний опис
Тарасенко, С. А. Прикладнi можливостi застосування мультимножинного випадку теореми Шпернера та частковi випадки теореми : магістерська дис. : 113 Прикладна математика / Тарасенко Степан Анатолійович. – Київ, 2021. – 60 с.