algoritma pendidikan matematika univ muhammdiyah sampit.pdf

algoritma matematika komputasi

1. Pengantar Algoritma
Matematika Diskrit
ISTADI, M.Pd
STKIP Muhammadiyah Sampit

2. 2
Definisi
Algoritma adalah himpunan hingga perintah yang
terinci dalam melakukan perhitungan atau
pemecahan masalah.
Istilah Algoritma diambil dari tokoh matematika Abu
Ja’far Muhammad bin Musa Al Khowarizmi, kemudian
Orang Eropa mengejanya menjadi Algoritma.
Misalnya: Program Komputer
Contoh: Mencari bilangan terbesar dalam barisan
hingga bilangan bulat.

3. 3
Langkah Langkah:
1. Tentukan nilai maksimum sementara sama dengan
bilangan bulat pertama dalam barisan
2. Bandingkan bilangan bulat berikut dalam barisan
dengan maksimum sementara, jika ia lebih besar dari
maksimum sementara, maka maksimum sementara
dibuat sama dengan bilangan tersebut.
3. Ulangi langkah sebelumnya jika terdapat bilangan
bulat lain dalam barisan.
4. Berhenti jika tidak ada bilangan bulat lain di
barisan.
5. Nilai maksimum sementara adalah bilangan
terbesar dalam barisan.

4. 4
Pseudocode
Pseudocode dari suatu algoritma memberikan
representasi yang jelas dari suatu algoritma dan
juga dapat diubah ke dalam satu atau lebih bahasa
pemrograman.
Algortima1. Cari_Maksimum
Procedure max(a1, a2, …,an: integer)
max := a1
for i := 2 to n
if max < ai, then max := ai
Return max {max is the largest element}

5. 5
Sifat Algoritma
● Input : algoritma memiliki input dari himpunan
tertentu.
● Output : merupakan solusi dari suatu masalah
● Definiteness : langkah harus jelas dan rinci
● Correctness : menghasilkan output yang benar
● Finiteness : harus dalam jumlah hingga langkah
● Effectiveness : memperhatikan waktu/proses
yang hingga
● Generality : prosedur bersifat umum.

6. 6
Beberapa Algoritma Permasalahan
● Masalah Pencarian
Mencari posisi suatu elemen pada suatu daftar
● Masalah Pengurutan
Mengurutkan elemen pada daftar
● Masalah Optimasi
Menentukan nilai optimum dari masukan

7. 7
Masalah Pencarian
Masalah pencarian digambarkan bahwa lokasi
suatu elemen X pada elemen yang berbeda tidak
terdapat pada daftar tersebut.
Solusinya adalah lokasi dari daftar tersebut
sama dengan X, dan jika 0 maka X tidak ada
dalam daftar.
Dengan kata lain pencarian tidak ditemukan
(not found).

8. 8
Algoritma Pencarian Linier/Beruntun
Dilakukan dengan mengecek satu per satu dari
elemen dari daftar dan membandingkan nilai x
dengan a1, jika sama kembali ke posisi awal,
jika tidak, kemudian ke a2 dst.
Misalnya, kita menginginkan nilai tertentu dari
4, 7, 3, 2, 1, 0, 9
Misalnya x = 1
4 7 3 2 1 0 9
a1 a2 a3 a4 a5 a6 a7

9. 9
Algoritma Pencarian Linier/Beruntun
Pseudo Code
PencarianLinier(larik, kunci)
for setiap item in larik
if item == nilai
kembali index

10. 10
Program Pencarian Linier/Beruntun
# Linear Search in Python
def linearSearch(array, n, x):
# Going through array sequencially
for i in range(0, n):
if (array[i] == x):
return i
return -1

11. 11
Program Pencarian Linier/Beruntun
array = [2, 4, 0, 1, 9]
x = 1
n = len(array)
result = linearSearch(array, n, x)
if(result == -1):
print("Element not found")
else:
print("Element found at index: ", result)

12. 12
Pencarian Binary
Diasumsikan bahwa daftar dari elemen telah
terurut naik.
Algoritma akan membandingkan nilai x dengan
nilai tengah elemen.
Jika nilai tengah ternyata kurang dari X maka
algoritma akan diteruskan ke bagian atas dari
daftar tanpa memuat nilai tengahnya
Jika nilai tengah ternyata TIDAK kurang dari X
maka algoritma akan diproses ke bagian bawah
dari daftar dengan memuat nilai tengahnya

13. 13
Algoritma Binary Search
To search for 19 in the list
1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22
1 2 3 5 6 7 8 10
12 13 15 16 18 19 20 22.
12 13 15 16 18 19 20 22.
18 19 20 22.

14. 14
Algoritma Binary Search
Lakukan sampai penunjuk bawah dan atas bertemu satu sama
lain.
tengah = (bawah + atas)/2
jika (x == larik[tengah])
kembali tengah
lainnya jika (x > larik[tengah]) // x berada pada sisi kanan
bawah = tengah + 1
lainnya // x berada pada sisi kiri
atas = tengah - 1

15. 15
Program Binary Search
# Binary Search in python
def binarySearch(array, x, low, high):
# Repeat until the pointers low and high meet each other
while low <= high:
mid = low + (high - low)//2
if array[mid] == x:
return mid

16. 16
Program Binary Search
elif array[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1

17. 17
Program Binary Search
array = [3, 4, 5, 6, 7, 8, 9]
x = 4
result = binarySearch(array, x, 0, len(array)-1)
if result != -1:
print("Element is present at index " + str(result))
else:
print("Not found")

18. 18
Latihan 1
Gunakan pencarian linier dan pencarian binary
untuk menunjukkan lokasi dari n = 20 dari
daftar di bawah ini.
0, 2, 4, 6, 10, 11, 15, 20, 22, 28

19. 19
Algoritma Pengurutan
Mengurutkan elemen dari daftar dengan urutan naik, baik
pengurutan angka, abjad, dlsb.
Bubble Sort : membandingkan elemen terdekat, kemudian
mengubahnya ke urutan yang benar, untuk setiap urutan
dinamakan dengan pass.

20. 20
Algoritma Bubble Sort
bubbleSort(larik)
for i : 1 ke index_dari_Element_belum terurut - 1
if Element_kiri > Element_kanan
tukar Element_kiri dengan Element_kanan
akhir bubbleSort

21. 21
Program Bubble Sort
# Bubble sort in Python
def bubbleSort(array):

# loop to access each array element
for i in range(len(array)):
# loop to compare array elements
for j in range(0, len(array) - i - 1):
# compare two adjacent elements
# change > to < to sort in descending order
if array[j] > array[j + 1]:

22. 22
Program Bubble Sort
# swapping elements if elements
# are not in the intended order
temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
data = [-2, 45, 0, 11, -9]
bubbleSort(data)
print('Sorted Array in Ascending Order:')
print(data)

23. 23
Insertion Sort
Pengurutan dilakukan dengan elemen kedua
dibandingkan dengan elemen pertama,
selanjutnya bergantian dengan elemen ketiga
dst.
Misalnya, 4 3 5 2 1
4 3 5 2 1 | 3 4 5 2 1 | 2 3 4 5 1 | 1 2 3 4 5

24. 24
Algoritma Insertion Sort
insertionSort(larik)
tandai elemen pertama ketika mengurutkan
untuk setiap elemen X tak terurut
'uraikan' elemen X
for j : indeks terurut akhir turunkan ke posisi 0
jika elemen utama j > X
ubah elemen terurut ke kanan 1 langkah
berhenti
akhir insertionSort

25. 25
Program Insertion Sort
# Insertion sort in Python
def insertionSort(array):
for step in range(1, len(array)):
key = array[step]
j = step - 1

# Compare key with each element on the left of it until an element
smaller than it is found
# For descending order, change key<array[j] to key>array[j].
while j >= 0 and key < array[j]:
array[j + 1] = array[j]
j = j - 1

26. 26
Program Insertion Sort

# Place key at after the element just smaller than it.
array[j + 1] = key
data = [9, 5, 1, 4, 3]
insertionSort(data)
print('Sorted Array in Ascending Order:')
print(data)

27. 27
Latihan 2
Gunakan algoritma bubble sort dan algoritma
insertion sort untuk mengurutkan daftar di
bawah ini.
42, 19, 32, 11, 8, 1

28. 28
Algoritma Greedy
● Algoritma yang mencari pilihan terbaik dalam
setiap langkah disebut algoritma greedy.
● Contoh,
➔ Menentukan jarak terpendek dari 2 titik (shortest
path) yang akan dipelajari di bagian graf.
➔ Menghubungkan jaringan dengan jumlah koneksi
minimal.
➔ Scheduling/penjadwalan.

29. 29
Contoh Algoritma Greedy
➔ Menukarkan sejumlah mata uang dengan
jumlah lembar paling sedikit.
➔ Rp. 88.000
1 lembar uang Rp. 50.000
1 lembar uang Rp. 20.000
1 lembar uang Rp. 10.000
1 lembar uang Rp. 5000
1 lembar uang Rp. 2000
1 lembar uang Rp. 1000