SMS dikirim...

SMS diterima...

Convex Hull merupakan persoalan klasik dalam geometri komputasional. Persoalan ini saya ketahui pertama kali ketika lomba pemrograman waktu SMA. Persoalannya digambarkan secara sederhana dalam ruang dimensi dua (bidang) sebagai mencari subset dari himpunan titik pada bidang tersebut sedemikian rupa sehingga jika titik-titik tersebut dijadikan poligon maka akan membentuk poligon yang konveks. Suatu poligon dikatakan konveks jika digambarkan garis yang menghubungkan antar titik maka tidak ada garis yang memotong garis yang menjadi batas luar poligon. Definisi lain dari convex hull adalah poligon yang disusun dari subset titik sedemikian sehingga tidak ada titik dari himpunan awal yang berada di luar poligon tersebut (semua titik berada di batas luar atau di dalam area yang dilingkupi oleh poligon tersebut).

convex hull

Petunjuk untuk menyelesaikan persoalan ini adalah persamaan garis pada bidang. Persamaan garis pada bidang memisahkan bidang menjadi dua bagian yaitu area di sebelah kanan bidang (relatif terhadap orientasi garis). Sebagai contoh garis berorientasi adalah sumbu koordinat. Misalkan saja sumbu vertikal (ordinat, arah orientasi ke atas), seluruh titik di sebelah kanan garis ini memiliki nilai komponen koordinat horizontal (X) yang positif sedangkan seluruh titik di sebelah kiri garis memiliki nilai komponen koordinat horizontal negatif.

Petunjuk di atas dimanfaatkan dengan membuat definisi bahwa garis yang dibentuk oleh titik-titik poligon jika diasumsikan memiliki orientasi yang sama, maka setiap titik berada di sebelah kanan seluruh garis batas tersebut. Definisi ini kemudian dimanfaatkan untuk menentukan aksi awal yaitu memilih titik yang berada paling luar pertama. Mencari titik pertama cukup mudah yaitu cukup memilih titik yang memiliki nilai komponen koordinat (horizontal atau vertikal) yang ekstrim (minimum atau maksimum). Titik-titik convex hull lainnya ditentukan berdasarkan titik pertama tadi.

Algoritma awal yang intuitif dari deskripsi paragraf sebelumnya adalah.

Algoritma tersebut menggunakan pendekatan exhaustive (brute-force). kompleksitas algoritma tersebut mendekati O(n²). Algoritma tersebut dapat dioptimasi dengan membuat agar kumpulan titik-titik tersebut terurut secara lexicografis (urutkan dulu berdasarkan koordinat sumbu-X lalu untuk koordinat pada sumbu-X yang sama urutkan berdasarkan koordinat pada sumbu-Y). Sifat keterurutan ini kemudian dimanfaatkan sehingga pada setiap fase tiap titik hanya dikunjungi satu kali (kompleksitas linier). Adapun fase-fase yang perlu dilalui terdiri dari dua fase yaitu batas bagian atas (upper boundary) dan batas bagian bawah (lower boundary). Misal pada contoh algoritma berikut :

procedure TForm1.ConvexHull( ap: array of TPoint );
var

  pi                : array of integer;
  hull              : array of integer;
  h, i, j, k, l     : integer;
  dx, dy, dx2, dy2  : integer;
  found             : boolean;
begin
  { initialize index }
  setlength( pi, length( ap ) );
  for i := 0 to high( pi ) do
    pi[i] := i;

  { sort the index lexicographically, shown here using simple quadratic complexity sort algorithm }
  for i := 0 to high( pi ) - 1 do begin
    for j := i + 1 to high( pi ) do begin
      if ( ap[pi[j]].X < ap[pi[i]].X ) or ( ( ap[pi[j]].X < ap[pi[i]].X ) and ( ap[pi[j]].Y > ap[pi[i]].Y ) ) then begin
        k := pi[j];
        pi[j] := pi[i];
        pi[i] := k;
      end;
    end;
  end;

  { build upper boundary }
  setlength( hull, 2 );
  hull[0] := pi[0];
  hull[1] := pi[1];
  h := 1;

  for i := 2 to high( pi ) do begin
    found := false;
    for k := 1 to high( hull ) do begin
      dx := ap[hull[k]].X - ap[hull[k - 1]].X;
      dy := ap[hull[k]].Y - ap[hull[k - 1]].Y;

      dx2 := ap[pi[i]].X - ap[hull[k]].X;
      dy2 := ap[pi[i]].Y - ap[hull[k]].Y;

      j := dy * dx2 - dx * dy2;
      { delete previous non-convex edge w.r.t current point }
      if j > 0 then begin
        hull[k] := pi[i];
        setlength( hull, k + 1 );
        found := true;
        break;
      end;
    end;

    { add if current point lies on the right side of previous upper edges }
    if not found then begin
      setlength( hull, length( hull ) + 1 );
      hull[high( hull )] := pi[i];
    end;
  end; 

  { build lower boundary }
  h := high( hull ) - 1;
  for i := high( pi ) downto 0 do begin
    found := false;
    for k := h to high( hull ) do begin
      dx := ap[hull[k]].X - ap[hull[k - 1]].X;
      dy := ap[hull[k]].Y - ap[hull[k - 1]].Y;

      dx2 := ap[pi[i]].X - ap[hull[k]].X;
      dy2 := ap[pi[i]].Y - ap[hull[k]].Y;

      j := dy * dx2 - dx * dy2;
      if j > 0 then begin
        hull[k] := pi[i];
        setlength( hull, k + 1 );
        found := true;
        break;
      end;
    end;

    if not found then begin
      setlength( hull, length( hull ) + 1 );
      hull[high( hull )] := pi[i];
    end;
  end;

  { display result }
  Image1.Canvas.Pen.Color := clLime;
  Image1.Canvas.MoveTo( ap[hull[0]].X, ap[hull[0]].Y );
  for i := 1 to high( hull ) do
    Image1.Canvas.LineTo( ap[hull[i]].X, ap[hull[i]].Y );
  for i := 0 to high( hull ) do
    drawpt( ap[hull[i]].X, ap[hull[i]].Y, clRed );

end;

Algoritma di atas terdiri dari tiga bagian yaitu pengurutan titik, penyusunan batas bagian atas, dan penyusunan batas bagian bawah. Pada contoh di atas kompleksitas ditentukan oleh algoritma pengurutan titik yang cenderung kuadratik (O(n²)) untuk mempermudah pemahaman, jika dibutuhkan algoritma pengurutan dapat menggunakan algoritma yang memiliki kompleksitas lebih rendah/linearitmik (O(n.log n)).

Lately I’m developing a portal , using codeigniter as framework, and jqgrid as view grid,,

It’s so great and maximize the lookability of my site.

Later I’ll describe more about how to things…

Satryo Soemantri Brodjonegoro

Data Badan Pusat Statistik menunjukkan, penganggur yang sarjana telah mencapai lebih dari 600.000. Keadaan ini jauh lebih berbahaya daripada penganggur yang bukan sarjana karena dapat menimbulkan masalah sosial.

Berbagai upaya telah ditempuh guna mengatasi hal ini, tetapi tiap tahun angka pengangguran meningkat. Beberapa pihak lalu mencari kambing hitam penyebab pengangguran massal tersebut.

Tanggalkan gelar

Masyarakat kita sudah terbius dengan kehausan akan gelar. Setiap orang ingin mempunyai gelar sebanyak mungkin, ada yang melalui pendidikan, ada yang membeli gelar. Seolah seseorang menjadi tidak berharga jika tidak mempunyai gelar. Hanya masyarakat miskin yang tidak mempunyai gelar karena tidak mampu membayar pendidikan dan tidak mampu membeli gelar.

Perguruan tinggi menangkap gejala ini dengan menyediakan berbagai layanan untuk mendapatkan gelar, baik melalui pendidikan sebenarnya maupun seadanya, bahkan dengan menjual gelar. Perguruan tinggi membutuhkan uang, sedangkan masyarakat yang mampu akan rela membayar untuk mendapatkan gelar. Maka, terjadilah perpaduan yang menyesatkan.

Mudahnya memperoleh gelar membuat masyarakat berduyun- duyun ”lulus” dari perguruan tinggi dengan menyandang gelar tanpa dibarengi keahlian atau kompetensi. Ketika mencari peluang kerja, mereka tidak memenuhi syarat sehingga terjadilah penganggur bergelar. Seharusnya mereka segera menanggalkan gelarnya karena tidak bermanfaat sama sekali.

Penjenjangan

Perusahaan swasta dan industri menerapkan pola rekrutmen pegawai berdasarkan kemampuan/kompetensi, tidak semata- mata berdasarkan gelar. Para calon pegawai ketat diseleksi secara ketat melalui uji kemampuan/kompetensi disesuaikan jenis pekerjaan yang akan ditangani.

Adapun untuk menjadi pegawai negeri sipil (PNS), seleksi hanya dilakukan terhadap gelar yang dimiliki calon pegawai, tanpa ada uji kemampuan/kompetensi. Karena sebagian besar masyarakat masih amat ingin menjadi PNS, mereka semua memburu gelar dengan berbagai cara, termasuk dengan memalsukan ijazah.

Penjenjangan karier di PNS juga hanya memerhatikan masa kerja dan gelar. Bagi mereka yang sudah bergelar S-2 atau magister akan dapat dipromosi ke golongan lebih tinggi, bahkan bagi mereka yang sudah bergelar S-3 atau doktor dapat dipromosi ke golongan tertinggi. Badan Kepegawaian Negara dan Kantor Menneg PAN menganggap para penyandang gelar itu mempunyai kemampuan memadai. Padahal, kenyataannya mereka hanya memburu gelar melalui berbagai cara, termasuk cara tidak wajar, yaitu membeli gelar atau mengikuti kelas jauh, kelas eksekutif, kelas Sabtu-Minggu, kelas paralel, kelas ekstensi, dan berbagai macam nama lain.

Lengkap sudah kekalutan yang ada di Indonesia ini tentang gelar. Masyarakat amat terbius dengan gelar, pendidikan hanya sebatas formalitas untuk memberi gelar para ”lulusan” dan sistem kepegawaian kita terjebak gelar.

Berikan contoh

Bagaimana mengatasi hal ini? Mudah sekali. Mulai hari ini kita semua menanggalkan semua gelar yang tercantum di kartu nama, papan nama, foto, surat menyurat, undangan, panggilan pada acara resmi, dan lainnya.

Mulai hari ini kita semua hanya menggunakan nama masing- masing yang sudah diberikan oleh orangtua sebagai suatu amanah. Nama sudah amat membanggakan seandainya kita memiliki keahlian, sedangkan gelar sama sekali tidak memberi nilai tambah terhadap keahlian. Jika semua orang tidak menggunakan gelar, termasuk para pemimpin, masyarakat akan menjadi lebih realistis dan tidak lagi terbius oleh gelar.

Mudah-mudahan, setelah itu mereka semua mencari keahlian dan perguruan tinggi akan memberi keahlian kepada lulusan, dan akhirnya penganggur bergelar akan berubah menjadi pekerja ataupun pemberdaya yang andal.

Satryo Soemantri Brodjonegoro Guru Besar Toyohashi University of Technology; Mantan Dirjen Dikti

http://cetak.kompas.com/read/xml/2009/09/24/02422099/penganggur.bergelar

ps: tulisan pak satrio ini sangat menarik sekali. pemikiran mantan pejabat dikti yang bergelut dengan persoalan gelar-gelaran. solusi yg simple dan tampaknya sulit diwujudkan dalam iklim negeri ini yang masih memuja gelar. btw usul ini tampaknya perlu diajukan kepada pejabat yg suka mencantumkan gelar dalam setiap UU yang disahkan, di era pemerintahan sekarang baru terjadi :P.

Solusi yang mirip bisa diterapkan terhadap kebijakan Ujian nasional, beberapa akhli pendidikan sudah mengusulkan ini. Memperbaiki mental dan fasilitas sekolah dulu baru dikasih ujian nasional.

Ondel - Ondel Betawi

Sewaktu lebaran kemarin saya dan keluarga mengunjungi keluarga besar kami di derah Parung, Bogor. Kelurga besar saya merupakan keluarga besar betawi yang bisa dibilang masih asli. Saya menjadi cengar – cengir sendiri sewaktu berkumpul kemudian mendengar obrolan, logat, kelakar – kelakar serta lawakan – lawakan orang Betawi. Sesuatu yang jarang saya jumpai kecuali ketika menonton film Almarhum Benyamin S.

Sungguh ironis memang, orang Betawi yang aslinya berasal dari Jakarta secara turun temurun harus tersingkir hingga di pinggiran Jakarta seperti Depok, Bekasi, Tanggerang, Condet, Citayem dll. Kalau mau mundur sejenak, dahulu sebelum tahun 50-an keluarga besar saya berdomisili di daerah Senayan Jakarta. Menurut cerita dari tetangga saya yang asli betawi, dahulu di daerah Senayan merupakan kampung Betawi, dimana banyak orang Betawi yang tinggal di daerah tersebut, ada beberapa yang merupakan keturunan etnis Tionghoa. Di daerah tersebut dibagi menjadi 3 bagian yaitu daerah Senayan, Petunduan, dan Bendungan, dimana ketiga kampung tersebut dipisahkan oleh sebuah jalan saja. Kemudian arus pembangunan bergerak sangat cepat, di daerah senayan tersebut akan dibangun lapangan Istora Senayan (sekarang Gelora Bung Karno). Oleh karena itu daerah tersebut terpaksa digusur, untuk orang Senayan dan Petunduan digusur ke daerah Tebet Barat (tempat tinggal saya sekarang) dan Tebet Timur. Hingga sekarang masih bisa dijumpai di daerah Tebet barat dan Tebet timur orang betawi gusuran Senayan. Namun apa boleh dikata, arus urbanisasi semakin deras sehingga memaksa orang betawi tersebut untuk menyingkir dari tanah kelahirannya. Satu persatu tetangga yang saya kenal betawi asli mulai menjual tanahnya kepada orang luar dan memilih untuk pindah ke pinggiran Jakarta.

Tidak bisa dipungkiri memang kalau orang betawi itu terkenal dengan juragan tanah, mempunyai banyak tanah di Jakarta ini. Bukan bermaksud sombong, keluarga besar saya mempunyai tanah yang luas di daerah Tebet (bekas gusuran Senayan), namun hingga hari ini satu persatu tanah tersebut dijual, kemudian saudara saya mulai pindah ke daerah Parung Bogor. Keluarga saya mempunyai Pesantren di daerah Parung tersebut, saudara – saudara saya mempunyai pendapat lebih bak tanah di Jakarta dijual dan kemudian dana hasil penjualan tanah tersebut dapat dialokasikan ke pesantren. Kalau menurut saya alasan tersebut masih bisa masuk di akal, namun bagaimana dengan alasan orang betawi yang lain, yang rela menjual tanahnya kepada etnis lain dan berpindah ke daerah Depok, Citayem, Condet dll.

Yah, kasihan juga orang Betawi, juragan tanah yang tidak mempunyai kampung halaman lagi.

Photo Credit : **