Desain dan Analisis Penerapan Metode Stern Brocot Tree dan Convex Hull pada Komputasi Barisan AFS 3: Studi Kasus SPOJ 33039 Amazing Factor Sequence Hard

Francisko, Rendi Dwi (2024) Desain dan Analisis Penerapan Metode Stern Brocot Tree dan Convex Hull pada Komputasi Barisan AFS 3: Studi Kasus SPOJ 33039 Amazing Factor Sequence Hard. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025201056-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 October 2026. Download (4MB) | Request a copy

Abstract

Bilangan bulat positif memiliki Amazing Factor Sequence (AFS) 3 yang terdiri dari Positive Proper Divisors. AFS 3 merupakan sekumpulan Positive Proper Divisors dari 1 sampai bilangan ke-n yang dapat direpresentasikan menjadi formula S\left ( n \right )=\sum_{i=1}^{n}S_{1}\left ( i \right ), dimana S_{1}\left ( i \right ) merupakan jumlah dari Positive Proper Divisors. Jumlah keseluruhan Positive Proper Divisors dari 1 sampai bilangan ke-n yang menjadi permasalahan dalam tugas akhir ini. Permasalahan ini dikategorikan sebagai Stern Brocot Tree dan Convex Hull. Dengan memandang permasalahan ini berdasarkan kategori tersebut maka akan menjadi permasalahan geometri sesuai dengan formula yang diberikan. Dalam tugas akhir ini, akan dilakukan analisis, desain, dan implementasi solusi permasalahan tersebut.
Tugas akhir ini mengacu pada penerapan Convex Hull dan dikombinasikan dengan Stern Brocot Tree yang akan digunakan untuk mencari jumlah keseluruhan Positive Proper Divisors dari 1 sampai bilangan ke-n agar memenuhi batasan waktu yang telah diberikan. Berdasarkan pada formula yang diberikan jika diubah ke permasalahan geometri akan membentuk Convex Hull. Stern Brocot Tree akan digunakan untuk menemukan kemiringan dan menerjemahkan titik agar sesuai dengan Convex Hull. Selain itu, dengan batasan dari bilangan maksimal mencapai 2^63 hasil perhitungan akan melebihi 2^63, maka diperlukan implementasi Big Integer untuk permasalahan tugas akhir ini. Implementasi Big Integer akan dilakukan dengan menggunakan tipe data __int128
Berdasarkan hasil uji coba pada studi kasus yang diberikan, penyelesaian menggunakan metode Stern Brocot Tree dan Convex Hull membutuhkan waktu rata-rata 5.43092 detik dan memori stabil pada 40 MB. Solusi ini berhasil menempati peringkat yang tinggi, yaitu peringkat kedua pada situs Sphere Online Judge yang merupakan online judge system dengan lebih dari satu juta pengguna. Hal ini menegaskan keunggulan kinerja dan efisiensi dari metodologi yang diusulkan.
==============================================================================================================
Positive integer has an Amazing Factor Sequence (AFS) 3 consisting of Positive Proper Divisors. The AFS 3 is a set of Positive Proper Divisors from 1 to the nth number which can be represented as a formula S\left ( n \right )=\sum_{i=1}^{n}S_{1}\left ( i \right ), where S_{1}\left ( i \right ) is the sum of the Positive Proper Divisors. The total number of Positive Proper Divisors from 1 to number i which is the problem in this final project. This problem is categorized as Stern Brocot Tree and Convex Hull. By looking at this problem based on the category, this problem will be a geometric problem according to the given formula. In this final project, analysis, design, and implementation of solutions to these problems will be carried out.
This final project refers to the application of Convex Hull and combined with the Stern Brocot Tree which will be used to find the total number of exact divisors of a number to meet the given time limit. Based on the given formula, if it is changed to a geometric problem, it will form a convex hull. The Stern Brocot Tree will be used to find the slope and translate the points to match the Convex Hull.. In addition, with the limit of the maximum number reaching 2^63, the calculation results will exceed 2^63, so it is necessary to implement big integer for this final project problem. Big Integer implementation will be carried out using the __int128 data type.
Based on the test results of the given case studies, completion using the Stern Brocot Tree and Convex Hull methods took an average time of 5.43092 seconds and stable memory at 40 MB. The solution was ranked the second highest on the Sphere Online Judge site which is an online judge system with more than one million users. This confirming the performance and efficiency advantages of the proposed methodology.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Stern Brocot Tree, Convex Hull, Big Integer.
Subjects:	Q Science > QA Mathematics > QA141 Numeracy--Problems, exercises, etc. Q Science > QA Mathematics > QA401 Mathematical models. Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Rendi Dwi Francisko
Date Deposited:	26 Jul 2024 03:53
Last Modified:	26 Jul 2024 03:54
URI:	http://repository.its.ac.id/id/eprint/108983

Actions (login required)

View Item