William, Andy (2015) Perancangan Dan Analisis Algoritma Graph Dinamis Pada Penyelesaian Permasalahan Sistem Persamaan Kongruen Yang Dinamis. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
5111100095-Undergraduate_Thesis.pdf - Accepted Version Download (2MB) | Preview |
Abstract
Persamaan kongruen merupakan dasar dari banyak teorema pada ilmu matematika. Kumpulan persamaan kongruen yang saling merujuk satu sama lain disebut sistem persamaan kongruen. Solusi umum untuk permasalahan sistem persamaan kongruen tidak cukup, karena pada kenyataannya seringkali terjadi perubahan pada sistem persamaan yang sedang diteliti. Sistem persamaan kongruen yang dapat berubah-ubah disebut sistem persamaan kongruen dinamis. Pada permasalahan sistem kongruen dinamis, hasil persamaan harus dapat dihitung tanpa mengulang dari awal jika terjadi modifikasi pada persamaan, termasuk penambahan atau perubahan persamaan. Persamaan kongruen selalu mengacu persamaan lain, sehingga sistem persamaan dapat dimodelkan menjadi graph. Perubahan persamaan dapat dilambangkan sebagai penghapusan edge dan penyisipan edge pada graph. Graph ini dinamakan link cut tree. Pada Tugas Akhir ini diimplementasikan solusi untuk permasalahan sistem persamaan kongruen dinamis dengan menggunakan graph dinamis, yaitu link cut tree. Solusi tersebut dapat menemukan hasil atau mengubah setiap persamaan kongruen pada sistem persamaan kongruen dinamis, serta mempunyai kompleksitas space linear dan kompleksitas time O(log n) untuk setiap operasi.
=====================================================================================================
Congruence equation is the base of many mathematics theorems. Multiple congruence equation that refer to each other is called congruence equation system. Solution for a normal congruence equation system is not enough, because in practice there will be a lot of changes on the observed system. This constantly changing system is called dynamic congruence equation system. In this problem, the answer of each equation can be calculated without calculating from scratch if some modification occurs, including addition or variable changes on the equations. Since every congruence equation refers to other congruence equation, the congruence equation system can be remodeled into graph. A change in the equation can be represented as edge deletion and edge insertion in the graph In this undergraduate thesis will be implemented the solution for dynamic congruence equation system problem using dynamic graph, specifically link cut tree. The solution is able to find the answer or change every congruence equation in dynamic congruence equation system. Furthermore, the solution has a linear space complexity and O(log n) time complexity for each operation.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Additional Information: | RSIf 005.133 Wil p |
| Uncontrolled Keywords: | Sistem Persamaan Kongruen Dinamis, Graph Dinamis, Penghapusan Edge, Penyisipan Edge. |
| Subjects: | Q Science > QA Mathematics > QA76.9 Computer algorithms. Virtual Reality. Computer simulation. |
| Divisions: | Faculty of Information Technology > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Yeni Anita Gonti |
| Date Deposited: | 02 Apr 2020 12:42 |
| Last Modified: | 02 Apr 2020 12:42 |
| URI: | http://repository.its.ac.id/id/eprint/75662 |
Actions (login required)
 |
View Item |