Abstrak —Permasalahan dalam penelitian ini adalah permasalahan  prediksi  hasil  penjumlahan  beberapa  urutan berkala.  Dalam  permasalahan  ini,  diberikan  banyak  urutan berkala  N  dimana  panjang  dari  masing-masing  urutan  berkala berbeda  satu  dengan  yang  lainnya.  Panjang  dari  urutan  berkala dimulai dari N, N-1, N-2, hingga 1. Diberikan nilai f(0), f(1), f(2), hingga  f(N 2 -1),  dimana  f(x)  didefinisikan  sebagai  penjumlahan tiap elemen N buah urutan berkala. Selanjutnya ditanyakan nilai f(x)  dari  nilai  x  yang  diberikan.  Penelitian  ini  akan mengimplementasikan metode pencarian solusi sistem persamaan linear,  yaitu  metode  eliminasi  gauss.  Implementasi  dalam penelitian ini menggunakan bahasa pemrograman C++. Hasil uji coba  menunjukkan  bahwa  metode  gauss  eliminasi  dapat menghasilkan  jawaban  permasalahan  dengan  benar,  tetapi membutuhkan  waktu  yang  sangat  lama,  yaitu  dengan kompleksitas  O(TN 6 +  TN 3 ).  Perlu  adanya  optimasi  dengan mengubah permasalahan ke dalam bentuk interpolasi trigonometri  yang  diselesaikan  dengan  metode  interpolasi polinomial  Lagrange  dan  perkalian  polinomial  yang  diselesaikan dengan metode transformasi Fourier cepat.
Kata Kunci —Eliminasi Gauss, Sistem Persamaan Linear, Urutan Berkala.

## I. PENDAHULUAN
ENELITIAN  ini  terinspirasi  dari  banyaknya  perusahaan yang  melakukan  prediksi  siklus  matahari,  khususnya memprediksi  jumlah  bintik  matahari  per  bulan,  untuk menentukan  umur  dari  satelit  buatan  yang  berada  pada  orbit bumi rendah dikarenakan umur satelit buatan bergantung pada siklus  matahari  [1].  Peneliti  tertarik  untuk  mengetahui  lebih lanjut  metode  yang  digunakan  untuk  memprediksi  jumlah bintik  matahari  per  bulan.  Grafik  jumlah  bintik  matahari  per bulan  mengikuti  grafik  hasil  penjumlahan  beberapa  urutan berkala seperti yang terlihat pada Gambar 1 yang diambil dari situs NOAA [2].
Permasalahan  prediksi  hasil  penjumlahan  beberapa  urutan berkala  terdapat  pada  situs  penilaian  daring Sphere  Online Judge (SPOJ)  dengan  kode  soal  PERIOD4  dengan  judul Periodic function, trip 3 (easy) [1].
Pada  permasalahan  ini,  diberikan  banyak  urutan  berkala  N dimana  panjang  dari  masing-masing  urutan  berkala  berbeda satu dengan yang lainnya. Panjang dari urutan berkala dimulai dari  N,  N-1,  N-2,  hingga  1.  Diberikan  nilai  f(0),  f(1),  f(2),
hingga f(N 2 -1), dimana f(x) didefinisikan sebagai penjumlahan tiap  elemen  N  buah  urutan  berkala.  Untuk  nilai  N=2 penjumlahan  urutan  berkala  terdapat  pada  Tabel  1  dan  untuk nilai  N=3  penjumlahan  urutan  berkala  terdapat  pada  Tabel  2. Urutan  c  =  (c 0 ,  c 0 ,  c 0 ,  c 0 ,  c 0 ,  c 0 ,  …)  merupakan  urutan  1- berkala yang berulang setiap satu bilangan, urutan b = (b 0 , b 1 , b 0 ,  b 1 ,  b 0 ,  b 1 ,  …)  merupakan  urutan  2-berkala  yang  berulang setiap  dua  bilangan,  dan  urutan  a  =  (a 0 ,  a 1 ,  a 2 ,  a 0 ,  a 1 ,  a 2 ,  …) merupakan  urutan  3-berkala  yang  berulang  setiap  tiga bilangan.  Selanjutnya  ditanyakan  nilai  f(x)  dari  nilai  x  yang diberikan. Semua hal di atas diulang sebanyak T kali.
Gambar 1. Jumlah bintik matahari per bulan hingga Juni 2017
Tabel 1.
Definisi f(x) untuk N=2 dengan 4 nilai f(x) diketahui
Definisi 0
1 2 3 4 ?? 5 ?? 6 ?? …  … …

## Desain dan Analisis Algoritma Pencarian Prediksi Hasil Penjumlahan Beberapa Urutan Berkala dengan Metode Eliminasi Gauss
Daniel Henry, Victor Hariadi, dan Rully Soelaiman Departemen Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS)
e-mail : rully@is.its.ac.id
P
Tabel 2.
Definisi f(x) untuk N=3 dengan 9 nilai f(x) diketahui
Definisi 0 1
2 3 4 5 6 7 8 9 ?? 1 0 ?? 1 1 ?? 1 2 ?? …  … …

## II. TINJAUAN PUSTAKA

## A. Urutan Berkala
Urutan  berkala  ( periodic  sequence )  [3] adalah suatu urutan s = (s 0 , s 1 , s 2 , …) dimana
untuk semua
. Urutan
juga  bisa  disebut  sebagai  urutan  N-berkala,  dimana  N merupakan nilai periode dari urutan  s. Sebagai contoh, urutan U = (2, 3, 4, 2, 3, 4, 2, 3, 4, …) merupakan sebuah urutan 3- berkala  dan  urutan  V  =  (5,  4,  2,  3,  5,  4,  2,  3,  5,  4,  2,  3,  …) merupakan sebuah urutan 4-berkala.

## B. Persamaan Linear
Persamaan  linear  [4]  dalam  variabel    dan    didefinisikan sebagai  sebuah  garis  lurus  pada  bidang  datar yang  dapat direpresentasikan dengan persamaan (1) dimana , , dan merupakan konstanta real serta dan tidak bernilai 0.
(1)
(2)
Secara umum, persamaan linear dalam   variabel , ,  , dapat ditulis ke dalam bentuk persamaan (2) dimana , , , , dan   merupakan konstanta real.

## C. Sistem Persamaan Linear
Sistem persamaan linear [4] adalah kumpulan dari dua atau lebih  persamaan  linear  dalam  variabel , ,  , .  Sebuah urutan  angka
disebut  sebagai  solusi  dari suatu  sistem  persamaan  linear  jika
,
, , adalah  solusi  dari  setiap  persamaan  linear  dalam sistem.
(3)
(4)
Sebagai  contoh,  persamaan  (3)  dan  (4)  merupakan  dua persamaan  linear  yang  berada  dalam  suatu  sistem  persamaan linear,  dimana  memiliki  solusi , , . Solusi  ini  dapat  menyelesaikan  persamaan  (3)  dan  persamaan (4). Namun, , ,
bukan merupakan solusi sistem persamaan karena hanya menjadi solusi dari persamaan (3).

## D. Eliminasi Gauss
Eliminasi  gauss  [5]  adalah  suatu  algoritma  yang  digunakan untuk  mencari  solusi  dari  suatu  sistem  persamaan  linear. Sistem persamaan linear (5) diubah ke dalam bentuk perkalian matriks, sehingga berubah bentuk menjadi persamaan (6).
(5) . . . .
. . (6)
Dalam  proses  eliminasi  gauss,  matriks    dilakukan  operasi perkalian,  penjumlahan,  pengurangan,  dan/atau  pembagian baris matriks hingga terbentuk matriks pada persamaan (7).
(7)
Selanjutnya,  dilakukan  proses back  substitution agar mendapatkan  solusi  dari  sistem  persamaan  linear.  Gambar  2 menunjukkan  proses  eliminasi  gauss  dari  awal  sampai  proses back substitution .
Kompleksitas  algoritma  eliminasi  gauss  adalah dengan adalah  banyaknya  variabel  pada  satu  persamaan linear pada sistem persamaan linear. Kompleksitas dari proses back  substitution yaitu dengan    adalah  banyaknya variabel. Total kompleksitas dari keseluruhan proses eliminasi gauss adalah .

## III. STRATEGI PENYELESAIAN
Untuk  nilai =  2,  definisi    yang  tertera  pada  Tabel  1 dapat  diubah  ke  dalam  bentuk  sistem  persamaan  linear  pada Tabel  3  dengan  memasukkan  semua  variabel  pada  semua urutan  berkala  yang  tersedia.  Dalan  kasus =  2,  banyak urutan  berkala adalah dua buah urutan, yaitu urutan 2-berkala berisi 2 variabel dan urutan 1-berkala berisi 1 variabel dengan total  jumlah  variabel  adalah  3  variabel.  Jumlah  persamaan linear  yang  digunakan  hanya  3  persamaan  pertama  dari  4 persamaan  linear  yang  ada  karena  mengikuti  total  jumlah variabel yang digunakan.
Tabel 3.
Persamaan linear awal untuk N=2
Persamaan Linear 0
1 2
Untuk  nilai =  3,  definisi    yang  tertera  pada  Tabel  2 dapat  diubah  ke  dalam  bentuk  sistem  persamaan  linear  pada Tabel  4  dengan  memasukkan  semua  variabel  pada  semua urutan  berkala  yang  tersedia.  Dalan  kasus =  3,  banyak urutan berkala adalah tiga buah urutan, yaitu urutan 3-berkala berisi 3 variabel, urutan 2-berkala berisi 2 variabel, dan urutan 1-berkala berisi 1 variabel dengan total jumlah variabel adalah 6  variabel.  Jumlah  persamaan  linear  yang  digunakan  hanya  6 persamaan  pertama  dari  9  persamaan  linear  yang  ada  karena mengikuti total jumlah variabel yang digunakan.
Tabel 4. Persamaan linear awal untuk N=3
Persamaan Linear
0
1 2 3 4 5
Banyak variabel dapat dikurangi dengan cara menjumlahkan variabel pada  -urutan berkala dengan variabel pada -urutan berkala  sehingga  menghasilkan -urutan  berkala  baru, dimana    merupakan  bilangan  bulat  positif  dan    merupakan bilangan bulat lebih besar dari 1.
Tabel  5  menunjukkan  banyak  variabel  awal  yang dibutuhkan oleh setiap nilai   pada selang
.
Tabel 5. Banyak variabel awal setiap nilai N
Banyak Urutan Berkala Awal ( ) Banyak Variabel Awal 1 1 1 2 2+1 3 3 3+2+1 6 4 4+3+2+1 10 5 5+4+3+2+1 15 6 6+5+4+3+2+1 21 7 7+6+5+4+3+2+1 28 8 8+7+6+5+4+3+2+1 36 9 9+8+7+6+5+4+3+2+1 45 10 10+9+8+7+6+5+4+3+2+1 55 11 11+10+9+8+7+6+5+4+3+2+1 66 12 12+11+10+9+8+7+6+5+4+3+2+1 78 13 13+12+11+10+9+8+7+6+5+4+3+2+1 91 14 14+13+12+11+10+9+8+7+6+5+4+3+2+1 105
Tabel  6  menunjukkan  banyak  variabel  akhir  yang dibutuhkan oleh setiap nilai   pada selang .
Tabel 6. Banyak variabel akhir setiap nilai N
Banyak Urutan Berkala Awal ( ) Banyak Urutan Berkala Akhir ( ) Banyak Variabel Akhir ( ) 1 1 1 1 2 2 1 2 3 3+2 2 5 4 4+3 2 7 5 5+4+3 3 12 6 6+5+4 3 15 7 7+6+5+4 4 22 8 8+7+6+5 4 26 9 9+8+7+6+5 5 35 10 10+9+8+7+6 5 40 11 11+10+9+8+7+6 6 51 12 12+11+10+9+8+7 6 57 13 13+12+11+10+9+8+7 7 70 14 14+13+12+11+10+9+ 8 7 77
Sehingga,  persamaan  linear  akhir  untuk  N  =  2  tertera  pada Tabel  7  dan  persamaan  linear  akhir  untuk  N  =  3  tertera  pada Tabel  8.  Sistem  persamaan  linear  selanjutnya  diselesaikan dengan eliminasi gauss untuk mendapatkan nilai yang ada pada masing-masing  urutan  berkala.  Selanjutnya,  nilai  f(x)  dapat dicari  dengan  menggunakan  nilai-nilai  yang  ada dalam urutan berkala. Kompleksitas total untuk menyelesaikan permasalahan  yaitu  O(TN 6 +  TN 3 )  dimana  T  menandakan banyak sub-kasus uji dan N merupakan banyak urutan berkala awal.
Tabel 7. Persamaan linear akhir untuk N=2
Persamaan Linear 0 1
Tabel 8. Persamaan linear akhir untuk N=3
A
Persamaan Linear
0
1 2 3 4 IV. UJI COBA DAN ANALISIS

## A. Uji Coba Kebenaran
Uji  coba  kebenaran  dilakukan  dengan  membandingkan keluaran  yang  dihasilkan  solusi  berdasarkan  masukan  yang dibuat oleh data generator , dengan keluaran yang dibuat oleh data generator .
Tabel 9.
Percobaan perbandingan jawaban solusi dengan jawaban benar Uji
coba ke- Total selisih angka keluaran hasil solusi dan keluaran benar Jumlah jawaban sesuai per jumlah jawaban total Akuras i 1 0 61000/61000 100% 2 0 71500/71500 100% 3 0 6422/6422 100% 4 0 17742/17742 100% 5 0 26487/26487 100% 6 0 32334/32334 100% 7 0 37199/37199 100% 8 0 44149/44149 100% 9 0 49108/49108 100% 10 0 56397/56397 100% 11 0 61681/61681 100% 12 0 64381/64381 100% 13 0 71981/71981 100% 14 0 1597/1597 100% 15 0 5745/5745 100% 16 0 11031/11031 100% 17 0 16306/16306 100% 18 0 22425/22425 100% 19 0 28217/28217 100% 20 0 31381/31381 100%
Hasil  uji  coba  menunjukkan  bahwa  20  keluaran  solusi  dari 20  kali  uji  coba  sama  dengan  keluaran  hasil data  generator . Keluaran  hasil data generator dipastikan benar. Hasil dari 20 kali uji coba kebenaran tertera pada Tabel 9.

## B. Uji Coba Kinerja
Uji  coba  kinerja  dilakukan  dengan  mengukur  lama berjalannya  solusi  perangkat  lunak  dengan  20  masukan  yang sama  dan  urutan  yang  sama  dengan  masukan  yang  digunakan untuk  uji  coba  kebenaran.  Hasil  uji  coba  pada  Gambar  3 menunjukkan  waktu  eksekusi  maksimal  adalah  178  detik, waktu  eksekusi  minimal  adalah  3.482  detik,  dan  waktu  rata- rata adalah 84.2321 detik.

## Gambar 3. Hasil uji coba kinerja sebanyak 20 kali
Uji  coba  kinerja  juga  dilakukan  untuk  mengukur  pengaruh banyak urutan berkala awal N terhadap pertumbuhan waktu.
Gambar  4.  Pengaruh  banyak  urutan  berkala  awal  terhadap  pertumbuhan waktu
Hasil  uji  coba  pada  Gambar  4  menunjukkan  bahwa pertumbuhan waktu yang terjadi bersifat eksponensial.

## V. KESIMPULAN/RINGKASAN
Dari  hasil  uji  coba  yang  telah  dilakukan  terhadap implementasi  penyelesaian  permasalahan,  dapat  diambil kesimpulan sebagai berikut:
1. Implementasi  metode  eliminasi  gauss  menghasilkan jawaban prediksi yang tepat untuk 20 kasus acak.
2. Waktu  yang  dibutuhkan  oleh  perangkat  lunak  untuk melakukan  penyelesaian  permasalahan  mengalami pertumbuhan  secara  eksponensial  pangkat  6  terhadap pertumbuhan banyak urutan berkala awal.
3. Kompleksitas  waktu  yang  dibutuhkan  untuk  seluruh proses  perangkat  lunak  adalah pada banyak  sub-kasus  uji dan  banyak  urutan  berkala awal  .
4. Perlu  adanya  optimasi  waktu  dengan  mengubah permasalahan ke dalam bentuk interpolasi trigonometri yang diselesaikan dengan metode interpolasi polinomial  Lagrange  dan  perkalian  polinomial  yang diselesaikan  dengan  metode  transformasi  Fourier
cepat.

## UCAPAN TERIMA KASIH
Penulis  mengucapkan  terima  kasih  kepada  Tuhan  Yang Maha  Esa  atas  segala  karunia  dan  rahmat-Nya  yang  telah diberikan  selama  ini.  Penulis  juga  mengucapkan  terima  kasih kepada  orang  tua  yang  selalu  menyemangati  penulis  D.H. (inisial  nama  mahasiswa)  dengan  menanyakan  progress penelitian  setiap  minggu,  saudara  penulis  D.H.  yang  selalu memberikan  semangat,  Bapak  Rully  Soelaiman  dan  Bapak Victor  Hariadi  selaku  dosen  pembimbing  penulis  D.H.,  serta seluruh  pihak  yang  tidak  bisa  penulis  D.H.  sebutkan  satu
persatu  yang  telah  memberikan  dukungan  selama  penelitian ini.
DAFTAR PUSTAKA [1] SPOJ,  “PERIOD4  -  Periodic  function,  trip  3  (easy),”  2015. [Online]. Available: http://www.spoj.com/problems/PERIOD4/.
[2] NOAA,  “Solar  Cycle  Progression,”  2017.  [Online].  Available: http://www.swpc.noaa.gov/products/solar-cycle-progression.
[3] P.  C.  v.  O.  dan  S.  A.  V.  A.  J.  Menezes, Handbook  of  Applied Cryptography . Boca Raton: CRC Press, 1997. [4] H.  A.  dan  C.  Rorres, Elementary  Linear  Algebra  Ninth  Edition Applications Version . Hokoben: John Wiley & Sons, 2003.
[5] S.  C.  C.  dan  R.  P.  Canale, umerical  Methods  for  Engineers  Sixth Edition . New York: McGraw-Hill Education, 2009.