Cari Ilmu: Maret 2018

Seputar Struktur Data

Oleh : Mochkammad Tabah Syafi'uddin

1) Program yang bagus adalah program yang memenuhi beberapa syarat seperti yang ada dalam beberapa buku algoritma dan struktur data, yaitu :

a. Program berjalan secara benar

b. Program mudah dibaca dan dimengerti

c. Program mudah di debug

d. Program mudah dilakukan modifikasi

Selain itu, sebuah program juga harus menghasilkan output yang benar serta berjalan secara efisien. Dikatakan efisien jika dalam menjalankan eksekusi program memiliki durasi waktu yang singkat dan hanya memerlukan ruang memory yang kecil. Dengan demikian, untuk menulis program yang efisien maa harus perlu mengaplikasikan konsep manajemen data yang pasti.

2) Jenis-jenis Struktur Data

1. Struktur Data Sederhana

a. Array (Larik)

Larik adalah struktur data statistik yang menyimpan sekumpulan elemen yang bertipe sama. Setiap elemen diakses langsung melalui indeksnya. Indeks larik harus tipe data yang menyatakan keterurutan misalnya integer atau karakter. Banyaknya elemen larik harus sudah diketahui sebelum program dieksekusi. Tipe elemen larik dapat berupa tipe sederhana, tipe terstruktur, atau tipe larik lain. Nama lain array adalah LARIK, TABEL, atau VEKTOR.

b. Record (Catatan)

ADT adalah definisi tipe dan sekumpulan primitif (operasi datar) terhadap tipe tersebut. Tipe diterjemahkan menjadi tipe terdefinisi dalam bahasa pemrograman yang bersangkutan.

2. Struktur Data Majemuk

a. Linier

1. Stack (Tumpukan)

Stack (tumpukan) adlah list linier yang dikenali elemen puncaknya (top), aturan penyisipan dan penghapusan elemennya tertentu (penyisipan selalu dilakukan “di atas” (top), penghapusan selalu dilakukan pada top). Karena aturan penyisipan dan penghapusan semacam itu, top adalah satu-satunya alamat tempat terjadi operasi. Elemen yang ditambahkan paling akhir akan menjadi elemen yang akan dihapus. Dikatakan bahwa elemen stack akan tersusun secara LIFO (Last In First Out).

2. Queue (Antrian)

Queue (antrian) adalah list linier yang dikenali elemen pertama (head) dan elemen terakhirnya (tail). Aturan penyisipan dan penghapusan elemennya didefinisikan penyisipan selalu dilakukan setelah elemen terakhir, penghapusan selalu dilakukan pada elemen pertama; satu elemen dengan elemen lain dapat diakses melalui informasi next.

3. List dan Multi-List (Daftar)

List linier adalah sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari 2 bagian, sebuah list linier dikenali dengan (1) Elemen pertamanya, biasanya melalui alamat elemen pertama yang disebut (first); (2) Alamat elemen berikutnya (suksesor). Jika kita mengetahui alamat sebuah elemen, yang dapat diakses melalui field text; (3) Setiap elemen mempunyai alamat, yaitu tempat elemen disimpan dapat diacu. Untuk mengacu sebuah elemen, alamat harus terdefinisi. Dengan alamat tersebut informasi yang tersimpan pada elemen list dapat diakses; (4) Elemen terakhirnya.

b. Non-Linier

1. Binary tree (Pohon Biner)

Sebuah pohon biner (binary tree) adalah himpunan terbatas yang mungkin kosong atau terdiri dari sebuah simpul yang disebut sebagai akar dan dua buah himpunan lain yang disjoint yang merupakan pohon biner yang disebut sebagai sub pohon kiri (left) dan sub pohon kanan (right) cari pohon biner tersebut. Pohon biner merupakan tipe yang sangat penting dari struktur data dan banyak dijumpai dalam berbagai terapan. Karakteristik yang dimiliki oleh pohon biner adalah bahwa setiap simpul paling banyak hanya memiliki dua buah anak, dan mungkin tidak punya anak. Istilah-istilah yang digunakan sama dengan istilah pada pohon secara umum.

2. Graph (Graf)

Graph merupakan struktur data yang paling umum. Jika struktur linier memungkinkan pendefinisian keterhubungan sekuensial antara entitas data, struktur data tree memungkinkan pendefinisian keterhubungan hirarkis, maka struktur graph memungkinkan pendefinisian keterhubungan tak terbatas antara entitas data. Banyak entitas-entitas data dalam masalah-masalah nyata secara alamiah memiliki keterhubungan langsung (adjacency) secara tak terbatas demikian. Contoh: informasi tapologi dan jarak antar kota-kota dipulau jawa. Dalam masalah ini kota X bisa berhubungan langsung dengan hanya satu atau lima kota lainnya. Untuk memeriksa keterhubungan dan jarak titik langsung antara dua kota dapat diperoleh berdasarkan data keterhubungan-keterhubungan langsung dari kota-kota lainnya yang memperantarainya. Representasi data struktur data liner ataupun hirarkis pada masalah ini masih bisa digunakan namun membutuhkan pencarian-pencarian yang kurang efisien. Struktur data graph secara eksplisit menyatakan keterhubungan ini sehingga pencariannya langsung (straightforward) dilakukan pada strukturnya sendiri.

3) Model dalam Metode Pengembangan Perangkat Lunak

Ada beberapa model dalam metode pengembangan perangkat lunak, yaitu:

1. Model Prototype

Contoh Model Prototype :

Pendekatan prototyping model digunakan jika pemakai hanya mendefinisikan objektif umum dari perangkat lunak tanpa merinci kebutuhan input, pemrosesan dan outputnya, sementara pengembang tidak begitu yakin akan efisiensi algoritma, adaptasi sistem operasi, atau bentuk interaksi manusia-mesin yang harus diambil.

Kelebihan model prototype:

1. Menghemat waktu pengembangan

2. Adanya komunikasi yang baik antara pengembang dan pelanggan

3. Pengembang dapat bekerja lebih baik dalam menentukan kebutuhan pelanggan

4. Penerapan menjadi lebih mudah karena pemakai mengetahui apa yang diharapkannya

5. User dapat berpartisipasi aktif dalam pengembangan sistem

Kekurangan model prototype:

1. Biaya untuk membuat prototyping cukup tinggi

2. Biasanya kurang fleksible dalam mengahadapi perubahan

3. Proses analisis dan perancangan terlalu singkat

Contoh studi kasus:

Seorang pelanggan mendefinisikan serangkaian sasaran umum bagi perangkat lunak, tetapi tidak melakukan mengidentifikasi kebutuhan output, pemrosesan, atupun input detail. Pada kasus yang lain, pengembang mungkin tidak memiliki kepastian terhadap efisiensi algoritme, kemampuan penyesuaian dari sebuah sistem operasi,atau bentuk-bentuk yang harus dilakukan oleh interaksi manusia dengan mesin. Dalam hal ini, serta pada banyak situasi yang lain, prototyping paradigma mungkin menawarkan pendekatan yang terbaik.

Prototyping paradigma dimulai dengan pengumpulan kebutuhan. Pengembang dan pelanggan bertemu dan mendefinisikan obyektif keseluruhan dari software, mengidentifikasi segala kebutuhan yang diketahui, dan area garis besar diman definisi lebih jauh merupakan keharusan kemudian dilakukan “perancangan kilat”. Perancangan kilat berfokus pada penyajian dari aspek-aspek software tersebut yang akan nampak bagi pelanggan atau pemakai (contohnya pendekatan input dan format output). Perancangan kilat membawa kepada konstruksi sebuah prototipe. Prototipe tersebut dievaluasi oleh pelanggan/pemakai dan dipakai untuk menyaring kebutuhan pengembangan software. Iterasi terjadi pada saat prototipe disetel untuk memenuhi kebutuhan pelanggan, dan pada saat yang sama memungkinkan pengembang untuk secara lebih baik memahami apa yang harus dilakukannya.

2. Model Waterfall

Waterfall model adalah model yang melakukan pendekatan pada perkembangan perangkat lunak secara seistematik dan sekuensial. Yang artinya kegiatan pada model ini dilakukan secara terurut berdasarkan panduan proses mulai dari komunikasi kepada client atau pelanggan sampai dengan aktifitas sampai pengorderan setelah masalah dipahami secara lengkap dan berjalan stabil sampai selesai.

Kelebihan model waterfall :

1. Mudah diaplikasikan

2. Memberikan template tentang metode analisis, desain, pengkodean, pengujian, dan pemeliharaan.

3. Cocok digunakan untuk produk software yang sudah jelas kebutuhannya di awal, sehingga minim kesalahannya.

Kekurangan model waterfall:

1. Waterfall model bersifat kaku sehingga sulit untuk melakukan perubahan pada sistem perangkat lunak.

2. Terjadinya pembagian proyek menjadi tahap-tahap yang tidak fleksibel, karena komitmen harus dilakukan pada tahap awal proses.

3. Customer harus sabar untuk menanti produk selesai, karena dikerjakan tahap per tahap,menyelesaikan tahap awal baru bisa ke tahap selanjutnya.

4. Perubahan ditengah-tengah pengerjaan produk akan membuat bingung team work yang sedang membuat produk.

5. Adanya waktu menganggur bagi pengembang, karena harus menunggu anggota tim proyek lainnya menuntaskan pekerjaannya.

Contoh studi kasus:

Sulitnya petugas bagian administrasi dalam mengolah data perpustakaan yang mengakomodasi peminjaman, buku, pengembalian dan membuat laporan yang membutuhkan banyak waktu. Adapun tujuan dari model sistem ini adalah

memodelkan sebuah sistem informasi Perpustakaan yang berbasis komputer dengan menggunakan metode waterfall dan sistem informasi perpustakaan ini, untuk membantu petugas dalam menghadapi kendala yang dihadapi dalam melakukan transaksi, sehingga dengan adanya sistem informasi tersebut diharapkan dapat menyelesaikan permasalahan yang berhubungan dengan Perpustakaan.

3. Model Spiral

Spiral model adalah model proses yang pendekatannya bersifat realistis pada software besar karena proses dari awal sampai proses pengiriman dan perbaikan dapat dipahami dnegan baik oleh clieent dan developer. Model ini mempunyai rangkaian kerja yang iterasi (peningkatan pada model) awal yang berbentuk prototype dan kemudian iterasi selanjutnya akan menjadi perkembangan dari model sebelumnya. Model ini dapat terus digunakan meskipun software sudah dikirimkan karena proses (siklus)dapat berputar lagi jika ada perubahan pada software sampai tidak ada permintaan perupbahan pada software oleh client.

Kelebihan model spiral :

1. Setiap tahap pengerjaan dibuat prototyping sehingga kekurangan dan apa yang diharapkan oleh client dapat diperjelas dan juga dapat menjadi acuan untuk client dalam mencari kekurangan kebutuhan.

2. Lebih cocok untuk pengembangan sistem dan perangkat lunak skala besar.

3. Dapat disesuaikan agar perangkat lunak bisa dipakai selama hidup perangkat lunak komputer.

4. Pengembang dan pemakai dapat lebih mudah memahami dan bereaksi terhadap resiko setiap tingkat evolusi karena perangkat lunak terus bekerja selama proses.

5. Menggunakan prototipe sebagai mekanisme pengurangan resiko dan pada setiap keadaan di dalam evolusi produk.

6. Tetap mengikuti langkah-langkah dalam siklus kehidupan klasik dan memasukkannya ke dalam kerangka kerja iteratif.

7. Membutuhkan pertimbangan langsung terhadp resiko teknis sehingga mengurangi resiko sebelum menjadi permaslahan yang serius.

Kekurangan model spiral :

1. Banyak konsumen (Client) tidak percaya bahwa pendekatan secara evolusioner dapat dikontrol oleh kedua pihak. Model spiral mempunyai resiko yang harus dipertimbangkan ulang oleh konsumen dan developer.

2. Memerlukan tenaga ahli untuk memperkirakan resiko, dan harus mengandalkannya supaya sukses.

3. Belum terbukti apakah metode ini cukup efisien karena usianya yang relatif baru.

4. Memerlukan penaksiran resiko yang masuk akal dan akan menjadi masalah yang serius jika resiko mayor tidak ditemukan dan diatur.

5. Butuh waktu lama untuk menerapkan paradigma ini menuju kepastian yang absolute.

Contoh studi kasus:

Tuan X adalah General Manager A Company, sebuah perusahaan perkapalan yang berbasis di Singapura. Sebagai perusahaan UKM muda yang terus berkembang, Tuan X menginvestasikan sebagian modal perusahaan untuk promosi di media cetak dan elektronik, serta melatih kemampuan karyawan melalui berbagai kursus. Untuk mendukung kerja karyawan, A Company menggunakan komputer dasar (Basic PC) yang dilengkapi dengan office software. Seperti kebanyakan UKM lainnya, A Company juga memiliki akses internet yang hanya dapat digunakan secara terbatas di beberapa PC. A Company memiliki satu buah email resmi yang masih menggunakan domain dari ISP (Internet Service Provider). Untuk komunikasi dilingkungan karyawan, mereka menggunakan fasilitas email gratis yang banyak tersedia di internet. Email gratis ini kadang juga digunakan untuk berkomunikasi dengan supplier dan pelanggan. Sebagai perusahaan UKM yang terus berkembang cepat, Tuan X mulai berfikir untuk mengembangkan A Company lebih professional. Harapan Tuan X, calon pelanggan potensial, pelanggan, supplier dan karyawan lebih mengenal A Company. Disisi lain, ia juga berharap agar cara yang digunakan lebih efisien, hemat biaya, tetapi menampilkan sosok perusahaan yang meyakinkan atau bonafit. Tuan X meyakini, bahwa berkomunikasi menggunakan alamat email atau domain sendiri; promosi melalui website sendiri; data yang terintegrasi dan dapat diakses disemua komputer perusahaan akan dapat membawa perusahaan menjadi lebih profesional. A Company tidak memiliki departemen khusus untuk menangani TI. Untuk mewujudkan keinginannya, Tuan X meminta bantuan perusahaan khusus TI. Implementasi TI dikerjakan oleh perusahaan TI (sebagai pemenang tender) dalam jangka waktu kontrak 1 tahun, Dalam proses implementasi, Tuan X menyerahkan tugas dan tanggungjawab kepada bawahannya. Semua karyawan dilibatkan dalam pertemuan dan diskusi dengan perusahaan pembangun TI. Dari waktu kontrak 1 tahun yang disepakati, TI yang bisa diimplementasikan adalah pembangunan jaringan komputer, akses internet, email, dan pembangunan data.

4. Model Increment

Dalam model Incremental ini proses pengerjaan perangkat lunak akan dilakukan perbagian sehingga bagian selanjutnya akan dikerjakan setelah bagian awal telah selesai dan selanjutnya sampai menghasilkan perangkat lunak yang lengkap dengan semua fungsi yang diperlukan dan pengerjaan perangkat lunak berakhir. Sebelum pengerjaan perangkat lunak akan dilakukan perancangan arsitektur software sebagai kerangka dalam pengerjaan perbagian.

Kelebihan model increment :

1. Resiko yang rendah pada pengembangan sistem.

2. Mengutamakan fungsi-fungsi pada sistem perangkat lunak sehingga kemudahan pemakaian sistem yang paling di utamakan.

3. Tahap awal adalan dasar dari pembuatan tahap berikutnya (dikerjakan secara terurut).

4. Cocok digunakan bila pembuat software tidak banyak/kekurangan pembuat

5. Mampu mengakomodasi perubahan kebutuhan customer.

6. Mengurangi trauma karena perubahan sistem. Klien dibiasakan perlahan-lahan menggunakan produknya bagian per bagian.

7. Memaksimalkan pengembalian modal investasi konsumen.

Kekurangan model increment :

1. Hanya akan berhasil jika tidak ada staffing untuk penerapan secara menyeluruh.

2. Penambahan staf dilakukan jika hasil incremental akan dikembangkan lebih lanjut.

3. Hanya cocok untuk proyek dengan skala kecil.

4. kemungkinan tiap bagian tidak dapat diintegrasikan.

Contoh studi kasus :

Puskesmas sebagai salah satu bentuk pelayanan kesehatan yang dituntut untuk memberikan pelayanan kesehatan dengan baik. Diantaranya adalah rekam medis pasien di Puskesmas Mranggen I masih menggunakan sistem manual, sehingga menyebabkan beberapa kendala diantaranya pengolahan data pasien yang masih lambat yang mengakibatkan tingginya tingkat kesalahan dalam pengolahan data pasien. Sistem rekam medis ini menggunakan metode penelitian deskriptif dengan jenis studi kasus pada Puskesmas Mranggen I, teknik pengumpulan data yang digunakan adalah observasi, wawancara, dan studi literature. Teknik analisis data menggunakan model incremental yang dikembangkan dari model waterfall, sedangkan model analisis menggunakan analisis terstruktur yaitu ERD (Entity Relationship Diagram) dalam menggambarkan model data dan DFD (Data Flow Diagram) untuk mengembangkan model fungsional.Perangkat pembangun adalah Borland Delphi 7 dengan database MySQL. Data yang diproses yaitu pendaftaran, rekam medis, rujukan, laboratorium sedangkan keluaran dari system berupa laporan-laporan.

4) Analogi abstaction pada windows phone.

Saya telah menetapkan bahwa memiliki perakitan "inti" per platform untuk kode portabel (viewmodel, pembantu, dll.) Dan perakitan terpisah per basis data / toko penyimpanan (SqlCe, Sqlite, dll.) Bahwa rakitan inti spesifik platform nampaknya bekerja Ini berarti kelas model saya masih didefinisikan dalam majelis DAL, namun setidaknya saya bisa menyediakan antarmuka umum sederhana (yang didefinisikan di setiap majelis DAL, sayangnya, karena kelas model DAL) yang masih memberi saya dukungan IQueryable.

Berkat "copy as link" dalam Visual Studio, menyiapkan majelis inti dan memastikan bahwa antarmuka layanan database umum sama untuk setiap perakitan DAL cukup mudah. Dengan # ifdef saya bahkan dapat menggunakan kembali banyak file kelas model DAL dan mengkompilasi atribut secara bersyarat, kode khusus database, dll. Yang memungkinkan saya untuk menggunakan "copy as link" untuk mereka juga.

public interface IDataService

{

IQueryable<ModelType1> ModelType1 { get; }

IQueryable<ModelType2> ModelType2 { get; }

void AddModelType1(ModelType1 item);

void RemoveModelType1(ModelType1 item);

void AddModelType2(ModelType2 item);

void RemoveModelType2(ModelType2 item);

void CreateDatabase();

void ResetDatabase();

}

The resulting map of references is kind of like this:

System.Data.Linq -> App.Data.SqlCe -> App.Core.WP -> App.WP

/ /

(some shared code) (all shared code)

/ /

Sqlite -> App.Data.Sqlite -> App.Core.Win8 -> App.Win8

Tempat itu sama bersihnya seperti yang kuinginkan, tapi setidaknya sepertinya berhasil.

5) Penjelasan dan Perbandingan beberapa pendekatan yang dapat digunakan untuk merancang sebuah algoritma

Terdapat dua pendekatan Umum yang bisa digunakan dalam merancang algoritma, yaitu pendekatan perancangan top down dan bottom-up, pendekatan perancangan secara top-down dimulai dengan cara membagi algoritma yang kompleks menjadi satu atau lebih dari satu modul. Modul yang terbagi ini masih bisa duraikan lagi menjadi beberapa sub-modul, dan proses ini dilakukan berulang-ulang hingga kompleksitas modul yang diinginkan terpenuhi. Metode perancangan top-down merupakan bentuk perbaikan secara bertahap yang dimulai dengan modul paling atas kemudian secara bertahap menambah modul lain yang dipanggil.

Untuk pendekatan secara bottom-up, merupakan kebalikan dari top down. Dimana modul ini dimulai dengan pembuatan modul paling dasar, kemudian dilanjutkan ke perancangan modul tingkat yang lebih tinggi.

Dari kedua pendekatan diatas, yaitu top-down dan bottom-up, apakah strategi top down / bottom-up, tentu tergantung pada aplikasi yang ditangani. Pendekatan top-down mengkuti perbaikan secara bertahap dengan menguraikan algoritma ke dalam modul secara terkelola. Sementara pendekatan bottom-up mendefinisikan modul terlebih dahulu baru kemudian mengelompokan beberapa , modul secara bersama untuk membentuk modul baru tingkat lebih tinggi. Pendekatan top-down sangat bagus dalam hal kemudahan membuat dokumentasi modul, menghasilkan uji kasus, implementasi kode, dan debugging. Namun, terdaopat kekurangan karena sub-modul dianalisis dalam sebuah isolasi tanpa memperhatikan komuikasi dengan modul lain sehingga mengabaikan konsep penyembunyian informasi.

6) Algoritma :

Inisialisaikan bil1, bil2, oprs, hasil

Input nilai a, b

Pilih salah satu operasi dari (+),(-),(x),(:)

Jika anda memilih operasi (+), maka hasil = a + b

Jika anda memilih operasi (-), maka hasil = a - b

Jika anda memilih operasi (x), maka hasil = a * b

Jika anda memilih operasi (:), maka hasil = a / b

Cetak hasil

Flowchart

7) Notasi Big O

Pernyataan “f(x) adalah O(g(x))” sebagaimana didefinisikan sebelumnya, biasa ditulis f(x) = O(g(x)) Pernyataan ini adalah penyalahgunaan notasi. Persamaan dari dua buah fungsi tidak dinyatakan. Properti O(g(x)) tidaklah simetrik: Karena alasan ini, beberapa penulis lebih memilih menggunakan notasi himpunan dan menulis Menganggap O(g) sebagai himpunan dari fungsi fungsi yang didominasi oleh g. Dalam penggunaan yang lebih rumit, , O( ) dapat muncul pada tempat yang berbeda di dalam sebuah persamaan, bahkan beberapa kali untuk masing-masing sisi.

Misalnya, pernyataan berikut benar untuk (n + 1)2 = n2 + O(n) nO(1) = O(en)

Maksud dari pernyataan diatas adalah :

Untuk setiap fungsi yang memenuhi untuk setiap O( ) pada sisi kiri, terdapat fungsi-fungsi yang memenuhi masing-masing O( ) pada sisi kanan, melakukan substitusi untuk semua fungsi-fungsi ini ke dalam persamaan menyebabkan kedua sisi menjadi sama. Misalnya, persamaan ke-3

Referensi :

Selasa, 06 Maret 2018

Seputar Struktur Data