Algoritma Iteratif

Author

Muhammad Syafiq

Rangkuman Materi

Pendahuluan

Algoritma merupakan urutan langkah logis untuk menyelesaikan suatu masalah dengan tujuan memperoleh keluaran (output) dari masukan (input).
Dalam pemrograman, algoritma sering kali memerlukan pengulangan (iterasi) agar dapat mencapai hasil yang diinginkan — misalnya, menemukan nilai maksimum, menyortir data, atau menghitung nilai limit dari suatu fungsi.

Ciri-ciri algoritma yang baik:

1. Harus berakhir (finite)

2. Didefinisikan secara tepat dan tidak ambigu

3. Memiliki input dan output

4. Efektif dan efisien dari segi waktu serta memori

Iteratif dengan for

Struktur for digunakan ketika jumlah iterasi sudah diketahui sebelumnya.
Umumnya dipakai untuk melakukan operasi berulang pada setiap elemen vektor atau indeks tertentu.

Contoh

Temukan nilai minimum dari vektor acak berikut menggunakan for.

set.seed(123)
x <- sample(5:25, 6)
x
[1] 19 23 18  7 14  6
n <- length(x)
for (i in 2:n) {
  if (x[i] < x[1]) {
    temp <- x[1]
    x[1] <- x[i]
    x[i] <- temp
  }
}
cat("Nilai minimum dari vektor adalah:", x[1])
Nilai minimum dari vektor adalah: 6
set.seed(123)
x <- sample(5:25, 6)
x
[1] 19 23 18  7 14  6
n <- length(x)
for (i in 2:n) {
  if (x[i] < x[1]) {
    x[1] <- x[i]
    x[i] <- x[1]
  }
}
cat("Nilai minimum dari vektor adalah:", x[1])
Nilai minimum dari vektor adalah: 6

Iteratif dengan while

Struktur while digunakan ketika jumlah iterasi belum diketahui, dan pengulangan dilakukan sampai suatu kondisi terpenuhi.

Contoh

Gunakan algoritma iteratif untuk mencari akar persamaan non-linear

\(f(x) = x^3 - 5x + 1 = 0\)$ menggunakan metode Newton-Raphson

x <- 1   # tebakan awal
e <- 2   # selisih awal
while (e > 1e-5) {
  x_old <- x
  f <- x_old^3 - 5*x_old + 1
  f_deriv <- 3*x_old^2 - 5
  x <- x_old - f / f_deriv
  e <- abs(x - x_old)
}
cat("Akar pendekatan =", x)
Akar pendekatan = 0.2016397

Metode Newton-Raphson memperbarui nilai x hingga selisih antar iterasi sangat kecil. Hasil akhir mendekati akar dari fungsi tersebut.

Pengurutan Data (Sorting)

Urutkan vektor x secara menaik menggunakan algoritma sederhana tanpa fungsi sort().

x <- c(9, 2, 7, 4, 1)
n <- length(x)
for (i in 1:(n-1)) {
  for (j in (i+1):n) {
    if (x[i] > x[j]) {
      temp <- x[i]
      x[i] <- x[j]
      x[j] <- temp
    }
  }
}
x
[1] 1 2 4 7 9

Deret Tak Hingga (Konvergensi Iteratif)

Hitung nilai konvergen dari deret berikut:

\[ Z = \sum_{i=1}^{\infty} \frac{3i + 2}{i^2 + 5} \]

Gunakan pendekatan hingga perubahan antar iterasi < 10⁻⁵.

e <- 10
z0 <- 0
i <- 1
while (e > 1e-5) {
  z1 <- z0 + (3*i + 2)/(i^2 + 5)
  e <- abs(z1 - z0)
  z0 <- z1
  i <- i + 1
}
cat("Nilai konvergen dari deret =", z1)
Nilai konvergen dari deret = 36.5743

Latihan

  1. Lakukan tracing pada sintaks berikut
# Data awal
x <- c(9, 2, 7, 4, 1)

# Selection Sort
for (i in 1:(length(x)-1)) {
  min_index <- i
  for (j in (i+1):length(x)) {
    if (x[j] < x[min_index]) {
      min_index <- j
    }
  }
  # Tukar elemen
  temp <- x[i]
  x[i] <- x[min_index]
  x[min_index] <- temp
}

x  # Hasil setelah diurutkan
[1] 1 2 4 7 9

  1. Lakukan tracing pada syntaks berikut

    # Data awal
x <- c(9, 2, 7, 4, 1)

# Insertion Sort
for (i in 2:length(x)) {
  key <- x[i]
  j <- i - 1
  while (j > 0 && x[j] > key) {
    x[j + 1] <- x[j]
    j <- j - 1
  }
  x[j + 1] <- key
}

x  # Hasil setelah diurutkan
    [1] 1 2 4 7 9

  2. Susunlah sintaks R untuk menghitung nilai konvergen dari deret berikut!

    \[ z = 1 + \frac{2}{3} - \frac{3}{5} + \frac{4}{7} - \frac{5}{9} + \frac{6}{11} - \cdots \]

  3. Susunlah sintaks R untuk menghitung nilai konvergen dari deret berikut!

    \[ z = 3 - \frac{5}{4} + \frac{7}{9} - \frac{9}{16} + \frac{11}{25} - \cdots \]

Referensi:

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo