matriks dan sorting kel. bagus samsu vicky
Post on 08-Jul-2015
352 Views
Preview:
DESCRIPTION
TRANSCRIPT
MATRIKS
Setelah menyaksikan tayangan ini anda dapat
menentukan penyelesaiansuatu persamaan matrikdengan menggunakan
sifat dan operasi matrik
Perhatikan Tabel: Absensi siswa kelas IIIBulan: Februari 2006
Nama
Siswa
Sakit Ijin Alpa
Agus 0 1 3
Budi 1 2 0
Cicha 5 1 1
Jika judul baris dan kolomdihilangkan
Nama
Siswa
Sakit Ijin Alpa
Agus 0 1 3
Budi 1 2 0
Cicha 5 1 1
Judul kolom
Judul baris
Maka terbentuksusunan bilangansebagai berikut:
0 1 31 2 05 1 1
disebut matriks
Matriksadalah
Susunan bilangan berbentukpersegipanjang yang diatur
dalam baris dan kolom,ditulis diantara kurung kecil
atau siku
Bilangan yang disusundisebut elemen.
Banyak baris x banyak kolomdisebut ordo matriks.
Sebuah matriksditulis dengan huruf besar
Contoh:
Matriks A =654
321 baris ke 1
baris ke 2
kolom ke 1kolom ke 2
kolom ke 3
•matriks A berordo 2 x 3
•4 adalah elemen baris ke 2 kolom ke 1
Matriks persegiAdalah matriks yang
banyak baris dan kolom sama
Contoh:
Banyak baris 4, banyak kolom 4A adalah matriks berordo 4
A =
2409
8765
1052
4321
500
710
321
A =
A adalah matriks segitiga atasyaitu matriks yang elemen-elemen
di bawah diagonal utamanyabernilai nol
Perhatikan matriks berikut:
B =
B adalah matriks segitiga bawahyaitu matriks yang elemen-elemen
di atas diagonal utamanyabernilai nol
Perhatikan matriks berikut:
534
017
001
C =
C adalah matriks diagonalyaitu matriks persegi yang elemen-
elemen di bawah dan di atasdiagonal utama bernilai nol
Perhatikan matriks berikut:
500
010
003
I =
I adalah matriks Identitasyaitu matriks diagonal yang
elemen-elemen padadiagonal utama bernilai satu
Perhatikan matriks berikut:
100
010
001
Transpos Matriks
Transpos matriks A, ditulis At
adalah matriks baru dimanaelemen baris matriks At
merupakan kolom matriks A
Transpos matriks A
A =654
321
63
52
41
adalah At =
Kesamaan Dua Matriksmatriks A = matriks B
jika ordo matriks A = ordo matriks Belemen yang seletak sama
dan B =
A = 107
321
x
Jika matriks A = matriks B, maka x – 7 = 6 x = 13
2y = -1 y = -½
y206
321
Contoh 1:
113
342
85
q
r
p
Diketahui K =
dan L =
1123
442
856
p
q
Jika K = L, maka r adalah….
Bahasan: K = L
1123
442
856
p
q
=
113
342
85
q
r
p
p = 6; q = 2p q = 2.6 = 123r = 4q 3r = 4.12 = 48
jadi r = 48 : 3 = 16
yxy
xyxMisalkan A =
dan B =32
12
1
y
x
Jika At adalah transpos matriks Amaka persamaan At = B
dipenuhi bila x = ….
Contoh 2:
Bahasan:
yxy
xyxA =
=
yxx
yyx
At = B
yxx
yyx
At =
32
12
1
y
x
x + y = 1x – y = 32x = 4Jadi x = 4 : 2 = 2
Operasi PadaMatriks
PenjumlahanPenguranganPerkalian:
perkalian skalardengan matriks
perkalian matriksdengan matriks
Penjumlahan/pengurangan
Matriks A dan B dapat dijumlahkan/dikurangkan,
jika ordonya sama.
Hasilnya merupakanjumlah/selisih
elemen-elemen yang seletak
Contoh 1:
dan B =A =
7 43
3 -21
9 03
1 -52
A + B =
+
16 40
4 -71=
7 43
3 -21
9 03
1 -52
Jika A =
43
21 , B =
03
52
dan C =
40
71
Maka (A + C) – (A + B) =….
Contoh 2:
(A + C) – (A + B) = A + C – A – B
C – B
40
71
03
52
0430
5721
43
21
Bahasan
Perkalian skalar dengan matriks
Jika k suatu bilangan (skalar)maka perkalian k dengan matriks A
ditulis k.A,adalah matriks yang elemennya
diperoleh dari hasil kalik dengan setiap elemen
matriks A
Matriks A =
5
1 43
3 -21
Tentukan elemen-elemenmatriks 5A!Jawab:
5A =
5
1 43
3 -21.5
Contoh 1:
1 2015
15 -105
Matriks A =
43
2a, B =
ba0
51
dan C =
27
31
Jika A – 2B = 3C, maka a + b = ….
Contoh 2:
–
A – 2B = 3C
43
2a
ba0
51
27
31
43
2a
– 2
ba 220
102
621
93
Bahasan
–
43
2a
ba 220
102
621
93
ba
a
2243
122
621
93
ba
a
2243
122
621
93
a – 2 = -3 a = -1
4 – 2a – 2b = 6
4 + 2 – 2b = 6
6 – 2b = 6
-2b = 0 b = 0
Jadi a + b = -1 + 0 = -1
Matriks A =ml
k
32
4
dan B =
7
1232
lk
klm
Supaya dipenuhi A = 2Bt,dengan Bt adalah matriks transpos
dari B maka nilai m = ….
Contoh 3:
B =
7
1232
lk
klm
berarti Bt =
712
32.2
lk
klm
A = 2Bt
ml
k
32
4 =
712
32
lk
klm
Bahasan
712
32.2
lk
klm
A = 2Bt
ml
k
32
4=
ml
k
32
4=
)7(2)12(2
2)32(2
lk
klm
ml
k
32
4
14224
264.
lk
klm=
m3l2
4k =
14l22k4
k2l6m4
4 = 2k k = 2
2l = 4k + 2 2l = 4.2 + 2
2l = 10 l = 5
3m = 2l + 14
3m = 2.5 + 14 = 24
Jadi m = 8
Bubble Sort
• Metode sorting termudah
• Diberi nama “Bubble” karena proses pengurutansecara berangsur-angsur bergerak/berpindah keposisinya yang tepat, seperti gelembung yang keluardari sebuah gelas bersoda.
• Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya.
Bubble Sort (2)
• Pengurutan Ascending :Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar.
• Pengurutan Descending: Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar.
• Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya, asc atau desc.
• Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya sampai dengan iterasi sebanyak n-1.
• Kapan berhentinya? Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.
banyaknya data: nData diurutkan/disorting dari yang bernilai besar
Prosesstep 1 : Periksalah nilai dua elemen mulai dari urutan ke-n
sampai urutan ke-1. Jika nilai kiri<kanan, tukarkankedua data itu.
step 2 : Periksalah nilai dua elemen mulai dari urutan ke-n sampai urutan ke-2. Jika nilai kiri<kanan, tukarkankedua data itu.
step n-1 : Periksalah nilai dua elemen mulai dari urutan ke-nsampai urutan ke-n-1. Jika nilai kiri<kanan, tukarkankedua data itu.
…
Contoh Algoritma: BUBBLE SORT
7 4 5 8 10Awal
Bubble Sort: tahap demi tahap
7 4 5 8 10
7 4 5 8 10Step-1
Awal
Bubble Sort: tahap demi tahap
7 4 5 8 10
7 4 5 10 8Step-1
Awal
Bubble Sort: tahap demi tahap
7 4 5 8 10
7 4 10 5 8Step-1
Awal
Bubble Sort: tahap demi tahap
7 4 5 8 10
7 10 4 5 8Step-1
Awal
Bubble Sort: tahap demi tahap
7 4 5 8 10
10 7 4 5 8Step-1
Awal
Bubble Sort: tahap demi tahap
7 4 5 8 10
10 7 4 5 8
10 7 4 5 8
Step-1
Awal
Step-2
Bubble Sort: tahap demi tahap
7 4 5 8 10
10 7 4 5 8
10 7 4 8 5
Step-1
Awal
Step-2
Bubble Sort: tahap demi tahap
7 4 5 8 10
10 7 4 5 8
10 7 8 4 5
Step-1
Awal
Step-2
Bubble Sort: tahap demi tahap
7 4 5 8 10
10 7 4 5 8
10 8 7 4 5
Step-1
Awal
Step-2
Bubble Sort: tahap demi tahap
7 4 5 8 10
10 7 4 5 8
10 8 7 4 5
10 8 7 4 5
Step-1
Awal
Step-2
Step-3
Bubble Sort: tahap demi tahap
7 4 5 8 10
10 7 4 5 8
10 8 7 4 5
10 8 7 5 4
Step-1
Awal
Step-2
Step-3
Bubble Sort: tahap demi tahap
7 4 5 8 10
10 7 4 5 8
10 8 7 4 5
10 8 7 5 4
Step-1
Awal
Step-2
Step-3
Bubble Sort: tahap demi tahap
7 4 5 8 10
10 7 4 5 8
10 8 7 4 5
10 8 7 5 4
10 8 7 5 4
Step-1
Awal
Step-2
Step-3
Step-4
Bubble Sort: tahap demi tahap
Bubble Sort (3)
Bubble Sort (4)
Bubble Sort (5)
Bubble Sort (6)
• Versi 1
• Versi 2
Bubble Sort (6)
• Dengan prosedur diatas, data terurut naik (ascending), untuk urut turun (descending) silahkan ubah bagian:
if (data[j]<data[j-1]) tukar(&data[j],&data[j-1]);
Menjadi:
if (data[j]>data[j-1]) tukar(&data[j],&data[j-1]);
• “The bubble sort is an easy algorithm to program, but it is slower than many other sorts”
Exchange Sort
• Sangat mirip dengan Bubble Sort• Banyak yang mengatakan Bubble Sort sama dengan Exchange
Sort• Pebedaan : dalam hal bagaimana membandingkan antar
elemen-elemennya.– Exchange sort membandingkan suatu elemen dengan elemen-elemen
lainnya dalam array tersebut, dan melakukan pertukaran elemen jika perlu. Jadi ada elemen yang selalu menjadi elemen pusat (pivot).
– Sedangkan Bubble sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian elemen tersebut itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya.
Exchange Sort (2)
Exchange Sort (3)
Exchange Sort (4)
Exchange Sort (5)
• Prosedur Exchange Sort
Selection Sort
• Merupakan kombinasi antara sorting dan searching• Untuk setiap proses, akan dicari elemen-elemen yang belum
diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array.
• Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]).
• Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.
Selection Sort: contoh
5 2 4 6 1 3
1 2 3 4 5 6
1 2
3 4
5 6
1 2 4 6 5 3
1 2 4 6 5 3
1 2 3 6 5 4
1 2 3 4 5 6
Carilah elemen terkecil &
tukar dengan “5”
1 fixed. Carilah elemen terkecil
& tukar dengan “2”
1,2 fixed. Carilah elemen
terkecil & tukar dengan “4”
1,2,3 fixed. Carilah elemen
terkecil & tukar dengan “6”
1,2,3,4 fixed. Carilah elemen
terkecil & tukar dengan “5”
1,2,3,4,5 fixed, otomatis elemen
terakhir sudah pada posisi yang
benar
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
Selection Sort (2)
Beberapa Algoritma Sorting
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort
Bubble Sort: pseudocode
BUBBLESORT(A)
1 for i←1 to length[A]
2 do for j←length[A] downto i+1
3 do if A[j] < A[j-1]
4 then exchange A*j+ ↔ A*j-1]
top related