Seminar Tugas Akhir

Indriani Juvita Khustantiliem
g54160047

PERBANDINGAN ALGORITME BRUTE FORCE DAN DIVIDE AND CONQUER RECURRENCE UNTUK MENENTUKAN SOLUSI SISTEM PERSAMAAN TAK-LINEAR MULTIVARIAT BINER

Pada skripsi ini sembarang polinomial p pada ring polinomial multivariat biner F_2 [x_1,x_2,…,x_n] dipandang sebagai suatu fungsi Boolean p∶ F_2^n→F_2 dan varitas aljabar dari p dapat dipandang sebagai himpunan solusi persamaan multivariat tak-linear biner P={x∈F_2^n/p(x)=0}. Berikutnya, variatas aljabar subhimpunan {p_1,p_2,…,p_m}⊆F_2 [x_1,x_2,…,x_n] dipandang sebagai himpunan solusi sistem persamaan tak-linear multivariat biner S={x∈F_2^n/p_i (x)=0,i=1,2,…,m}. Metode brute force untuk menyelesaikan sistem tersebut diartikan sebagai melacak semua nilai x∈F^n sedemikian sehingga evaluasi p_i (x)=0. Metode ini tergolong buruk karena harus melacak semua nilai domain F_2^n. Selanjutnya metode alternatif ditambahkan yaitu divide and conquer recurrence, dengan ide dasarnya membagi suatu problem menjadi subproblem. Dalam skripsi ini proses komputasi direpresentasikan sebagai himpunan integer. Implementasi algoritme dikerjakan dalam program MAPLE, dan hasilnya menunjukkan bahwa divide and conquer recurrence jauh lebih cepat dari brute force.