PELAKSANAAN STRUKTUR DATA MELALUI TEORI DAFTAR

ABSTRAK

Konsep set dapat didefinisikan melalui fungsi karakteristik dan tas didefinisikan melalui fungsi hitungan. Mengikuti pendekatan ini, Tripathy, Ghosh dan Jena memperkenalkan konsep Fungsi posisi untuk menentukan daftar. Definisi baru memiliki banyak kekakuan dari yang sebelumnya digunakan dalam ilmu komputer  khususnya  dalam pemrograman umum dan fungsional . Beberapa konsep dalam bentuk operasi, operator dan properti telah dibentuk di urutan makalah yang ditulis oleh Tripathy. Juga, konsep daftar kabur  dan bahwa dari daftar kabur intuitionistic  memiliki didefinisikan dan dipelajari oleh mereka. Baru-baru ini sebuah aplikasi untuk mengembangkan daftar teori database  relasional dan operasi telah diajukan oleh Tripathy dan Gantayat . Dalam artikel kami ini menyediakan aplikasi lain dari pendekatan ini dalam mendefinisikan struktur data seperti Stack, Antrian dan Array dan mendirikan operasi pada mereka. Salah satu keuntungan utama dari pendekatan ini adalah kemudahan dalam memperluas semua konsep untuk daftar dasar untuk konteks daftar kabur  dan daftar kabur intuitionisti. Didalam makalah, kita menggambarkan bagaimana hal ini dapat dilakukan. Pengertian tentang daftar kabur dan daftar kabur intuitionistic yang baru dan setidaknya dihadiri konsep dan karya-karya dalam makalah ini akan membuka area aplikasi baru untuk mengembangkan fuzzy dan struktur data intuitionistic fuzzy.

KEYWORDS

Daftar, daftar Fuzzy, daftar kabur Intuitionistic, Stack, Antrian, Array

 

  1. PERKENALAN

Seperti yang kita ketahui, konsep dan Fungsi Pertukaran. Serta fungsi menghitung yang telah termasuk di pertukaran. Jadi wajar saja apabila konsep ini termasuk fungsi yang umum di bidang ilmu data komputer. Pertama kali diperkenalkan oleh Tripathy, Ghosh dan Jena. Gagasan fungsi posisi ini lalu dikembangkan lagi menjadi banyak konsep yang terkait dengan daftar melalui definisi baru. Mereka juga mencetuskan beberapa teorema yang mengungkap sifat dari sebuah daftar. Konsep fuzzy set intuitionistic diperkenalkan oleh Atanassov. Merupakan perluasan dari konsep fuzzy set dan menjadikan model yang lebih baik dari fuzzy set di data. Pada bab ini kita akan membahas tentang berbagai fungsi struktur data. Dengan tujuan mempermudah pengolahan data.

 

  1. DEFINISI DAN SIFAT

Definisi 2.1: Sebuah daftar L yang diambil dari satu set X diwakili oleh PL fungsi posisi, didefinisikan sebagai

PL: X → P (N),

dimana P (N) menunjukkan kekuatan set himpunan bilangan bulat non-negatif N.

Definisi 2.2: Untuk setiap daftar yang terbatas L diambil dari X, anggota himpunan L dilambangkan dengan #L dan didefinisikan sebagai

1

setiap kali sisi kanan ada. Dalam hal ini L dikatakan terbatas, jika L dikatakan tak terbatas.

Definisi 2.3: Untuk setiap daftar yang terbatas L diambil dari X, kebalikan dari L, dilambangkan dengan rev (L) adalah daftar pada X, dan diberikan oleh fungsi posisi,

2

Definisi 2.4: Untuk setiap daftar yang terbatas L diambil dari X, kepala L merupakan unsur dilambangkan dengan hd (L), di mana hd (L) = x jika 0 PL (x).

Definisi 2.5: Misalkan L daftar. Kami mendefinisikan ekor L dilambangkan dengan tl (L) sebagai

3

Definisi 2.6: Untuk setiap daftar L kita mendefinisikan fungsi init dan terakhir sebagai:

init (L) = rev (tl (rev (L))) dan last(L) = x; jika (# L -1) IPL (x).

Definisi 2.7: Untuk setiap x X dan daftar L yang diambil dari X, kita menunjukkan daftar yang diperoleh dengan menambahkan elemen x pada awal daftar L oleh kontra (x, L) dan menentukan dengan nya fungsi keanggotaan,

4

Definisi 2.8: Sebuah daftar L kosong jika PL (x) =  untuk setiap x X dan dinotasikan sebagai L = [].

Definisi 2.9: Biarkan L1 dan L2 menjadi dua daftar yang terbatas diambil dari X. Kemudian kita mendefinisikan Rangkaian dari L1 dan L2 dilambangkan dengan L1╫L2 dan diberikan oleh fungsi posisi,

5

Definisi 2.10: Misalkan L daftar terbatas diambil dari X dan [x] menjadi daftar tunggal. Kemudian posisi fungsi dari daftar L – [x] didefinisikan sebagai berikut

Kasus I: PL(x)

6

Kasus II: PL(x)

7

Definisi.2.11: Biarkan L1 dan L2 akan dua daftar ditarik dari X, maka zip dari L1 dan L2 diberikan sebagai

8

Definition.2.12: Untuk setiap dua hingga daftar L dan L ` diambil dari X, perbedaan daftar L

– L ` diberikan oleh fungsi posisinya, didefinisikan secara rekursif oleh

9

Definisi 2.13: Misalkan L daftar terbatas diambil dari X. Kemudian operator ambil pada L, untuk diberikan n N, dilambangkan dengan mengambil (n, L) dan itu adalah daftar yang fungsinya posisi diberikan oleh

10

Definisi 2.14: Misalkan L daftar terbatas yang diambil dari X. Kemudian, untuk setiap n  N drop operator pada L dilambangkan dengan drop (n, L) dan itu adalah daftar yang fungsinya posisi diberikan oleh

11

Definisi 2.15: Untuk setiap daftar L diambil dari X dan sejumlah n alami, kita mendefinisikan elemen

Indeks (L, n) sebagai XX, sehingga x = hd (mengambil (n + 1, L) – mengambil (n, L).

Berikut dua sifat daftar, yang Teorema didirikan pada ([7]) yang akan digunakan dalambagian yang akan datang:

Teorema 2.1: Jika L1 dan L2 adalah daftar yang diambil dari X dan f adalah pemetaan dari X ke X, maka untuk setiap n  N,

12

Teorema 2.2: Untuk setiap n  N dan untuk daftar L1 dan L2 diambil dari X,

13

3.   STRUKTUR DATA MELALUI DAFTAR

 

  1. INTUITIONISTIC FUZZY STRUKTUR DATA MENGGUNAKAN INTUITIONISTIC FUZZY LISTS

Gagasan dari intuitionistic fuzzy list yang sudah diperkenalkan

 4.1 : Salah satu cara untuk melalu literatur bahwa gagasan dari fuzzy list dan oleh karena itu, fuzzy stack, fuzzy queue, fuzzy array dan sesuai operasi intuitionistic fuzzy adalah sepenuhnya baru. Kami telah memperkenalkan pendekatan sehingga dapat mengembangkan relasi database dalam [9]. Menggunakan gagasan dari  fuzzy list dan intuitionistic fuzzy list dan struktur data yang didefinisikan berdasarkan ketika seperti array, salah satu dapat mengembangkan teori intuitionistic fuzzy list dan teori intuitionistic fuzzy list database. Dalam aplikasi modern tanpa diduga telah menjadi bagian integral dan database yang diusulkan akan menjadi bagian terpenting dari nilai sebuah aplikasi.

Definisi 5.1 : Sebuah intuitionistic fuzzy list L yang diterapkan pada X yaitu menggambarkan sesuai posisi dari fungsi PL yang didefinisikan sebagai

PL : X x J -> P(N)

Dimana = { (a , b) : a,b Î[0 ,1] and 0£ a + b £ 1} dan P(N) merupakan set dari keseluruhan set dari N. Dengan demikian, untuk semua X Î X dan (a,b) Î J, PL(x, (a,b)) menyediakan posisi dari set dimana elemen X terjadi dalam L dengan tingkatan dari anggota (a,b).

Sebuah intuitionistic fuzzy list merupakan sebuah ekstensi dari fuzzy list. Intuitionistic fuzzy struktur data seperti intuitionistic fuzzy STACK (IF-STACK), intuitionistic fuzzy QUEUE(IF-QUEUE) dan intiunistic fuzzy ARRAY (IF-ARRAY) merupakan ekstensi sesuai dengan versi fuzzy.

Beberapa operasi pada STACK/F-STACK, QUEUE/IF-QUEUE dan ARRAY/IF-ARRAY secara luas dapat digunakan untuk mendefinisikan operasi tersebut pada IF-STACK, IF-QUEUE dan IF-ARRAY dalam cara yang biasa. Jadi kita menghilangkannya.

 

Jurnal Struktur Data 2

PERANCANGAN STRUKTUR DATA YANG EFISIEN UNTUK PEMROGRAMAN ANALISIS

JARINGAN

Wayan Firdaus Mahmudy, Ani Budi Astuti

Jurusan Matematika, FMIPA, Universitas Brawijaya

 

ABSTRAK

Pada penelitian ini telah dirancang Tipe Data Abstrak (Abstract Data Type/ADT) graph yang efisien untuk masalah analisis jaringan. ADT graph ini dirancang untuk menyimpan data matriks berukuran besar sesuai kapasitas memori komputer. ADT tersebut digunakan untuk menyusun perangkat lunak untuk menyelesaikan persoalan pencarian rute terpendek (shortest route/shortest path) dan persoalan minimasi jaringan atau rentang pohon minimal (minimal spanning tree). Program yang telah dibuat dengan memanfaatkan struktur data graph mampu memecahkan masalah jaringan (jarak terpendek dan rentang pohon minimal) dengan tepat dan memberikanpemecahan langkah demi langkah.

 

PENDAHULUAN

Analisis jaringan merupakan suatu masalah dalam penelitian operasional yang mencakup persoalan pencarian rute terpendek (shortest route/shortest path), persoalan minimasi jaringan atau rentang pohon minimal (minimal spanning tree) dan persoalan aliran maksimum (maximal flow). Pemecahan persoalan dalam analisis jaringan secara manual memerlukan waktu yang lama dan ketelitian perhitungannya tidak terjamin sehingga diperlukan suatu perangkat lunak atau program komputer sebagai alat bantu.

Pembuatan program untuk masalah analisis jaringan memerlukan memori komputer yang cukup besar untuk menampung data masukan dan data untuk pemrosesan. Dengan menggunakan model struktur data standart yang terdapat dalam kompiler bahasa pemrograman (dalam penelitian ini digunakan bahasa pemrograman Pascal dengan kompiler Delphi2.0) maka memori yang dialokasikan kompiler tersebut tidak akan mencukupi. Untungnya kompiler Delphi 2.0 mengijinkan pemrogram untuk mendefinisikan tipe data buatan (users defined) yang biasa disebut tipe data abstrak (abstract data type/ADT).

ADT yang telah dibuat akan digunakan dalam penyusunan program untuk memecahkan persoalan pencarian rute terpendek (shortest route/shortest path) dan persoalan minimasi jaringan atau rentang pohon minimal (minimal spanning tree).

 

TINJAUAN PUSTAKA

Suatu jaringan terdiri atas suatu set titik-titik yang dihubungkan yang disebut node. Node-node tersebut dilambangkan dengan sebuah huruf atau angka, Node tertentudihubungkan dengan node lain dengan sebuah garis yang disebut busur (edge)

Suatu busur bisa berarah atau tak berarah. Angka-angka pada busur merupakan suatu nilai yang tergantung permasalahannya. Gambar 1 menunjukkan jaringan dengan busur tak berarah, Gambar 2 menunjukkan jaringan dengan busur berarah

gambar 1 busur node

 

Persoalan Rute Terpendek (Shortest Route)

Pada persoalan rute terpendek, yang menjadi masalah adalah mencari rute dengan jarak terpendek dari suatu node ke node yang lainnya dengan angka pada busur merupakan jarak node yang dihubungkan oleh busur tersebut. Pada masalah nyata, node yang ada bisa mewakili suatu kota, sedangkan angka pada busur merupakan jarak antar kota.

Untuk memecahkan persoalan rute terpendek bisa digunakan algoritma Dijkstra atau algoritma Floyd (Dimyati, 1992) (Wirt, 1976). Algoritma Dijkstra untuk mencari rute terpendek dari satu node sumber ke semua node yang lain. Algoritma Floyd untuk mencari rute terpendek dari semua node ke semua node yang lain.

 Di bawah ini disajikan algoritma Floyd:

gambar floyd

C  matrik untuk menyimpan jarak antar node secara langsung; A untuk menyimpan jarak antar node yang terdekat; Path merupakan matriks global untuk menyimpan jalur/lintasan dengan jarak terdekat; n menyatakan banyaknya node.

Inti dari algoritma Floyd di atas adalah untuk mencari jarak terdekat antara dua node (node i dan node j) adalah dengan mencoba melalui semua node yang lain (node k).

 

Persoalan Rentang Pohon Minimal (Minimal Spanning Tree)

Pada persoalan rentang pohon minimal, yang menjadi masalah adalah menghubungkan semua node yang ada dengan jarak minimum.

Pada rute terpendek, yang dicari adalah lintasan/rute dari sumber ke tujuan yang memberikan total jarak minimum, sedangkan pada persoalan rentang pohon minimal yang dipersoalkan adalah menentukan busur-busur yang menghubungkan node-node yang ada pada jaringan sehingga diperoleh panjang busur total minimum.

 

Persoalan rentang pohon minimal ini bisa diselesaikan dengan 2 cara: (Dimyati, 1992):

  1. Dipilih sembarang salah satu node, kemudian node ini dihubungkan dengan node lain terdekat.
  2. Ditentukan node lain yang belum terhubung yang terdekat dengan node – node yang sudah terhubung. Node ini kemudian dihubungkan.

Struktur Data Graph

Graph adalah suatu ADT yang digunakan untuk menangani masalah jaringan. graph dalam Pascal bisa dituliskan sebagai berikut. (Schneider, 1987)

data grap

N digunakan untuk menyimpan banyaknya node, A merupakan array dua dimensi untuk menyimpan jarak antar node.

Struktur data di atas merupakan struktur data statis. Apabila banyaknya node yang ada semakin bertambah maka ukuran A harus ditambah, padahal ukuran data termasuk program dalam Pascal dibatasi sampai 64 KB. Untuk memecahkan masalah ini bisa digunakan struktur data dinamis dengan menggunakan pointer (Kadir, 1990).

Dengan menggunakan pointer, struktur data graph di atas bisa dimodifikasi sebagai berikut:

rubah grap

 Perancangan Input Program Perangkat lunak dibuat dengan bahasa pemrograman Borland Delphi 2.0 yang bekerja pada lingkungan sistem operasi 32 bit. Perangkat lunak menerima masukan data berupa file text dan keluarannya juga berupa file text yang berisi penyelesaian masalah langkah demi langkah.

 

Perancangan Obyek TdataMatrixReal

Merupakan inti dari pemecahan masalah dalam penelitian ini. Berisi data dan metoda untuk memanipulasi data matriks berukuran besar. Data disimpan dalam memori dinamis dengan menggunakan gabungan array dan pointer.

Kerangka obyek ini adalah:

tmatriks

 

Perancangan Obyek TGraph

Obyek untuk menangani data jaringan. Berisi data matriks jarak antar node dan metoda untuk membaca nilai tersebut dari file. Tugas utama obyek ini adalah meangalokasikan serta mendealokasikan memori untuk menyimpan data jaringan.

Kerangka obyek ini adalah:

kerangka 2

HASIL PEMBAHASAN

Tampilan antar muka (interface) program dirancang secara visual dengan menggunakan fasilitas yang disediakan oleh Delphi.

Pertama kali program dijalankan akan muncul tampilan seperti pada Gambar 3. Dengan memilih menu File, Open dan memilih file data yang akan diproses dihasilkan tampilan seperti pada Gambar 4. Setelah data dibuka, analisis dilakukan dengan memilih menu Analisys dan hasil analisis akan disimpan ke file.

gambar 3 kes

gambar 4 kes

 Pemecahan Persoalan Rute Terpendek (Shortest Route)

Misalkan terdapat masalah jaringan seperti pada Gambar 1. Hasil dari program adalah adalah file text yang berisi:

pemecahan 1

Pada hasil di atas terdapat dua matriks, yang pertama adalah matriks jarak minimum antar node dan matrik jalur terpendeknya.

Pemecahan Persoalan Rentang Pohon Minimal (Minimal Spanning Tree)

Untuk masalah jaringan seperti pada Gambar 1, hasil dari analisis untuk mencari rentang pohon minimal adalah:

pemecahan 2

Dari hasil diatas bisa digambarkan node yang harus dihubungkan sebagai berikut:

hasil pengujian 2

KESIMPULAN

 Struktur data graph yang telah dirancang dan diimplementasikan mampu untuk menyimpan data matriks berukuran besar sesuai kapasitas memori komputer. Program yang telah dibuat dengan memanfaatkan struktur data graph mampu memecahkan masalah jaringan (jarakterpendek dan rentang pohon minimal) dengan tepat dan memberikan pemecahan langkah demi langkah.