Fragmentasi Data dalam sebuah Komputer


Apa sih fragmentasi data itu???

 

Fragmentasi adalah sebuah fenomena di ruang penyimpanan yang digunakan secara tidak efisien, mengurangi kapasitas penyimpanan. Istilah ini juga digunakan untuk menunjukkan tempat yang gersang itu sendiri.

Ada tiga bentuk yang terkait dengan fragmentasi: fragmentasi eksternal, internal fragmentasi, dan data fragmentasi. Berbagai skema alokasi penyimpanan pameran satu atau beberapa kelemahan. Fragmentasi dapat diterima di kembali untuk peningkatan kecepatan atau kesederhanaan.

 

Fragmentasi internal

Fragmentasi internal terjadi saat penyimpanan dialokasikan tanpa pernah ingin menggunakannya. Ini adalah ruang-siakan. Sementara ini tampaknya bodoh, sering diterima dalam kembali untuk meningkatkan efisiensi atau kesederhanaan. Istilah “internal” merujuk pada kenyataan bahwa unusable penyimpanan yang dialokasikan di dalam wilayah namun tidak sedang digunakan.

Misalnya, dalam banyak sistem file, setiap file selalu dimulai pada awal sebuah cluster, karena ini simplifies organisasi dan memudahkan tumbuh file. Setiap ruang kiri atas antara terakhir byte dari file yang pertama dan byte berikutnya dari cluster adalah bentuk internal disebut fragmentasi file atau kendur kendur ruang.

Demikian pula, sebuah program yang mengalokasikan satu byte data seringkali banyak yang dialokasikan untuk tambahan byte metadata dan berpihak. Spasi ini juga fragmentasi internal.

Contoh lainnya: Inggris teks sering disimpan dengan satu karakter di masing-masing 8-bit byte meskipun standar ASCII encoding yang paling signifikan sedikit setiap byte selalu nol. Bit yang digunakan adalah bentuk fragmentasi internal.

Serupa dengan meninggalkan masalah daya cipta unused muncul di banyak daerah lain. Misalnya, alamat IP hanya dapat dimiliki dalam ukuran blok tertentu, sehingga banyak IP yang dilindungi undang-undang, tetapi tidak sedang digunakan. Ini adalah kontribusi terhadap kekurangan alamat IPv4.

Tidak seperti jenis fragmentasi, fragmentasi internal yang sulit untuk kembali, biasanya cara terbaik untuk melepaskannya adalah dengan perubahan desain. Misalnya, dalam alokasi memori dinamis, memori internal renang secara drastis memotong fragmentasi oleh menyebarkan overhead ruang yang lebih besar atas jumlah benda.

 

Fragmentasi eksternal

Fragmentasi eksternal adalah fenomena yang gratis menjadi dibagi menjadi beberapa bagian kecil dari waktu ke waktu. Ini adalah kelemahan dari beberapa algoritma alokasi penyimpanan, terjadi ketika aplikasi dan mengalokasikan deallocates ( “frees”) dari daerah penyimpanan berbagai ukuran, dan alokasi oleh algoritma merespon meninggalkan dialokasikan dan deallocated daerah interspersed. Hasilnya adalah bahwa, walaupun gratis tersedia, maka secara efektif unusable karena dibagi menjadi potongan-potongan yang terlalu kecil untuk memenuhi kebutuhan dari aplikasi. Istilah “eksternal” merujuk pada kenyataan bahwa unusable penyimpanan yang dialokasikan di luar daerah.

Misalnya, dalam alokasi memori dinamis, blok 1000 byte mungkin diminta, tetapi yang terbesar adalah berdekatan blok ruang kosong yang hanya 300 byte. Bahkan jika terdapat sepuluh blok 300 byte dari ruang kosong, yang dipisahkan oleh daerah dialokasikan, satu masih tidak dapat mengalokasikan yang diminta blok 1000 byte, dan alokasi permintaan akan gagal.

Fragmentasi eksternal juga terjadi di banyak file sebagai sistem file yang berbeda ukuran dibuat, mengubah ukuran, dan akan dihapus. Efek lebih buruk lagi adalah jika sebuah file yang dibagi menjadi beberapa bagian kecil akan dihapus, karena ini mirip daun kecil daerah bebas spasi.

 

Fragmentasi data

Data fragmentasi terjadi ketika sebuah bagian dari data dalam memori rusak ke dalam banyak potongan-potongan yang tidak saling berdekatan. Hal ini biasanya hasil dari mencoba untuk memasukkan benda yang besar ke dalam penyimpanan yang telah menderita fragmentasi eksternal.

Misalnya, file dalam file sistem biasanya diatur dalam unit yang disebut blok atau kelompok. Ketika sebuah file sistem yang dibuat, ada ruang untuk menyimpan file blok bersama contiguously. Hal ini memungkinkan untuk cepat berurut membaca dan menulis file. Namun, seperti file ditambahkan, dihapus, dan berubah dalam ukuran, ruang bagi menjadi eksternal, hanya meninggalkan lubang kecil di tempat yang tepat untuk data baru. Bila file yang baru ditulis, atau jika file yang sudah ada diperpanjang, maka data baru blok pasti tersebar, karena perlambatan akses untuk mencari waktu dan pemutaran penundaan dari membaca / menulis head, dan overhead incurring tambahan untuk mengelola tambahan lokasi. Hal ini disebut fragmentasi file system.

Sebagai contoh lain, jika node yang terhubung daftar dialokasikan turut dalam memori, ini akan meningkatkan lokalitas dari referensi dan data cache meningkatkan kinerja selama traversal dari daftar. Jika memori renang gratis bagi ruang adalah, baru node akan tersebar di seluruh memori, meningkatkan jumlah cache misses.

Seperti compaction dapat menghilangkan fragmentasi eksternal, data fragmentasi dapat dihapuskan oleh rearranging data terkait agar buah yang saling berdekatan. Misalnya, pekerjaan utama dari defragmentation alat ini untuk mengatur ulang blok pada disk, sehingga setiap file blok yang berdekatan. Paling defragmenting utilitas juga berusaha untuk mengurangi atau menghilangkan fragmentasi ruang kosong. Beberapa pindah pengumpul sampah terkait juga akan memindahkan objek dekat bersama (disebut Memadatkan) untuk meningkatkan kinerja cache.

Sumber Artikel : Wikipedia Indonesia

http://id.wikipedia.org/wiki/Fragmentasi_(komputer)

 

Iklan

Binary Tree Traversal


Pengertian

  • Binary Tree

sebuah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal 2 subtree yang disebut sebagai sub pohon kiri (left subtree) dan sub pohon kanan (right subtree) dan kedua subtree tersebut harus terpisah, atau dengan kata lain tiap node dalam binary tree hanya boleh memiliki paling banyak 2 child.

  • Traversal

Traversal adalah proses kunjungan dalam pohon, dengan setiap node hanya dikunjungi tepat satu kali.

Jadi, binary tree traversal adalah proses mengunjungi node tepat satu kali dan tiap node hanya boleh memiliki maksimal 2 subtree yang disebut sebagai sub pohon kiri (left subtree) dan sub pohon kanan (right subtree).

Dengan melakukan kunjungan secara lengkap, maka akan didapatkan urutan informasi secara linier yang tersimpan dalam sebuah binary tree.

Algoritma Binary Tree Traversal secara umum

Tiga teknik rekursif untuk binary tree traversals ,yaitu:

  1. Mengunjungi simpul akar (root),
  2. Melakukan traversal subpohon kiri (left subtree), dan
  3. Melakukan traversal subpohon kanan (right subtree).

Yang membedakan antara teknik satu dengan yang lain adalah proses pengurutan tugas mereka.

Macam – macam Binary Tree Traversal

Terdapat tiga macam binary tree traversal, yaitu:

  • Preorder Traversal
  1. Mengunjungi simpul akar (root),
  2. Melakukan traversal subpohon kiri (left subtree),
  3. Melakukan traversal subpohon kanan (right subtree).
  • Inorder Traversal
  1. Melakukan traversal subpohon kiri (left subtree),
  2. Mengunjungi simpul akar (root),
  3. Melakukan traversal subpohon kanan (right subtree).
  • Postorder Traversal
  1. Melakukan traversal subpohon kiri (left subtree),
  2. Melakukan traversal subpohon kanan (right subtree),
  3. Mengunjungi simpul akar (root).

Metode Pengurutan(Sorting) dalam Algoritma


Bubble Sort


Metode pengurutan gelembung (Bubble Sort) diinspirasikan oleh gelembung sabun yang berada dipermukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan. Prinsip di atas dipakai pada pengurutan gelembung.
Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.

-Kelebihan Bubble Sort:
1. Metode Buble Sort merupakan metode yang paling simpel
2. Metode Buble Sort mudah dipahami algoritmanya

-Kelemahan Bubble Sort:
Meskipun simpel metode Bubble sort  merupakan metode pengurutanyang paling tidak efisien.  Kelemahan buble sort adalah pada saat mengurutkan data yang sangat besar akan mengalami kelambatan luar biasa, atau dengan kata lain kinerja memburuk cukup signifikan ketika data yang diolah jika  data cukup banyak. Kelemahan lain adalah jumlah pengulangan akan tetap sama jumlahnya walaupun data sesungguhnya sudah cukup terurut. Hal ini disebabkan setiap data dibandingkan dengan setiap data yang lain untuk menentukan posisinya.

Selection Sort




Metode selection sort merupakan perbaikan dari metode bubble sort dengan mengurangi jumlah perbandingan. Selection sort merupakan metode pengurutan dengan mencari nilai data terkecil dimulai dari data diposisi 0 hingga diposisi N-1.
Jika terdapat N data dan data terkoleksi dari urutan 0 sampai dengan N-1 maka algoritma pengurutan dengan metode selection sort adalah sebagai berikut:
1. Cari data terkecil dalam interval j = 0 sampai dengan j = N-1
2. Jika pada posisi pos ditemukan data yang terkecil, tukarkan data diposisi pos
dengan data di posisi i jika k.
3. Ulangi langkah 1 dan 2 dengan j = j+i sampai dengan j = N-1, dan seterusnya
sampai j = N – 1.

Bila diketahui data awal berupa: 44 55 12 42 94 18 6 67, maka langkah per
langkah pengurutan dengan metode selection sort adalah sebagai berikut:


Insertion Sort

Metode pengurutan selection sort sering dipakai oleh orang saat bermain kartu bridge dalam mengurutkan kartunya, yaitu dengan cara menyisip kartu yang lebih kecil ke urutan sebelum posisi kartu yang dibandingkannya. Perhatikan tabel berikut. :


Masih ada beberapa metode sorting yang lain, yang belum sempat saya tulis disini.

tunggu update-an nya ya…


Rekursif vs Iterasi


Dua hal menarik yang membuat saya terkesan memahami istilah perulangan adalah Rekursif dan Iterasi.

pengertian iterasi terlebih dahulu,

Iterasi merupakan suatu teknik perulangan yang digunakan pada penulisan program. Perulangan yang dimaksud adalah seperti perintah-perintah while .. do ataupun for .. do. Perulangan akan terus terjadi selama kondisinya terpenuhi. Yah, perulangan yang umum kita gunakan seperti pada program deret fibonanci, prima, genap, ganjil atau lainnya.

Lalu apa itu Fungsi rekursif ? 

Rekursif sebenarnya merupakan teknik perulangan juga, namun dalam konteks yang berbeda. Fungsi refursif adalah fungsi yang dapat memanggil dirinya sendiri. Maksudnya fungsi tersebut menggunakan dirinya sendiri untuk proses perulangan.

Lalu mengapa ada fungsi rekursif jika sudah ada teknik perulangan itu sendiri? Memang antara iterasi dan rekrusif itu sama-sama digunakan untuk proses perulangan. Namun ada beberapa masalah yang akan lebih mudah jika dipecahkan menggunakan fungsi rekursif. Disamping itu kode program yang menggunakan fungsi rekursif akan lebih mudah dipahami dari pada versi iterasinya.

Untuk lebih jelasnya mengenai perbandingan dari rekursif dan interasi tersebut, mari kita lihat pada tabel berikut ini.

Rekursif

Iterasi

Kode program lebih ringkas dan mudah dipahami

Kode program lebih panjang, untuk beberapa kasus solusi iteratif lebih sulit diterapkan

Membutuhkan alokasi memori yang besar

Relatif lebih kecil alokasi memorinya

Tidak cocok ketika kinerja tinggi diperlukan, karena terjadi overhead pemanggilan fungsi dalam jumlah yang relatif besar

Cocok diterapkan ketika kinerja aplikasi harus diterapkan (hanya ada satu kali pemanggilan fungsi)

Bersambung…

Representasi Data dengan Pohon Biner




Representasi data dalam sebuah perangkat komputer.

Para perancang sistem operasi selalu berusaha memikirkan algoritma yang tepat, efektif dan efisien guna “menjaga” data yang ada agar tidak hilang. Seperti ketika suatu data akan disimpan di suatu media penyimpanan, bagaimana menentukan alamatnya agar dapat diraih kembali, bagaimana agar keterhubungan antara satu bagian data dengan bagian data lain tidak terputus, dan sebagainya.

Salah satu metode yang digunakan adalah binary tree. Alamat dan keterkaitan antar data dapat digambarkan sebagai pohon biner, seperti contoh berikut ini :

 


 

Gambar 10. Contoh keterkaitan antardata

 

Start menunjuk ke alamat 100, yaitu “N”. “N” sendiri menunjuk alamat kiri ke 201 (yaitu “O”), dan kanan ke 350 (yaitu “N”). Buatlah algoritma agar informasi yang akan dihasilkan adalah “NOVIANA”.

 

Dengan berbagai pertimbangan, tidak semua perancang komputer membuat algoritma untuk melakukan perhitungan data matematis seperti yang dilakukan oleh manusia pada umumnya (secara infix). Ada komputer yang mengolahnya secara prefix dan ada yang secara postfix.

 

Contoh bentuk infix     : A + B

        prefix    : + A B

        postfix    : A B +

 

Lambang yang digunakan manusia untuk melakukan penjumlahan angka 5 dan 7, adalah 5 + 7 (infix). 5 dan 7 disebut operand, dan + disebut operator. Untuk komputer yang melakukan proses matematis secara prefix, kalimatnya diubah dengan “tambahkan 5 dengan 7” atau dilambangkan dengan + 5 7, dan untuk postfix, kalimatnya adalah “5 dan 7 ditambahkan”, atau dilambangkan dengan 5 7 +.

 

Bagaimana penulisan notasi infix : A + B * C + D secara prefix dan postfix ?.

 

Prefix :

langkah 1, tentukan mana yang pertama kali yang akan diproses, diperoleh B * C. Misal B * C diganti dengan E, maka soalnya menjadi : A + E + D

A + B * C + D

E

 

langkah 2, tentukan kembali mana yang akan diproses pertama kali, diperoleh A + E. Bila A + E diganti dengan F, maka soalnya menjadi F + D

A + E + D

                     F

 

langkah 3, karena sudah menjadi 2 operand, maka notasi prefixnya menjadi + F D

 

 


 

Gambar 11a. Binary tree dari F + D

 

langkah 4, kembalikan nilai F sebenarnya. F = A + E, prefixnya = + A E, sehingga notasi keseluruhannya menjadi + + A E D

 


 

Gambar 11b. Binary tree dari (A + E) + D

 

langkah 5, kembalikan nilai E sebenarnya. E = B * C, prefixnya = * B C, sehingga notasi keseluruhannya menjadi + + A * B C D

 


 

Gambar 11c. Binary tree dari A + (B * C) + D

 

Ekspresi matematis A + ( B * C ) + D = A + B * C + D.

 

Postfix :

langkah 1, tentukan mana yang pertama kali yang akan diproses, diperoleh B * C. Misal B * C diganti dengan E, maka soalnya menjadi : A + E + D

langkah 2, tentukan kembali mana yang akan diproses pertama kali, diperoleh A + E. Bila A + E diganti dengan F, maka soalnya menjadi F + D

langkah 3, karena sudah menjadi 2 operand, maka notasi postfixnya menjadi F D +

langkah 4, kembalikan nilai F sebenarnya. F = A + E, postfixnya = A E +, sehingga notasi keseluruhannya menjadi A E + D +

langkah 5, kembalikan nilai E sebenarnya. E = B * C, postfixnya = B C *, sehingga notasi keseluruhannya menjadi A B C * + D +

 

Untuk soal : (A + B) * C + D bentuk binary treenya sebagai berikut :

 


 

Gambar 12. Skema binary tree untuk (A+B)*C+D

 

Prefixnya     : + * + A B C D

Postfixnya    : A B + C * D +

 

Dari gambar binary tree, kita dapat secara langsung menentukan bentuk notasi infix,
prefix, maupun postfixnya. Perhatikan gambar berikut ini.

 


 

Gambar 13. Tentukan infix,
prefix, dan postfixnya

 

Infix : Ingat, konsep binary tree adalah “pembelahan dua.” Jika gambar 13 itu dibelah menjadi dua, maka belahan kiri (left substree) terdiri dari A / B, dan belahan kanan (right substree) adalah C * – E F, sementara yang di tengah (root) adalah +. Di belahan kiri kita sudah mendapatkan notasi (A / B). Di belahan kanan, kita belah lagi menjadi belahan kiri2 C, dan belahan kanan2 E – F, sedangkan yang di tengah (root) adalah *.

 

Hasil pembelahan itu kini kita gabungkan (setiap operator atau root), kita letakkan di tengah.

Notasinya menjadi : (A + B) + ( C * (E – F))

         kiri kanan

Hilangkan tanda kurung pemisah yang tidak penting (bila dibuang, hasil pemrosesan tidak berubah). Notasinya menjadi : A + B + C * (E – F)

 

Prefix : Karena operand berada di depan, sehingga untuk notasi A + B dituliskan dengan + A B, maka bila bila kita sebut A adalah kiri, + adalah tengah, dan B adalah kanan, maka rumusnya adalah tengah-kiri-kanan secara rekursif (lakukan berulang di setiap node mana yang sedang dikunjungi)

 

Lakukan rumus itu dari atas, kita dapat tengah + (sementara hasilnya adalah +).

Setelah tengah, kita menuju ke kiri, yaitu /. Stop di situ, kita ulangi lagi rumus semula, tengah-kiri-kanan. Tengah = /, kiri = A dan kanan = B. Hasil berikutnya menjadi + /.

 

Dari / kita menuju ke kiri lagi, kita dapat A. Stop di situ, ulangi lagi rumus tengah-kiri-kanan. Karena tidak ada lagi yang lebih kiri dari A, maka A dijadikan hasil, sehingga hasilnya menjadi + / A. Setelah tidak ada yang di kiri lagi, maka lanjutkan rumus, setelah kiri adalah kanan, yaitu B. Ulangi lagi rumus tengah-kiri-kanan, karena tidak ada lagi yang berada di kiri maupun di kanan B, maka jadikan B sebagai hasil, sehingga hasilnya menjadi + / A B.

 

Substree kiri sudah selesai, maka lanjutkan ke substree kanan, lakukan sama dengan rumus tengah-kiri-kanan. Maka hasil akhirnya akan diperoleh : + / A B * C – E F.

 

Postfix : Karena operator di belakang operand, maka rumusnya : kiri-kanan-tengah.

(Ulangi seperti yang telah diuraikan di penyelesaian notasi prefix dengan rumus yang berbeda).

 

Dimulai dengan substree kiri, kita peroleh : A B /.

Dilanjutkan dengan substree kanan, kita peroleh : C E F – * +.

Hasil akhirnya : A B / C E F – * +

 

Prefix menempatkan puncak (akar/ root) di awal notasi, sedangkan postfix menempatkan puncak (root) di akhir notasi. Dengan sering melakukan latihan, dengan hanya melihat gambar binary treenya, kita akan mudah menemukan pola pergerakan untuk menentukan notasi prefix dan postfixnya.

 

Bisakah anda mencari jalannya bila diketahui postfix = A B C – + D E F / + *, maka prefixnya = * + A – B C + D / E F, dan infixnya = (A + B – C ) * ( D + E / F) ?. Gambarlah binary treenya.

Apa itu TUMPUKAN (STACK) ?…


Pengertian Stack

merupakan sebuah koleksi objek yang menggunakan prinsip LIFO (Last In First Out), yaitu data yang terakhr kali dimasukkan akan pertama kali keluar dari stack tersebut. Stack dapat diimplementasikan sebagai representasi berkait atau kontigu (dengan tabel fix)

Ciri-ciri Stack

  • Elemen TOP (puncak) diketahui
  • Penyisipan dan penghapusan elemen selalu dilakukan di TOP
  • LIFO ( Last IN First Out)

contoh :

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

Operasi pada Stack

  • Push (input E : typeelmt, input/output data : stack): menambahkan sebuah elemen ke stack
  • Pop (input/output data : stack, output E : typeelmt ) : menghapus sebuah elemen stack
  • IsEmpty ()
  • IsFull () dan beberapa selektor yang lain


1. buat stack (stack) – create

membuat sebuah stack baru yang masih kosong

Spesifikasi:

  • tujuan : mendefinisikan stack yang kosong
  • input : stack
  • syarat awal : tidak ada
  • output stack : – (kosong)‏
  • syarat akhir : stack dalam keadaan kosong

2. stack kosong (stack) – empty

fungsi untuk menentukan apakah stack dalam keadaan kosong atau tidak

spesifikasi:

  • tujuan : mengecek apakah stack dalam keadaan kosong
  • input : stack
  • syarat awal : tidak ada
  • output : boolean
  • syarat akhir : stack kosong bernilai true jika stack dalam keadaan kosong

3. stack penuh (stack) – full

fungsi untuk memeriksa apakah stack yang ada sudah penuh

spesifikasi:

  • tujuan : mengecek apakah stack dalam keadaan penuh
  • input : stack
  • syarat awal : tidak ada
  • output : boolean
  • syarat akhir : stack penuh bernilai true jika stack dalam keadaan penuh

4. push (stack, info baru)‏

menambahkan sebuah elemen kedalam stack.

spesifikasi:

  • tujuan : menambahkan elemen, info baru pada stack pada posisi paling atas
  • input : stack dan Info baru
  • syarat awal : stack tidak penuh
  • output : stack
  • syarat akhir : stack bertambah satu elemen

5. pop (stack, info pop)‏

mengambil elemen teratas dari stack

spesifikasi:

  • tujuan : mengeluarkan elemen dari stack yang berada pada posisi paling atas
  • input : stack
  • syarat awal : stack tidak kosong
  • output : stack dalam info pop
  • syarat akhir : stack berkurang satu elemen

Contoh Pemanfaatan Stack

  • Notasi Infix Prefix
  • Notasi Infix Postfix

Pemanfaatan stack antara lain untuk menulis ungkapan dengan menggunakan notasi tertentu.

Contoh :

( A + B ) * ( C – D )‏

Tanda kurung selalu digunakan dalam penulisan ungkapan numeris untuk mengelompokkan bagian mana yang akan dikerjakan terlebih dahulu.

Dari contoh ( A + B ) akan dikerjakan terlebih dahulu, kemudian baru ( C – D ) dan terakhir hasilnya akan dikalikan.

A + B * C – D

B * C akan dikerjakan terlebih dahulu, hasil yang didapat akan berbeda dengan hasil notasi dengan tanda kurung.

Notasi InfixPrefix

Cara penulisan ungkapan yaitu dengan menggunakan notasi infix, yang artinya operator ditulis diantara 2 operator.

Seorang ahli matematika bernama Jan Lukasiewiccz mengembangkan suatu cara penulisan ungkapan numeris yang disebut prefix, yang artinya operator ditulis sebelum kedua operand yang akan disajikan.

Contoh :

Proses konversi

dari infix ke prefix :

= ( A + B ) * ( C – D )‏

= [ + A B ] * [ – C D ]

= * [ + A B ] [ – C D ]

= * + A B – C D

Notasi InfixPostfix

Cara penulisan ungkapan yaitu dengan menggunakan notasi postfix, yang artinya operator ditulis sesudah operand.

Contoh :

Proses konversi

dari infix ke postfix :

= ( 6 – 2 ) * ( 5 + 4 )‏

= [ 6 2 – ] * [ 5 4 + ]

= [ 6 2 – ] [ 5 4 + ] *

= 6 2 – 5 4 + *

Tips Membuat Notasi Prefix, Infix, dan Postfix



Dalam struktur data yang banyak dipelajari, kita ketahui adanya 3 notasi operasi yang dilakukan untuk suatu operasi aritmatika, yaitu prefix, infix, dan postfix.

Sebelum kita kupas mengenai notasi di atas, perlu dipahami terlebih dahulu indikator yang membentuk terjadinya notasi dalam struktur data. Notasi terbentuk dari operand dan operator. Operand adalah data atau nilai yang membantu dalam proses sedangkan operator adalah fungsi yang digunakan dalam proses.

Contoh :

A + B * C

2 + 3 * 5

Keterangan : A, B, C, 2, 3, 5 adalah operand

+, * adalah operator

Nahh… sekarang mudah-mudahan sudah dapat diketahui indikator yang membentuk suatu notasi. Selanjutnya kita harus mengetahui level/hirarkhi dari operator seperti

1. ^ (pangkat)

2. * (kali) atau / (bagi)

3. + (jumlah) atau – (kurang)

Seperti yang telah dibahas di awal, diketahui notasi pada struktur data terdiri atas 3 macam, yaitu

1. Prefix

yaitu notasi yang terbentuk atas operator dengan operand, dimana operator berada didepan operand.

Contoh :  A + B * C (Infix)

maka notasi prefixnya adalah   +A*BC

    Pemecahannya :

                       A  +  B  *  C

diketahaui ada 3 operand yaitu : A, B, C, dan 2 operator yaitu : +, *. Proses dimulai  dengan melihat dari hirarkhi operator. Contoh diatas operator yang tertinggi adalah * kemudian +.

Tanda * diapit oleh dua operand yaitu B dan C yaitu B * C , prefixnya dengan menggabungkan operand dan memindahkan operator kedepan dari operand, sehingga fungsi B * C, notasi prefixnya menjadi *BC. Sehingga hasil sementara dari notasi prefix adalah

       A + *BC

selanjutnya mencari prefix untuk operator yang berikutnya, yaitu +, cara yang dilakukan sama seperti di atas, operator +, diapit oleh 2 operand, yaitu A dan *BC, gabungkan operand, sehingga menjadi A*BC, lalu pindahkan operator kedepan operand, sehingga hasil akhir menjadi

      + A * B C

Contoh yang lain:

1.  A + B  – C * D

        2     3    1   —–>    hirarkhi level

     A + B – *CD   —–>    1

     +AB – *CD     —–>    2

     – +AB *CD     —–>    3

2. A * B ^ C – D

       2   1    3      —–>    hirarkhi

    A * ^BC – D     —–>    1

    *A^BC – D       —–>    2

    -*A^BCD         —–>    3

3.  A + ( B – C ) * D

        3      1      2   —–> hirarkhi

     A + -BC * D      —–>  1 (karena diapit tanda paranthesis atau kurung buka/tutup,( ) )

     A + *-BCD        —–>  2

     + A *-BCD        —–>  3 

2. Infix

yaitu notasi yang terbentuk atas operator dengan operand, dimana operator berada diantara operand. Notasi ini hanya dikenal oleh manusia dan selalu digunakan dalam perhitungan aritmatika.

     Contoh :  A + B * C

                    ( A + B ) * C

                    A – ( B + C ) * D ^ E

3. Postfix

yaitu notasi yang terbentuk atas operator dengan operand, dimana operator berada dibelakang operand. Notasi ini hanya dikenal oleh processor dan dipahami dalam ALU. 

     Contoh :  A + B * C (Infix)

maka notasi postfixnya adalah   ABC*+

    Pemecahannya :

                       A  +  B  *  C

diketahaui ada 3 operand yaitu : A, B, C, dan 2 operator yaitu : +, *. Proses dimulai  dengan melihat dari hirarkhi operator. Contoh diatas operator yang tertinggi adalah * kemudian +.

Tanda * diapit oleh dua operand yaitu B dan C yaitu B * C , postfixnya dengan menggabungkan operand B dan C menjadi BC lalu memindahkan operator ke belakang operand C, sehingga fungsi B * C, notasi postfixnya menjadi BC*. Sehingga hasil sementara dari notasi postfix adalah

       A + BC*

selanjutnya mencari postfix untuk operator yang berikutnya, yaitu +, cara yang dilakukan sama seperti di atas, operator +, diapit oleh 2 operand, yaitu A dan BC*, gabungkan operand tersebut, sehingga menjadi ABC*, lalu pindahkan operator + ke belakang operand ABC*, sehingga hasil akhir menjadi

      ABC*+

Contoh yang lain:

1.  A + B  – C * D

        2     3    1   —–>    hirarkhi level

     A + B – CD*   —–>    1

     AB+ – CD*     —–>    2

     AB+CD*-       —–>    3

2. A * B ^ C – D

       2   1    3      —–>    hirarkhi

    A * BC^ – D     —–>    1

    ABC^* – D       —–>    2

    ABC^*D-         —–>    3

3.  A + ( B – C ) * D

        3      1      2   —–> hirarkhi

     A + BC- * D      —–>  1 (karena diapit tanda paranthesis atau kurung buka/tutup,( ) )

     A + BC-D*        —–>  2

     A BC-D*+         —–>  3 

 

Jika ingin menguasai cara pembentukkan notasi ini caranya adalah dengan PERBANYAK LATIHAN KASUS.

1. A * ( B + C ) / ( D – E ), Notasi Postfix dan Prefix?

2. ABC+*DE-/, Notasi Infix dan Prefix?

3. 223+*32-, berapakah hasilnya?

 

Smoga bermanfaat….