Enumeration Sort
Asumsikan kita mempunyai Tabel dengan n buah elemen yang ditandai dengan \(a_0,a_1,…,a_{n-1}\)
Author: toosa
Menggabungkan Dua Daftar Terurut
Sebuah Algoritma RAM yang optimal akan membuat satu elemen dalam satu waktu. Algoritma ini memerlukan paling banyak n – 1 buah perbandingan untuk menggabungkan 2 (dua) buah Daftar Terurut yang berukuran n/2. Kompleksitas waktunya . Sedangkan algoritma PRAM hanya membutuhkan
dengan sebuah prosesor untuk setiap elemennya. Dua daftar yang sudah terurut yang akan digabungkan ini memiliki elemen-elemen yang saling disjoint.
(Merging Two Sorted List – Quinn)
Algoritma Paralel Pewarnaan Graph (Graph Coloring)
Persoalan pewarnaan Graph (Graph Coloring) adalah mencari banyaknya warna yang dapat digunakan untuk mewarnai setiap vertex yang ada pada sebuah Graph sehingga tidak ada vertex yang bertetangga memiliki warna yang sama.
Asumsikan bahwa kita memiliki sebuah Graph dengan n buah vertex. Kemudian kita membuat sebuah matriks tetangga (matrik adjacency) n x n dan sebuah bilangan konstan c , sebuah prosessor disiapkan untuk setiap kemungkinan pewarnaan Graph. Contoh, prosesor \(P(i_0,i_1, … , i_{n-1})\) berkaitan dengan pewarnaan vertex 0 dengan warna \(i_0\), pewarnaan vertex 1 dengan warna \(i_1\), … pewarnaan vertex n-1 dengan warna \(i_{n-1}\)
Setiap prosesor pada awalnya mengatur nilainya dalam candidate array berdimensi-n ke nilai 1 (satu). Kemudian menghabiskan waktu \(\Theta (n^{2})\) untuk menentukan apakah untuk pewarnaan pada vertex tertentu dapat dilakukan, dua vertex yang bertetangga telah diberi warna yang sama. Jika A[j,k] = 1 dan \(i_j = i_k\), maka proses pewarnaan salah, karena A[j,k] = 1 berarti vertex j dan k bertetangga, dan \(i_j = i_k\) artinya j dan k memiliki warna yang sama. Jika prosesor mendeteksi pewarnaan yang salah ini, dia akan mengubah nilainya di candidate array menjadi 0. Setelah \(n^2\) kali pembandingan, jika ada elemen di candidate array yang masih bernilai 1, maka pewarnaan dinyatakan benar. Dengan menjumlahkan semua elemen \(c^n\) dalam candidate array, maka kita dapat menyatakan apakah proses pewarnaan dapat dilakukan (lihat gambar dan algoritma di bawah ini)
Kompleksitas : \(\Theta (n^2)\) dengan menggunakan n buah Prosesor.
Preorder Tree Traversal
Preorder Traversal adalah proses kunjungan pada graph pohon dimana penandaan kunjungan dilakukan di awal yaitu ketika node untuk pertama kali terkunjungi. Urutan kunjungan mengikuti kaidah depth first search order. Secara sekilas persoalan preorder traversal seperti persoalan sekuensial. Coba perhatikan fungsi rekursif di bawah ini :
Dimana parallelisme nya ? Kita akan melihat bahwa cara pandang dengan vertex sebagai fokusnya akan menyebabkan kita melihat persoalan ini sebagai persoalan sekuensial murni yang tidak ada proses paralel nya.
Sekarang, mari kita lihat dengan cara pandang yang berbeda. Mari kita pandang ruas/edge dari graph ini. Kita melihat bahwa ketika perjalanan kunjungan graph dilakukan, maka setiap ruas/edge akan dilewati 2 (dua) kali dengan arah yang berlawanan, turun dan naik. Jika kita pisahkan setiap ruas/edge ini menjadi 2, yang pertama menjadi ruas turun, dan yang satu lagi menjadi ruas naik, maka sekarang kita akan melihat persoalan preorder traversal ini menjadi sebuah persoalan singly-linked list.
Cara pandang terhadap ruas/edge inilah yang menjadikannya sebagai persoalan yang dapat diparalelkan dengan sebuah algoritma yang cepat. (dipublikasikan oleh Tarjan dan Vishkin 1984).
Selanjutnya mari kita bahas algoritma ini dengan lebih rinci. Algoritma ini memiliki 4 fase. Pada fase pertama, algoritma akan membentuk sebuah singly-linked list. Setiap vertex/simpul dari singly-linked list ini akan berkait dengan ruas penelusuran naik atau ruas penelusuran turun di dalam tree.
Pada fase kedua, algoritma akan memberikan bobot kepada semua vertex/node dari singly-linked list yang baru dibuat tersebut. Pada algoritma preorder traversal, sebuah vertex/node diberi label/tanda segera saat dilewati traversal/penelusuran edge yang turun. (Vertex root adalah pengecualian dan harus ditangani secara khusus). Untuk itu pada setiap vertex/node yang terkait dengan penelusuran edge turun diberi bobot 1 (satu)., artinya hitungan node nya bertambah ketika ruas/edge nya ditelusuri. Kemudian daftarkan element-element yang terakit dengan ruas/edge naik dengan bobot 0 (nol), karenanya hitungan node nya tidak akan bertambah ketika penelusuran pohon melaluinya saat menuju node yang sudah diberi label/tanda sebelumnya.
Pada fase ketiga kita menghitung rank dari daftar element untuk setiap elemen di sinly-linked list.
Langkah/fase keempat, prosesor2 yang memegang ruas turun menggunakan rank yang sudah dihitung olehnya untuk memberikan angka penelusuran/traversal preorder pada node-2 yang terkait dengannya (node di akhir ruas turun)
Implementasi alogritma ini menggunakan sturktur data yang tidak biasa dalam menampilkan pohon/tree nya.
Untuk setiap tree node, struktur data menyimpan : parent dari node, sibling langsung yang berada di kanannya (immediate sibling to the right) dan anak paling kiri (leftmost child).
Algoritma di bawah ini adalah algoritma PRAM untuk preorder tree traversal. Algoritma ini memasangkan setiap prosesor dengan setiap ruas/edge yang ditelusuri. Sebuah pohon/tree dengan n buan node akan memiliki n-1 buah ruas/edge. Karena kita membagi setiap ruas/edge menjadi ruas turun dan ruas naik , maka algoritma ini membutuhkan 2(n-1) buah prosesor untuk menghitung 2(n-1) elemen dari singly-linked list.
Setelah semua prosesor dalam keadaan aktif, mereka akan segera membentuk linked list yang terkait dengan preorder traversal. Diberikan ruas/edge (i,j), setiap prosesor harus menghitung penerusnya/successor dari ruas/edge tersebut dalam penelusurannya. Jika parent[i]=j, ruasnya akan menuju kebagian atas dari pohon, dari node anak ke parent nya. Ruas naik memiliki tiga macam successor. Jika anak memiliki sebuah sibling ruas successor akan bergerak dari parent node menuju ke sibling nya, selain itu jika anak memiliki kakek/grandparent , maka ruas successor akan bergerak dari node parent ke node kakek/grandparent nya. Jika kedua kondisi tersebut tidak terpenuhi maka artinya ruas berada di akhir/ujung dari pohon traversal, jadi selanjutnya kita letakkan sebuah loop di ujung dari daftar elemen ini. Dalam kasus ini kita juga mengetahui identitas dari node root/akar, dan kita jadikan nomor preordernya menjadi 0.
Berikutnya kita perhatikan kasus \(parent[i] \neq j\) ; dimana ruas bergerak turun di dalam pohon, dari node parent ke anaknya. Hanya ada dua macam successor edge. Jika node anaknya memiliki anak, maka successor nya adalah edge dari anak ke cucunya. Selain itu, node anak adalah daun dan successor adalah ruas dari anak menuju parent nya.
Setelah prosesor membentuk linked list, mereka akan memberikan nilai posisi 1 untuk elemen yang merupakan ruas turun dan 0 untuk elemen yang merupakan ruas naik.
Nilai akhir dari nilai posisi ini menunjukkan angka penelusuran preorder antara daftar elemen ke ujung dari list. Untuk menghitung lebel dari setiap node preorder traversal, setiap prosesor dihubungkan dengan ruas turun dan dikurangangi nilai position nya dari n+ 1. Penamahan 1 karena penomoran preorder traversal dimulai dari 1 bukan 0
List Ranking
[Ke Urutan Pembelajaran Paralel]
Berikut ini adalah masalah bagaimana menghitung suffix sums dari i buah element terakhir dari sebuah daftar(list), dimana untuk setiap n element linked list
Suffix Sums ini adalah varian dari prefix sums, dimana terdapat sejumlah bilangan pada sebuah array yang ditampilkan dalam bentuk linked list, kemudian kita akan menghitung jumlah angka-angka tadi yang dimulai dari bagian akhir linked list nya, bukan dari depan.
Jika bilangan-bilangan yang berada di dalam array tersebut adalah 1 atau 0 saja, dan operasi asosiatif nya adalah penjumlahan, maka persoalan ini sering disebut persoalan List Ranking. (Karp and Ramachandran 1990)
Salah satu cara untuk menentukan posisi list adalah dengan cara menghitung banyaknya link yang sudah dikunjungi antara element list dengan akhir dari list.
Jika kita menghubungkan sebuah prosesor dengan setiap element list dan jump pointers dalam pralel, jarak ke bagian akhir dari list akan tinggal setengah dengan perintah : \( next[i]\leftarrow next[next[i]] \)
Karena itu dengan hanya sebanyak lompatan logaritmik saja sudah cukup untuk melipat list , sehingga setiap element list akan menunjuk ke element list yang terakhir.
Jika sebuah prosessor menambahkan kepada penghitungan link-traversal nya sendiri, yaitu position[i], perhitungan link-traversal dari penerus yg dilaluinya, maka posisi list akan diperoleh.
Algorithma untuk permasalahan di atas dapat dilihat di bawah ini :
Fade out layer dengan Gimp
Ctt : artikel ini menggunakan Gimp 2.8.2 di Ubuntu 12.10
Untuk membuat fade out sebuah layer dengan Gimp tidaklah terlalu sulit, mari ikuti langkah-langkah sebagai berikut. Misalkan kita memiliki gambar sebagai berikut :
Source from : islamicmonitor.blogspot.com
Buka lah gambar tersebut sehingga muncul di jendela Gimp.
Aktifkan Toolbox dengan Dockable menu Layer (Windows > Docable Dialogs > Layers / Ctrl+L ). Kemudian tambahkan Layer Mask dengan cara click-kanan pada layer list gambar kita yang ada di Toolbox, lalu pilih Add Layer Mask.
Pilih White (full opacity), klik pada tombol “Add”. Langkah berikutnya adalah memilih fungsi Blend Tool dengan Gradient : FG to BG (RGB).
Ctt : Jika Tab Gradient belum muncul di Toolbox, Anda dapat memunculkan dengan cara click pada tanda segitiga kecil di kanan atas Tab list di Toolbox, lalu pilih Add Tab dan pilihlah Gradient.
Kemudian drag sebuah garis semu pada gambar yang akan diberi efek fade out.
Lalu akan menjadi sebagai berikut :
Setelah fade-out ini cocok dan menjadi tetap, maka langkah terakhir adalah menetapkan perubahan ini dengan cara click kanan di layer list yang ada gambar kita, lalu pilih Apply Layer Mask.
Sehingga gambar kita menjadi :
Selamat mencoba !
Search Path di PostgreSQL
Search Path (search_path) adalah daftar schema yang menjadi patokan bagi PostgreSQL untuk mencari objek yang digunakan, apakah itu table, view, dan sebagainya. Urutan daftar ini juga akan menentukan prioritas pencarian. Untuk menampilkan current search path :
#show search_path;
ossystem=# show search_path;
search_path
---------------------------------
sys, public, helpdesk, hrd, sym
(1 row)
Untuk membentuk search_path kita mengunakan statement SET, contoh :
SET search_path TO my_schema, public;
E: Could not get lock /var/lib/aptitude/lock – open …
Error ini diperoleh pada saat sedang melakukan Upgrade paket-paket Ubuntu dengan menggunakan aptitude .
Pada saat aptitude sedang berproses melakukan upgrade, sayat tertidur dan membiarkan laptop hidup hingga akhrinya jaringan putus sendiri seiring dengan matinya laptop saya. Ternyata proses yang belum tuntas tadi meninggalkan sampah ‘lock’ . Karena itu ketika koneksi kembali lalu mencoba menghidupkan masuk ke aptitude lagi, maka muncullah pesan :
E: Could not get lock /var/lib/aptitude/lock – open (11: Resource temporarily unavailable)” error
Untuk memperbaiki hal ini saya lakukan beberapa hal sebagai berikut :
- apt-get update
- killall -9 apt-get aptitude
- rm -f /var/lib/aptitude/lock
Semoga berguna, terimakasih.
How To Create a New User and Grant Permissions in MySQL
I always forget the MySQL create database with UTF8 character set syntax, so here it is:
CREATE DATABASE `mydb` CHARACTER SET utf8 COLLATE utf8_general_ci; GRANT ALL ON `mydb`.* TO `username`@localhost IDENTIFIED BY 'password'; FLUSH PRIVILEGES;
Alternatively, you can use ‘CREATE SCHEMA’ instead of ‘CREATE DATABASE’:
CREATE SCHEMA `mydb` CHARACTER SET utf8 COLLATE utf8_general_ci; GRANT ALL ON `mydb`.* TO `username`@localhost IDENTIFIED BY 'password'; FLUSH PRIVILEGES;
I hope this helps someone else too!
Algoritma-algoritma PRAM
[Ke Urutan Pembelajaran Paralel]
PRAM adalah singkatan dari Parallel Random Access Machine
Ini adalah salah satu model komputasi paralel. Model ini sangat sederhana, PRAM belum memperhitungkan jumlah prosesor dan komunikasi antar prosesor. Karena kompleksitas komunikasi ini tidak menjadi isu/masalah akhirnya para desainer/pembuat algoritma PRAM dapat lebih fokus pada paralalisme komputasinya.
Model Komputasi Serial
Model Komputasi Paralel PRAM
x
Algoritma-algoritma PRAM
- Parallel Reduction
- Prefix Sums
- List Ranking
- Preorder Tree Traversal
- Merging Two Sorted Lists
- Graph Coloring