Saturday, July 6, 2013

Strukutur dan Organisasi Data 2

Halo teman-teman semua!
Pada postingan saya kali ini saya ingin menceritakan sedikit point-point ulasan mengenai materi yang ada pada mata kuliah saya semester 4 ini, Struktur dan Organisasi Data 2. Silahkan membaca :)


BAB 1. STRUKTUR DATA
Struktur data adalah cara menyimpan atau merepresentasikan data di dalam komputer agar bisa dipakai secara efisien.Sedangkan data adalah representasi dari fakta dunia nyata.Fakta atau keterangan tentang kenyataan yang disimpan, direkam atau direpresentasikan dalam bentuk tulisan, suara, gambar, sinyal atau simbol.

Secara garis besar type data dapat dikategorikan menjadi:
1.       Type data sederhana
- Type data sederhana tunggal, misalnya : Integer, real, boolean, dan karakter
- Type data sederhana majemuk, misalnya : String
2.   -    Struktur Data, meliputi:
- Struktur data sederhana, misalnya array dan Record
- Struktur data majemuk, yang terdiri:
    -Linier : Stack, Queue, serta List dan Multilist
    -Non Linier : Pohon Biner dan Graph
Pemakaian struktur data yang tepat di dalam proses pemrograman akan menghasilkan algoritma yang lebih jelas dan tepat,sehingga menjadikan program secara keseluruhan lebih efisien dan sederhana.
Struktur data yang ″standar″ yang biasanya digunakan dibidang informatika adalah,
- ADT , Array , Struk
- List linier (Linked List) dan variasinya
- Multilist
- Stack (Tumpukan)
- Queue (Antrian)
- Tree (Pohon)
- Graph (Graf)

Integer adalah anggota dari himpunan bilangan (…,-n+1, -n, -2, -1, 0, 1, 2, n, n+1, …). Operasi dasar dalam integer adalah +, -, *, /, ^.
Real adalah numeric yang bukan integer, digolongkan dalam jenis data real, dan ditulis dengan menggunakan titik decimal atau koma decimal.
Boolean adalah jenis data logical, yang mempunyai nilai True atau False.
Karakter adalah suatu himpunan yang terdiri atas bilangan abjad dan symbol khusus seperi (0, 1, …9, 10, A, B, c, d, Z, +, -, *, /,… )
String adalah barisan hingga karakter yang dibentuk oleh suatu kumpulan dari karakter.
Ada banyak istilah yang ada di string, seperti;
Jumlah karakter dalam string à length
Gabungan 2 buah string à concat
Sub bagian dari string à substr
Menyisipkan string ke dalam string lain à insert
Menghapus karakter dalam string à delete

Ada 3 cara bentuk mapping ke storage, yaitu;
1.       Skema sign and magnitude
2.       Skema one’s complement
3.       Skema two’s complement

BAB 2. ARRAY
Array adalah suatu himpunan hingga elemen, terurut dan homogen. Contoh dari array dimensi 1 yaitu vector. Bentuk umumnya N(L:U) à L(Lower Bound), U(Upper Bound).
Contoh dari array dimensi 2 adalah matriks, yaitu suatu array yang setiap elemennya merupakan tipe data array pula. Subskrip pertama disebut baris, subskrip kedua disebut kolom.
Pemetaan array ke storage;
Dimensi satu àB + (I-L) * S
Dimensi dua à 1. Row Major Order > B + (I-L1)*(U2-L2+1)*S+(J-L2)*S
2. Column Major Order > B+(J-L2)*(U1-L1+1)*S+(I-L1)*S
**Keterangan rumus: B = Base Location, S= setiap elemen dari array perbyte.
Array dimensi tiga adalah array yang setiap elemennya merupakan tipe data array juga yang merupakan array dimensi dua.
Cross section adalah pengambilan salah satu subskrip.
Transpose adalah penulisan baris menjadi kolom atau kolom menjadi baris.
Triangular array dapat berupa: Upper Tringular (semua elemen dibawah diagonal utama = 0), dan Lower Tringular (semua elemen diatas diagonal utama = 0).
Sparse array adalah suatu array yang sangat banyak elemen nol-nya.

BAB 3. STACK
1.       Linear List
Adalah suatu struktur data umum yang berisi suatu kumpulan terurut dari elemen. Jumlah elemen dapat berubah-ubah.
2.       Stack
Adalah bentuk khusus dari linear list, dengan operasi penyisispan dan penghapusan dibatasi hanya pada satu sisinya, yaitu sebagai puncak atau elemen atas (TOP(S)). Jumlah elemen didalam stack kita notasikan dengan NOEL(S). operator penyisipan disebut PUSH, dan operator penghapusan disebut POP. Operasi pada stack adalah LIFI (Last In First Out), contoh, tumpukan piring yang digunakan di café.

Empat operasi daar pada stack:
-          CREATE: operator yang menunjukan suatu stack kososng dengan nama S.
-          ISEMPTY: operator yang menentukan apakah stack S itu kosong.
-          PUSH: menambahkan elemen E pada puncak stack S.
-          POP(stack): menghapus sebuah elemen dari puncak stack S.
BAB 4. QUEUE (ANTREAN)
Queue adalah suatu bentuk khusus dari linear list dengan operasi penyisipan yang hanya boleh do satu sisi (rear), dan operasi penghapusan pada sisi lainnya (front).
Operasi antrean yaitu FIFO (First In First Out).

OPERASI-OPERASI PADA QUEUE
- Create()
o Untuk menciptakan dan menginisialisasi Queue
o Dengan cara membuat Head dan Tail = -1
- IsEmpty()
o Untuk memeriksa apakah Antrian sudah penuh atau belum
o Dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty
o Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala
antrian (elemen pertama dalam antrian) yang tidak akan berubahubah
o Pergerakan pada Antrian terjadi dengan penambahan elemen
Antrian kebelakang, yaitu menggunakan nilai Tail
- IsFull()
o Untuk mengecek apakah Antrian sudah penuh atau belum
o Dengan cara mengecek nilai Tail, jika Tail >= MAX-1 (karena MAX-1
adalah batas elemen array pada C) berarti sudah penuh
- Enqueue(data)
o Untuk menambahkan elemen ke dalam Antrian, penambahan
elemen selalu ditambahkan di elemen paling belakang
o Penambahan elemen selalu menggerakan variabel Tail dengan cara
increment counter Tail
- Dequeue()
o Digunakan untuk menghapus elemen terdepan/pertama dari Antrian
o Dengan cara mengurangi counter Tail dan menggeser semua
elemen antrian kedepan.
o Penggeseran dilakukan dengan menggunakan looping
- Clear()
o Untuk menghapus elemen-elemen Antrian dengan cara membuat
Tail dan Head = -1
o Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus
arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai
-1 sehingga elemen-elemen Antrian tidak lagi terbaca
- Tampil()
o Untuk menampilkan nilai-nilai elemen Antrian
o Menggunakan looping dari head s/d tail

BAB 5. GRAPH
Problema & Model Graf
Secara umum, langkah-langkah yang perlu dilalui dalam penyelesaian suatu masalah dengan bantuan komputer adalah sebagai berikut :
Problema ® Model Yang Tepat ® Algoritma ® Program Komputer
Graf Secara Formal
Sebuah Graf G mengandung 2 himpunan :
(1). Himp. V, yang elemennya disebut simpul
                ® Vertex / point / titik / node
(2). Himp. E, yang merupakan pasangan tak terurut dari simpul-simpul, disebut ruas
                ® Edge / rusuk / sisi
Sehingga sebuah graf dinotasikan sebagai G ( V, E )         




Contoh :
                G ( V, E )
                                V = { A, B, C, D }
                                E = { ( A, B ), ( B, C ), ( C, D ), ( D, A ), ( B, D ) }
Beberapa istilah lain dalam graf :
-          Berdampingan : simpul U dan V disebut berdampingan bila terdapat ruas (U,V)                                                                                                                                             
-          Order : banyaknya simpul
-          Size : banyaknya ruas
-          Self-loop (loop) / Gelung : ruas yang menghubungkan simpul yang sama ( sebuah simpul )
-          Ruas sejajar / berganda : ruas-ruas yang menghubungkan 2 simpul yang sama



Graf Null / Hampa
Ada beberapa pengertian tentang graf null/hampa. Di sini akan dipakai pengertian bahwa suatu graf dikatakan graf null/hampa bila graf tersebut tidak mengandung ruas.
Contoh :
Berdasarkan derajat simpul, sebuah simpul dapat disebut :
-          Simpul Ganjil, bila derajat simpulnya merupakan bilangan ganjil
-          Simpul Genap, bila derajat simpulnya merupakan bilangan genap
-          Simpul Bergantung / Akhir, bila derajat simpulnya adalah 1
-          Simpul Terpencil, bila derajat simpulnya adalah 0
Dalam keterhubungan sebuah graf, akan dikenal beberapa istilah-istilah berikut :
-          Walk : barisan simpul dan ruas
-          Trail : Walk dengan ruas yang berbeda
-          Path / Jalur :               Walk dengan simpul yang berbeda
-          Cycle / Sirkuit : Trail tertutup dengan derajat setiap simpul = 2




Agar kalian dapat lebih mengerti tentang materi graph ini, saya telah membuat langkah-langkah dalam pembuatan graph menggunakan aplikasi tertentu, dan mencari jalur terpendek dengan menggunakan metode Djikstra. Silahkan unduh di sini.

Semoga materi yang saya sampaikan ini berguna bagi kalian semua ^_^ 

sumber:
> Modul Diskusi Algotitma & Pemrograman Universitas Narotama Surabaya oleh Tony Hartono Bagio.
> Modul Stack dan Queue dengan Linked List oleh Harjanto Sutejo.
> Graph dan Analisis Algoritma oleh Marhaendi.