Desain dan Implementasi Solver Dynamic Congruence Equation System Berbasis Struktur Link Cut Tree

Amari, Luthfiyyah and Anggraeni, Agnesfia (2024) Desain dan Implementasi Solver Dynamic Congruence Equation System Berbasis Struktur Link Cut Tree. Project Report. [s.n.], [s.l.]. (Unpublished)

Text 5025201090_5025201059-Project_Report.pdf - Accepted Version Restricted to Repository staff only Download (1MB) | Request a copy

Abstract

Persamaan kongruen adalah konsep fundamental dalam teori bilangan dengan aplikasi yang luas di berbagai bidang. Sistem Persamaan Kongruen Dinamis adalah masalah di mana tujuannya adalah menemukan solusi untuk sistem persamaan kongruen yang variabelnya berubah seiring waktu, menjadikan masalah ini bersifat dinamis. Pendekatan langsung dengan menghitung ulang dari awal setiap kali terjadi modifikasi tidaklah efisien. Oleh karena itu, tantangannya adalah merancang metode yang efisien untuk menangani perubahan tersebut sambil mempertahankan kondisi sistem. Karena setiap persamaan kongruen dalam sistem dapat merujuk pada persamaan lainnya, seluruh sistem dapat direpresentasikan sebagai sebuah graf. Dalam graf ini, perubahan pada persamaan dapat dimodelkan sebagai penghapusan dan penyisipan edge, yang menjadikannya graf dinamis. Dalam laporan ini, kami mengusulkan solusi untuk masalah sistem persamaan kongruen dinamis menggunakan graf dinamis, dengan menggunakan struktur data link-cut tree. Link-cut tree memungkinkan operasi seperti cut, link, expose, dan path queries dilakukan dalam waktu teramortisasi O(log n). Berdasarkan hasil studi kasus, waktu eksekusi rata-rata untuk solusi menggunakan link-cut tree adalah 0,116 detik dengan konsumsi memori sebesar 5,2 MB. Solusi ini terbilang efisien karena dapat menyelesaikan permasalahan Dynamic Congruence Equation System dengan batasan yang ditentukan.
============================================================================================================================
Congruence equations are a fundamental concept in number theory with wide-ranging applications across various fields. The Dynamic Congruence Equation System is a problem where the goal is to find solutions for a system of congruence equations whose variables change over time, making the problem dynamic. A straightforward approach of recomputing from scratch every time a modification occurs is inefficient. Hence, the challenge is to devise an efficient method to handle such changes while maintaining the state of the system.Since each congruence equation within the system can reference other equations, the entire system can be represented as a graph. In this graph, changes to the equations can be modeled as edge deletions and insertions, effectively making it a dynamic graph. In this report, we propose a solution to the dynamic congruence equation system problem using a dynamic graph structure, specifically employing the link-cut tree data structure.Link-cut trees allow operations such as cut, link, expose, and path queries to be performed in amortized time O(log n). Based on case study results, the average execution time for the solution using a link-cut tree is 0.116 seconds with a memory consumption of 5.2 MB. This solution is considered efficient as it can solve the Dynamic Congruence Equation System problem within the specified constraints.

Item Type:	Monograph (Project Report)
Uncontrolled Keywords:	Dynamic Congruence Equation System, Link-Cut Tree, Dynamic Data Structure, Dynamic Graph
Subjects:	Q Science > QA Mathematics > QA76.F56 Data structures (Computer science)
Divisions:	Faculty of Information Technology > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	luthfiyyah hanifah amari
Date Deposited:	01 Aug 2024 02:58
Last Modified:	01 Aug 2024 02:58
URI:	http://repository.its.ac.id/id/eprint/111450

Actions (login required)

View Item