Sabtu, 24 November 2012

Matriks Dan Transformasi Linier (SPL 3 Variabel) (Semester 3)


SISTEM PERSAMAAN LINIER 3 (TIGA) VARIABEL




1. 3/X - 2/y + 1/z = 5   .....(1)
   1/x - 5/y + 3/z = 2   .....(2)
   2/x + 1/y + 1/z = 12  .....(3)

Ditanya tentukan x,y,z....?

Penyelesaian :

mis : 1/x = a
      1/y = b
      1/z = c

jadi, 3a - 2b + c = 5 ....(1)
      a - 5b + 3c = 2 ....(2)
      2a + b + c = 12 ....(3)


Persamaan 1 dan 3                                          
  3a - 2b + c = 5
  2a -  b + c = 12 -
  ________________
    a - 3b      = -7  ....(4)


persamaan 1 dan 2
  3a - 2b +  c  = 5 |x3| 9a - 6b + 3c  = 15
   a - 5b + 3c  = 2 |x1|  a - 5b + 3c  = 2   -
                        ___________________
                                8a  - b          = 13  ....(5)

Persamaan 4 dan 5
   a - 3b = -7 |x1|   a - 3b   = -7
  8a - b  = 13 |x3| 24a - 3b = 39  -
                   _______________
                         -23a        = -46
                            a          = -46/-23
                            a          = 2

Persamaan 4
  a - 3b = -7
  2 - 3b = -7
    - 3b = -7-2
       b = 3

Persamaan 1
  3a - 2b + c = 5
   6 -  6 + c = 5
            c = 5

Jadi, X= 1/2, y = 1/3, z = 1/5


2.  x1 +  y2 -  z3 = 1 ....(1)
   8x1 + 3y2 - 6z3 = 1 ....(2)
  -4x1 -  y2 + 3z3 = 1 ....(3)

Ditanya tentukan nilai x1,y2,z3...?

Penyelesaian :

Persamaan 1 dan 2
  x1 +  y2 -  z3 = 1    |x8| 8x1 + 8y2 - 8z3 = 8
 8x1 + 3y2 - 6z3 = 1  |x1| 8x1 + 3y2 - 6z3 = 1 -
                                   _____________________
                                               5y2 - 2z3 = 7 ....(4)

Persamaan 1 dan 3
   x1 +  y2  -  z3 = 1   |x4|  4x1 + 4y2 - 4z3 =  4
 -4x1 -  y2  + 3z3 = 1 |x1 |-4x1 -  y2 + 3z3 =  1 +
                                    _____________________
                                                 3y2 -  z3 = 5 .... (5)

Persamaan 4 dan 5
   5y2 - 2z3 = 7 |x3| 15y2 - 6z3 = 21
   3y2 -  z3 = 5 |x5| 15y2 - 5z3 = 25 -
                           _________________
                                      -  z3 = -4
                                         z3 = 4


Persamaan 5
  3y2 - z3 = 5
  3y2 - 4  = 5
  3y2      = 5 +4
  3y2      = 9
   y2      = 9/3
   y2      = 3

Persamaan 1
  x1 + y2 - z3 = 1
  x1 + 3  - 4  = 1
  x1           = 1+1
  x1           = 2

Jadi, x1 = 2, y2 = 3, z3= 4


3.  p + 2q + r =  7 .....(1)
   2p +  q + r =  4 .....(2)
    p +  q - r = -3 .....(3)


Ditanya tentukan nilai p,q,r....?

Penyelesaian :

Persamaan 1 dan 2
  p + 2q + r = 7 |x2| 2p + 4q + 2r = 14
 2p +  q + r = 4 |x1| 2p +  q +  r   = 4  -
                     ____________________
                                      3q +  r = 10 .... (4)

Persamaan 1 dan 3
  p + 2q +  r =  7
  p +  q -  r = -3  -
____________________
       q + 2r = 10 .... (5)

Persamaan 4 dan 5
  3q +  r = 10 |x2| 6q + 2r = 20
   q + 2r = 10 |x1|  q + 2r = 10  -
                   __________________
                           5q      = 10
                             q      = 10/5
                             q      = 2

Persamaan 5
   q + 2r = 10
   2 + 2r = 10
       2r = 8
        r = 4

Persamaan 1
   p + 2q   + r = 7
   p + 2(2) + 4 = 7
   p + 8        = 7
   p            = -1


Jadi, p=-1, q=2 r=4


4.  2x + 2y +  z = 1400 .....(1)
     x +  y + 2z = 1300 .....(2)
     x + 3y +  z = 1500 .....(3)


Ditanya tentukan x,y,z....?


Persamaan 1 dan 2
    2x + 2y +  z = 1400 |x1| 2x + 2y +  z = 1400
     x +  y + 2z = 1300 |x2| 2x + 2y + 4z = 2600  -
                                   ______________________
                                                    - 3z = -1200
                                                        z = 400

Persamaan 1 dan 3
    2x + 2y + z = 1400 <=> 2x + 2y + 400 = 1400 ----> 2x + 2y = 1000  |x1| 2x + 2y = 1000
     x + 3y + z = 1500 <=>  x + 3y + 400 = 1500 ---->  x + 3y = 1100    |x2| 2x + 6y = 2200  -
                                                                                                        _________________
                                                                                                                    -4y = -1200
                                                                                                                       y = 300

Persamaan 1
    2x + 2y     + z       = 1400
    2x + 2(300) + 400 = 1400
    2x + 1000             = 1400
    2x                        = 400
     x                         = 200


Jadi, x=200, y=300, z=400


5.  X1 - 3y2 + 2z3 = 8  ....(1)
   2x1 +  y2 - 2z3 = 0  ....(2)
   3x1 + 5y2 -  z3 = 17 ....(3)

Ditanya tentukan x1,y2,z3....?


Persamaan 1 dan 2
    X1 - 3y2 + 2z3 = 8 |x2| 2x1 - 6y2 + 4z3 = 16
   2x1 +  y2 + 2z3 = 0 |x1| 2x1 +  y2 - 2z3 = 0  -
                                     ______________________
                                            - 7y2 + 6z3 = 16 ....(4)

Persamaan 1 dan 3
    x1 - 3y2 + 2z3 = 8   |x3|  3x1 -  9y2 + 6z3 = 24
   3x1 + 5y2 -  z3 = 17 |x1|  3x1 +  5y2 -  z3 = 17 -
                                     _______________________
                                              - 14y2 + 7z3 = 7 ....(5)

Persamaan 4 dan 5
   -7y2 + 6z3 = 16 |x7| -49y2 + 42z3 = 112
  -14y2 + 7z3 = 7  |x6| -84y2 + 42z3 =  42  -
                                ______________________
                                   35y2            =  70
                                       y2            = 2


Persamaan 5
  -14y2  + 7z3 = 7
  -14(2) + 7z3 = 7
  -28    + 7z3 = 7
           7z3 = 35
            z3 = 5


Persamaan 1
   x1 - 3y2  + 2z3  = 8
   x1 - 3(2) + 2(5) = 8
   x1               = 4

Jadi, X1=4, y2=2, z3=5


By : Cutt Iswahyuni 
Diposting oleh di Tidak ada komentar:
Label:

Kamis, 22 November 2012

Struktur Data (Sorting) (Semester 3)


Algoritma sorting


D

I

S

U

S

U

n
OLEH
Nama : ISWAHYUNI
Mata Kuliah : Struktur Data
NPM : 1111706
STMIK BUDIDARMA MEDAN
TA 2011-2012


Sorting bisa didefinisikan sebagai suatu proses pengurutan data yang sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut suatu aturan tertentu. Sorting yang kita terapkan menggunakan tipe data array agar pemahaman serta pengimplementasiannya lebih mudah. Pada umumnya terdapat dua jenis pengurutan :

- Ascending (Naik).
Contoh : 2,3,10,15,22
- Descending (Turun).
Contoh : 22,15,10,3,2
  Untuk melakukan proses pengurutan tersebut dapat digunakan berbagai macam cara/metode.

    1.      Bubble Sort
    2.      Selection Sort
    3.      Merge Sort
    4.      Heap Sort
    5.      Shaker Sort

Metode Pengurutan Data
Pengurutan berdasarkan perbandingan (comparison-based sorting)
 • Bubble sort
Pengurutan berdasarkan prioritas (priority queue sorting method)
 • Selection sort, heap sort
Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep sorted method)
• Merge Sort
Pengurutan berkurang menurun (diminishing increment sort method)

    1.      BUBBLE SORT

Metode ini merupakan metode yang paling sederhana dan paling tidak efisien, karena memerlukan waktu yang relatif lebih lama dibandingkan dengan metode­ - metode yang lainnya. Konsep dasar dari Bubble sort ialah membandingkan elemen yang sekarang dengan elemen yang berikutnya, jika elemen sekarang > elemen berikutnya (untuk ascending), maka dilakukan proses penukaran. Proses sorting dapat dimulai dari data awal atau data akhir.
Idenya adalah :
¨  Lakukan pengulangan ( pass ) pada array, tukar elemen yang bersebelahan jika diperlukan ( perbandingan nilainya tidak sesuai ); jika tidak ada pertukaran elemen maka array sudah terurut.
¨  Dalam pass pertama, temukan elemen dengan nilai tertinggi ( maksimal ) dalam array dan tukarkan dengan elemen di sebelah kanannya dan seterusnya sampai dengan mencapai posisinya di ujung array sebelah kanan.
¨  Kemudian dalam pass kedua, nilai tertinggi kedua dalam array akan ditempatkan dalam posisinya ( di sebelah kiri elemen dengan nilai tertinggi ( maksimal ).
¨  Teruskan langkah ketiga sampai semua elemen array terurut.

Berikut ini merupakan Procedure BubbleSort pada Pascal :
Procedure Bubble( Var Temp : Data; JmlData : Integer);
Var I,J : Integer;
Begin
For I:=1 To JmlData Do
For J:=JmlData DownTo I Do
If Temp[J] < Temp[J-1] Then {Untuk Descending >}
SWAP  à  Temp = a[J-1];
                   a[J-1] = a[J];
                   a[J] = Temp;

End;

Langkah Langkah Bubble Sort Ascending





Langkah Langkah Bubble Sort Descending




                      Contoh Sorting dengan Bubble Sort
Iterasi
Ke
A[1]
A[2]
A[3]
A[4]
A[5]
Awal
22
10
15
3
2
1
10
22
15
3
2

10
15
22
3
2

10
15
3
22
2

10
15
3
2
22






2
10
15
3
2
22

10
3
15
2
22

10
3
2
15
22

10
3
2
15
22






3
3
10
2
15
22

3
2
10
15
22

3
2
10
15
22

3
2
10
15
22






4
2
3
10
15
22

2
3
10
15
22

2
3
10
15
22

2
3
10
15
22






5
2
3
10
15
22

2
3
10
15
22

2
3
10
15
22

2
3
10
15
22






Akhir
2
3
10
15
22

Di sini terlihat ketidakefisienan dari bubble sort yaitu harus menyelesaikan JumMax –1 dari data. Sedangkan jika kita melihat dari tabel diatas pada iterasi ke empat saja data sudah terurut dan seharusnya pada saat itu proses sudah berhenti, tapi dengan bubble sort proses harus dilakukan sampai looping selesai.
Pada seluruh prosedur yang menggunakan metode sorting pasti memerlukan prosedur tambahan tukar data (Swap) untuk menukarkan dua buah elemen dalam data. Berikut ini merupakan prosedur untuk menukarkan dua buah data.

    2.      SELECTION SORT
Mirip dengan bubble sort, namun algoritma ini lebih sedikit usaha untuk menempatkan setiap elemen ke posisinya.
Idenya :
¨  Pertama temukan elemen array terkecil ( minimum ) dan pertukarkan dengan elemen array di posisi ( indeks ) pertama
¨  Kemudian temukan elemen array terkecil kedua dan pertukarkan dengan elemen array di posisi ( indeks ) kedua
¨  Ulangi langkah-langkah diatas sampai semua array terurut

Berikut ini merupakan Procedure Selection Sort pada Pascal :
Procedure selectionSort(var a : array[1..size] of integer );
var
integer i,j, min, tmp;
begin
for( i:=1 to size-1) do begin
      for (j = i + 1 to size ) do begin
      min = j;
           if (a[i] > a[min]) then
        SWAP  à  tmp = a[i];
                            a[i] = a[min];
                             a[min] = a[i];
     end;
  end;
end; { end of procedure }

Langkah Langkah Selection Sort Ascending


Langkah Langkah Selection Sort Descending


Contoh sorting dengan Selection Sort
Iterasi Ke
A[1]
A[2]
A[3]
A[4]
A[5]
Awal
22
10
8
3
2






I=1, Lok=5
2
10
8
3
22






I=2, Lok=4
2
3
8
10
22






I=3, Lok=4
2
3
8
10
22






I=4, Lok=5
2
3
8
10
22






Akhir
2
3
8
10
22


   3.      MERGE SORT
Algoritma Merge Sort ditemukan oleh John von Neumann di tahun 1945. Merge Sort termasuk paradigma algoritma divide and conquer (kurang lebih berarti: bagi dan atasi). Hal ini dikarenakan algoritma ini melakukan pembagian struktur data sebelum kemudian dioperasi satu per satu. Intinya, algoritma ini menggunakan dua ide utama sebagai berikut, Sebuah list yang kecil membutuhkan langkah yang lebih sedikit untuk pengurutan daripada sebuah list yang besar.
Untuk membentuk sebuah list terurut dari dua buah list terurut membutuhkan langkah yang lebih sedikit daripada membentuk sebuah list terurut dari dua buah list tak terurut. Contoh: hanya diperlukan satu kali traversal untuk masing-masing list jika keduanya sudah terurut.



Algoritma Merge Sort
Algoritma Merge Sort sederhananya, dapat ditulis berikut:
a.       Bagi list yang tak terurut menjadi dua sama panjang atau salah satunya lebih panjang satu elemen.
b.      Bagi masing-masing dari 2 sub-list secara rekursif sampai didapatkan list dengan ukuran 1.
c.       Gabung 2 sublist kembali menjadi satu list terurut.

·         Merge Sort dengan metode rekursif
            Terdapat 3 prosedur dalam metode ini, yaitu prosedur merge sort,merge, dan insert.
prosedur mergesort

            Langkah-langkahnya:
1.      Membagi 1 array menjadi 2 dengan cara: cari tengahnya mid= (a+b) div 2 sehingga terdapat 2 bagian, (a,mid) dan (mid+1,b) lakukan terus pembagian sampai pada leaves (daun) yang tidak bisa dibagi lagi.
      2.  Lakukan merge pada daun yang tidak bisa dibagi lagi
      3.  Kedua langkah diatas dilakukan apabia a<b (indeks kiri lebih kecil dari indeks kanan)

Berikut ini merupakan Procedure Merge Sort pada Pascal :
algoritmanya:
procedure mergesort (a,b: integer)
begin
            if a<b then
            begin
                        mid:= (a+b) div 2
                        mergesort (a,mid)
                        mergesort (mid+1,b)
                        merge (a,b)
            end if
end



Procedure Merge
            Langkah - langkahnya:
1. Cari mid-nya
2. Tentukan indeks iàa=i
3. Tentukan k àk = mid+1
4. Bandingkan elemen yang ke i dengan elemen yang ke-k jika nilai elemen yang ke-i <= nilai elemen yang ke-k, maka naikkan jumlah i
             jika tidak,maka
·         insert elemen yang ke-k elemen yang ke-i
·         naikkan jumlah i
·         naikkan jumlah k
·         naikkan mid
5. lakukan langkah 4 sampai i>mid atau k>b

 Berikut ini merupakan Procedure merge :
algoritmanya:
prosedure merge (a,b:integer)
begin
            mid=(a+b) div 2
            i=a
            k=mid+1
            repeat
                        if a[i] <= a[k] then i =i+1
                        else
                                    begin
                                                insert (k,i)
                                                i= i+1
                                                k=k+1
                                                mid=mid+1
                        endif
            until i >mid or k>b
end



Prosedur Insert
Langkah - langkahnya:

1. Tentukan nilai yang akan diinsert (k), lalu masukkan nilai dari elemen ke-k ke variabel temp.
2. Tentukan bahwa j=k à posisi dari j sampai i+1 menggeser kekanan
3. Masukkan temp ke a[i]

Berikut ini merupakan Procedure insert :
procedure insert(k,i)
begin
            temp=a[k]
            for j=k downto i+1
                        a[j]=a[j-1]
            endfor
            a[i]=temp
end

    4.      Heap Sort
Heap Sort adalah sort yang memanfaatkan prinsip Pohon Heap. Pohon Heap adalah pohon biner complete dimana nilai yang terkandung dalam simpul bapak atau Father (F) lebih besar atau lebih kecil dari nilai kedua buah simpul anaknya atau simpul Son (5), sedangkan nilai simpul anak cabang kiri bisa lebih besar, lebih kecil, atau sama dengan nilai simpul anak cabang kanan.

I.          Contoh Pohon Heap






II.        Contoh Bukan Pohon Heap


III.       Sistem Penomoran Pada Simpul



IV.       Proses Pada Heap Sort
• Data yang akan disort berada dalam array satu dimensi. Sudah diketahui bahwa array satu dimensi dapat diilustrasikan atau dinyatakan dalam pohon biner. Proses Heap Sort terdiri dari 2 tahap.
–        Susunan data dalam array diubah sedemikian rupa sehingga bila dinyatakan dalam pohon biner, maka pohonnya menjadi Pohon Heap.
       – Setelah data dalam array IBerbentukO Pohon Heap, kemudian dilakukan proses sort dengan mempertahankan pohon tetap sebagai Pohon Heap, tapi nilai urut menaik atau menurun berdasarkan nomor simpul.



V.        Proses Pada Heap Sort
1.         Menyusun array menjadi pohon heap (secara lojik)




Ilustrasi penerapan algoritma untuk data array di atas, terlihat seperti di bawah.



Isi tabel menjadi:



Isi tabel menjadi:



Isi tabel menjadi:





Datanya menjadi :







Hasil akhir pohon heap



2.         Mengurutkan array pohon heap




Ilustrasi proses pengurutan sebagai berikut:


Langkah Langkah Heap Sort Ascending





Langkah Langkah Heap Sort Descending




5.      SHAKER SORT
Algoritma Shaker sort merupakan improvement dari algoritma pengurutan Bubble sort. Cara kerja dari algoritma ini hampir sama dengan cara kerja dari algoritma Bubble Sort. Perbedaannya adalah Shaker sort melakukan pengurutan array dari dua arah.

Berikut ini merupakan Procedure shaker sort :
procedure ShakeSort(var X : ArrayType; N : integer);
 var
   L,
   R,
   K,
   J : integer;
 begin
   L := 2;
   R := N;
   K := N;
   repeat
       for J := R downto L do
            if (X[J] < X[J - 1]) then
                begin
                   Swap(X[J], X[J - 1]);
                   K := J
                end;
       L := K + 1;
       for J := L to R do
           if (X[J] < X[J - 1]) then
               begin
                  Swap(X[J], X[J - 1]);
                  K := J
               end;
       R := K - 1;
   until L >= R
end;


 procedure Swap(var X, Y : integer);
   var
       Temp : integer;
    begin
       Temp := X;
       X := Y;
       Y := Temp
   end;








By : Cutt Iswahyuni 
Diposting oleh di Tidak ada komentar:
Label:
Langganan: Postingan (Atom)