Program Sapu Tangan

#include<iostream.h> main() {long int a,b,c,d,e,f; cout<<"Masukkan banyaknya saputangan ";cin>>a; b=a/...

Senin, 29 Juni 2015

Organisasi Berkas: Hashing

Soal
ð  Gunakanlah asumsi-asumsi yang tepat untuk menjawab pertanyaan-pertanyaan berikut :
#
Kode
Nama
Status
Sks
Smt
1
IPBU 11101
Pancasila
W
2
1
2
IPBU 11102
Agama
W
2
1
3
TIFS 11103
Database
W
2
1
4
TIFS 21202
Delphi
W
2
2
5
TIFS 21201
Foxpro
W
2
2
6
TIFS 22105
Pascal
w
2
2

ð  Disimpan dengan metode
1.      K MOD N
2.      K MOD P
3.      Midsquaring
4.      Penjumlahan Digit
5.      Multiplication
6.      Trunction
7.      Folding
8.      Konversi Radix
ð  Ditanyakan :
a.       Penempatan nilai-nilai kunci
b.      Rata-rata akses
Penyelesaian
ð  Asumsi yang digunakan pada kasus kode mata kuliah yang dijadikan kunci untuk penempatan penyimpanan di dalam memori yaitu :
1.      Kode mata kuliah berjumlah 9 buah dengan 4 buah berbentuk huruf dan 5 buah berbentuk angka
2.      4 buah yang berbentuk huruf menandakan jenis mata kuliah yang dikategorikan kedalam kategori tertentu
3.      Maka dari itu diasumsikan bahwa 4 buah huruf tersebut dikonversikan kedalam suatu angka tertentu dimana itu sebagai patokan dalam penghitungan untuk penempatan penyimpanan didalam memori
4.      Yaitu “IPBU”, diganti dengan angka “1” dan “TIFS” diganti dengan angka “2” dan jika ada kode lain maka menyesuaikan urutannya
5.      Sehingga dalam perhitungan nanti menjadi 6 digit dengan asumsi digit pertama yang paling kiri adalah pengganti kode mata kuliah yang berbentuk huruf, yang digunakan untuk memudahkan dalam proses penghitungan.
6.      Sehingga kuncinya menjadi :
#
Kode
Nama
Status
Sks
Smt
1
1 11101
Pancasila
W
2
1
2
1 11102
Agama
W
2
1
3
2 11103
Database
W
2
1
4
2 21202
Delphi
W
2
2
5
2 21201
Foxpro
W
2
2
6
2 22105
Pascal
W
2
2


a.       K MOD N
Kunci : 111101, 111102, 211103, 221202, 221201, 222105
N : 6
P : 7
Alamat indeks : 0-6
H(111101) è 111101 MOD 6 = 5 
H(111102) è 111102 MOD 6 = 0
H(211103) è 211103 MOD 6 = 5
ð  Collision, ditempatkan pada indeks terbesar yang masih kosong
ð  6 masih kosong, sehingga H(211103) è 6
ð  Home addres 5 diberi link ke 6
H(221202) è 221202 MOD 6 = 0
ð  Collision, ditempatkan pada indeks terbesar yang masih kosong
ð  4 masih kosong, sehingga H(221202) è 4
ð  Home address 0 diberi link ke 4
H(221201) è 221201 MOD 6 = 5
ð  Collision, ditempatkan pada indeks terbesar yang masih kosong
ð  3 masih kosong, sehingga H(221201) è 3
ð  Home address terahir 6 diberi link ke 3
H(222105) è 222105 MOD 6 = 3
ð  Coliision, ditempatkan pada indeks terbesar yang masih kosong
ð  2 masih kosong, sehingga H(222105) è 2
ð  Home address 3 diberi link ke 2

Pada K MOD N terdapat alamat kunci yang sama, sehingga diselesaikan dengan Collision agar tidak terjadi alamat kunci indeks yang sama, sehingga :

Record
Kunci
Link
0
111102
4
1


2
222105

3
221201
2
4
221202

5
111101
6
6
211103
3

Rata-rata akses = (6+2+3+4)/6 = 2.5
Ket :
ð  6 langkah penempatan kunci pada home address
ð  2 langkah penempatan kunci 211103, 221202 (collision)
ð  3 langkah penempatan kunci 221201 (collision)
ð  4 langkah penempatan kunci 222105 (collision)

b.      K MOD P
ð  H(K) = K MOD M
ð  Alamat indeks = 0 s/d M-1
Jawab :
Kunci = 111101, 111102, 211103, 221202, 221201, 222105
Pada kasus ini, saya hanya menyediakan lebar alamat indeksnya 2 digit, sehingga M=97
Alamat indeks= 0 – 96
H(111101) è 111101 MOD 97 = 36
H(111102) è 111102 MOD 97 = 37
H(211103) è 211103 MOD 97 = 31
H(221202) è 221202 MOD 97 = 42
H(221201) è 221201 MOD 97 = 41
H(222105) è 222105 MOD 97 = 72
Penempatan nilai-nilai kunci :
Record
Kunci
0
…
…
…
31
211103
…
…
36
111101
37
111102
…
…
41
221201
42
221202
…
…
72
222105
…
…
…
…
96

Rata –rata akses = 6/97 = 0.61
ð  H(K) = K MOD M+1
M=97
Alamat indeks = 1 – 97
H(111101) è 111101 MOD 97 + 1 = 37
H(111102) è 111102 MOD 97 + 1 = 38
H(211103) è 211103 MOD 97 + 1 = 32
H(221202) è 221202 MOD 97 + 1 = 43
H(221201) è 221201 MOD 97 + 1 = 42
H(222105) è 222105 MOD 97 + 1 = 73
Penempatan nilai-nilai kunci :
Record
Kunci
1
…
…
…
32
211103
…
…
37
111101
38
111102
…
…
42
221201
43
221202
…
…
73
222105
…
…
…
…
97


Rata –rata akses = 6/97 = 0.61
c.       Midsquaring
Kunci = 111101, 111102, 211103, 221202, 221201, 222105
Pada kasus ini, saya hanya menyediakan lebar alamat indeksnya 2 digit
K
K^2
H(K)
111101
12343432201
34
111102
12343654404
36
211103
44564476609
44
221202
48930324804
03
221201
48929882401
98
222105
49330631025
06
Penempatan kunci
Record
Kunci
0
…
…
…
03
221202
…
…
06
222105
…
…
34
111101

…
36
111102
…
…
44
211103
…
…
98
221201
99
…
Rata rata akses = 6/100 = 0.06
d.      Penjumlahan Digit
Kunci = 111101, 111102, 211103, 221202, 221201, 222105
Pada kasus ini, saya hanya menyediakan lebar alamat indeksnya 2 digit sehingga alamat indeks dari 0-99

H(111101) è 11 + 11 + 01 = 23
H(111102) è 11 + 11 + 02 = 24
H(211103) è 21 + 11 + 03 = 35
H(221202) è 22 + 12 + 02 = 36
H(221201) è 22 + 12 + 01 = 35
ð  Collision, ditempatkan pada indeks terbesar yang masih kosong
ð  99 masih kosong, sehingga H(221201) è 99
ð  Home address 35 diberi link ke 99
H(222105) è 22 + 21 + 05 = 48

Record
Kunci
Link
0
…

…
…

23
111101

24
111102

…
…

35
211103
99
36
221202

…
…

…
…

48
222105

…
…

…
…

…
…

99
221201

Rata-rata akses = (6+1)/100=0.07
Ket=
6 è langkah penempatan setiap kunci pada home address
1 è langkah penempatan kunci 221201 (collision)

e.       Multiplication
Kunci = 111101, 111102, 211103, 221202, 221201, 222105
Pada kasus ini, saya hanya menyediakan lebar alamat indeksnya 2 digit sehingga alamat indeks dari 0-99
H(111101)       è11 | 11 | 01
                        è 11 * 01
                        è 11
H(111102)       è 11 | 11 | 02
                        è 11 * 02
                        è 22
H(211103)       è 21 | 11 | 03
                        è 21 * 03
                        è 63
H(221202)       è 22 | 12 | 02
                        è 22 * 02
                        è 44
H(221201)       è 22 | 12 | 01
                        è 22 * 01
                        è 22
ð  Collision, ditempatkan pada indeks terbesar yang masih kosong
ð  99 masih kosong, sehingga H(221201) è 99
ð  Home address 22 diberi link ke 99
H(222105)       è 22 | 21 | 05
                        è 22 * 05
                        è 110
                        è 11
ð  Collision, ditempatkan pada indeks terbesar yang masih kosong
ð  99 masih kosong, sehingga H(222105) è 98
ð  Home address 11 diberi link ke 98

Record
Kunci
Link
0
…

…
…

11
111101
98
…
…

22
111102
99
…
…

…
…

44
221202

…
…

…
…

63
211103

…
…

98
222105

99
221201

Rata-rata akses = (6+2)/100=0.08
Ket=
6 è langkah penempatan setiap kunci pada home address
2è langkah penempatan kunci 221201,222105 (collision)

f.       Trunction
Kunci = 111101, 111102, 211103, 221202, 221201, 222105
Pada kasus ini, saya hanya menyediakan lebar alamat indeksnya 3 digit sehingga alamat indeks dari 0-999
Pemotongan pada 3 digit terahir
K
Pemotongan
H(K)
111101
111101
101
111102
111102
102
211103
211103
103
221202
221202
202
221201
221201
201
222105
222105
105


Record
Kunci
0
…
…
…
101
111101
102
111102
103
211103
…
…
105
222105
…
…
201
221201
202
221202
…
…
…
…
…
…
999
…
Rata-rata akses = 6/1000=0.006

g.       Folding
ð  Folding by boundary (non carry)
Kunci = 111101, 111102, 211103, 221202, 221201, 222105
Pada kasus ini, saya hanya menyediakan lebar alamat indeksnya 2 digit sehingga alamat indeks dari 0-99
H(111101) è 11 | 11 | 01
                  è 11 + 11 +10
                  è32
H(111102) è 11 | 11 | 02
                  è 11 + 11 +20
                  è 42
H(211103) è 21 | 11 | 03
                  è 12 + 11 + 30
                  è 53
H(221202) è 22 | 12 | 02
                  è 22 + 12 + 20
                  è 54
H(221201) è 22 | 12 | 01
                  è 22 + 12+ 10
                  è 44
H(222105) è 22 | 21 | 05
                        è 22 + 21 + 50
                        è 93
Record
Kunci
0
…
…
…
32
111101
…
…
42
111102
…
…
44
221201
…
…
53
211103
54
221202
…
…
93
222105
…
…
99
…
Rata-rata akses = 6/100=0.06

ð  Folding by boundary (carry)
Kunci = 111101, 111102, 211103, 221202, 221201, 222105
Pada kasus ini, saya hanya menyediakan lebar alamat indeksnya 2 digit sehingga alamat indeks dari 0-99
H(111101) è 11 | 11 | 01
                  è 11 + 11 + 10
                  è 32
H(111102) è 11 | 11 | 02
                  è 11 + 11 + 20
                  è 42
H(211103) è 21 | 11 | 03
                  è 12 + 11 + 30
                  è 53
H(221202) è 22 | 12 | 02
                  è 22 + 12 + 20
                  è 54
H(221201) è 22 | 12 | 01
                  è 22 + 12 + 10
                  è 44
H(222105) è 22 | 21 | 05
                        è 22 + 21 + 50
                        è 93
Record
Kunci
0
…
…
…
32
111101
…
…
42
111102
…
…
44
221201
…
…
53
211103
54
221202
…
…
93
222105
…
…
99
…
Rata-rata akses = 6/100=0.06

ð  Folding by shifting (non-carry)
Kunci = 111101, 111102, 211103, 221202, 221201, 222105
Pada kasus ini, saya hanya menyediakan lebar alamat indeksnya 2 digit sehingga alamat indeks dari 0-99
H(111101) è 11 | 11 | 01
                  è 11 + 11 + 01
                  è23
H(111102) è 11 | 11 | 02
                  è 11 + 11 + 02
                  è 24
H(211103) è 21 | 11 | 03
                  è 21 + 11 + 03
                  è 35
H(221202) è 22 | 12 | 02
                  è 22 + 12 + 02
                  è 36
H(221201) è 22 | 12 | 01
                  è 22 + 12 + 01
                  è 35
ð  Collision, ditempatkan pada indeks terbesar yang masih kosong
ð  99 masih kosong, sehingga H(221201) è 99
ð  Home address 35 diberi link ke 99
H(222105) è 22 | 21 | 05
                        è 22 + 21 + 05
                        è 48
Record
Kunci
Link
0
…

…
…

23
111101

24
111102

…
…

…
…

35
211103
99
36
221202

…
…

48
222105

…
…

…
…

…
…

99
221201

Rata-rata akses = (6+1)/100=0.07
Ket=
6 è langkah penempatan setiap kunci pada home address
1 è langkah penempatan kunci 221201 (collision)

ð  Folding by shifting (carry)
Kunci = 111101, 111102, 211103, 221202, 221201, 222105
Pada kasus ini, saya hanya menyediakan lebar alamat indeksnya 2 digit sehingga alamat indeks dari 0-99
H(111101) è 11 | 11 | 01
                  è 11 + 11 + 01
                  è 23
H(111102) è 11 | 11 | 02
                  è 11 + 11 + 02
                  è 24
H(211103) è 21 | 11 | 03
                  è 21 + 11 + 03
                  è 35
H(221202) è 22 | 12 | 02
                  è 22 + 12 + 02
                  è 36
H(221201) è 22 | 12 | 01
                  è 22 + 12 + 01
                  è 35
ð  Collision, ditempatkan pada indeks terbesar yang masih kosong
ð  99 masih kosong, sehingga H(221201) è 99
ð  Home address 35 diberi link ke 99
H(222105) è 22 | 21 | 05
                        è 22 + 21 + 05
                        è 48
Record
Kunci
Link
0
…

…
…

23
111101

24
111102

…
…

…
…

35
211103
99
36
221202

…
…

48
222105

…
…

…
…

…
…

99
221201

Rata-rata akses = (6+1)/100=0.07
Ket=
6 è langkah penempatan setiap kunci pada home address
1        è langkah penempatan kunci 221201 (collision)

h.      Konversi Radix
Kunci = 111101, 111102, 211103, 221202, 221201, 222105
Pada kasus ini, saya hanya menyediakan lebar alamat indeksnya 7 digit sehingga alamat indeks dari 0-9999999
H(111101) è1 * 155 + 1 * 154 + 1 * 153 + 1 * 152 + 0* 151 + 1* 150
                                    è813601
H(111102) è 1 * 155 + 1 * 154 + 1 * 153 + 1 * 152 + 0* 151 + 2* 150
                                    è813602
H(211103) è2 * 155 + 1 * 154 + 1 * 153 + 1 * 152 + 0* 151 + 3* 150
                                    è1572978
H(221202) è2 * 155 + 2 * 154 + 1 * 153 + 2 * 152 + 0* 151 + 2* 150
                                    è1623827
H(221201) è2 * 155 + 2 * 154 + 1 * 153 + 2 * 152 + 0* 151 + 1* 150
                                    è1623826
H(222105) è2 * 155 + 2 * 154 + 2 * 153 + 1 * 152 + 0* 151 + 5* 150
                                    è1626980
Record
Kunci
0
…
…
…
813601
111101
813602
111102
…
…
1572978
211103
…
…
1623826
221201
1623827
221202
…
…
1626980
222105
…
…
…
…
9999999


Rata –rata akses = 6/10000000=0.0000006


di Tidak ada komentar:
Langganan: Komentar (Atom)