Senin, 07 November 2011

7.) Representasi Data


Data Struktur                     :           Intoduction
Struktur dapat diartikan sebagai suatu susunan, bentuk, pola atau bangunan.
Data dapat diartikan sebagai suatu fakta, segala sesuatu yang dapat disimbolkan dengan kode-kode yang telah disediakan disetiap komputer.
Type data terdiri dari :
·         Data Tunggal   :  Integer, Real, Boolean, dan Karakter.
·         Data Majemuk :  String

Struktur data meliputi  :
·         Struktur data sederhana : Array dan Record
·         Struktur data majemuk   :
1.      Linier               :           Stack, Queue, Linier Link List
2.      Nonlinier         :           Tree, Binari Tree, Binary Search Tree, Graph.

Hal yang terpenting dalam mempelajari struktur data adalah erat kaitannya dengan pemilihan struktur data yan tepat membuat suatu algoritma yang digunakan untuk memecahkan suatu masalah menjadi efisien, yang akan membantu logika kita dalam membuat program yang rumit, sehingga operasi-operasi penting dapat dieksekusi dengan sumber daya yang lebih kecil, memori lebih kecil, dan waktu eksekusi yang lebih cepat dan outputnya sesuai dengan yang diharapkan.

Gambar dibawah ini menjelaskan posisi algoritma dan struktur data dalam membuat program.


Algoritma adalah suatu strategi yang mengandalkan kemampuan berpikir secara logis untuk memecahkan suatu masalah.

Type Data
Disetiap bahasa pemrograman, disediakan berbagai jenis tipe data. Penentuan tipe data yang tepat akan menjadikan sebuah program dapat dieksekusi secara efektif.
Jenis-jenis Data :

1.      Integer yaitu data numerik yang tidak mengandung pecahan, dan disajikan dalam memori komputer sebagai angka bulat. Mengacu pada obyek data dengan range
 -32768 s/d 32767.
Operasi yang dapat dilaksanakan :
·         Penambahan           ( + )
·         Pengurangan           ( - )
·         Perkalian                  ( * )
·         Pembagian Integer ( / )
·         Pemangkatan           ( ^ )
                                                                                

Operasi itu disebut operasi Binar atau aritmatic operator yaitu operasi yang bekerja terhadap 2 Integer (operand). Sedangkan operator yang mempunyai satu operand disebut Unar (Negasi = Not). Selain itu ada juga operasi tambahan yang disediakan oleh bahasa pemrograman tertentu, yaitu :
·         MOD   :   sisa hasil pembagian bilangan
·         DIV       :  hasil pembagi bilangan
·         ABS      :  mempositifkan bilangan negative
·         SQR     :  menghitung nilai akar dari bilangan

Penuisan didalam bahasa pemrograman Pascal : var a : integer

2.      Real

Data numerik yang mengandung pecahan digolongkan dalam jenis data Real ( floating point ). Operasi yang berlaku pada bilangan integer juga berlaku pada bilangan real. Selain itu ada operasi lainnya seperti :

INT   :  Membulatkan bilangan real, missal INT (34.67) = 34

3.      Boolean

Type ini dikenal pula sebagai “Logical Data Types”, digunakan untuk melakukan pengecekan suatu kondisi dalam suatu program. Elemen datanya hanya ada 2 yaitu True and False, biasanya dinyatakan pada sebagai 1 dan 0
Operatornya terdiri dari   :   AND, OR, NOT
                                                    Binar       Unar
Dalam urutan operasi Not mendapat prioritas pertama. Kemudian baru AND dan OR kecuali bila diberi tanda kurung.
Masih ingatkah anda dengan table logika?
Nilai True dan False dapat juga dihasilkan oleh operator Relational.
Operator tersebut : <, >, <=, >=, =, <>, =
Ex.    6  <  12   :  True
          A  <>  A  :  False
Contoh lainnya :




Logika
Dalam logika matematika, setiap pertanyaan atau kombinasi beberapa pernyataan memiliki nilai TRUE (benar) atau FALSE (salah). Kombinasi pernyataan dapat disusun dalam operasi-operasi logika, dengan operasi-operasi dasar sebagai berikut :
1.      Negasi (NOT), menghasilkan kebalikan nilai kebenaran dari suatu pernyataan.






2.      Disjungsi (OR), merupakan operasi dimana jika salah satu pernyataan bernilai benar, maka kombinasinya akan bernilai benar.
     








3.      Konjungsi (AND), merupakan operasi dimana jika salah satu pernyataan bernilai salah, maka kombinasinya akan salah.
           
      













4.      Karakter dan string

            Type Karakter mempunyai elemen sebagai berikut :
            (0,1,2,3,……,9,A,B,C,……X,Y,Z,?,*,/,…….)
            Data type majemuk yang dibentuk dari karakter disebut STRING.
            Suatu string adalah barisan hingga symbol yang diambil dari himpunan karakter yang
            digunakan untuk membentuk string dinamakan Alfabet.
            Contoh      :      Himpunan string (A.A.1) dapat berisi antara lain :
                                    (AB1), (A1B),(1AB),…..dst.
Secara umum suatu string S dinyatakan :
            S : a1, a2, a3, …. an.
Panjang dari string dilambangkan    I   S   I =N atau Length (S) = N dimana N adalah banyaknya karakter ppembentuk string.
Untuk string Null   l  l   =  0. Untuk blank (spasi)=1.


Operasi yang berlaku terhadap string

a.      Length(S)  Berfungsi untuk menghitung panjang suatu string.
            Contoh : S1adalah string = a1.a2.a3….an
                           S2 adalah string =b1.b2.b3….bk
                           Len(s2) = n  .   Len(s1) = k

b.      Concat (S1, S2)  yaitu concatenation (Penyambungan 2 buah string atau lebih. Penggabungan juga dapat dilakukan terhadap dirinya sendiri.
Contoh : Concat(s1,s2) = a1. . . . .an . b1 . . . . .bk
Atau dalam bentuk lain : a1 // s2, s1 + s2
c.       Substr(s,I,J) yaitu operasi pengambilan beberapa karakter dan string untuk membentuk string yang baru.
S  : adalah string
I   : adalah posisi karakter awal yang diambil
J   : adalah banyaknya karakter yang diambil
       Dimana I dan J bertype integer.
S1(a1,a2,a3,. . . . .an)
SUBSTR (s,3,2) = a3, a4  : s1 (a3,a4)
selain itu terdapat operasi pemenggalan lainnya yaitu :
RIGHT (s1,j) dan LEFT (s1, j)
        d.    Insert (s1,s2,j)

Operasi ini membutuhkan dua operand string dan sebuah operand integer.
Contoh : Insert (s1,s2,3) = a1,a2.b1,b2, . . . . bk,a3, . . . . an
                Menyisipkan s2 didalam s1 mulai posisi ke 3 dari s1.
Bila tidak ada statemen INSERT dalam bahasa pemrograman maka dapat dilakukan dengan cara lain, missal : LEFT (s1,j) // s2 // Right (s1,j)
        e.    Delete (s,i,j)

Operasi ini membutuhakan sebuah string dan dua operand integer.
Contoh : s1 : a1,a2,a3,. . . .an.
DELETE (s1,4,3) =  a1,a2,a3,a7,a8 . . . . an.
                Menghapus string pada posisi awal 4, sebanyak 3.
Bila tidak ada statemen DELETE dalam bahasa pemrograman maka dapat dilakukan dengan cara lain, missal :
LEFT (s1,j) // RIGHT (s1,j)
         f.    Index (s1,'substring')
Mencari posisi awal (karakter ke berapa) suatu substring pada suatu string.
Contoh : INDEX(s1,a3,a4,5) = 3
 
Dalam bahasa Pemrograman untuk membedakan sebuah string atau integer menggunakan tanda kutip. Integer : 34                  String : ‘34”.



Pemetaan (MAPPING) Type Data ke Storage

Komputermempresentasikan data dalambentukbiner, karenasetiap bit data dalamkomputerhanyadapatmenyimpanduamacam keada8an, yaituvoltasetinggidanvoltaserendah. Perbedaanvoltasetersebutmewakilinili TRUE dan FALSE atau bit ‘1’ dan ‘0’

RepresentasiKarakterdan String

Ada beberapaaturan yang digunakanuntukmenyatakankarakterdalam storage.Diantaranyaadalah :
1.      EBCDIC (Extended Binary Coded Decimal Interchange Code)
EBICDIC adalahsuatusistempeng-kode-an (mapping) yang menggunakan 8 binary digital (bit) untukmenyatakansuatukarakterdalam alphabet.
(1 karakter = 8)
Dalam 8 bit terdapat (256) kemungkinankarakter yang dapatdibentuk.
2.      ASCII (American Standard Code For Information Interchange)
ASCII adalahcarapeng-kode-an yang menggunakan 7 bit untukmenyatakansuatukarakterdalam alphabet
(1 karakter = 7 bit). Dalam 7 bit terdapat(128) kemungkinankarakter yang dapatdibentuk, separuhdari yang dimiliki EBCDIC.
3.      BCD (Binary Coded Decimal)
BCD inimenggunakan 4 bit untuksetiapkarkternya.
4.      PACKED DECIMAL
Packed Decimal umumnyadigunakanuntukkarakterberjenis data numeric dengancarapenyimpanannyamenggunakan 2 digit setiap 8 bit. Pada 8 bit terakhirdisimpanselain digit derajatterendah, jugatandadaribilangantersebut (positifataunegatif).

Berikutiniperbandingankode EBCDIC, ASCII, dan PACKED-DECIMAL untukmenyatakan +903.
                                                9          0            3                    +
EBCDIC                                  : 11111001 11110000 11110011 01001110
ASCII                          :   0111001   0110000   0110011    0101011
PACKED DECIMAL   : 10010000 00111100

5.      Unicode
Unicode menggunakan 16 bit untukmempresentasikankarkter. Dengandemikian, banyaknyakarakter yang dapatdipresentasikanadalah 216 atau 65.536 karakter.
6.      Keunggulan Unicode dari ASCII adalahkemampuannyauntukmenyimpansimbol / karakter yang jauhlebihbesar. Himpunan 256 karakterpertamadari Unicode merupakanpemetaankarakter ASCII 8 bit, sehingga Unicode tetapkompatibeldengan ASCII. Selainmempresentasikanseluruhkarakter ASCII, Unicode dapatmempresentasikanjugaberbagaimacamsimboldiluar ASCII, sepertihuruf Arab, Kanji, Hiragana, Katakana, dan lain-lain






RepresentasiBilanganBulat / Integer

BilanganBulatTakBertandadapatdipresentasikandengan
·         Bilanganbiner – octal – heksadesimal
·         Gray code
·         BCD (binary coded decimal)

BilanganbulatBertanda(positifataunegatif) dapatdipresentasikandengan
·         Sign/Magnitude (S/M)
·         1’s complement
·         2’s complement

Untukbilanganbulatpositif, tidakadaperbedaandalamketigamacamrepresentasibilangandiatas.Terdapatpersamaandalamketigarepresentasitersebutberupadigunakannya MSB (most significant bit)sebagaipenanda.MSB bernilai ‘0’ untukbilanganpositifdan ‘1’ untukbilangannegatif.









      7                     6                    5                   4                    3                    2                     1                         0
MSB                                                                                                                                             LSB


*      SIGN / MAGNITUDE

Salah satu storage mapping yang dapatdilakukanterhadap integer adalahapa yang disebutbentuksign-and-magnitude, yaitu digit untuktanda integer positifatau negative dansebarisan digit untukmenyatakan magnitude / besarnya.
Contoh :           -7 = -111 dan +7 = +111

Bagikitamudahbekerjaterhadapbilangandalambentuk sign-and-magnitude, namunapabiladilakukanpenjumlahandengankedua operand berbedatanda, penjumkahanakanberalihmenjadipengurangan yang kadang-kadangmenimbulkankesukaran. Untukitudigunakanapa yang disebutsebagaiCOMPLEMENT (merubahtandanegatifpadabilanganpenguranganmenjaditandapositif)

X’ adalah complement dari X terhadap R ( R’s complement dari X ) bila X + X’ = R
            X’ = R – X menyatakan integer negatif –X

Representasinegatifdarisuatubilangandiperolehdaribentukpositifnyadenganmengubah bit pada MSB menjadibernilai 1. Jikadipergunakan N bit untukrepresentasi data, makarentangnilai yang dapatdipresentasikanadalah
-1  s.d-1

Contoh :jikadipergunakan 5 bit untukrepresentasibilangan
+3 = 00011
-3 = 10011

TerdapatduajemisComplement :



*      ONE’S COMPLEMENT

Representasinegatifdarisuatubilangandiperolehdenganmengkomplmenkanseluruh bit darinilaipositifnya. Jikadipergunakan N bit untukrepresentasi data, makarentangnilai yang dapatdirepresentasikanadalah-1  s.d-1

1’s complement menggunakan mapping denganR = -1
N adalahjumlah bit integer yang dapatdisajikan

Contoh :jikadipergunakan 5 bit untukrepresentasibilangan
+3 = 00011
-3 = 10011


*      TWO’S COMPLEMENT
Representasinegatifdarisuatubilangandiperolehdenganmengurangkan 2n dengannilaipositifnya.Jikadipergunakan N bit untukrepresentasi data, makarentangnilai yang dapatdirepresentasikanadalah-1  s.d-1
Two’s Complement menggunakan mapping denganR =

Contoh :jikadipergunakan 5 bit untukrepresentasibilangan
 =  = 100000
+3 = 00011
-3 = 100000 – 00011
100000
00011  -

11101

→ -3 = 11101




















PERBANDINGAN
Berikuttabelperbandingaketigacarareprensentasibilanganbulatbertanda

B



b3b2b1
Sign/Magnitude
1’s complement
2’s complement
0111
+7
+7
+7
0110
+6
+6
+6
0101
+5
+5
+5
0100
+4
+4
+4
0011
+3
+3
+3
0010
+2
+2
+2
0001
+1
+1
+1
0000
+0
+0
+0
1000
-0
-7
-8
1001
-1
-6
-7
1010
-2
-5
-6
1011
-3
-4
-5
1100
-4
-3
-4
1101
-5
-2
-3
1110
-6
-1
-2
1111
-7
-0
-1





















RepresentasiBilanganPecahan / Floating Point

Bilanganpecahandapat di representasikandalambentukpecahanbiasaataudalambentikscientific

o   BentukPecahanBiasa

Dalambentukpecahanbiasa, bilangandirepresentasikanlangsungkedalambentukbinernya.
Contoh : 27.625 = 11011.1012

o   Bentuk S C I E N T I F I C

Dalamnotasi scientific, bilanganpecahandinyatakansebagai x - ±M .
M = mantissa
B = basis
E = eksponen
Contoh : 5.700.000 = 57.105 → M = 57, B = 10, E =5

Masalah :terdapattakberhinggabanyaknyarepresentasi yang dapatdibuat. Dalamcontohsebelumnya 5.700.000 = 57.10=570.104 = 5,7. 106 = 0,57.107= 0,057.108 dst. Untukmengatasinya, ditentukanadanyabentuknorma, dengansyarat

1/B =│M│< 1

Dengandemikian, bentuk scientific yang normal (memenuhipesyaratan) dari 5.700.000 adalah 0,57.107

Dalambentuk  normaltersebut, selaludiperoleh mantissa berbentuk 0, sehinggadalamrepresentasinyakedalam bit data, fraksi ‘0’ tersebutdapatdihilangkan

Mantissa daneksponentersebutdapatdirepresentasikanmenggunakansalahsatucararepresentasibilanganbulatbertanda yang telahdibahasdiatas. Representasi yang dipilihdapatsajaberbedaantara mantissa denganeksponennya.

Contoh :
o   Digunakanuntaian 16 bit untukrepresentasibilanganpecahan
o   10 bit pertamadigunakanuntukmenyimpan mantissa dalambentuk S/M
o   6 bit sisanyadigunakanuntukmenyimpan mantissa dalambentuk 1’s complement

Contohakandirepresentasikanbilangan 0,00000075
















15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0

Mantissa
Eksponen

0,00000075 = 0,75 . 10-6 → M = 0,75 ; E = -6

RepresentasiMantissa :
0,75 = 0,112. Karenasudahdalambentuk normal ‘0’ dapatdihilangkan
S/M → MSB sebagaipenanda.Dengandemikian, mantissa = 0110000000


RepresentasiEksponen :
6 = 1102. Karenadigunakan 6 bit. 1102 = 000110
1’s complement → -6 = 111001

Representasi :

0
1
1
0
0
0
0
0
0
0
1
1
1
0
0
1
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0














Tidak ada komentar:

Poskan Komentar