Description

Portofolio ini berisi implementasi program Python untuk menghitung Kelipatan Persekutuan Terkecil (KPK) dan Faktor Persekutuan Terbesar (FPB) menggunakan algoritma Euclidean, yang dikenal luas karena efisiensinya. Program ini tidak hanya memberikan hasil perhitungan secara akurat, tetapi juga menyertakan analisis efisiensi melalui fitur benchmarking. Dengan menggunakan pendekatan Computational Thinking, program ini menjadi contoh konkret penerapan teknologi komputasi dalam menyelesaikan masalah matematika yang sering digunakan dalam berbagai bidang seperti kriptografi, sistem jaringan, dan optimasi data.

1. Latar Belakang

Perhitungan FPB dan KPK merupakan salah satu konsep dasar dalam matematika yang memiliki aplikasi luas dalam kehidupan sehari-hari. Contohnya, FPB sering digunakan dalam pengelolaan data untuk menemukan pola kesamaan, sementara KPK bermanfaat dalam masalah sinkronisasi jadwal atau sistem jaringan. Meskipun masalah ini sederhana, proses penyelesaiannya bisa menjadi tidak efisien jika algoritma yang digunakan tidak tepat, terutama saat bekerja dengan bilangan besar.

Algoritma Euclidean adalah solusi ideal untuk masalah ini karena kompleksitas waktunya yang rendah dibandingkan metode iteratif sederhana. Dengan prinsip pembagian berulang, algoritma ini dapat menyelesaikan perhitungan dengan lebih sedikit iterasi, membuatnya sangat efisien untuk kasus-kasus besar. Portofolio ini juga mengintegrasikan analisis efisiensi algoritma dengan metode benchmarking untuk memberikan pemahaman yang lebih mendalam tentang performa setiap pendekatan.

2. Pendekatan Computational Thinking

Program ini dirancang dengan menerapkan prinsip-prinsip Computational Thinking, meliputi:

1. Decomposition:
   • Memecah masalah besar menjadi sub-masalah yang lebih kecil, seperti menghitung FPB terlebih dahulu sebelum digunakan untuk menghitung KPK.
2. Pattern Recognition:
   • Mengidentifikasi pola efisiensi dalam pembagian berulang menggunakan algoritma Euclidean.
3. Algorithm Design:
   • Merancang algoritma modular yang efisien dan mudah dipahami untuk menyelesaikan masalah secara sistematis.
4. Evaluation:
   • Menganalisis hasil dengan membandingkan performa algoritma Euclidean dan metode iteratif menggunakan teknik benchmarking.

3. Fitur dan Desain Program

Program ini memiliki beberapa fitur utama:

1. Penghitungan FPB:
   • FPB dihitung menggunakan algoritma Euclidean, yang bekerja dengan prinsip pembagian berulang hingga bilangan kedua menjadi nol.
2. Penghitungan KPK:
   • KPK dihitung menggunakan rumus memastikan akurasi yang tinggi.
3. Benchmarking:
   • Program membandingkan waktu eksekusi algoritma Euclidean dengan metode iteratif sederhana, menggunakan pustaka timeit untuk hasil yang akurat.
4. Validasi Input:
   • Program memverifikasi input pengguna untuk memastikan hanya bilangan positif yang diproses, mencegah error dalam perhitungan.

4. Implementasi Algoritma

Program ini dirancang modular untuk memudahkan pembacaan dan pengembangan. Berikut adalah komponen utama implementasi:

• Algoritma Euclidean:
  • Kompleksitas waktu: O(log(min(a, b))), memberikan performa optimal pada input besar.
  • Implementasi sederhana dengan loop while untuk menggantikan operasi berulang.
• Metode Iteratif:
  • Digunakan sebagai pembanding. Meskipun memberikan hasil yang sama, metode ini kurang efisien karena memerlukan lebih banyak iterasi pada input besar.

5. Hasil dan Analisis

Berikut adalah contoh hasil program untuk beberapa pasangan input:

1. Input Kecil: Bilangan pertama = 12, Bilangan kedua = 28.
   • FPB = 4.
   • KPK = 84.
2. Input Sedang: Bilangan pertama = 252, Bilangan kedua = 105.
   • FPB = 21.
   • KPK = 1260.
3. Input Besar: Bilangan pertama = 123456, Bilangan kedua = 789012.
   • FPB = 12.
   • KPK = 8117355456.

Benchmarking:

1. Metode Euclidean:
   • Waktu eksekusi: 0.012 detik (10.000 kali eksekusi).
2. Metode Iteratif:
   • Waktu eksekusi: 0.034 detik (10.000 kali eksekusi).

Hasil ini menunjukkan bahwa algoritma Euclidean jauh lebih efisien dibandingkan metode iteratif, terutama untuk input besar. Dengan kompleksitas waktu O(log(min(a, b))), algoritma Euclidean memberikan hasil lebih cepat dan stabil, sementara metode iteratif lebih lambat karena kompleksitasnya lebih tinggi.

6. Aplikasi di Dunia Nyata

Program ini memiliki aplikasi yang luas, antara lain:

1. Kriptografi:
   • FPB digunakan dalam menemukan bilangan prima relatif untuk algoritma enkripsi.
2. Sinkronisasi Sistem Jaringan:
   • KPK dapat digunakan untuk menentukan waktu sinkronisasi antara dua atau lebih sistem.
3. Optimasi Sistem Data:
   • FPB membantu dalam menemukan pola kesamaan dalam kumpulan data besar.

7. Kesimpulan

Portofolio ini berhasil mengimplementasikan algoritma Euclidean untuk menghitung KPK dan FPB secara efisien. Dengan fitur benchmarking, program memberikan analisis yang mendalam tentang performa algoritma dibandingkan metode iteratif. Melalui penerapan Computational Thinking, program ini menjadi contoh aplikasi nyata dari konsep algoritma dalam menyelesaikan masalah secara efektif, terukur, dan relevan dengan kebutuhan dunia nyata.

Referensi

1. Cormen, Thomas H., et al. Introduction to Algorithms. MIT Press, 2009.
2. Goodrich, Michael T., et al. Data Structures and Algorithm Analysis in Python. Wiley, 2013.
3. "Euclidean Algorithm - Basic and Extended." GeeksforGeeks. https://www.geeksforgeeks.org/euclidean-algorithms-basic-and-extended/
4. "Big O Notation in Python." Real Python. https://realpython.com/python-big-o-notation/
5. "Timeit - Measure Execution Time of Small Code Snippets." Python Documentation. https://docs.python.org/3/library/timeit.html