Combinatorial Problem

Combinatorial problem adalah masalah yang paling sulit dalam komputasi, dari kedua aspek heoritical dan praktek. Kesulitannya berasal dari bukti yang ada. Pertama, jumlah objek kombinatorial biasanya tumbuh dengan cepat dengan ukuran masalahnya. Kedua, tidak ada yang tahu algoritma untuk memecahkan sebagian besar masalah tersebut persis dalam masalah yang diterima pada waktu tersebut. 

Searching

1.      Pengertian Algoritma Pencarian (searching)

Pencarian(searhing) merupakan proses pengolahan data. Proses pencarian adalah menemukan nilai(data) tertentu didalam sekumpulan data yang bertipe sama. Sebuah algoritma pencarian dijelaskan secara luas adalah sebuah algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut, yang biasanya didapat dari evaluasi beberapa kemungkinan solusi. Algoritma pencarian (searching algorithm) adalah algoritma yang menerima sebuah argumen kunci dan dengan  langkah-langkah tertentu akan mencari rekaman dengan kunci tersebut.  Setelah proses pencarian dilaksanakan, akan diperoleh salah satu dari dua kemungkinan, yaitu data yang dicari ditemukan (successful) atau tidak ditemukan (unsuccessful).

·         Macam-macam Algoritma Pencarian (Searching)

1.       Pencarian sekuensial (Sequential searching).

Pencarian Sekuensial (sequential searching) atau pencarian berurutan sering disebut pencarian linear merupakan metode pencarian yang paling sederhana.  Pencarian beruntun adalah proses membandingkan setiap elemen larik satu per satu secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan atau seluruh elemen sudah diperiksa. Pencarian beruntun terbadi dua yaitu :

-     Pencarian beruntun pada larik tidak terurut;

-     Pencarian beruntun pada larik terurut.

·         Algoritma

Pencarian berurutan menggunakan prinsip sebagai berikut :

1.            data yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai data tersebut ditemukan atau tidak ditemukan.

2.            Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai dengan jumlah data.

3.            Pada setiap pengulangan, dibandingkan data ke-i dengan yang dicari.

4.            Jika sama, berarti data telah ditemukan.   Sebaliknya apabila sampai akhir pengulangan tidak ada data yang sama, berarti data tidak ada.

Kelemahan pada kasus yang paling buruk, untuk N elemen data harus dilakukan pencarian sebanyak N kali pula. Algoritma pencarian berurutan dapat dituliskan sebagai berikut :

(1)           i ← 0

(2)           ketemu ← false

(3)           Selama (tidak ketemu) dan (i <= N) kerjakan baris 4

(4)           Jika (Data[i] = x) maka ketemu ← true, jika tidak i ← i + 1

(5)           Jika (ketemu) maka i adalah indeks dari data yang dicari, jika data tidak ditemukan

·         Contoh 1 :

#include <stdio.h> #include <conio.h> void main(){ int data[8] = {4,10,8,-2,11,9,1,200};  int cari;    int flag=0;   printf("masukkan data yang dicari = ");scanf("%d",&cari);    for(int i=0;i<4;i++){                 if(data[i] == cari) flag=1;    }    if(flag==1) printf("Data ada!\n"); else printf("Data tidak ada!\n"); getch(); return 1; }

Dari program diatas, terlihat bahwa dilakukan perulangan untuk mengakses semua elemen array data satu persatu berdasarkan indeksnya.

·         Program menggunakan sebuah variabel flag yang berguna untuk menadai ada atau tidaknya data yang dicari dalam array data.  Hanya bernilai 0 atau 1.

·         Flag pertama kali diinisialiasasi dengan nilai 0.

·         Jika ditemukan, maka flag akan diset menjadi 1, jika tidak ada maka flag akan tetap bernilai 0.

·         Semua elemen array data akan dibandingkan satu persatu dengan data yang dicari dan diinputkan oleh user.

2.        Pencarian Beruntun dengan Sentinel.

Jika pencarian bertujuan untuk menambahkan elemen baru setelah elemen terakhir larik, maka terdapat sebuah varian dari metode pencarian beruntun yang mangkus. Nilai x yang akan dicari sengaja ditambahkan terlebih dahulu. Data yang ditambahkan setelah elemen terakhir larik ini disebut sentinel.

Perhatikan array data berikut ini:

  0                       1                    2                3                     4                  5              6          indeks

3          12        9          -4         21        6         

        ffea                 ffeb          ffec               ffed               ffef                  fffa           fffb       alamat

 

ü Terdapat 6 buah data dalam array (dari indeks 0 s/d 5) dan terdapat 1 indeks array tambahan (indeks ke 6) yang belum berisi data (disebut sentinel)

ü Array pada indeks ke 6 berguna untuk menjaga agar indeks data berada pada indeks 0 s/d 5 saja.  Bila pencarian data sudah mencapai array indeks yang ke-6 maka berarti data TIDAK ADA, sedangkan jika pencarian tidak mencapai indeks ke-6, maka data ADA.

• Algoritma

Procedure SeqSearchWithSentinel(input L: LarikInt, input n: integer, input x: integer, output idx: integer)

Contoh 2 :

I: integer ALGORITMA L[n+1]  ← X   {sentinel} I ← 1 While (L[i] ≠ x) do                  I ← i+1 Endwhile If idx = n+1 then                  idx  ← -1 else                  idx ← 1 endif •         Contoh #include <stdio.h> #include <conio.h> void main(){  int data[7] = {3,12,9,-4,21,6};  int cari,i; printf("masukkan data yang ingin dicari = ");scanf("%d",&cari); data[6] = cari;    i=0;  while(data[i] != cari) i++;  if(i<6) printf("Data ada!\n"); else printf("Data tidak ada!\n"); getch; return 1; }

3.       Pencarian Biner (binary search)

·  Terdapat metode pencarian pada data terurut yang paling efficient, yaitu metode pencarian bagidua atau pencarian biner (binary search). Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat. Prinsip pencarian dengan membagi data atas dua bagian mengilhami metode ini. Data yang disimpan di dalam larik harus sudah terurut.

BST adalah binary tree yang mana data di dalamnya tersusun sedemikian rupa sehingga pada setiap subtree di dalamnya berlaku:

setiap data di subtree kiri < data root subtree < setiap data di subtree kanan.

Contoh 3 :

class BinaryNode {       void printInOrder( )‏       {               if( left != null )‏            left.printInOrder( );                               // Left               System.out.println( element );            // Node               if( right != null )‏                right.printInOrder( );                          // Right    } } class BinaryTree {    public void printInOrder( )‏    {               if( root != null )‏               root.printInOrder( );    }

Ø  Prinsip dari pencarian biner dapat dijelaskan sebagai berikut :

1.      mula-mula diambil posisi awal 0 dan posisi akhir = N - 1, kemudian dicari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2.

2.      Kemudian data yang dicari dibandingkan dengan data tengah.

3.      Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah –1.

4.      Jika lebih besar, porses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah + 1.

5.      Demikian seterusnya sampai data tengah sama dengan yang dicari.

Algoritma pencarian biner dapat dituliskan sebagai berikut :

1.         L  ← 0

2.         R ← N - 1

3.         ketemu ← false

4.         Selama (L <= R) dan (tidak ketemu) kerjakan baris 5 sampai dengan 8  

5.         m ← (L + R) / 2 83

6.         Jika (Data[m] = x) maka ketemu ← true

7.         Jika (x < Data[m]) maka R ← m – 1 Jika (x > Data[m]) maka L  ← m + 1

8.         Jika (ketemu) maka m adalah indeks dari data yang dicari, jika tidak data tidak ditemukan.

 Contoh 5 :

int binary_search(int cari){ int l,r,m;  l = 0;    r = n-1;  int ktm = 0;  while(l<=r && ktm==0){                 m = (l+r)/2;                if(data[m] == cari) ktm=1;                else if (cari < data[m]) r=m-1;                else l=m+1; {  if(ktm==1) return 1; else return 0; }         }                     }

6.        Interpolation Search.

Teknik ini dilakukan pada data yang sudah terurut  berdasarkan kunci Tertentu. Teknik searching ini dilakukan dengan perkiraan letak data.

Contoh ilustrasi: jika kita hendak mencari suatu nama di dalam buku telepon, misal yang berawalan dengan huruf T, maka kita tidak akan mencarinya dari awal buku, tapi kita langsung membukanya pada  2/3 atau ¾ dari tebal buku. Jadi kita mencari data secara relatif terhadap jumlah data. Rumus posisi relatif kunci pencarian dihitung dengan rumus:

Posisi =       kunci – data[low]       x (hight – low) + low

              Data[hight] – data[low]

Misal terdapat data sebagai berikut:

Kode   Judul Buku      Pengarang 025      The C++ Programming           James Wood 034      Mastering Delphi 6     Marcopolo 041      Professional C#           Simon Webe 056      Pure JavaScript v2      Michael Bolton 063      Advanced JSP & Servlet         David Dunn 072      Calculus Make it Easy            Gunner Christian 088      Visual Basic 2005 Express     Antonie 096      Artificial Life : Volume 1 Gloria        Virginia Kunci Pencarian ? 088 Low ? 0 High ? 7 Posisi = (088 - 025) / (096 - 025) * (7 - 0) + 0 = [6] Kunci[6] = kunci pencarian, data ditemukan : Visual Basic 2005 Kunci Pencarian ? 060 Low ? 0 High ? 7 Posisi = (060 – 025) / (096 – 025) * (7 – 0) + 0 = [3] Kunci[3] < kunci pencarian, maka teruskan Low = 3 + 1 = 4 High = 7 Ternyata Kunci[4] adalah 063 yang lebih besar daripada 060. Berarti tidak ada kunci 060. •         Contoh Program #include <stdio.h> #include <stdlib.h> #define MAX 5 int interpolationsearch(int a[],int low,int high,int x){       int mid;       while(low<=high){                                              mid=low+(high-low)*((x-a[low])/(a[high]-a[low]));                   if(x==a[mid])                               return mid+1;                   if(x<a[mid])                               high=mid-1;                   else                               low=mid+1;       }        return -1; } int main(){       int arr[MAX];       int i,n;       int val,pos;             printf("\nEnter total elements (n < %d) : ",MAX);       scanf("%d",&n);        printf("Enter %d Elements : ",n);        for(i=0;i<n;i++)                   scanf("%d",&arr[i]);                   printf("\nLIST : ");                  for(i=0;i<n;i++)                    printf("%d\t",arr[i]);                   printf("\nSearch For : ");                   scanf("%d",&val);                   pos=interpolationsearch(&arr[0],0,n,val);                   if(pos==-1)                               printf("\nElement %d not found\n",val);                               else                                           printf("\nElement %d found at position %d\n",val,pos);            return 0; }

Numerical Problem

Melibatkan objek matematika, memecahkan persamaan dan system persamaan, komputasi integral tertentu, dan mengevaluasi fungsi. Kebanyakan masalah matematika diselesaikan dengan menggunakan pendekatan. Poko kesulitan lain berasal dari kenyataan bahwa masalah biasanya membutuhkan manipulasi bilangan real, yang dapat di representasikan dalam computer dengan pendekatan.

Contoh Numerical problem :

Geometry Problem

Geometri komputasi adalah cabang ilmu computer yang mempelajari algoritma untuk memecahkan masalah geometris. Dalam teknik matematika modern, komputasi geometri memiliki aplikasi dalam bidang seperti computer grafis, robotika, pemodelan molekul, metalurgi, manufaktur, tata letak tekstil, kehutanan, dan statistik. Input untuk masalah komputasi geometri biasanya merupakan deskripsi masalah dari satu set objek geometris, seperti satu set poin, satu set segmen garis, atau simpul polygon. Outputnya dapat berupa garis berpotongan, atau mungkin objek geometris baru, seperti convex hull dari himpunan beberapa titik.

1.       Closest pair problem

-          Pasangan terdekat, diberikan poin n pada ruang metric, mencari pasangan terdekat antar poin

Contoh :

Closest pair menggunakan algoritma divide & conquer

Case : Menemukan dua titik yang jaraknya paling minimal dari garis S.

1.       Kita bagi menjadi dua bagian yaitu S1 dan S2 dengan garis m.

2.       Asumsikan bahwa {p1 dan p2} adalah point yang paling dekat di S1, lalu {q1 dan q2} adalah point yang terdekat di S2.

3.       Cari titk terdekat dari garis m pada bagian S1 dan S2 yaitu {p3 dan q3}.

4.       Selanjutnya pasangan titik yang jaraknya paling minimal pada garis S.

        Terdapat tiga kandidat :

{p1,p2}

{q1,q2}

{p3,q3}

Perhatikan : pasangan terdekat memiliki satu titik kontribusi dari masig-masing bgian S1 dan S2, maka kedua titik tersebut harus berada dalam area d dari garis tengah m.

KENAPA INI? Jika salah satu dari titik-titik ini adalah jauh dari titik tengah, maka tidak mungkin lebih dekat daripada unit d ke titik di bagian lain, dan karenanya tidak mungkin menentukan sepasang lebih dekat daripada d, yang telah ditetapkan sebagai minimal dua sub-solusi dihitung untuk S1 dan S2.

Kami membuat satu pengamatan akhir untuk meraih algoritma yang efisien: karena jarak minimum antara sub-solusi itu d, hanya ada maksimum satu titik dalam d m di setiap bagian S1 dan S2. Jika tidak, dua poin dalam interval yang akan menentukan pasangan dalam salah satu subset dekat daripada d, yang bertentangan dengan minimalitas d.

Oleh karena itu dalam rangka untuk melihat dari tiga pilihan kami adalah pasangan yang paling dekat yang benar, kita hanya perlu untuk menguji satu pasang poin untuk melihat apakah ada sepasang {p3, Q3} yang mendefinisikan pasangan lebih dekat daripada d! Oleh karena itu penggabungan solusi kami tentu dilakukan dalam waktu linier, jadi kami memang menggambarkan sebuah O (nlogn) algoritma.

Sumber : http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPair1D.html

2.       Convex-hull problem

-          Poligon, meminta untuk menemukan polygon cembung terkecil yang akan mencakup semua poin dari himpunan.

Contoh convex-hull :

Grap Problem

Grap

Pendahuluan

Menurut Dasgupta dkk (2008), graph merupakan himpunan tak kosong titik-titik yang

disebut vertex (juga disebut dengan node) dan himpunan garis-garis yang

menghubungkan titik tersebut yang disebut dengan edge (juga disebut dengan arc,

sehingga dapat dinotasikan sebagai G(V,E). Vertex atau node pada graf dapat

dinomori dengan huruf, seperti a,b,c,d, ..., atau dengan bilangan asli 1,2,3, … atau

juga gabungan dengan keduanya. Sedangkan untuk edge atau arc yang

menghubungkan antara simpul u dan v dinyatakan dengan (u,v) atau dapat dinyatakan

dengan lambang e1,e2,e3, … dengan 1,2,3 adalah indeks. Dapat dikatakan bahwa jika e

merupakan sisi yang menghubungkan simpul u dengan v, maka e dapat ditulis sebagai

e = (u,v)

1 Rinal munir

2 Usu

Grap pada umumnya di gunakan untuk sebagai cara yang sederhana untuk memodelkan banyak jaringan,

sebuah jaringan adalah sebuah sistem yang melibatkan perpindahan, bisa perpindahan data, atau informasi

dapat dimodelkan ke dalam bentuk grap, dimana

Dalam memodelkan sebuah jaringan dengan graph,

simpul dalam graph umumnya dinyatakan dalam bentuk titik yang menyatakan asal

aliran serta tempat berakhir (contohnya, stasiun kereta api, terminal,Sebuah graph juga memberikan model struktural dari jaringan. Dalam

kebanyakan jaringan, metode konstruksi biasanya dinyatakan oleh harga, efisiensi,

kehandalan dan kapasitas.

jenis grap

berdasarkan arah dan bobot

grap yang setiap sisinya diberikan orientasi arah yang disebut dengan busur, dalam grap berarah menyatakan dua buah busur yang berbeda

Graph berarah dan berbobot sering digunakan untuk menggambarkan aliran proses,

peta lintas kota dan lain sebagainya.

berdasarkan  arah dan tidak berbobot

Merupakan graph yang mempunyai orientasi arah namun tidak mempunyai bobot

apapun

grap tidak berarah dan tidak berbobot

String Matching

Pendahuluan

String Matching

Sebelum mengenal String Matching kita, karena string matching adalah salah satu cara untuk pencarian, karena itu kitaharus mengetahui dasar dari sebuah pencarian, pencarian digunakan oleh mesin pencarian yang fungsinya untuk mencari file-file yang tersimpan pada layanan seperti www, ftp, berita.

pada umumnya hasil dari pencarian ditampilkan dalam bentuk list, untuk melakukan proses pencarian, mesin pencari akan melakukan 3 proses, yaitu :

1.       Proses Crawling

2.       Proses Indexing

3.       Proses Searching

1.       Proses Crawling

Pada Proses Crawling digunakan istilah spider, spider bertugas untuk mengumpulkan informasi mengenai situs blog atau website, Spider mengumpulkan informasi dari mulai link, struktur HTML, meta tag, judul, hingga konten teks. Spider dapat merayapi situs blog atau website yang menggunakan/memiliki file robots.txt.Robots.txt berisi script yang kemudian akan diterjemahkan oleh spider sebagai perintah untuk mengumpulkan informasi-informasi yang disebutkan. Dan robots.txt juga akan memudahkan spider untuk mengumpulkan data. Proses crawling merupakan proses yang sangat penting. Jika proses crawling tidak berjalan dengan lancar, maka mesin pencari tidak akan mengenali situs blog atau website tersebut.

2.       Proses Indexing

Setelah proses crawling sudah dilakukan , maka informasi yang didapatkan akan disimpan dalam database. Penyimpanan pada database ini menggunakan index yang juga mencantumkan alamat URLnya.Penyimpanan ini dilakukan secara berkala, untuk mempercepat proses pencarian.

3.       Proses Searching

Yang terakhir adalah proses searching. Proses searching dilakukan berdasarkan perintah dari pengguna mesin pencarian. Pada saat pengguna melakukan pencarian menggunakan kata kunci (keyword) yang dikehendaki, maka Makalah IF2211 Strategi Algoritma, Semester II Tahun 2015/2016 mesin pencari (search engine) akan menampilkan informasi berdasarkan hasil proses indexing. Mesin pencari (search engine) akan menampilkan judul, cuplikan artikel yang sesuai dengan kata kunci (keyword), beserta cuplikan URL tersebut.

Pencarian Informasi dengan String Matching

                Proses String Matching akan dilakukan misalkan pada kotak pencarian di isikan keyword APEL sedangkan dalam database berisi informasi
MANGGA, JERUK

Maka proses akan dilakukan dengan cara brute force

Perbandingan sama dengan brute force karena tidak ada prefix yang sama dengan prefix pada “APEL”. Sehingga banyak perbandingan adalah 3 .