graph(graf)

graf dalam komputer sains (ilmu komputer) adalah sebuah tipe data abstrak. Graf terdiri dari titik-titik (nodes) yang terhubung dengan sisi/busur (edge/arcs).

Graf sebenarnya bisa diubah ke dalam bentuk matriks dan ditulis dalam bentuk array dua dimensi ke dalam kode. Namun, karena contoh yang saya temukan menggunakan dictionary, maka graf di atas bisa dituliskan seperti berikut ini.

graf = {'A': ['B', 'C'],
        'B': ['C', 'D'],
        'C': ['D'],
        'D': ['C'],
        'E': ['F'],
        'F': ['C']}

Pada kode di atas, kita menggunakan dictionary untuk membuat graf dan menggunakan list untuk menyimpan titik yang menjadi tetangga sebuah titik. Misalkan titik A, terbuhung dengan titik B dan C. Titik B terhubung dengan titik C dan D, dan seterusnya.

Fungsi untuk Menentukan Jalur

Fungsi ini akan menemukan sebuah jalur (path) dari titik awal hingga titik akhir atau tujuan.

def temukan_jalur(graf, awal, akhir, jalur=[]):
    jalur = jalur + [awal]
    if awal == akhir:
        return jalur
    if not graf.has_key(awal):
        return None
    for titik in graf[awal]:
        if titik not in jalur:
            jalur_baru = temukan_jalur(graf, titik, akhir, jalur)
            if jalur_baru: return jalur_baru
    return None

Misalkan kita ingin mencari jalur dari titik A ke titik D, maka kita bisa menggunakan fungsi tersebut.

>>> temukan_jalur(graf, 'A', 'D')
['A', 'B', 'C', 'D']

Fungsi untuk Menentukan Semua Jalur

Pada fungsi di atas, kita hanya diberikan satu jalur saja. Sedangkan fungsi berikut ini akan mengembalikan semua jalur yang bisa dilalui dari titik awal hingga akhir.

def temukan_semua_jalur(graf, awal, akhir, jalur=[]):
    jalur = jalur + [awal]
    if awal == akhir:
        return [jalur]
    if not graf.has_key(awal):
        return []
    semua_jalur = []
    for titik in graf[awal]:
        if titik not in jalur:
            jalur_jalur = temukan_semua_jalur(graf, titik, akhir, jalur)
            for jalur_baru in jalur_jalur:
                semua_jalur.append(jalur_baru)
    return semua_jalur

Misalkan kita ingin mencari semua jalur yang mungkin bisa dilalui dari titik A ke titik D, maka fungsi tersebut akan mengembalikan semua jalur dalam bentuk list.

>>> temukan_semua_jalur 

(graf, 'A', 'D')
[['A', 'B', 'C', 'D'], ['A', 'B', 'D'], ['A', 'C', 'D']]

Pada hasil eksekusi fungsi tersebut, kita diberikan tiga buah jalur yang bisa dilalui dari titik A menuju titik D.

Kesimpulan

Representasi graf ke dalam kode python dapat dilakukan dengan dictionary dan list. Semua titik dalam graf dijadikan kunci (key) dalam dictionary. Kemudian menyimpan titik tetangganya dalam list.

Tree

TREE

Ordered List yaitu metode penyimpanan data atau mengumpulkan data lalu diurutkan secara ascending atau descending. Ordered list menggunakan class yang bernama node, yang terdiri dari data sekarang dan data selanjutnya. Awal data pada Ordered list disebut Head sedangkan data akhir disebut tail. Data yang baru diambil dan diinputkan ditaruh disebelah kanan head.

Berikut ini program python dari Tree Search :

class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

    def insertLeft(self,newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)

        else:
            t = BinaryTree(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t


    def insertRight(self,newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)

        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t




    def getRightChild(self):
        return self.rightChild

    def getLeftChild(self):
        return self.leftChild

    def setRootVal(self,obj):
        self.key = obj

    def getRootVal(self):
        return self.key

    def show(self):

        current = self.key
        print (current)

        selfleft = self
        selfright = self
        while selfleft.getLeftChild() != None  and selfright.getRightChild() != None :

            print(selfleft.getLeftChild().getRootVal() )
            print(selfright.getRightChild().getRootVal() )

            selfleft = selfleft.getLeftChild()

        while selfright.getRightChild() != None :
            print(selfright.getRightChild().getRootVal() )

            selfright = selfright.getRightChild()
    def height(self):

        selfleft = self
        selfright = self
        count = 0
        while selfleft.getLeftChild() != None  or selfright.getRightChild() != None :

            count = count + 1
            if selfleft.getLeftChild() != None:
                selfleft = selfleft.getLeftChild()

            if selfright.getRightChild() != None:
                selfright = selfright.getRightChild()
        return count







r = BinaryTree('a')
print(r.getRootVal())

r.insertLeft('b')
r.insertRight('c')

print(r.getLeftChild().getRootVal())


print(r.getRightChild().getRootVal())
print(r.height())
 

Linear dan Binary Search

LINEAR DAN BINARY SEARCH

 Dalam algoritma pemrograman, ada banyak kasus di mana kita diharuskan mencari suatu value dalam kumpulan data. Misal dalam dunia nyata, kita memiliki 20 buah kelereng, kemudian kita cari kelereng mana yang memiliki tepat n buah di dalamnya.

Untuk melakukan sebuah pencarian, atau search, harus memiliki ketiga kriteria ini:

1. Teknik/algoritma search
2. Value/nilai yang dicari
3. Search space (ruang batas pencarian)

   Dalam contoh di atas, teknik pencarian bisa menggunakan linear search atau teknik lainnya. Value yang dicari adalah kelereng dengan n buah . Dan search space-nya adalah 20 buah kelereng yang kita miliki.

Dalam post ini hanya akan dibahas mengenai Linear Search dan Binary Search.

Linear Search

Linear search atau metode pencarian linear adalah teknik pencarian di mana program akan mencari anggota dari suatu search space satu per satu sampai value yang dicari ditemukan. Kompleksitas pencarian adalah O(n).

Linear search juga merupakan program search yang mudah dipahami, linear search memiliki kelebihan apabila data yang di cari letaknya pada data – data awal sehingga prosesnya berjalan cepat, namun apabila data yang di cari letaknya pada data terakhir maka pencarian lebih memakan waktu yang cukup lama pula.
#SEARCHING DARI KANAN KE KIRI(DARI LEN-1 KE 0)
search = 4
mylist = [1,2,3,4,5,6]
position = len(mylist)-1#first/awal
last = 0#akhir
found = False
while position >= last and not found:#lebih besar dari
    if mylist[position] == search:
        found = True
    else:
        position = position-1#DECREMENT
    if found:
        print("Found the search number =>",search)
        print("pada posisi ke -",position)
    else:
        print("Did not find the search number.")

 

 

Binary Search

Binary search adalah metode pencarian dalam suatu search space (atau lebih sering arrays) yang telah terurut isinya, baik terurut menaik maupun menurun. 

Binary search, bisa dilakukan jika data sudah terurut, dimana sistem pencariannya yang relatif cepat dan efisien walaupun ada banyak data sekalipun. Karena data dicari dari depan, tengah dan belakang. Tetapi sintaks dan algoritmanya sedikit lebih rumit, karena kita harus mengurutkan data terlebih dahulu. Pengurutan data disini bisa kalian lakukan dengan metode ascending ataupun descending.

Untuk dasar dari binary search ini, saya akan memberikan array dengan data yang telah diurut sebelumnya. Agar lebih mudah memahami dasar dari binary search ini. Adapun algoritma dari binary search ini adalah sebagai berikut :

1. Membaca data yang ada di array, jika data belum terurut, maka lakukan pengurutan data.
2. Menentukan data yang akan dicari di dalam array.
3. Menentukan nilai elemen tengah array, jika nilai elemen tengah array sama dengan data yang dicari, maka pencarian akan dihentikan, jika elemen tengah tidak sama dengan data yang dicari, maka:
• Jika nilai tengah lebih besar dari nilai yang dicari, maka pencarian hanya dilakukan pada setengah array pertama.

Jika nilai tengah lebih kecil dari nilai yang dicari, maka pencarian hanya dilakukan pada setengah array sisa. 

#BINARY SEARCH
search = 9
mylist = [3,1,9,7,5,6]
mylist.sort()
first= 0
last = len(mylist)-1

found = False
counter = 0

while first <= last and not found :
    middle = (first + last)//2

    if mylist[middle] == search:
       
        found = True
    else :
        if search < mylist[middle]:
            last = middle -1
        else:
            first = middle +1
           
        counter = counter +1
    if found:
        print (
            "Found the search number.")
        print("pada indeks ke-",middle)
    else:
        print("Did not find the search number.")

print(search)

Buble Sort dan Selection Sort

SORTING 1

Sorting dapat diartikan sebagai algoritma mengurutkan data, baik itu dari terendah ataupun tertinggi.  Yang secara tidak langsung akan menjadikan data lebih terstruktur, rapi dan teratur.

Ada banyak algoritma populer untuk mengurutkan data, seperti : insertion sort, selection sort, merge sort, quick sort, bubble sort, shell sort. Tapi pada artikel ini saya hanya menuliskan  algoritma untuk mengurutkan data dengan buble sort dan selection sort menggunakan bahasa pemrograman Python.

Bubble Sort

Bubble sort adalah metode sorting (pengurutan ) yang paling populer digunakan dan sederhana. Proses pengurutan ini dilakukan dengan membandingkan masing-masing  data dalam suatu list secara berpasangan, kemudian tukar data  jika diperlukan  dan mengulanginya sampai akhir list secara berurutan(data terurut), sehingga tidak ada lagi nilai yang dapat ditukar.

Langkahnya seperti di bawah ini :

1.      Bandingkan nilai pada data ke-1 dengan data ke-2.

2.      Jika nilai data ke-1 lebih besar dari data ke-2 maka tukar posisinya.

3.      Kemudian data yang lebih besar tersebut dibandingkan lagi dengan data ke-3.

4.      Jika data ke-3 lebih kecil dari data ke-2 maka tukar posisinya, dan begitu seterusnya sampai semua data yang ada jadi terurut.

Kode Program(Bubble Sort)

Selection Sort

Selection sort adalah metode pengurutan data dengan memilih elemen dengan nilai paling rendah dan menukar elemen tersebut dengan elemen ke-i. Nilai dari i dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.

Langkah-langkahnya:

1.      Pengecekan dimulai dari data ke-1 sampai dengan data ke n.

2.      Tentukan bilangan dengan index terkecil dari data bilangan tersebut.

3.      Tukar bilangan dengan index terkecil tersebut dengan bilangan pertama (i=1) dari data bilangan tersebut.

4.      Lakukanlah langkah 2 dan 3 untuk bilangan beikutnya (i=i+1) sampai didapatkan data yang sesuai.

Kode Programnya

Hashing

HASHING

Hashing adalah teknik atau metode memetakan data ke sebuah tempat dimana data sebenarnya dirubah dalam bentuk lain. semisal huruf a menjadi huruf e. Hashing juga merupakan teknik secara khusus digunakan untuk mengidentifikasi obyek tertentu dari sekumpulan obyek yang serupa.

Pada python, cara metode Hashing dengan membuat sebuah List yang akan diisi oleh data masukan. Data masukan diberi 2 buah nilai yaitu value sebagai data tersebut dan juga key sebagai alat untuk memasukan value ke List.

Algoritma Hashing sebagai berikut :
1. Membuat tabel hash yang berisikan None
2. Memasukan data yang ingin dimasukan 
3. Data masukan terdiri dari value dan keynya
4. Lakukan pencarian modulus dari key yang dibagi panjang tabel hash
5. Masukan value dari data tersebut ke dalam tabel hash sesuai indexnya

Kode Programnya:

table = [None] * 11

def hash(x):

  return x % 11

def insert(table,key,value):

  index = hash(key)

if table[index] == None:

    table[index] = value

  else :

    collusion=index

    found = False

    ind=collusion+1

    if ind>= len(table)-1:

        ind = 0

    while (ind<=len(table)-1) and not(found):

        if table[ind]== None:

            found=True

            table[ind]=value

            print(ind)

        ind=ind+1

print(table)

insert(table,54,54)

print(table)

insert(table,26,26)

print(table)

insert(table,93,93)

print(table)

insert(table,17,17)

print(table)

insert(table,77,77)

print(table)

insert(table,31,31)

print(table)

insert(table,44,44)

print(table)

insert(table,55,55)

print(table)

insert(table,20,20)

print(table)

insert(table,25,25)

print(table)

##

Linear probbing:[77, 44, 55, 20, 26, 93, 17, 25, None, 31, 54]

 ##dengan list=

54,26,93,17,77,31,44,55,20

  

Infix Prefix dan Postfix

INFIX,PREFIX DAN POSTFIX
A. Infix adalah notasi yang membentuk atas operator dengan operand,dimana operator berada diantara operand.
   Contoh :        
                 - A + B * C
                 - (A + B) * C
                 - A - (B + C) * D ^ E

B. Postfix adalah notasi yang membentuk atas operator dengan operand, dimana operator berada dibelakang operand.

   Contoh : A + B * C ( infix).

maka notasi postfix adalah ABC*+.

C. Prefix adalah cara penulisan atau ungkapan yang meletakan operator disebelah kiri 2 operand dan dalam kurung sangat menentukan posisi.

Contoh Prefix :

+ A B

* - A B C

 Algoritma:

Berikut ini algoritma dari konversi Infix ke Postfix:

1. Buat presisi atau kekuatan operator ( Penjumlahan dan Pengurangan bernilai 2 , Perkalian dan Pembagian bernilai 3 , Kurang buka dan tutup bernilai 1 )
2. Input data dalam bentuk infix
3. Pisahkan data infix menggunakan split menjadi bentuk List
4. Periksa semua data yang berada di dalam list secara urut mulai dari awal hingga akhir
5. Jika bertemu operand, maka masukan data ke PostfixList untuk dicetak
6. Jika bertemu kurung buka '(' maka masukan ke Stack Operator
7. Jika bertemu kurung tutup ')' maka Stack Operator yang paling atas dan bukan kurung buka '(' diambil untuk dicetak ke PostfixList
8. Jika bertemu operator maka jika Stack Operator tidak kosong dan kekuatan operator yang digunakan lebih kecil dari kekuatan operator yang berada di top Stack Operator maka operator yang berada di Stack Operator diambil (pop) untuk dicetak di PostfixList. lalu masukan operator yang digunakan ke dalam Stack Operator.
9. Begitu seterusnya sampai List yang berisi data Infix habis.
10. Jika Stack Operator masih ada isinya maka ambil dan tambahkan ke PostfixList untuk dicetak.
11. Cetak PostfixList

Berikut ini Algoritma dari konversi Infix ke Prefix:

1. Balikan data Infix
2. Jika operator kurung buka '(' maka ganti dengan kurung tutup ')' begitu sebaliknya
3. Masukan data tersebut ke konversi Infix ke Postfix 
4. Setelah keluar hasil, Balikan lagi hasil tersebut
5. Maka keluar bentuk Prefix

kode programnya:

class Stack:

     def __init__(self):

         self.items = []

     def isEmpty(self):

         return self.items == []

     def push(self, item):

         self.items.append(item)

     def pop(self):

         return self.items.pop()

     def peek(self):

         return self.items[len(self.items)-1]

     def size(self):

         return len(self.items)

def infixToPostfix(infixexpr):

    prec = {}

    prec["*"] = 3

    prec["/"] = 3

    prec["+"] = 2

    prec["-"] = 2

    prec["("] = 1

    opStack = Stack()

    postfixList = []

    tokenList = infixexpr.split()

    tokenList.reverse()

    for i in range(len(tokenList)):

         if tokenList[i] == '(':

              tokenList[i]=')'

         elif tokenList[i] == ')':

              tokenList[i]='('

    for token in tokenList:

        if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":

            postfixList.append(token)

        elif token == '(':

            opStack.push(token)

        elif token == ')':

            topToken = opStack.pop()

            while topToken != '(':

                postfixList.append(topToken)

                topToken = opStack.pop()

        else:

            while (not opStack.isEmpty()) and \

               (prec[opStack.peek()] >= prec[token]):

                  postfixList.append(opStack.pop())

            opStack.push(token)

    while not opStack.isEmpty():

        postfixList.append(opStack.pop())

    postfixList = postfixList[::-1]

    return " ".join(postfixList)

print(infixToPostfix("A * B + C * D"))

print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))

 
 Kode Program PostfixEval:

class Stack:

     def __init__(self):

         self.items = []

     def isEmpty(self):

         return self.items == []

     def push(self, item):

         self.items.append(item)

     def pop(self):

         return self.items.pop()

     def peek(self):

         return self.items[len(self.items)-1]

     def size(self):

         return len(self.items)

def postfixEval(postfixExpr):

    operandStack = Stack()

    tokenList = postfixExpr.split()

    for token in tokenList:

        if token in "0123456789":

            operandStack.push(int(token))

        else:

            operand2 = operandStack.pop()

            operand1 = operandStack.pop()

            result = doMath(token,operand1,operand2)

            operandStack.push(result)

    return operandStack.pop()

def doMath(op, op1, op2):

    if op == "*":

        return op1 * op2

    elif op == "/":

        return op1 / op2

    elif op == "+":

        return op1 + op2

    else:

        return op1 - op2

print(postfixEval('4 5 6 * +'))