kali ini saya akan membagikan makalah Struktur Ogranisasi Data dengan materi Stack.





Pengenalan stack yang kita pelajari sudah mulai dari  semester 2 yang lalu, dan berlanjut hingga semester 4 ini.

Stack merupakan urutan elemen yang mengikuti konsep LIFO (Last In First Out). Maksud dari kata itu adalah, suatu antrian yang terakhir masuk kedalam antrian tersebut tetapi antrian itu yang paling awal dikeluarkan contohnya seperti tumpukan dalam suatu kardus yang paling atas, yang duluan diambil. Add(penambahan) dan remove(penghapusan) selalu dilakukan dari atas.

Operasi pada stack:

a. Create (stack)
b. Isempty (stack)
c. Push (elemen, stack)
d. POP

Stack atau tumpukan adalah bentuk khusus dari linear list. Pada stack, penghapusan serta pemasukan elemennya hanya dapat dilakukan di satu posisi, yakni posisi akhir dari list. Posisi ini disebut puncak atau top dari stack. Elemen stack S pada posisi ini dinyatakan dengan TOP(S).

Jelasnya, bila stack S [S1, S2, …, ST], maka TOP(S) adalah ST. Banyaknya elemen
stack S pada suatu saat tertentu biasa kita sebut sebagai NOEL(S). Jadi untuk stack kita di atas, NOEL(S) = T. Seperti halnya pada semua linear list, pada stack dikenal operasi penghapusan dan pemasukan. Operator penghapusan elemen pada stack disebut POP, sedangkan operator pemasukan elemen, disebut PUSH. Untuk menggambarkan kerja kedua operator di atas.

Meskipun stack amat luas digunakan, banyak bahasa pemrograman tidak mempunyai tipe data stack secara built-in. Dalam hal ini, Pemrogram harus memanipulasi sendiri fasilitas yang dimiliki bahasa pemrograman tersebut, untuk dapat melakukan operasi stack terhadap variabel stack.

Mungkin cara yang paling sederhana adalah membentuk stack dalam bentuk semacam array. Jelas kita harus membedakan suatu stack dengan suatu array yang sesungguhnya. Pemrogram harus memaksakan berlakunya aturan LIFO (Last In First Out) bagi stack. Selain itu juga, penempatan stack dalam bentuk array mengakibatkan suatu keterbatasan, yakni bahwa elemen stack harus homogen. Keterbatasan lain yang timbul adalah keharusan.

Pemrogram untuk menentukan batas atas dari subscript array, walaupun stack secara teori tidak memiliki batas maksimum dalam jumlah elemen. Jika diinginkan, seharusnya kita dapat membuat stack yang panjangnya tak hingga. Satu hal yang nyata membedakan stack dengan array adalah banyaknya elemen stack yang dapat bertambah atau berkurang setiap waktu, sementara banyaknya elemen sebuah array selalu tetap.



* LINEAR LIST

Linear List adalah suatu struktur data yang merupakan himpunan terurut. Misal didefinisikan  suatu linear list A yang terdiri atas T buah elemen sebagai berikut :


Jika T = 0, maka A dikatakan sebagai “Null List”.
Suatu elemen dari sembarang posisi pada linear list A dapat dihilangkan. Sebaliknya, suatu elemen baru dapat dimasukkan ke dalam list dan dapat menempati sembarang posisi pada list tersebut. Jadi suatu linear list dapat berkurang atau bertambah setiap saat.

* DEFINISI STACK

Stack adalah suatu bentuk khusus dari linear list di mana operasi penyisipan dan penghapusan atas elemen-elemennya hanya dapat dilakukan pada satu sisi saja yang disebut sebagai “TOP”.
Misal diberikan Stack S sebagai berikut :


Untuk menunjukkan jumlah elemen suatu stack digunakan notasi NOEL. Dari stack di atas, maka NOEL(S) = T. Selanjutnya, jika diberikan sebuah stack S = [A,B,C,D], maka stack S ini dapat digambarkan sebagai berikut :



* OPERASI DASAR PADA STACK

Ada empat operasi dasar yang didefinisikan pada stack, yaitu :

1. CREATE(stack)
2. ISEMPTY(stack)
3. PUSH(elemen,stack)
4. POP


1. CREATE
Operator ini berfungsi untuk membuat sebuah stack kosong dan didefinisikan bahwa :


2. ISEMPTY
Operator ini berfungsi untuk menentukan apakah suatu stack adalah stack kosong. Operasinya akan bernilai boolean, dengan definisi sebagai berikut :

Catatan : ISEMPTY(CREATE(S)) = true.

3. PUSH
Operator ini berfungsi untuk menambahkan satu elemen ke dalam stack. Notasi yang digunakan adalah :

PUSH(E,S)

Artinya : menambahkan elemen E ke dalam stack S.
Elemen yang baru masuk ini akan menempati posisi TOP.
Jadi : TOP(PUSH(E,S)) = E.

Akibat dari operasi ini jumlah elemen dalam stack akan bertambah, artinya NOEL(S) menjadi lebih besar atau stack menjadi tidak kosong (ISEMPTY(PUSH(E,S)) = false).

4. POP
Operator ini berfungsi untuk mengeluarkan satu elemen dari dalam stack.Notasinya:

                                             POP(S)

Elemen yang keluar dari dalam stack adalah elemen yang berada pada posisi TOP.
Akibat dari operasi ini jumlah elemen stack akan berkurang atau NOEL(S) berkurang dan elemen pada posisi TOP akan berubah. Operator POP ini tidak dapat digunakan pada stack kosong, artinya :

POP(CREATE(S)) = error condition

Catatan : TOP(PUSH(E,S)) = E


* DEKLARASI STACK PADA BAHASA PEMROGRAMAN

Dalam bahasa pemrograman, untuk menempatkan stack biasanya digunakan sebuah array. Tetapi perlu diingat di sini bahwa stack dan array adalah dua hal yang berbeda. Misalkan suatu variabel S adalah sebuah stack dengan 100 elemen. Diasumsikan elemen S adalah integer dan jumlah elemennya maksimum adalah 100 elemen. Untuk mendeklarasikan stack dengan menggunakan array, harus dideklarasikan pula variabel lain yaitu TOP_PTR yang merupakan indeks dari array. Variabel TOP_PTR ini digunakan untuk menyatakan elemen yang berada pada posisi TOP dalam stack tersebut. Selanjutnya gabungan kedua variabel ini diberi nama STACK_STRUCT. Kemudian didefinisikan bahwa :

NOEL(S) = TOP_PTR
ISEMPTY(S) = TRUE, jika TOP_PTR = 0 dan
                    FALSE, jika TOP_PTR > 0.

Maka bentuk deklarasinya dalam PASCAL adalah :

TYPE Stack_Struct = Record
        Stack   : array[1..100] of integer;
        TopPtr : integer;
End;
VAR S : Stack_Struct;

Selanjutnya, untuk keperluan operasi PUSH dan POP harus dibuat suatu prosedur tersendiri, yaitu :

PROCEDURE PUSH(Eon : integer);
Begin
If (S.TopPtr < NoelMax) Then 
Begin
S.TopPtr := S.TopPtr + 1;
S.Stack [S.TopPtr] := Eon
End
Else Overflow_Condition
End;

PROCEDURE POP(Eoff : integer);
Begin
If (S.TopPtr > 0) Then 
Begin
Eoff := S.Stack[S.TopPtr];
S.TopPtr := S.TopPtr - 1
End
Else Underflow_Condition  
End;

Catatan :
Overflow adalah suatu keadaan di mana kita melakukan operasi PUSH terhadap stack dalam keadaan penuh. Underflow adalah keadaan di mana kita melakukan operasi POP terhadap stack kosong. Eon adalah elemen yang akan dimasukkan ke dalam stack dan Eoff adalah elemen yang akan dikeluarkan dari dalam stack.


* PENGGUNAAN / APLIKASI STACK

Logika stack digunakan untuk menyelesaikan berbagai macam masalah. Antara lain digunakan pada compiler, operating system dan dalam program-program aplikasi. Berikut ini tiga buah contoh aplikasi stack, yaitu :

* MATCHING PARENTHESES

Proses ini dilakukan compiler untuk memeriksa kelengkapan tanda kurung yang terdapat pada suatu ekspresi aritmetik. Sedangkan stack di sini digunakan sebagai tempat prosesnya. Algoritma yang digunakan adalah :

1.Elemen-elemen suatu ekspresi aritmetik (string) di-Scan dari kiri ke kanan.
2.Jika ditemukan simbol "(" atau "Left parenthesis", maka simbol tersebut di-push ke dalam stack.
3. Jika ditemukan simbol ")" atau "Right parenthesis", maka isi stack diperiksa.
* Jika stack kosong
* terjadi kesalahan.
berarti : ada simbol ")", tetapi tidak ada simbol "(" yang seharusnya mendahului.
*Jika stack tidak kosong * artinya ada pasangannya dan langsung di-POP keluar stack.

Misalkan NEXT CHAR adalah suatu karakter terakhir dalam suatu string. Berikut ini bentuk flowchart (logika proses) yang digunakan pada proses matching ini :





* NOTASI POSTFIX

Bentuk aplikasi stack yang lain adalah mengubah suatu ekspresi aritmatik (string) ke dalam notasi postfix. Notasi postfix ini digunakan oleh compiler untuk menyatakan suatu ekspresi aritmatik dalam bahasa tingkat tinggi (high level language). Stack digunakan oleh compiler untuk mentransformasikan ekspresi aritmatik menjadi suatu ekspresi dalam bentuk/notasi postfix.

Contoh :
Misal diberikan ekspresi aritmatik : A + B ;
Maka bentuknya dalam notasi postfix menjadi : AB+
Urutan (prioritas) dari operator adalah :
1. Perpangkatan (^)
2. Perkalian (*) atau Pembagian (/)
3. Penjumlahan (+) atau Pengurangan (-)

Aturan yang digunakan dalam proses transformasi tersebut adalah :

• Ekspresi aritmatik yang diberikan di- "Scan" dari kiri ke kanan.
• Bila simbol yang di-scan adalah "(", maka simbol tersebut di push ke dalam stack.
• Bila simbol yang di-scan adalah ")", maka seluruh isi stack di pop keluar mulai dari simbol "(" yang pertama ditemukan dalam stack.
• Bila simbol adalah operator, maka dilakukan perbandingan dulu dengan simbol (operator) yang berada pada posisi top dalam stack.

1. Jika derajatnya setara atau lebih rendah dari simbol yang berada pada posisi top, maka top stack di-pop keluar sebagai output dan simbol yang baru di-push ke dalam stack.
2. Jika derajatnya lebih tinggi dari simbol yang berada pada posisi top, maka simbol (operator) yang di-scan tersebut di-push ke dalam stack.
3. Bila simbol yang di-scan adalah operand, maka simbol tersebut langsung sebagai output.
4. 6Bila simbol adalah ";" maka seluruh isi stack di-pop sebagai output.

Contoh :
Misal diberikan sebuah ekspresi aritmatik dengan bentuk sbb:

( (A + B) * C / D + E ^ F ) / G ;

Selanjutnya akan dicari bentuk ekspresi diatas dalam notasi postfix.
Proses yang dilakukan dapat digambarkan dalam tabel berikut :



Pemanggilan ketiga procedure HITUNG, dimana nilai Thn = 23







  MAPPING KE STORAGE DARI STACK

       Bentuk mapping ke storage dari stack yang paling sederhana adalah dengan menggunakan pendekatan array satu dimensi. Hal ini karena sarana yang digunakan untuk menyatakan suatu stack adalah array.
       Jika diberikan stack S dengan m elemen maka bentuk mappingnya seperti mapping array satu dimensi dengan m elemen.



Selanjutnya jika terdapat dua stack S1 dan S2 masing-masing dengan jumlah maksimum elemennya adalah M dan N, maka kedua stack ini dialokasikan dalam dengan bentuk sbb:


Konsep mapping seperti diatas dianggap tidak efisien, terutama jika S1 dan S2 tidak penuh pada saat yang bersamaan.

Cara dianggap lebih baik adalah :
Jika diketahui bahwa jumlah elemen S1 dan S2 tidak melebihi jumlah tertentu, misal N.


Maka bentuk mapping yang digunakan adalah :


Terimakasih sudah datang dan membaca artikel kami Sertakan link sumber untuk menghargai karya cipta orang lain :)

Terimakasih sudah datang dan membaca artikel kami Sertakan link sumber untuk menghargai karya cipta orang lain :)

1. Pengertian newton raphson !
2. Soal + jawaban !


Diketahui fungsi ƒ(x) dan turunannya ƒ '(x), kita memulai dengan tebakan pertama, x 0 . Hampiran yang lebih baik x 1 adalah







Contoh :

Tentukan akar dari persamaan 4x3 – 15x2 + 17x – 6 = 0 menggunakan Metode Newton Raphson. Penyelesaian :

f(x) = 4x3 – 15x2 + 17x – 6
f’(x) = 12x2 – 30x + 17

iterasi 1 :
ambil titik awal x0 = 3

f(3) = 4(3)3 – 15(3)2 + 17(3) – 6 = 18
f’(3) = 12(3)2 – 30(3) + 17 = 35
x1 = 3 – 18/35 = 2.48571

Berikut ini adalah gambar Coding program Regula falsi :




Atau Kalian Bisa Copas Kodingnya disini :


uses crt;
label ulang;
var
x1,x2,x3,y1,y2,y3 : real;
i : integer;
Ab :char;
data1 : real;
begin
    ulang:
    clrscr;
    writeln('Tentukan nilai akar dari persamaan f(x)=x^3+x^2-3x-3=0 dengan Regula Falsi');
    write('Masukan nilai x1 = ');readln(x1);
    y1 := x1 * x1 * x1 + x1 * x1 - 3 * x1 - 3;
    writeln(' Nilai f(x1)= ',y1:0:4);
    repeat
    begin
      write( 'Masukan nilai x2 = ' ); readln(x2);
      y2 := x2 * x2 * x2 + x2 * x2 - 3 * x2 - 3;
      write(' Nilai f(x2)= ',y2:0:4);
    end;
    if (y1*y2)<0 then
      Writeln(' Syarat Nilai Ok')
    else
      Writeln(' Nilai X2 Belum Sesuai');
    until ( y1 * y2 ) <0;
    writeln;
    writeln('Penyelesaian persamaan karekteristik dengan metoda regula falsi');
    writeln('----------------------------------------------------------------------');
    writeln(' n          x                    f(x)               error ');
    writeln('----------------------------------------------------------------------');
    repeat
    begin
      i:= i + 1; x3 := ( x2-( y2 / ( y2 - y1))*(x2-x1));
      y3 := x3 * x3 * x3 + x3 * x3 - 3 * x3 - 3;
    if i<10 then
      writeln(' ',i,' : ',x3,' : ',y3,' : ',abs(y3),' : ')
    else
      writeln(i,' : ',x3,' : ',y3,' : ',abs(y3),' : ');
    if ( y1 * y3 ) <0 then
      begin
      x2 := x3 ; y2 := y3 ;
      end
    else
    begin
      x1 := x3 ; y1 := y3;
    end;
    end;
    until abs( y3 ) < 1E-07;
    writeln('----------------------------------------------------------------------');
    writeln('Akar persamaannya= ',x3);
    writeln('Errornya=' ,abs( y3 ));
    writeln('----------------------------------------------------------------------');
    write('Apakah anda ingin mengulangi (y/t): ');
    readln(ab);
    if (ab='y') or (ab='Y') then
      begin
      goto ulang;
      end
    else
end.

Atau bisa di download saja disini : Download !


Hasil Outputnya akan seperti ini : (jika di isi Nilai X1 = 1 & X2 = 2 )




Jika di kerjakan secara manual maka akan seperti ini :

xc = xb - (f(xb) / f(xb) - f(xa)) *(xb - xa)

Carilah penyelesaian dari persamaan nonlinear di bawah ini dengan metode Regula Falsi:
f(x) = x3 + x2 - 3x - 3 = 0

Penyelesaian:

Langkah 1: Menentukan dua titik nilai f(x) awal, f(x1) dan f(x2) dan harus memenuhi hubungan f(x1)*f(x2)<0. misalkan nilai x1 = 1 dan x2 = 2.
f(x1)= 13 + 12 - 3(1) – 3 = -4
f(x2)= 23 + 22 - 3(2) – 3 = 3

Di dapat F(x1)*f(x2)<0 maka titik penyelesaian berada di antara nilai x1 = 1 dan x2 = 2.

Langkah 2: mencari nilai x3 dengan persamaan :
x3 = x2 - (f(x2) / f(x2) - f(x1)) *(x2 - x1)
Dan f(x3)= 1.571423 + 1.57142 2 - 3(1.57142) – 3 = -1.3644314869

Langkah 3: Melakukan Iterasi dengan persamaan 2.1 pada hasil langkah 2 nilai f(x3) hasilnya negative, dan untuk memnentukan nilai x4 harus f(xa*f(xb)<10 maka yang memenuhi syarat nilai yang digunakan yaitu x2 dan x3 karena nilai f(x2)*f(x3)<0 maka :

x4 = 2 - (3 / 3 - (-1.3644)) *(3 - 1.57142) = 1.7054108216
Dan f(x4) = 1.705413 + 1.705412 - 3(1.70541) – 3 = -0.247745

Iterasi selanjutnya mencari nilai x5 dan f(x5) dan begitu seterusnya sampai didapatkan nilai error lebih kecil dari 10-7. Maka dari hasil perhitungan didapatkan nilai x = 1.7320508074.
dengan nilai errornya f(x)= 2.0008883439E-09


sumber : http://myleaf-clover.blogspot.com/2013/04/la-matlan-2-iii.html

Terimakasih sudah datang dan membaca artikel kami Sertakan link sumber untuk menghargai karya cipta orang lain :)

2. Dengan menggunakan rumus x^3 + x^2 – 3x – 3
dapat dicari nila f(x) dari suatu nilai x nya itu sendiri.
Sedangkan untuk mencari nilai x3 rumusnya adalah x1 + x2 / 2.
pencarian akar persamaan terus berjalan sampai nilai errornya mendekati/abs 10^-7.
Pencarian akar persamaan akan berlanjut asalkan memenuhi syarat (fx1*fx2) < 0.

Contoh :

x1 = 7
x2 = 1

f(x1) = 7^3 + 7^2 – 3(7) – 3 = 368
f(x2) = 1^3 + 1^2 – 3(1) – 3 = -4

selanjutnya kita mencari nilai x3;
x3 = x1 + x2 / 2
    = 7 + 1 / 2
= 4
Kemudian mencari f(x3);
f(x3) = 4^3 + 4^2 – 3(4) – 3 = 65

lalu mencari nilai x4;

untuk mencari nilai x4 perlu diketahui kita menggunakan x1 dengan x3 atau x2 dengan
x3 , berhubung f(x) yang mengandung nilai minus ada pada x2 maka sebaiknya kita gunakan x2 dengan x3 maka didapat;

x4 = x2 + x3 / 2
= 1 + 4 / 2
= 2.5

Dan cari juga nilai f(x4);
f(x4) = 2.5^3 + 2.5^2 – 3(2.5) – 3 = 11,375

Dan seteruuussssnyaaaa sampai error mendekati 10^-7.


Terimakasih sudah datang dan membaca artikel kami Sertakan link sumber untuk menghargai karya cipta orang lain :)