Perbandingan Kecepatan Metode Brute Force dan Algoritme Divide and Conquer untuk Menentukan Varitas Aljabar Polinomial Multivariat Biner

Abstract

Sembarang polinomial multivariat biner p anggota ring polinomial multivariat biner 𝔽����2[𝑥����1,𝑥����2,…,𝑥����𝑛����] pada skripsi ini dapat dipandang sebagai suatu fungsi Boolean 𝑝����∶ 𝔽����2𝑛����→𝔽����2. Selanjutnya, varitas aljabar suatu fungsi polinomial multivariat biner dapat dipandang sebagai himpunan solusi dari persamaan dengan n peubah 𝑝����(𝒙����)=0 yang didefinisikan sebagai himpunan 𝑃����={𝒙����∈𝔽����2𝑛����| 𝑝����(𝒙����)=0}. Metode brute force untuk menentukan varitas aljabar tersebut diartikan sebagai proses pelacakan semua nilai 𝒙����∈𝔽����2𝑛���� sedemikian sehingga terpenuhi 𝑝����(𝒙����)=0. Metode brute force tergolong metode komputasi yang buruk, karena harus melacak seluruh anggota himpunan domain 𝔽����2𝑛����. Jalan alternatif untuk menentukan varitas aljabar tersebut diterapkan algoritme divide and conquer, dengan ide dasarnya adalah memecah suatu problem menjadi subproblem hingga yang terkecil dan kemudian menyelesaikan secara rekursif. Penerapan dari kedua metode tersebut diimplementasikan pada softwareMAPLE. Hasil implementasi menunjukan bahwa metode divide and conquer jauh lebih cepat daripada brute force.