Kuis Sitem Berkas

KUIS KE-2

SISTEM BERKAS

DISUSUN OLEH :

Daniel Oktavian Duha

(121051053 )

JURUSAN TEKNIK INFORMATIKA

INSTITUT SAINS & TEKNOLOGI AKPRIND

YOGYAKARTA

2015

1.    Diketahui :

berkas memuat 1.000.000 record

panjang setiap record 250 byte

IRG 0.50 Inchi

Data dencity 2.000 BPI

Laju Pita 10 inchi/detik

Ditanya:

a.    Dengan metode tanpa blocking hitunglah

Lama Waktu untuk mengakses 250.000 record

Jawab:

Lama akses = panjang pita/laju pita

Panjang pita= ∑record * (panjang 1 record +IRG)

Panjang pita=250.000*( 250byte/2000 bpi +0.50 inchi)

                   =250.000*(0,125+0,5)

                   =250.000*(0,625)

                   =156.250 inchi

Lama Akses=156.250 / 10

                   =15.625 detik

Jadi untuk mengakses 250.000 record membutuhkan waktu 15.625 detik

b.    Jumlah Record yang bisa dibaca dalam waktu 20 detik

Lama Akses=Panjang pita/laju pita

20 =panjang pita/10

Panjang pita= 20*10

Panjang pita=200 inchi

Panjang pita= ∑record * (panjang 1 record +IRG)

200           =∑record *( 250byte/2000 bpi +0.50 inchi)

200=∑record*(0,125+0,50)

200=∑record*(0,625)

∑record=200/0,625

∑record=320 record

Jadi jumlah record yang bisa dibaca dalam waktu 20 detik = 320 record

2.    Diketahui:

Nilai kunci : 2432, 2440, 2444, 2445, 2535, 2536, 2639, 2640, 2645, 2646

Ditanyakan :

Menemukan record 2536 dalam file menggunakan metode :

a.    Binary search

b.    Interpolation

Jawab :

a.    Binary search

Kunci 2536 akan ditelusuri dengan urutan langkah sebagai berikut:

Langkah ke -	BAWAH	ATAS	TENGAH	K[TENGAH]
1	1	10	5	2535
2	6	10	8	2640
3	6	9	7	2639
4	6	6	6	2536

Jadi kunci 2536 ditemukan

-                      Pada langkah ke-4

-                      Posisi record pada urutan ke-6

-                      Waktu pencarian 0Log10=1 detik

b.                  Interpolation

Algoritma :
- indeks posisi dimulai dari 0
- jika data[posisi] < data yang dicari, maka low=pos+1
- jika data[posisi] > data yang dicari, maka high=pos – 1
- rumus :
Posisi=( kunci-data[low]/data[high]-data[low] ) x (high-low) + low

Jawab :
Langkah pertama :
Kunci perncarian =
Low = 0
High = 9
Posisi = ( (2536 – 2432 ) / (2646 - 2432 ) ) x ( 9-0) + 0 = (104 / 214 ) x 9
= 4,373831
Pos[4] < kunci pencarian , maka
Low = Pos +1 = 5
High = 9
Posisi = ( (2536 – 2535 ) / (2646 - 2535 ) ) x ( 9 - 5) +5 = (1 / 111 ) x 4 +5
= 0.036 + 5
= 5.036
Ketemu diposisi ke-5 , dengan indeks posisi dari 0.
waktu pencarian 0 log 10 =1 s

3.    Diketahui :

Kunci : 2427, 2433, 2435, 2436, 2439

Disimpan dengan alamat indeks 2 digit

Ditanyakan:

Jelaskan dan gambarkan penempatan setiap nilai kunci terebut dalam memory jika disimpan dengan fungsi :

a.    K MOD M+1

b.    Midsquaring

c.    Multiplication

d.   Folding by Boundary secara non Carry

Jawab:

a.    K MOD M+1

M=97

Alamat indeks =1-97

H(2427)=2427 MOD 97+1 =3

H(2433)=2433 MOD 97+1 =9

H(2435)=2435 MOD 97+1 =11

H(2436)=2436 MOD 97+1 =12

H(2439)=2439 MOD 97+1 =15

Rata-rata Akses

= 5/97

=0.05

RECORD	KUNCI
1
...
3	2427
...
9	2433
...
11	2435
12	2436
...
15	2439
...
97

b.                  MIDSQUARING

Kunci : 2427, 2433, 2435, 2436, 2439

Alamat indeks 2 digit

K	2427	2433	2435	2436	2439
K2	05890329	05919489	05929225	05934096	05948721
H(K)	90	19	29	34	48

Record	Kunci
0
...
19	2427
...
29	2433
...
34	2435
...
48	2436
...
90	2439
...
99

Rata-rata Akses =

5/100 =0.05

c.    MULTIPLICATION

Kunci : 2427, 2433, 2435, 2436, 2439

Alamat indeks =0-99

-       H(2427) = 24 | 27

                           =24*27

                           =648 =64

-       H(2433) =24|33

                           =24*33

                           =792 =79

-       H(2435) =24|35

                           =24*35

                           =840 =84

-       H(2436) =24|36

                           =24*36

                           =864 =86

-       H(2439) =24|39

                           =24*39

                           =936 =93

Record	Kunci
0
...
64	2427
...
79	2433
...
84	2435
...
86	2436
...
93	2439
...
99

Rata-rata Akses = 5/100=0.05

d.   Folding by boundary secara non carry

Kunci : 2427, 2433, 2435, 2436, 2439

Alamat indeks =0-99

-       H(2427) = 24 | 27

                           =24+72

                           =96

-       H(2433) =24|33

                           =24+33

                           =57

-       H(2435) =24|35

                           =24+35

                           =59

-       H(2436) =24|36

                           =24+63

                           =87

-       H(2439) =24|39

                           =24+93

                           =117=17

Record	Kunci
0
...
17	2439
...
57	2433
...
59	2435
...
87	2436
...
96	2427
...
99

Rata-rata akses : 5/100=0,05

4.      Diketahui : Kunci : 27, 18, 29, 28, 39, 13, 16, 42, 17

Ditanya:

Jelaskan dan gambarkan penempatan setiap nilai kunci dalam memori jika disimpan menggunakan metode :

a.       LISCH

b.      EISCH

Jawab:

a.    LISCH (Late Insertion Standard Coalesced Hashing

Kunci : 27, 18, 29, 28, 39, 13, 16, 42, 17

Maka:

N = 9

P = 11

Alamat indeks : 0 s/d 10

H(27) = 27 MOD 11 = 5

H(18) = 18 MOD 11 = 7

H(29) = 29 MOD 11 = 7 (Collision)       

          Ditempatkan pada indeks terakhir yang kosong,

          10 masih kosong, sehingga H(29) = 7

          Home address 7 diberi link ke indeks 10

H(28) = 28 MOD 11 = 6

H(39) = 39 MOD 11 = 6 (Collision)

          Ditempatkan pada indeks terakhir yang kosong,

          9 masih kosong, sehingga H(39) = 9

          Home address 6 diberi link ke indeks 9

H(13) = 13 MOD 11 = 2

H(16) = 16 MOD 11 = 5 ( Collision)

          Ditempatkan pada indeks terakhir yang kosong,

          8 masih kosong, sehingga H(16) = 8

          Home address 5 diberi link ke indeks 8

H(42) = 42 MOD 11 = 9 (Collision)

          Ditempatkan pada indeks terakhir yang kosong,

          4 masih kosong, sehingga H(42) = 4

          Home address 9 diberi link ke indeks 4

H(17)= 17 MOD 11 = 6 (Collision)

          Ditempatkan pada indeks terakhir yang kosong,

          3 masih kosong, sehingga H(17) = 3

          Home address (terakhir) 4 diberi link ke indeks 3

Penempatan kunci :

Record	Kunci	Link
0
1
2	13
3	17
4	42	3
5	27	8
6	28	9
7	18	10
8	16
9	39	4
10	29

Rata-rata akses : (9+4+3)/9 = 16/9 =1,78

 

b.   EISCH

Kunci : 27, 18, 29, 28, 39, 13, 16, 42, 17

Maka:

N = 9

P = 11

Alamat indeks : 0 s/d 10

H(27) = 27 MOD 11 = 5

H(18) = 18 MOD 11 = 7

H(29) = 29 MOD 11 = 7 (Collision)                  

                    Ditempatkan pada indeks terakhir yang kosong,

                    10 masih kosong, sehingga H(29) = 7

                    Home address 7 diberi link ke indeks 10

H(28) = 28 MOD 11 = 6

H(39) = 39 MOD 11 = 6 (Collision)

                    Ditempatkan pada indeks terakhir yang kosong,

                    9 masih kosong, sehingga H(39) = 9

                    Home address 6 diberi link ke indeks 9

H(13) = 13 MOD 11 = 2

H(16) = 16 MOD 11 = 5 ( Collision)

                    Ditempatkan pada indeks terakhir yang kosong,

                    8 masih kosong, sehingga H(16) = 8

                    Home address 5 diberi link ke indeks 8

H(42) = 42 MOD 11 = 9 (Collision)

                    Ditempatkan pada indeks terakhir yang kosong,

                    4 masih kosong, sehingga H(42) = 4

                    Home address 9 diberi link ke indeks 4

H(17)= 17 MOD 11 = 6 (Collision)

                    Ditempatkan pada indeks terakhir yang kosong,

                    3 masih kosong, sehingga H(17) = 3

                    Home address (terakhir) 6 diberi link ke indeks 3

Penempatan kunci :

Record	Kunci	Link
0
1
2	13
3	17	9
4	42
5	27	8
6	28	3
7	18	10
8	16
9	39	4
10	29

Rata-rata akses : (9+6)/9 = 15/9 =1,67