Menghitung T(n) min, max, dan average

 Contoh algo1 :


Procedure RataMaxMin ()


Deklarasi

  data, max, min : integer

  rata : real


Algoritma

tot = 0

i = 1

input (n)

while i ≤ n do

    input data

if i = 1 then

      min ← max ← data

else

   if max < data then

          max  ← data

   else

      if min > data then

               min ← data

      endif

   endif

endif

tot ← tot + data

i ← i + 1

endwhile

rata ← tot / n

output (rata)

output (min)

output (max)

Menentukan Indeks Nilai

Procedure menentukan _indeks_nilai(input:nilai, output:indeks)

Kamus :

indeks = char

Algoritma :

//menentukan indeks nilai

                if (nilai >= 80)then

                                indeks = 'A'

                else

                                if (nilai >= 70 and nilai < 80)then

                                                indeks = 'B'

                                else

                                                if (nilai >= 60 and nilai < 70)then

                                                                indeks = 'C'

                                                else

                                                                if (nilai >= 50 and nilai < 60)then

                                                                                indeks = 'D'

                                                                else

                                                                                indeks = 'E'

                                                                endif

                                                endif

                                endif

                endif

                output("indeks nilai anda =  ", indeks)

                output("ket : ")

                depend on (indeks) //memberi keterangan dari setiap indeks

                                'A' :

                                                output ("Sangat Baik")

                                'B' :

                                                output ("Baik")

                                'C' :

                                                output ("Cukup")

                                'D' :

                                                output ("Kurang")

                                ‘E’:

                                                output("Sangat Kurang")                                                             

enddepend

EndAlgoritma

PERHITUNGAN WAKTU

Menghitung Luas Permukaan limas segitiga

Procedure HitungLuas ()

Deklarasi

   sisialas, tinggisegitiga, luaspermukaan : real

   

   luasalas, luassisi, luassegitiga : real

Algoritma 

   {Input}

   

     sisialas ← 10

           

     tinggisegitiga ← 12

   {Proses}

   

   //Menghitung Luas Alas

       luasalas ← sisialas1 * sisialas2

   

   //Menghitung Luas Sisi

       luassegitiga ← 0,5 * tinggisegitiga * sisialas

       luassegitiga ← 4 * luassegitiga

   //Menghitung jumlah Luas permukaan

       luaspermukaan ← luasalas + luassegitiga 

A. Operasi pengisian nilai 

    

B. Operasi penjumlahan   

   

C.Operasi Perkalian

      

Total kebutuhan waktu eksekusi algoritma HitungRata2 :

Total Waktu = t1 + t2 + t3 = 6a + b + 3c

MENGHITUNG FAKTORIAL

Start

    Input A

    F ← A

    While  A>1 do

                A ← A – 1

                F ← F * A

    While end

    Output F

    End

MENGHITUNG PERKALIAN MATRIKS

procedure PerkalianMatriks(input A, B : Matriks, input n: integer, output C : Matriks)

Deklarasi

i, j, k : integer

Algoritma

for i¬1 to n do

     for j¬1 to n do

        C[i,j]¬0    { inisialisasi penjumlah }

        for k ¬ 1 to n do

           C[i,j]¬C[i,j] + A[i,k]*B[k,j]

        endfor

     endfor

   endfor

Reference http://zeromin0.blogspot.co.id/2011/07/r-algoritma.html#ixzz4Mm4lCc1Z

GRAPH PROBLEM

GRAPH

I.Pengertian Graph

         Graf (Graph) adalah kumpulan noktah (simpul) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan garis (sisi). Graph dapat digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual darigraph adalah dengan menyatakan objek sebagai noktah, bulatan atau titik (Vertex), sedangkan hubungan antara objek dinyatakan dengan garis (Edge).

       G = (V,E)

Dimana :
  G = Graph
  V = Simpul, Vertex, Node, atau Titik
  E = Busur atau Edge

          Graf adalah cabang ilmu yang memiliki banyak terapan, dan banyak masalah juga yang dapat di pecahkan dengan bantuan graf. Seringkali Graf digunakan untuk menggambarkan suatu jaringan. Seperti menggambarkan suatu alur data di motherboard dengan Bank / peripheral sepertu CPU , RAM , dan Hardisk sebaagai Simpul (vertex/node) dan jalur Bus yang menghubungkan mereka sebagai sisi (edege)yang weight nya adalah panjang Bus tersebut.
       
          Ada beberapa cara untuk menyimpan graph di dalam sitem komputer. Struktur data bergantung pada struktur graph dan algoritma yang digunakan untuk memmanipulasi graph. Secara teori salah satu dari keduanya dapat dibedakan antara struktur list dan matriks, tetapi dalam penggunaannya struktur terbaik yang sering digunakan adalah kombinasi keduanya.

         1. Graph tak berarah (undirected graph atau non-directed graph) :

• Urutan simpul dalam sebuah busur tidak dipentingkan. Misal busur e1 dapat disebut busur AB atau BA

         2. Graph berarah (directed graph) :

• Urutan simpul mempunyai arti. Misal busur AB adalah e1 sedangkan busur BA adalah e8.

         3. Graph Berbobot (Weighted Graph)

• Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki bobot.

• Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, dll.

II.Istilah - istilah dalam graph

       1. Vetex

           Adalah himpunan node / titik pada sebuah graph.

        

        2. Edge

            Adalah himpunan garis yang menghubungkan tiap node / vertex.

        3. Adjacent
       

         Adalah dua buah titik dikatakan berdekatan (adjacent) jika dua buah titik tersebut terhubung dengan sebuah sisi. Adalah Sisi e3 = v2v3 insident dengan titik v2 dan titik v3, tetapi sisi e3 = v2v3tidak insident dengan titik v1 dan titik v4.

         
Titik v1 adjacent dengan titik v2 dan titik v3, tetapi titik v1 tidakadjacent dengan titik v4.

         6. Weight
              Adalah Sebuah graf G = (V, E) disebut sebuah graf berbobot (weight graph), apabila terdapat sebuah fungsi bobot bernilai real W pada himpunan E,

                        W : E ® R

nilai W(e) disebut bobot untuk sisi e, " e Î E. Graf berbobot tersebut dinyatakan pula sebagai G = (V, E, W).

Graf berbobot G = (V, E, W) dapat menyatakan

* suatu sistem perhubungan udara, di mana

· V = himpunan kota-kota

· E = himpunan penerbangan langsung dari satu kota ke kota lain

· W = fungsi bernilai real pada E yang menyatakan jarak atau ongkos atau waktu

* suatu sistem jaringan komputer, di mana

· V = himpunan komputer

· E = himpunan jalur komunikasi langsung antar dua komputer

                        · W = fungsi bernilai real pada E yang menyatakan jarak atau ongkos atau waktu      

               7. Path
             Adalah Walk dengan setiap vertex berbeda. Contoh, P = D5B4C2A Sebuah walk (W) didefinisikan sebagai urutan (tdk nol) vertex & edge. Diawali origin vertex dan diakhiri terminus vertex. Dan setiap 2 edge berurutan adalah series. Contoh, W = A1B3C4B1A2.

               8. Cycle
                  Adalah Siklus ( Cycle ) atau Sirkuit ( Circuit ) Lintasan yang berawal dan berakhir pada simpul yang sama

III.  Representasi Graf 

 

       Dalam pemrograman, agar data yang ada dalam graph dapat diolah, maka graph harus dinyatakan dalam suatu struktur data yang dapat mewakili graph tersebut. Dalam hal ini graph perlu direpresentasikan kedalam bentuk array dan dimensi yang sering disebut matrix atau direpresentasikan dalam bentuk linked list. Bentuk mana yang dipilih biasanya tergantung kepada efisiensi dan kemudahan dalam membuat program. Berikut ini beberapa bentuk representasi graph:

         I. Representasi Graph dalam bentuk Matrix:

1. Adjacency Matrik Graf Tak Berarah 

              Matrik yang digambarkan pada gambar 1b merupakan representasi dalam bentuk Adjacency Matrik dari graf yang digambarkan pada gambar 1a. Beberapa hal yang dapat dilihat atau dapat diterangkan pada Adjacency Matrik tersebut adalah sebagai berikut :

               1. Matrik yang terbentuk adalah matrik bujur sangkar n x n, dimana n = jumlah simpul yang ada dalam graf tersebut. Matrik ini menyatakan hubungan antara simpul satu dengan simpul lainnya.

               2. Matrik yang terbentuk adalah matrik simetris dengan sumbu simetris adalah diagonal dari titik kiri atas ke titik kanan bawah. 3. Data yang tedapat baik dalam baris maupun kolom, dapat menyatakan degree sebuah simpul. Contoh : baik pada baris D maupun kolom D jumlah angka 1 nya adalah 3 buah, dimana jumlah ini menyatakan degree simpul D.

          

           2. Adjacency Matrik Graf Berarah 

Matrik yang digambarkan pada gambar 2b merupakan representasi dalam bentuk Adjacency Matrik dari graf yang digambarkan pada gambar 2a. Beberapa hal yang dapat dilihat atau dapat diterangkan pada Adjacency Matrik tersebut adalah sebagai berikut :

          1. Matrik yang terbentuk adalah matrik bujur sangkar n x n, dimana n = jumlah simpul yang ada dalam graf tersebut. Matrik ini menyatakan hubungan antara simpul satu dengan simpul lainnya.

          2. Matrik yang terbentuk mungkin simetris mungkin juga tidak simetris. Menjadi Simetris bila hubungan antara dua buah simpul (v1 dan v2) terdapat busur dari v1 ke v2 dan juga sebaliknya.

          3. Hal pokok yang dinyatakan oleh matrik ini adalah : busur yang ’keluar’ dari suatu simpul. Dengan demikian, data yang terdapat dalam suatu baris, dapat menyatakan outdegree simpul yang bersangkutan.

Contoh : Jumlah elemen yang nilainya = 1 pada baris B ada 3 elemen,ini menyatakan jumlah outdegree simpul B adalah 3 buah.

             4. Data yang terdapat dalam suatu kolom, dapat menyatakan indegree simpul bersangkutan. Contoh : Jumlah elemen yang nilainya 1 pada kolom B ada 2 elemen, ini menyatakan indegree simpul B adalah 2 buah.

           3. Adjacency Matrik Graf Berbobot Tak Berarah   

               Nilai yang ada dalam tiap elemen matrik, menyatakan bobot busur yang menghubungkan dua buah simpul yang bersangkutan. Untuk dua buah simpul yang tidak berhubungan langsung oleh sebuah busur, maka dianggap dihubungkan oleh sebuah busur yang nilai bobotnya tidak terhingga. Dalam pemograman, karena keperluan algoritma, maka dari total bobot seluruh busur yang ada atau yang mungkin ada. Contoh: pada gambar 3a simpul A dan C tidak berhubungan langsung melalui sebuah busur, maka untuk elemen matrik yang bersangkutan diisi dengan nilai 999 karena nilai 999 dalam kasus ini cukup mewakili nilai tidak terhingga.



         II.Representasi graf dalam bentuk Linked List

              1. Adjacency List

             Bila ingin direpresentasikan dalambentuk linked list, dapat diilustrasikan secara sederhana seperti gamabar 4b. Dari ilustrasi sederhana tersebut terlihat ada 5 buah simpul A,B,C,D,dan E yang dibariskan dari atas kebawah seperti pada gambar 4a. Kemudian dari masing-masing simpul ’keluar’ pointer kearah kanan yang menunjuksimpul-simpul lain. Salah satu contoh, yang dapat dilihat pada gambar 4b dimana A menunjuk simpul B dan simpul D.

            Dalam Adjacency List, kita perlu membedakan antara simpul-vertex dan simpul-edge. Simpul-vertex untuk menyatakan simpul atau vertex, dan simpul-edge untuk menyatakan hubungan antar simpul yang biasa disebutbusur. Struktur keduanya bisa sama, bisa juga tidak sama,tergantung kebutuhan.Untuk memudahkan pembuatan program, struktur kedua macam simpul dibuat sama seperti yang digambarkan pada gambar 5c. Yang membedakan antara simpul-vertex dan simpul-edge, adalah anggapan terhadap simpul tersebut. Dalam contoh ini, terlihat struktur simpul dibuat terdiri dari 3 elemen. Satu elemen untuk INFO, dua elemen untuk pointer.pointer kiri (left) dan pointer kanan (right).

Struct tipes{

Struct tipes *Left;

int INFO;

Struct tipes *Right;

};

Struct tipes *First,*Pvertex,*Pedge;


- Bila simpul dianggap sebagai simpul-vertex, maka :

   Pointer left digunakan untuk menunjuk simpul berikutnya dalam untaian simpul-simpul yang ada,atau diisi NULL bila sudah tidak ada simpul yang peluditunjuk.Sedangkan pointer Right digunakan untuk menunjuk simpul edge yang pertama.

- Bila Simpul dianggap sebagai simpul-edge, maka :

  Pointer left digunakan untuk menunjuk simpul-vertex ‘tujuan’ yang berhubungan dengan simpul-vertex ‘asal’ dan pointer right digunakan untuk menunjuk simpul-edge berkiutnya bila masih ada, atau diisi NULL bila tak ada lagi simpul-busur yang ditunjuk

Kombinatorial Problem ( Combinatorial Problems)

Combinatorial Problem merupakan suatu permasalahan matematis utuk menyusun, mengelompokan, atau memilih jumlah objek diskrit tertentu.

Kombinatorial Problem atau bisa juga di sebut masalah kombinasi muncul dibanyak penerapan ilmu komputer dan aplikasi domain : 

• finding shortest/cheapest round trips (TSP)  
• finding models of propositional formulae (SAT)  
• planning, scheduling, time-tabling  
• internet data packet routing  
• protein structure prediction  
• combinatorial  winner determination

Kombinatorial Problems melibatkan pencarian a grouping, ordering, atau assignment dari diskrit, dari obyek himpunan berhingga yang memenuhi kondisi tertentu.

Candidate solutions adalah kombinasi dari komponen solusi yang mungkin dihadapi selama upaya solusi, tapi tidak perlu memenuhi semua kondisi yang diberikan. (Solusi-solusi dari calon solusi kandidat yang memenuhi semua kondisi yang diberikan) 

Contoh :

• Given: Set poin dalam Euclidean plane  
• Objective: Find the shortest round trip

Catatan

• Rount trip (RTT) sesuai dengan urutan point (penugasan poin untuk urutan posisi)
• Komponen solusi  : rangkaian yang terdiri dari dua titik yang dikunjungi langsung setelah yang lain 
• Candidate solution: round trip  
• Solusi                    : round trip dengan panjang minimal

Problem vs problem :

Problem  : Mengingat setiap set poin X, menemukan round trip(RTT) terpendek.

Solusi     :  Algoritma yang menemukan perjalanan pulang terpendek untuk setiap X

Problem Instance : Mengingat satu set khusus point P , menumukan roundtrip(RTT) terpendek.

Solusi                   : Routrip(RTT) terpendek di gunakan untuk point P

(Secara teknis, masalah dapat diformalkan sebagai set contoh masalah)

Decision problems: 

Solusi = solusi kandidat yang memenuhi untuk diberikan kondisi logis

Contoh: Grafik Warna Masalah

Setiap masalah keputusan memiliki dua varian:
Search variant     : Mencari solusi untuk di berikan masalah (menentukan bahwa tidak ada solusi)
Decision variant  : Menentukan apakah solusi untuk masalah yang diberikan misalnya ada.

Catatan: Cari dan putuskan varian yang erat terkait algoritma untuk dapat digunakan  memecahkan masalah yang lainnya.

Optimisation problems:

• Dapat dilihat sebagai generalisasi dari masalah keputusan
• Tujuan fungsi F kualitas langkah solusi (Sering didefinisikan pada semua solusi calon)
• Tujuan khas: mencari solusi dengan kualitas optimal 
• minimisation problem:  kualitas optimal = nilai minimal f
• maximisation problem: kualitas optimal = nilai maksimal f

Varian dari masalah optimasi:

Search variant         : Mencari solusi dengan optimal nilai fungsi  untuk diberikan  masalah. 

Evaluation variant: : Menentukan nilai fungsi tujuan yang optimal untuk diberikan masalah

Setiap masalah optimasi telah dikaitkan masalah keputusan

Contoh masalah dan solusi tetap  terikat b, menemukan solusi dengan nilai fungsi tujuan ≤ b (untuk meminimalkan masalah ) atau menentukan bahwa tidak ada solusi. Banyak masalah optimasi memiliki fungsi tujuan serta kondisi logis bahwa solusi harus memenuhi.

Kandidat solusi disebut layak (atau valid) jika memenuhi kondisi logis yang diberikan.

Catatan: kondisi logis selalu dapat ditangkap oleh fungsi tujuan sehingga kandidat solusi yang layak

sesuai dengan solusi dari masalah keputusan yang terkait

Note :

• Algoritma untuk masalah optimasi dapat digunakan untuk memecahkan masalah  terkait keputusan.
• Algoritma untuk masalah keputusan selalu dapat diperpanjang untuk masalah optimasi terkait.
• Tidak selalu memecahkan masalah dengan efisien

Sumber Referensi : Hoos, Holger H & St¨utzle, Thomas , , " STOCHASTIC LOCAL SEARCH FOUNDATIONS AND APPLICATION ( Introduction: Combinatorial Problems and Search )  , http://www.sls-book.net, 3 Oktober 2016 .

String Matching

String Macthing

Pengertian String Macthing

String macthing adalah pencarian sebuah pattern pada sebuah teks (Corman, T.M. et al. 1994). String macthing digunakan untuk menemukan suatu string yang di sebut dengan pattern dalam string yang di sebut dengan teks(Charras, C. Dan Lecroq. T.1997). Prinsin kerja algoritma string macthing(Effendi, D. Et al. 2013) adalah sebagai berikut:

1.           Memindai teks dengan bantuan sebuah window  yang           ukurannya sama dengan panjang pattern.

2.           Menempampatkan window pada awal teks.

3.           Membandingan karakter pada window dengan karakter dari pattern. Setelah pencocokan dilakukan pergeseran ke kanan pada window. Prosedur ini di lakukan berulang-ulang sampai window berada pada akhir teks. Mekanisme ini di sebut mekanisme sliding window.

Cara kerja Sting Matching

                 Cara yang jelas untuk mencari pattern yang cocok dengan teks adalah dengan mencoba mencari di setiap posisi awal dari teks dan mengabaikan pencarian secepat mungkin jika karakter yang salah di temukan (Knuth, D.E. et al. 1997). Proses pertama adalah menyelaraskan bagian paling kiri dari pattern dengan teks kemudian di bandingkan karakter yangb sesuai dari tks dan pattern setelah seluruhnya cocok maupun tidak cocok dari pattern, window di geser ke kanan sampai posisi (n-m+

                 Dengan sebuah nilai karakter (m < n) yang akan di cari dari teks dalam algoritma pencocokan sting, teks di asumsikan berada di dalam memory, sehingga bila kita mencari string di dalam sebuah arsip, maka semua isi arsip perlu di baca terlebih dahulukemudian di simpan di dalam memory. Jika pattern muncul lebih dari sekali di dalam teks, maka pencarian hanya akan memberikan keluaran berupa lokasi pattern di temukan pertama kali (Wulan. 2011).

  Teknik Algoritma String Matching

Menurut singla, N. Dan Grag, D.(2012), ada dua tekhnik utama dalam algoritma string matching yaitu:

1.                 Exact string matching

Exact string matching merupakan pencocokan string secara tepat dengan susunan karakter dalam string yang dicocokan memiliki jumlah maupun urutan karakter dalam string yang sama. Bagian algoritma ini bermanfaat jiga penggunaan ingin mencari string dalam dokumen yang sama percis dengan string masukan. Beberapa algoritma exact string matching antara lain:

a. Knuth-Morris-Pratt

Metode ini mencari kehadiran sebuah kata dalam teks dengan melakukan observasi awal (preprocessing) dengan cara mengecek ulang kata sebelumnya. Algoritma ini melakukan pencocokan dari kiri ke kanan.

b. Boyer-Moore

Algoritma Boyer-Moore adalah algoritma string matching yang paling efisien dibandingkan algoritma string matching lainnya. Sebelum melakukan pencarian string, algoritma melakukan proses terlebih dahulu pada pattern, bukan pada string pada teks tempat pencarian. Algoritma ini melakukan pencocokan karakter yang dimulai dari kanan ke kiri. Karena sifatnya yang sangat efisien, Boyer-Moore memiliki banyak variasi penyederhanaannya. Salah satunya adalah algoritma Horspool yang akan digunakan dalam penelitian ini dan akan dijelaskan pada poin berikutnya

2.                  Approximate string matching atau Fuzzy string matching.

Fuzzy string matching merupakan pencocokan string secara samar, maksudnya pencocokan string dimana string yang dicocokkan memiliki kemiripan memiliki susunan karakter yang berbeda (mungkin jumlah atau urutannya), tetapi string tersebut memiliki kemiripan baik kemiripan tekstual/penulisan (approximate string matching) atau kemiripan ucapan (phonetic string matching)

   Algoritma Horspool

Algoritma Horspool adalah penyederhanaan dari algoritma Boyer-Moore yang dibuat oleh R. Nigel Horspool. Menurut Horspool, R.N. (1980), masalah dalam pencarian teks ini adalah mencari dalam teks yang besar untuk menemukan pattern pertama. Karena teks yang dicari bisa sangat besar (memungkinkan ratusan ribu karakter) maka penting untuk menggunakan teknik yang lebih efisien. Algoritma Horspool bekerja dengan metode yang hampir sama dengan algoritma Boyer-Moore namun tidak melakukan lompatan berdasarkan karakter pada pattern yang ditemukan tidak cocok pada teks.

Algoritma Horspool mempunyai nilai pergeseran karakter yang paling kanan dari window. Pada tahap observasi awal (preprocessing), nilai shift akan dihitung untuk semua karakter. Pada tahap ini, dibandingkan pattern dari kanan ke kiri hingga kecocokan atau ketidakcocokan pattern terjadi. Karakter yang paling kanan pada window digunakan sebagai indeks dalam melakukan nilai shift. Dalam kasus ketidakcocokan (karakter tidak terdapat pada pattern) terjadi, window digeser oleh panjang dari sebuah pattern. Jika tidak, window digeser menurut karakter yang paling kanan pada pattern (Baeza-Yates, R.A. & Regnier, M. 1992).

Berikut adalah pseudocode algoritma Horspool pada tahap praproses:

Procedure preBmBc (

input P : array[0. . m-1] of char,

input m : integer,

input/output BmBc : array [0 . . n-1] of integer

)

Deklarasi:

i : integer

Algoritma:

for (i := 0 to ASIZE – 1)

BmBc[i] := m;

endfor

for (i := 0 to m-2)

BmBc[P[i]] := m – i – 1;

Endfor

Dan berikut adalah pseudocode algoritma Horspool pada tahap pencarian:

Procedure HorspoolSearch (

input m, n : integer,

input P : array[0 . . m-1] of char,

input T : array[0 . . n-1] of char,

output find : array[0 . . m-1] of boolean

)

Deklarasi:

j : integer

BmBc : array[0 . . n] of integer

c : char

Algoritma:

preBmBc(P, m, BmBc)

j := 0

while (j <= n – m) do

c = T[j + m – 1];

if (P[m – 1] == c && memcmp(P, T + j, m-1) == 0) then

find[j] := true;

endif

j := j + BmBc[c];

endwhile

sumber : 
http://repository.usu.ac.id/