Selasa, 20 Desember 2011

Tutorial 1 - 5


video video video video

STACK

Pengertian

Secara Bahasa, Stack di artikan dengan  tumpukan.Jika dihubungkan dengan struktur data, Stack dapat di artikan sebagai sekumpulan data yang organusasi atau strukturnya bersifat tumpukan atau menyerupai tumpukan.

Ilustrasi Stack

Terdapat dua buah kotak yang satu akan ditumpuk di atas kotak yang lainnya. Jika kemudian stack dua kotak tadi, ditambah kotak ketiga, keempat, kelima, dan seterusnya, maka akan diperoleh sebuah stack yang terdiri dari N kotak.


Ciri-ciri Stack

1.       Elemen Top (puncak) diketahui
2.       Penyisipan atau penghapusan elemen selalu dilakukan di Top
3.       Bersifat LIFO (Last In First Out)
Yang berarti data yang terakhir masuk ke dalam stack akan menjadi data pertama yang dikeluarkan dari stack.

Operasi  Stack
·         Create, digunakan untuk membuat stack baru
·         Push, digunakan untuk menambahkan elemen pada urutan terakhir
·         Pop, digunakan untuk mengambil elemen stack pada tumpukan paling atas
·         Clear, digunakan untuk mengosongkan stack
·         Print, digunakan untuk menampilkan semua elemen-elemen stack
·         IsEmpty, digunakan untuk mengecek apakah stack dalam keadaan kosong
·         IsFull, digunakan untuk memeriksa apakah sudah penuh

Manfaat Stack :

·         Pengolahan struktur  yang “nested” (berisi salinan dirinya sendiri di dalam dirinya), Misalnya Pengolahan ekspresi aljabar, himpunan dari himpunan
·         Implementasi algoritma parsing, evaluasi dan backtracking
·         Digunakan OS untuk memungkinkan pemanggilan prosedur secara nested
·         Digunakan untuk memungkinkan konversi program rekursif menjadi non-rekursif
·         Untuk mendukung mekanisme Pushdown Automata (PDA)
·         Untuk mendukung kompailer mengkonversi infix menjadi postfix dan kemudian mengevaluasi postfix menjadi atomic (assembly) command

Sorting


Pengertian Sorting

                Adalah Proses Pengurutan data yang sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut suatu aturan tertentu

Dua Cara Pengurutan Data

·         Ascending
Pengurutan dilakukan mulai dari nilai terkecil menuju nilai terbesar

·         Descending
Pengurutan dilakukan mulai dari nilai terbesar menuju
nilai terkecil
 
 
Bubble Sort

                Adalah sederhana algoritma sorting. Bekerja dengan berulang kali melakukan melalui daftar akan di sortir, membandingkan dua item sekaligus dan swapping mereka jika mereka berada di salah pesanan

Contoh pengurutan Bubble sort:

Misalkan kita mempunyai sebuah array dengan elemen-elemen
“ 4 2 5 3 9”. Proses yang akan terjadi apabila digunakan algoritam bubble sort adalah sebagai berikut

Pass Pertama
(4 2 5 4 9) menjadi (2 4 5 3 9)
(2 4 5 3 9) menjadi (2 4 5 3 9)
(2 4 5 3 9) menjadi (2 4 3 5 9)
(2 4 3 5 9) menjadi (2 4 3 5 9)

Pass Kedua
(2 4 3 5 9) menjadi (2 4 3 5 9)
(2 4 3 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)

Pass Ketiga
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)

                Dapat dilihat pada proses di atas, sebenarnya pada pass kedua, langkah kedua, array telah terurut. Namun algoritma tetap dilanjutkan hingga pass kedua berakhir. Pass ketiga dilakukan karena definisi terurut dalam algoritma bubblesort adalah tidak ada satupun penukaran pada suatu pass, sehingga pass ketiga dibutuhkan untuk memverifikasi keurutan array tersebut

Kelebihan Bubble sort

·         Algoritma yang simple
·         Mudah untuk diubah menjadi kode
·         Definisi terurut terdapat dengan jelas dalam algoritma
·         Cocok untuk pengurutan data dengan elemen kecil telah terurut

Kekurangan Bubble sort

·         Tidak efektif dalam pengurutan data berskala besar
·         Langkah pengurutan yang terlalu panjang
 
Selection Sort

        Adalah mencari elemen yang tepat untuk diletakkan di posisi yang telah diketahui, dan meletakkannya di posisi tersebut setelah data tersebut ditemukan

Contoh Selection Sort :
 
Algoritma Selection Sort

Jumlah Data : 6
Data Awal : 5 2 4 7 6 3

Iterasi ke-1 : 2 5 4 7 6 3
Iterasi ke-2 : 2 3 5 7 6 4
Iterasi ke-3 : 2 3 4 7 6 5
Iterasi ke-4 : 2 3 4 5 7 6
Iterasi ke-1 : 2 3 4 5 6 7
                       
 
 
Insertion Sort

                Dapat dirangkum sebagai berikut :
·         Simpan nilai ti kedalam variabel sementara, dengan I = 1
·         Bandingkan nilainya dengan elemen sebelumnya
·         Jika elemen sebelumnya (Ti-1) lebih besar nilainya daripada Ti, maka tindih nilai Ti dengan nilai Ti-1 tersebut. Decrement i (kurangi nilainya dengan 1)
·         Jika Ti-1 Ti terpenuhi, tindih nilai di Ti dengan variabel sementara yang disimpan sebelumnya
·         Ulangi langkah dari poin q di atas dengan i di-increment (ditambah satu)

Contoh Insertion Sort :

QUEUE

QUEUE

Pengertian

Secara Bahasa, Queue di artikan dengan  antrian.Jika dihubungkan dengan struktur data, Stack dapat di artikan sebagai suatu bentuk khusus dari linear list dengan operasi penyisipan hanya pada salah satu sisi dan operasi penghapusan hanya diperbolejkan pada sisi lainnya dari list.

                Operasi Queue

·         EnQueue,  digunakan untuk memasukkan data ke dalam antrian
·         DeQueue, digunakan untuk mengeluarkan data terdepan dari antrian
·         Clear, digunakan untuk menghapus seluruh antrian
·         IsEmpty, digunakan untuk memeriksa apakah antrian kosong
·         IsFull, digunakan untuk memeriksa apakah antrian penuh

Ciri-Ciri Queue

·         Bersifat FIFO (First In First Out)

GRAPH

GRAPH


Pengertian Graph

                Adalah Jenis Struktur data yang terdiri dari simpul atau titik (vertex) dan garis (edge), dimana dalam graph tersebut, vertex-vertex yang ada dihubungkan oleh edge, hingga menjadi suatu kesatuan.

Secara Matematis, dinyatakan :

G = (V, E)

Keterangan :
V = Simpul atau Vertex atau Node atau Titik
E = Edge atau Arc atau Garis
G = Graph












Jenis-Jenis Graph :

·         Graph Berarah (Directed graph)
Jika sisi-sisi graph hanya berlaku satu arah. Misalnya :
{x, y} yaitu arah x ke y, bukan dari y ke x; x disebut origin dan y disebut terminus . Secara notasi sisi di graph ditulis sebagai vector (x, y).

·         Graph Tak Berarah (Undirected Graph)
Setiap sisi {x, y} berlaku pada kedua arah: baik x ke y mau pun y ke x.Secara grafis sisi pada undirected graph tidak memiliki mata panah dan secara notasional menggunakan kurung kurawal.

·         Graph Berbobot
Suatu Graph dimana edge dari graph tersebut memiliki bobot atau nilai

·         Graph Tak Berbobot
Suatu Graph dimana edge dari graph tersebut tidak memilik bobot atau nilai

Contoh Graph :

TREE

TREE

Pengertian Tree
               
Adalah graph terhubung yang tidak mengandung sirkuit. Karena merupakan graph terhubung, maka pada pohon selalu terdapat path atau jalur yang menghubungkan setiap dua simpul dalam pohon

Sifat Utama Sebuah Pohon Biner :

·         Jika pohon mempunyai simpul sebanyak n, maka banyaknya ruas atau edge adalah (n-1)

·         Mempunyai simpul khusus yang disebut AKAR atau ROOT, jika simpul tersebut memiliki derajat ke luar >= 0, dan derajat masuk = 0

·         Mempunyai simpul yang disebut sebagai DAUN atau LEAF, jika simpul tersebut berderajat keluar = 0 dan berderajat masuk = 1

·         Setiap simpul mempunyai TINGKATAN atau LEVEL, yang dimulai dari root, yang levelnya = 0, sampai dengan level n pada daun paling bawah. Simpul yang mempunyai level yang sama disebut Bersaudara atau Brother atau Sibling


·         Pohon mempunyai KETINGGIAN atau KEDALAMAN atau HEIGHT, yang merupakan level tertinggi + 1

·         Pohon mempunyai BERAT atau WEIGHT yang merupakan banyaknya daun pada pohon


Contoh Tree :