The library to proceed with relations (task #6, discrete math).
- read_relation, write_relation - використані стандартні знання, отримані на курсі з ОП: інструкція with open для відкриття файлу, if-умови, цикли, зрізи.
- get_reflexive_closure - було використано означення рефлексивного відношення, спосіб отримання з відношення його рефлексивного замикання, а саме: доповнення його дельта-відношенням. В алгоритмі кожному і-тому-і-тому елементу матриці було присвоєно значення 1.
- get_symmetric_closure - було використано означення симметричного відношення, спосіб отримання симетричного замикання, а саме: доповнення відношення оберненим йому відношенням. Тому в алгоритмі якщо кожний і-тий-j-тий елемент має значення 1, то й кожному j-тому-і-тому елементу присвоюється 1.
- get_transitive_closure - для розробки цієї функції було використано алгоритм Уоршалла: для кожного елементу матриці залишаємо його попереднє значення, якщо шляха між умовними i та j через k не існує, або 1, якщо існує. Складність алгоритму О(n^3).
- is_transitive - для перевірки, чи відношення транзитивне, було використано теорему: якщо відношення дорівнює своєму транзитивному замиканню, то це відношення транзитивне. Для знаходження замикання використаний знову алгоритм Уоршалла, який переривається при знаходженні хоча б одної невідповідності.
- is_transitive_alternative - ще одна версія функції для визначення, чи відношення транзитивне. Вона працює з відношенням заданим у вигляді масиву таплів (множини упорядкованих пар), адже функція get_number_of_transitive працює з відношенням саме в такому форматі. Тут було використано означення транзитивного відношення: якщо пари (a, b) та (b, c) є у відношенні, то й пара (a, c) також є. Алгоритм: проходить по кожній парі у відношенні, маючи список других елементів кожної пари (елементів с) та перевіряє на транзитивність кожний випадок.
- get_equivalence_classes - використано означення класу еквівалентності для конкретного елементу а: це множина таких елементів х, що aRx. Тут множина, на якій задано відношення R, вважається А = {0, 1, 2, ...}. Алгоритм: створюємо словник класів еквівалетності, де ключ - елемент, для якого створений клас еквівалентності, значення - сет (спочатку пустий, потім заповнений на основі даних з матриці), що репрезентує клас.
- get_number_of_transitive - використана властивість транзитивності декартового квардату.
- Створення декартового квардрату множини з n елементами (у форматі списку таплів).
- Створення бінарного сету з n^2 нулів. Тут 0 - відсутність відповідної пари в декартовому квадраті, 1 - присутність. Якщо значення стає 2, то завдяки циклу наступне значення стає 1, а поточне - 0. Таким чином можна перебрати всі підмножини А^2.
- На основі бінарного сету складається відношення й перевіряється його транзитивнсть завдяки is_transitive_alternative.
- Якщо в бінарному сеті не залишиться жодного нуля, то цикл переривається й повертається підрахована кількість транзитивних відношень.
-
Перша зустріч: розбір завдань і розподіл роботи (тему було визначено ще до зустрічі):
Антон Мазурик - розробка get_number_of_transitive, "чистка" коду (виправлення документації, додавання коментарів, дотримання вимог PEP8).
Марія Плис - розробка is_transitive_alternative, написання частини звіту.
Надія Заячковська - розробка get_reflexive_closure, get_symmetric_closure та get_equivalence_classes.
Дарина Чебан - розробка get_transitive_closure.
Дмитро Калітін - розробка read_relation, write_relation та is_transitive. Створення репозиторію, злиття функцій, написання частини звіту.
-
Самостіна робота: розробка функцій, тобто розробка ефективного робочого алгоритму, написання документації та доктестів.
-
Друга зустріч, частина перша: зливаємо разом наші функції (перевірка на баги на малих обсягах даних), пояснюємо алгоритми.
-
Друга зустріч, частина друга: тестуємо алгоритми на великих обсягах даних, за необхідності збільшуємо ефективність.
-
Третя зустріч: фінальні штрихи: додаткова перевірка коду, "чистка", написання звіту, здача проекту.
З точки зору вивчення дискретної математики - це завдання дало поштовх для глибшого розуміння вибраної теми. Під час першої зустрічі, коли проходила основне опрацювання поставлених задач, ми заново розібрали деякі теми та принципи з точки зору їхньої користі у написанні функцій, їхніх алгоритмів і, відповідно, глибше та якісніше зрозуміли ці теми.
З точки зору командного проекту - це цікавий досвід роботи в команді, враховуючи що деякі зустрічі відбувалися виключно дистанційно. Незважаючи на це, ми змогли адекватно організувати нашу роботу навіть у віддаленому форматі. Також, це достатньо нетипова ситуація, а отже люди відкриваються з нових сторін, тому ми більше дізналися один про одного.
З точки зору командного комп'ютерного проекту з дискретної математики - це наочний приклад комбінування та застосування наших вмінь з цих предметів в одному проекті. Ми мали бути достатньо підкованими і в програмуванні, і в дискретній математиці, мали доречно і коректно використовувати свої знання під час мозгових штурмів та роботи над власними завданнями.
На цей проект йде набагато більше часу, ніж вказані три години.