buku ajar struktur data

Buku Ajar Struktur Data

Kadwi Suharsono 1

B a g ia n

Tujuan Instruksional Khusus

Mahasiswa mampu menjelaskan materi yang dipelajari da-lam Struktur Data

Mahasiswa mampu memahami Struktur Data sebagai dasar dari pemrograman komputer.

Pokok Bahasan

Istilah-istilah yang digunakan dalam Struktur Data

Materi pokok yang dibahas dalam Struktur Data

Operasi yang dilakukan pada Struktur Data

Notasi dan fungsi Matematika

Notasi algoritma

Struktur Kendali

Kompleksitas algoritma

Istilah

ata adalah nilai atau sekumpulan nilai sederhana. Suatu item data merujuk pada suatu nilai. Suatu item data dapat dibagi menjadi sub item data. Sekumpulan data umumnya diorganisa-sikan dalam suatu hirarki data: field, record dan file. Agar istilah

ini menjadi lebih jelas, perlu ditambahkan lagi beberapa istilah tambahan.

Suatu entitas merupakan sesuatu yang mempunyai atribut tertentu. Atri-but ini dapat diberi nilai, berbentuk numerik atau alfanumerik. Berikut ini contoh atribut dan nilai yang berhubungan dengan entitasnya, suatu kar-yawan dalam perusahaan.

Atribut : Nama Umur Kelamin NIP

Nilai : Janoko 30 L 123-24-5533

Entitas dengan atribut yang mirip, misalnya semua karyawan dalam peru-sahaan membentuk sekumpulan entitas. Setiap atribut dalam suatu enti-tas mempunyai jangkauan nilai, sederetan nilai yang mungkin diisikan ke dalam atribut tertentu.

Istilah informasi umumnya digunakan untuk data yang telah diberi atribut tertentu, atau dengan kata lain data yang lebih berarti atau data yang telah diproses.


Kadwi Suharsono 2

Cara mengorganisasikan data ke dalam hirarki field, record dan file meng-gambarkan hubungan di antara atribut, entitas dan sekumpulan entitas. Sebuah field merupakan elemen tunggal dari informasi yang mewakili atri-but suatu entitas, sebuah record merupakan sekumpulan nilai field dari suatu entitas, dan sebuah file merupakan sekumpulan record dari suatu entitas dalam sekumpulan entitas.

Setiap record dalam sebuah file mungkin berisi bermacam-macam nilai, tetapi nilai dalam field tertentu yang bersifat unik, disebut dengan kunci primer atau primary key.

Contoh 1.1.

a. Suatu dealer mobil menyimpan data data file inventori yang berisi data berikut:

No Seri, Jenis, Tahun pembuatan, Harga

Field No Seri dapat dijadikan sebagai kunci primer atau primary key, karena setiap mobil mempunyai No Seri yang unik, tidak ada 1 no seri digunakan oleh lebih dari 1 mobil.

b. Suatu organisasi menyimpan data anggotanya yang berisi data berikut:

Nama, Alamat, No telpon, iuran

Walaupun terdapat 4 item data, nama dan alamat mungkin dapat dikelompokkan, dan nama dapat dijadikan sebagai primary key.

Pengorganisasian data ke dalam field, record dan file tersebut di atas mungkin tidak begitu rumit untuk dikelola dan pemrosesan struktur data tertentu dapat dilakukan dengan efisien. Data juga dapat diorganisasikan ke dalam struktur yang lebih rumit dan komplek. Untuk mempelajari struk-tur data tersebut meliputi 3 tahap:

1. Deskripsi logik atau matematik suatu struktur data

2. Implementasi struktur data dalam sebuah komputer

3. Analisis kuantitatif terhadap suatu struktur data, yang meliputi pe-nentuan jumlah memori yang diperlukan untuk menyimpan struktur data dan waktu yang diperlukan untuk memroses struktur data.

Catatan: langkah 2 dan langkah 3 tergantung pada tempat penyimpanan struktur data: memori utama (main memory) komputer atau memori tam-bahan (secondary memory). Dalam buku ini, penyimpanan menggunakan memori utama, artinya lokasi memori dan waktu yang digunakan untuk mengakses isi dari lokasi memori yang ada tidak tergantung pada sel ter-tentu atau sel sebelumnya. Pada penyimpanan yang menggunakan me-mori tambahan, disebut manajemen berkas/file atau manajemen basis data, materi yang tidak dibahas dalam buku ini.


Kadwi Suharsono 3

Struktur Data

Data mungkin diorganisasikan dalam berbagai macam cara; model logik atau matematik dari pengorganisasian tertentu data yang disebut dengan struktur data. Pemilihan model data tertentu tergantung pada 2 pertim-bangan. Pertama, menyediakan cukup banyak struktur yang mencermin-kan hubungan nyata data tersebut dengan dunia nyata. Kedua, struktur-nya harus cukup sederhana sehingga struktur data tersebut dapat dipro-ses dengan efektif pada waktu diperlukan.

Array

Jenis struktur data yang paling sederhana adalah array linier. Sebuah array linier merupakan sederetan elemen data yang dirujuk secara ber-urutan oleh sedertan angka urut, biasanya 1, 2, 3, . . . . .n. Jika suatu array diberi nama A, maka elemen A disimbulkan dengan notasi subscript:

a1, a2, a3, . . . . . . ., an

atau dengan notasi kurung

A(1), A(2), A(3), . . . . . , A(N)

atau dengan notasi kurung siku

A[1], A[2], A[3], . . . . ., A[N]

Berdasarkan hal tersebut di atas, maka angka K dalam A[K] disebut in-deks, dan A[K] disebut variabel berindeks.

Catatan: notasi kurung dan notasi kurung siku sering digunakan untuk na-ma array lebih dari 1 huruf atau muncul dalam algoritma. Pada saat meng-gunakan cara ini, digunakan huruf kapital untuk nama array, dan indeks-nya menggunakan A dan N. Di bagian lain mungkin digunakan notasi pe-nulisan nama array dengan huruf miring dengan indeks/subscript huruf kecil cetak miring, dari a dan n. Notasi penulisan yang pertama sesuai dengan teks dalam buku komputer, sedangkan notasi kedua sesuai dengan penulisan teks buku matematika.

Contoh 1.2.

Sebuah array linier SISWA terdiri dari 6 nama siswa, seperti yang ada dalam gambar 1.1. dalam gambar tersebut, data SISWA[1] adalah Janoko, SISWA[2] adalah Srikandi, SISWA[3] adalah Togog dan seterusnya.

Janoko1

Srikandi2

Togog3

Janoko4

Marmoyo5

Abimanyu6

SISWA

Gambar 1.1. Array 1 dimensi


Kadwi Suharsono 4

Array linier ini disebut array 1 dimensi, karena setiap elemen datanya diru-juk oleh 1 subscript atau indeks. Suatu array 2 dimensi merupakan sekum-pulan elemen data yang sama, dirujuk oleh 2 subscript atau indeks. Array semacam ini dalam ilmu matematika disebut dengan matrik, atau dalam dunia bisnis disebut tabel.

Contoh 1.3.

Suatu jaringan yang terdiri dari 28 mart, yang masing-masing mempunyai 4 depar-temen, membuat daftar penjualan mingguan, seperti yang tertera dalam gambar 1.2 berikut.

2872

2196

3257

805

1223

1017

3211

2525

3686

1560

1744

1951

1

2

3

...

...

2618

...

...

931

...

...

2333

...

...

982

...

...

28

1 2 3 4MartDept

Gambar 1.2. Array 2 dimensi

Data penjualan dari beberapa Mart tersebut dapat disimpan dalam komputer de-ngan menggunakan array 2 dimensi, indeks pertama menunjukkan Mart ke bera-pa, dan indeks kedua menunjukkan no departemennya. Jika nama array tersebut adalah PENJUALAN, maka PENJUALAN[1,1] adalah 2872, PENJUALAN[1,2] adalah 805, PENJUALAN[1,3] adalah 3211, dan PENJUALAN[28,4] adalah 982.

Ukuran array ini adalah 28x4, karena array ini terdiri dari 28 baris, dan 4 kolom.

List berkait

List berkait akan dibahas dengan contoh-contoh. Misalnya perusahaan broker menyimpan data pelanggannya, yang berisi nama pelangan dan nama salesman-nya, seperti yang terlihat pada gambar 1.3 berikut.

Sembrodo

Rahwono

Janoko

Rahwono

Sembrodo

Janoko

Abimanyu

Burisrowo

Cakil

Durno

Emban

Fetruk

Pelanggan

Rahwono

Sembrodo

Rahwono

Gatotkoco

Hanoman

Indrajit

Salesman

1

2

3

4

5

6

7

8

9

Gambar 1.3. List


Kadwi Suharsono 5

Terlihat dengan jelas bahwa file akan disimpan dalam komputer seperti ta-bel, yang terdiri dari 2 kolom dan 9 nama. Cara ini mungkin kurang bagus dalam menyimpan data.

Cara lain untuk menyimpan data yang tertera dalam gambar 1.3 tersebut adalah memisahkan array dari salesman dan menambahkan pointer da-lam file pelanggannya yang menunjuk ke alamat masing-masing sales-mannya, seperti yang terlihat dalam gambar 1.4.

Dalam gambar 1.4 tersebut terlihat, beberapa pointer dihubungkan de-ngan panah dari lokasi pointer menuju ke lokasi salesman yang sesuai. Sebuah data integer yang digunakan sebagai pointer akan memerlukan ruang yang lebih sedikit dibandingkan dengan nama, yang akan dapat menghemat ruang, khususnya jika terdapat ratusan pelanggan untuk masing-masing salesman.

3

2

1

2

3

1

Abimanyu

Burisrowo

Cakil

Durno

Emban

Fetruk

Pelanggan

2

3

2

Gatotkoco

Hanoman

Indrajit

Pointer

1

2

3

4

5

6

7

8

9

Janoko

Rahwono

Sembodro

Salesman

1

2

3

Gambar 1.4. List dengan pointer

Jika perusahaan tersebut menghendaki list pelanggan untuk masing-ma-sing salesman-nya, maka dengan menggunakan data yang terdapat da-lam gambar 1.4 tersebut, dengan mencarinya dalam file pelanggan. Salah satu cara menyederhanakan proses pencarian tersebut adalah dengan memberikan setiap salesman dengan beberapa pointer yang menunjuk ke para pelanggannya, seperti yang terlihat pada gambar 1.5. Tantangan yang dihadapi cara ini adalah masing-masing salesman akan mempunyai beberapa pointer, ada yang ditambahkan dan ada yang dihapus.

Janoko

Rahwono

Sembodro

Salesman

1

2

3

3, 6

2, 4, 7, 9

1, 5, 8

Pointer

Gambar 1.5 Salesman dengan pointer-nya

Cara lain yang sangat populer untuk menyimpan data yang tertera pada gambar 1.3 adalah seperti yang tertera dalam gambar 1.6.

Masing-masing salesman mempunyai 1 pointer yang menunjuk ke pelang-gannya yang pertama, file pelanggan mempunyai pointer juga yang me-


Kadwi Suharsono 6

nunjuk ke pelanggan berikutnya, dan seterusnya, sampai pointer pelang-gan bernilai 0, yang berarti pelanggan terakhir dari salesman yang ada.

Dalam gambar 1.6 tersebut digambarkan panah yang menunjuk dari sa-lesman Rahwono ke beberapa pelanggannya. Dengan menggunakan cara ini seseorang dengan mudah akan mendapatkan seluruh pelanggan dari nama salesman yang ada, dan yang paling penting adalah, sangat mudah untuk menambah dan menghapus data pelanggan seorang salesman.

5

4

6

7

8

0

Abimanyu

Burisrowo

Cakil

Durno

Emban

Fetruk

Pelanggan

9

0

0

Gatotkoco

Hanoman

Indrajit

Link

1

2

3

4

5

6

7

8

9

Janoko

Rahwono

Sembodro

Salesman

1

2

3

3

2

1

Pointer

Gambar 1.6. List Berkait

Data yang tersusun dalam gambar 1.6 tersebut adalah contoh dari list berkait. Walaupun terdapat penggunaan istilah ‘pointer’ dan ‘link’ yang se-benarnya sama, tetapi terdapat perbedaan penggunaan. Istilah ‘pointer’ akan digunakan pada elemen yang menunjuk ke list yang berbeda, se-dangkan istilah ‘link’ digunakan untuk menunjuk ke list yang sama.

Tree

Kerap kali data berisi hubungan hirarki di antara elemen datanya. Struktur data yang merefleksikan hubungan semacam ini disebut dengan Tree. Materi ini akan dibahas di bagian 5. Di sini hanya akan ditunjukkan sifat dasar dari Tree tersebut melalui 2 contoh.

Contoh 1.4. Struktur Record

Walaupun sebuah file menggunakan record, dengan 1 atau lebih array, yang menggambarkan kelompok item dan item dasar, akan lebih baik jika mengguna-kan struktur data Tree. Misalnya record pegawai adalah sebagai berikut:

No Pegawai, Nama, Alamat, Umur, Gaji, Tanggungan,

walaupun Nama merupakan kelompok item yang terdiri dari subitem Nama Depan dan Nama Belakang. Demikian juga dengan Alamat, yang terdiri dari Jalan dan Area. Area juga mempunyai subitem Kota, Negara dan Kode Pos. struktur data hirarki ini dapat digambarkan dalam gambar 1.7.


Kadwi Suharsono 7

Pegawai

No Pegawai Nama Alamat Umur Gaji Tanggungan

Depan Belakang Jalan Area

Kota Negara Kode pos

(a)

01 Pegawai

02 No Pegawai

02 Nama

03 Depan

03 Belakang

02 Alamat

03 Jalan

03 Area

04 Kota

04 Negara

04 Kode Pos

02 Umur

02 Gaji

02 Tanggungan

(b)

Gambar 1.7. Struktur Data Tree

Contoh 1.5. Ekspresi Aljabar

Perhatikan persamaan matematika berikut:

(2x + y) (a – 7b)3

Dengan menggunakan simbol ↑ sebagai pangkat, dan simbol * sebagai perkalian, dapat disusun dalam bentuk struktur data tree seperti pada gambar 1.8 berikut. Perlu diperhatikan bahwa urutan operasi yang ada menunjukkan bahwa pangkat dilakukan setelah operasi pengurangan, dan perkalian menempati puncak Tree, dilakukan yang paling akhir.


Kadwi Suharsono 8

*y

-

+↑

a *

3

*

2 x

7 b

Gambar 1.8. struktur data tree

Terdapat struktur data selain array, list berkait, dan tree yang akan diba-has. Beberapa di antaranya adalah:

a. Stack. Sebuah stack, juga disebut dengan sistem last-in first-out (LIFO), suatu list linier dengan cara penyisipan dan penghapusan hanya pada satu sisi, yang disebut dengan TOP. Struktur ini mirip dengan operasi tumpukan baki yang mempunyai pegas. Baki yang ditambahkan ke dalam tumpukan akan diletakkan di atas baki teratas, demikian pada waktu mengambil baki, diambil dari posisi baki yang teratas.

(a) Tumpukan baki (b) Antrian menunggu bis

Jakarta

Surabaya

Yogyakarta

Makassar

Denpasar

(c) Sistem Penerbangan

Gambar 1.9. Struktur Data Stack,Queue dan Graph

b. Queue. Suatu antrian, juga disebut dengan sistem first-in first-out (FIFO), merupakan list linier, penambahan elemen hanya dapat di-lakukan di satu sisi, yang disebut dengan ‘depan’, dan penyisipan


Kadwi Suharsono 9

hanya dapat dilakukan di sisi yang lain, yang disebut dengan ‘be-lakang’. Operasi sistem ini mirip dengan deretan orang yang antri menunggu kedatangan bis, seperti terlihat pada gambar 1.9. (b) di atas. Orang pertama dalam antrian, adalah orang pertama yang masuk bis.

c. Graph. Terkadang data berisi suatu hubungan di antara pasangan elemennya, yang bukan berbentuk hirarki. Misalnya jalur pener-bangan di antara kota dalam suatu sistem penerbangan pesawat terbang. Seperti yang tertera dalam gambar 1.9.(c). Struktur data yang merefleksikan hubungan ini disebut dengan graph.

Operasi pada Struktur Data

Data yang terdapat dalam struktur data akan diproses oleh operasi terten-tu. Struktur data tertentu, yang dipilih oleh pemrogram tergantung pada operasi khusus yang akan digunakannya. Berikut ini adalah operasi-ope-rasi yang sering digunakan, yaitu:

(1) Traversing, mengakses setiap record tepat 1 kali agar item tertentu dari record tersebut dapat diproses. Mengakses dan memroses ini kadang disebut dengan ‘mengunjungi’

(2) Searching, menemukan lokasi dari record dengan nilai kunci ter-tentu atau mencari lokasi semua record yang memenuhi kondisi tertentu.

(3) Inserting, menambah sebuah record baru ke dalam struktur data.

(4) Deleting, menghapus sebuah record dari struktur data.

Terkadang 1 atau 2 operasi juga digunakan pada situasi tertentu, misal-nya akan dihapus sebuah record dengan kunci tertentu. Yang dilakukan adalah mencari lokasi record yang sesuai dengan kunci pencarian, baru kemudian dilakukan penghapusan.

Dua operasi berikut digunakan pada situasi khusus, yaitu:

(1) Sorting, menyusun record sesuai dengan urutan logika tertentu, secara alfabetis berdasarkan kunci Nama, berdasarkan kunci No pegawai.

(2) Merging, menggabungkan record dalam 2 file terurut yang berbeda berbeda menjadi 1 file terurut.

Algoritma: Kompleksitas, Kendala Waktu-Ruang

Sebuah algoritma adalah sejumlah langkah-langkah yang terdefinisi de-ngan baik untuk memecahkan masalah tertentu. Tujuan utama dari buku ini adalah mengembangkan algoritma yang efisien untuk memroses struk-tur data. Waktu dan ruang yang digunakan adalah 2 hal yang diukur untuk mengetahui efisiensi suatu algoritma. Kompleksitas suatu algoritma meru-


Kadwi Suharsono 10

pakan fungsi dengan memberi input waktu yang diperlukan dan/atau ru-ang yang diperlukan.

Setiap algoritma yang dibuat melibatkan struktur data tertentu. Oleh kare-na itu mungkin tidak digunakan algoritma yang paling efisien, karena pe-milihan struktur data tergantung pada banyak hal, termasuk jenis data dan seringnya jenis operasi yang digunakan. Terkadang pemilihan struktur da-ta melibatkan kendala waktu-ruang: dengan meningkatkan jumlah ruang untuk menyimpan data, akan mampu menurunkan jumlah waktu yang di-perlukan untuk memroses data, atau sebaliknya.

engembangan suatu algoritma untuk menciptakan dan memro-ses struktur data merupakan bagian utama yang dibahas dalam bagian ini. Dalam buku ini banyak digunakan contoh se-derhana, untuk merepresentasikan algoritmanya. Bentuk yang

dipilih mirip dengan bentuk yang digunakan oleh Knuth dalam bukunya yang terkenal Fundamental Algorithms. Walaupun bentuk yang digunakan tidak terpengaruh oleh bahasa pemrograman tertentu, algoritma yang ada dapat langsung diterjemahkan ke dalam bahasa Pascal, FORTRAN, PL/1, atau BASIC. Beberapa bagian, algoritma yang ada mungkin sudah diterje-mahkan ke bahasa pemrograman tersebut dalam beberapa bagian.

Algoritma mungkin sangat kompleks. Program komputer mengimplemen-tasikan algoritma yang lebih rumit yang dengan mudah dipahami kalau diorganisasikan dalam hirarki modul, seperti yang tampak pada gambar 1.10 berikut. Dalam pengorganisasian semacam ini, sebuah program berisi modul utama, yang berisi deskripsi umum dari suatu algoritma; modul utama ini merujuk pada beberapa submodul tertentu, yang berisi informasi lebih detil dari modul utama; setiap submodul mungkin merujuk ke submodul yang lebih detil lagi, dan seterusnya. Pengorganisasian pro-gram ke dalam hirarki modul semacam ini memerlukan pola arus dasar tertentu dan struktur logika yang sering dihubungkan dengan gagasan program terstruktur.

P


Kadwi Suharsono 11

Main Module

Gambar 1.10. Hirarki Modul

Gambaran umum dan pembahasan berbagai fungsi matematis yang men-jadi kajian algoritma dan bagian dari ilmu komputer secara umum, berba-gai macam jenis variabel yang muncul dalam algoritma dan program akan dibahas dalam bagian ini.

Pembahasan tentang kompleksitas sebuah algoritma juga menjadi bagian yang akan dibahas. Pengukuran algoritma yang penting ini merupakan alat untuk membandingkan solusi algoritma yang berbeda untuk masalah-masalah tertentu, bukan pada area struktur data saja, melainkan hamper di semua bagian ilmu komputer.

Notasi dan Fungsi Matematika

Berbagai macam fungsi dan notasi matematika akan sering muncul dalam menganalisis suatu algoritma dan ilmu komputer secara umum.

Fungsi Floor dan Ceiling.

Misalkan x adalah bilangan pecahan (Real), maka x akan terletak antara 2 bilangan bulat (integer), yang disebut dengan floor dan ceiling dari x. Khususnya,

⌊𝑥⌋, disebut dengan floor dari x, merupakan bilangan bulat (integer) ter-besar yang tidak melebihi x

⌈𝑥⌉, disebut dengan ceiling dari x, merupakan bilangan bulat (integer) pa-ling kecil yang tidak lebih kecil dari x

Jika x adalah bilangan bulat (integer), maka ⌊𝑥⌋ = ⌈𝑥⌉; atau ⌊𝑥⌋ + 1 = ⌈𝑥⌉

Contoh 1.6.


Kadwi Suharsono 12

⌊3,14⌋ = 3, ⌊√5⌋ = 2, ⌊−8,5⌋ = -9, ⌊7⌋ = 7

⌈3,14⌉ = 4, ⌈√5⌉ = 3, ⌈−8,5⌉ = -8, ⌈7⌉ = 7

Fungsi sisa bagi, aritmatika Modular

Misalkan k adalah bilangan bulat (integer) berapapun, dan M adalah bi-langan bulat (integer) positif, maka

k(mod M)

(dibaca k modulo M) merupakan sisa bagi dari k dibagi dengan M. lebih te-patnya k(mod M) merupakan bilangan bulat unik r, yaitu:

k = Mq + r, di mana 0 ≤ r ≤ M

jika k positif, maka k dibagi dengan M akan menghasilkan sisa bagi r, jadi

25(mod 7) = 4, 25(mod 5) = 0, 35(mod 11) = 2, 3(mod 8) = 3

Bilangan Bulat dan Fungsi absolut

Misalkan x adalah bilangan pecahan. Nilai bilangan bulat x, ditulis dengan INT(x), mengubah x ke dalam bilangan bulat dengan menghapus (memo-tong) bagian angka pecahannya. Jadi

INT(3,14) = 3, INT(√5) = 2, INT(-8,5) = -8, INT(7) = 7

Perhatikan bahwa INT(x) = ⌊𝑥⌋ atau INT(x) = ⌊𝑥⌋, sesuai dengan x itu bi-langan positif atau bilangan negatif.

Nilai absolut dari bilangan pecahan x, ditulis dengan ABS(x) atau |𝑥|, me-rupakan bilangan x atau –x. Jadi, ABS(0) = 0, untuk x ≠ 0, maka ABS(x) = x atau ABS(x) = -x tergantung dari x itu bilangan positif atau bilangan ne-gatif. Jadi

|15|=15, |7| = 7, |−3,33| = 3,33, |4,44| = 4,44,

|−0,075|=0,075

Simbol penjumlahan

Simbol hasil penjumlahan adalah , huruf Yunani, sigma. Perhatikan se-rangkaian angka a1, a2, a3, . . . ., maka hasil penjumlahannya dari:

a1 + a2 + a3 + . . . + an dan am + am+1 + . . . + an

akan dinyatakan dengan

∑ 𝑎𝑗

𝑛

𝑗=1

dan

∑ 𝑎𝑗

𝑛

𝑗=𝑚


Kadwi Suharsono 13

Huruf j dalam ekspresi di atas disebut dengan index dummy atau variabel dummy. Huruf yang sering digunakan sebagai variable dummy adalah i, k, s, dan t.

Contoh 1.6

∑ 𝑎𝑖𝑏𝑖 =

𝑛

𝑖=1

𝑎1𝑏1 + 𝑎2𝑏2 + ⋯ + 𝑎𝑛𝑏𝑛

∑ 𝑗2

5

𝑗=2

= 22 + 32 + 42 + 52 = 4 + 9 + 16 + 25 = 54

∑ 𝑗

𝑛

𝑗=1

= 1 + 2 + ⋯ + 𝑛

Hasil penjumlahan terakhir pada contoh 1.6 akan sering muncul. Itu meru-pakan nilai dari n(n+1)/2, oleh karena itu:

1 + 2 + 3 + ⋯ + 𝑛 =𝑛(𝑛+1)

2

Jadi, contoh berikut: 1 + 2 + 3 + ⋯ + 50 =50(51)

2=

2550

2= 1275

Fungsi Faktorial

Perkalian bilangan bulat dari 1 sampai n, dinyatakan dengan n! (dibaca faktorial n), yaitu:

n! = 1 2 3 (n-2) (n-1) n

dan dinyatakan bahwa 0! = 1.

Permutasi

Permutasi adalah himpunan n elemen yang disusun dalam urutan terten-tu. Misalnya permutasi dari himpunan huruf a ,b dan c adalah:

abc, acb, bac, bca, cab, cba

Terdapat n! permutasi dari himpunan n elemen. Oleh karena itu terdapat 4! Atau 24 permutasi dari himpunan 4 elemen, dan 5! Atau 120 permutasi dari himpunan 5 elemen. Dan seterusnya.

Notasi Algoritma

Sebuah algoritma adalah sederetan langkah-langkah instruksi yang terde-finisi dengan baik untuk memecahkan masalah tertentu. Definisi formal sebuah algoritma menggunakan gagasan dari mesin Turing atau ekivalen-sinya. Bagian ini menjelaskan format yang digunakan untuk menyusun al-goritma dalam buku ini. Notasi algoritma ini akan menjadi mudah kalau di-deskripsikan menggunakan contoh.

Contoh 1.7


Kadwi Suharsono 14

Sebuah array DATA berisi data numeric yang disimpan di memori. Ingin dicari lokasi LOC dan nilai MAX, elemen yang berisi nilai terbesar dalam DATA. Salah satu cara terbaik untuk memecahkan masalah ini adalah sebagai berikut:

Inisialisasi nilai LOC = 1 dan MAX = DATA[1]. Kemudian bandingkan MAX dengan masing-masing elemen DATA[K] secara berurutan. Jika DATA[K] melebihi MAX, mutakhirkan LOC dan MAX, agar LOC = K, dan MAX = DATA[K]. Hasil akhir dari LOC dan MAX menunjukkan lokasi dan nilai dari elemen DATA terbesar.

Algoritma 1.1. (Nilai Terbesar dalam array) sebuah array DATA yang tidak kosong dengan jumlah elemen data sebanyak N.

Algoritma berikut mencari lokasi LOC dan nilai MAX, yang merupakan elemen ter-besar dalam DATA. Variabel K digunakan untuk pencacah. Langkah 1. [Inisialisasi] K:=1 dan MAX := DATA[K]. Langkah 2. [Naikkan nilai Pencacah] K := K+1. Langkah 3. [Uji Pencacah] Jika K > N, maka: Cetak:LOC, MAX, dan Selesai. Langkah 4. [Bandingkan, Mutakhirkan] Jika MAX<DATA[K], maka: LOC:= K dan MAX:=DATA[K]. Langkah 5. [Ulang Perulangan] Ke langkah 2.

Algoritma formal tersebut dapat disusun dalam bagan arus seperti yang tertera pada gambar 1.11.

Format dari algoritma formal tersebut terdiri dari 2 bagian. Bagian pertama adalah paragraph yang menjelaskan tujuan dari algoritma, variabel yang digunakan dalam algoritma dan data masukan. Bagian kedua dari algorit-ma berisi sejumlah langkah-langkah yang akan dilaksanakan.


Kadwi Suharsono 15

Start

Kß1

LOC ß 1

MAX ßDATA[1]

K ß K + 1

Apa K > N?

Apakah

MAX<DATA[K]

?

Tidak

LOC ß K

MAX ßDATA[K]

Ya

TidakCetak:

LOC,

MAX

Ya

Selesai

Gambar 1.11. Bagan Arus Mencari LOC dan MAX

Struktur Kendali

Algoritma dan program komputer akan menjadi mudah untuk dimengerti ji-ka algoritma tersebut menggunakan modul dan 3 jenis logik, atau arus kendali, yang disebut dengan:

1. Logika urut, atau arus sekuensial 2. Logika pilihan, atau arus kondisional 3. Logika iterasi, atau arus perulangan

Logika urut (Arus sekuensial)

Logika urut telah ada di bagian sebelumnya. Kecuali kalau intruksi yang diberikan bertentangan, modul-modul dieksekusi dalam urutan yang jelas. Urutan langkahnya jelas, dengan nomor langkah, atau secara implisit urut-an dari penulisan modulnya. Proses pada umumnya, bahkan pada masa-lah yang rumit sekalipun, akan menghasilkan pola arus dasar ini.


Kadwi Suharsono 16

Modul A

Modul B

Modul C

Bagan ArusAlgoritma

Modul A

Modul B

Modul C

Gambar 1.12. Logika Urut

Logika Pilihan (Arus Kondisional)

Logika pilihan menggunakan sejumlah kondisi mengarahkan pilihan dari beberapa alternatif modul. Struktur yang menggunakan logika ini disebut struktur kondisional atau struktur jika. Agar lebih jelas, perlu ditambahkan pernyataan yang menunjukkan akhir dari struktur, yaitu:

[Akhir dari struktur Jika]

atau pernyataan yang mirip.

Struktur kondisional ini dibagi menjadi 3 jenis, yaitu:

1. Alternatif Tunggal. Struktur ini mempunyai bentuk: Jika kondisi, maka:

[Modul A] [Akhir dari Struktur Jika]

Logika dari struktur ini dapat dilihat pada gambar 1.13(a). Jika kon-disi terpenuhi, maka Modul A, yang mungkin terdiri dari beberapa instruksi, akan dieksekusi. Jika kondisinya tidak terpenuhi, maka Modul A akan diabaikan, dan kendali program akan berlanjut ke instruksi berikutnya dalam algoritma.

2. Alternatif Ganda. Struktur ini mempunyai bentuk:

Jika Kondisi, maka: [Modul A]

Lainnya: [Modul B]

[Akhir dari Struktur Jika] Logika dari struktur ini dapat dilihat pada gambar 1.13(b). Seperti yang pada gambar bagan arus tersebut, jika kondisi terpenuhi, ma-ka modul A akan dieksekusi, sebaliknya, Modul B yang akan diek-sekusi.


Kadwi Suharsono 17

Kondisi?

Modul A

Ya

TidakKondisi?

Modul A

Ya

Tidak

Modul B

(a) Alternatif Tunggal (b) Alternatif Ganda

Gambar 1.13. Logika Pilihan

3. Alternatif Jamak. Struktur ini mempunyai bentuk: Jika Kondisi(1), maka:

[Modul A1] Lainnya Jika Kondisi(2), maka:

[Modul A2] : Lainnya Jika Kondisi(M), maka:

[Modul AM] Lainnya:

[Modul B] [Akhir dari struktur Jika]

Logika dari struktur ini hanya mengijinkan 1 modul untuk diekseku-si. Khususnya, salah satu dari modul dari kondisi pertama yang ter-penuhi, akan dieksekusi, atau modul sesuai dengan akhir dari per-nyataan Lainnya yang akan dieksekusi. Dalam kenyataan, jarang sekali pilihan lebih dari 3 alternatif.

Contoh 1.8

Solusi untuk persamaan kuadrat:

𝑎𝑥2 + 𝑏𝑥 + 𝑐 = 0

Jika x ≠ 0, maka rumus kuadrat tersebut adalah:

𝑥 =−𝑏 ± √𝑏2 − 4𝑎𝑐

2𝑎

Jumlah D = b2 – 4ac disebut dengan diskriminan, jika nilai D negatif, maka tidak ada solusinya. Jika D = 0, maka hanya terdapat 1 solusi, yaitu –b/2a. Jika D posi-tif, maka rumus tersebut akan menghasilkan 2 solusi yang berbeda. Algoritma ber-ikut mencari solusi untuk persamaan kuadrat tersebut.


Kadwi Suharsono 18

Catatan untuk algoritma 1.2 adalah: terdapat 3 kondisi eksklusif pada langkah 3, yang tergantung dari nilai D, yaitu positif, 0, atau negatif. Dalam hal ini, alternatif penyusunannya mungkin seperti ini: Langkah 3. (1) Jika D > 0, maka: . . . . . . . . . . (2) Jika D = 0, maka: . . . . . . . . . . (3) Jika D > 0, maka: . . . . . . . . . . Dalam Pascal ini menggunakan pernyataan CASE.

Algoritma 1.2. (Persamaan Kuadrat) Algoritma ini menginputkan koofisien A, B, C dari persamaan kuadrat dan menghasilkan solusinya.

Langkah 1. Baca: A, B, C. Langkah 2. Hitung D := B2 – 4AC. Langkah 3. Jika D > 0, maka:

(a) Hitung X1:=(-B+√𝐷)/2A dan X2:=(-B-√𝐷)/2A. (b) Cetak: X1, X2.

Lainnya Jika D=0, maka: (a) Hitung X:= -B/2A. (b) Cetak: ‘Solusi Unik’, X.

Lainnya: Cetak: ‘Tidak ada jawabnya’. [Akhir dari struktur Jika.]

Langkah 4. Selesai.

Logika Iterasi (Arus Perulangan)

Logika ketiga merujuk pada salah satu dari 2 jenis struktur perulangan. Setiap jenis dimulai dengan pernyataan Ulangi dan diikuti dengan Modul, yang disebut dengan badan perulangan. Agar jelas, akan ditandai akhir dari struktur ini dengan:

[Akhir dari Perulangan]

atau pernyataan yang mirip.

Perulangan Ulangi Untuk menggunakan sebuah variabel indeks, misalnya K, untuk mengendalikan perulangan. Perulangan ini mempunyai bentuk:

Ulangi Untuk K = R sampai S setiap T

[Modul]

[Akhir dari Perulangan]

Logika dari struktur ini tertera pada gambar 1.14(a). Di sini R disebut de-ngan nilai inisial, S adalah nilai penguji, dan T adalah penambah. Perhati-kan bahwa badan dari perulangan yang dieksekusi pertama adalah K = R, berikutnya adalah K = R + T, berikutnya lagi adalah K = R + 2T dan sete-rusnya. Perulangan akan diakhiri pada saat K > S. Pada bagan arus di-asumsikan bahwa penambah T adalah bernilai positif. Jika T bernilai ne-


Kadwi Suharsono 19

gatif, maka nilai K akan dikurangi, dan perulangan akan berakhir pada sa-at K < S.

Perulangan Ulangi Selama menggunakan sebuah kondisi untuk mengen-dalikan perulangan. Perulangan ini mempunyai bentuk:

Ulangi Selama Kondisi:

[Modul]

[Akhir dari perulangan]

Logika dari struktur ini dapat dilihat pada gambar 1.14(b). perhatikan bah-wa perulangan akan dieksekusi sampai kondisinya salah. Perlu ditekan-kan di sini bahwa harus disediakan suatu pernyataan sebelum perulangan yang menginisialisasi kondisi yang akan mengendalikan perulangan, dan agar perulangan dapat diakhiri, harus terdapat pernyataan dalam badan perulangan yang dapat mengubah kondisi.

Kondisi?

Modul (Badan

Perulangan)

Ya

Tidak

Apa K > S?

Modul (Badan

Perulangan)

Tidak

Ya

K ß K + T

Kß R

(a) Struktur Ulangi Untuk (b) Struktur Ulangi Selama

Gambar 1.14. Struktur Perulangan

Contoh 1.9.

Algoritma 1.1 ditulis ulang dengan menggunakan perulangan ulangi-selama, yang dapat menghindarkan penggunaan perintah Ke Langkah 2

Algoritma 1.3 menunjukkan beberapa sifat dari algoritma. Biasanya, algo-ritma mengabaikan penggunaan kata ‘langkah’. Disarankan menggunakan struktur perulangan daripada menggunakan perintah ‘ke’ (Go To). Pernya-taan perulangan secara eksplisit telah membentuk badan perulangan. Pernyataan ‘Akhir dari Perulangan’ menunjukkan akhir dari perulangan.


Kadwi Suharsono 20

Algoritma 1.3. (Elemen Terbesar dalam array) sebuah array DATA yang tidak kosong dengan jumlah elemen data sebanyak N. Algoritma berikut mencari lokasi LOC dan nilai MAX, yang merupakan elemen terbesar dalam DATA. 1. [Inisialisasi] K:=1, LOC:=1, dan MAX:=DATA[K]. 2. Ulangi langkah 3 dan 4 selama K≤N: 3. Jika MAX < DATA[K], maka:

LOC := K, dan MAX:= DATA[K]. [Akhir dari perulangan.]

4. K := K + 1. [Akhir dari Perulangan langkah 2.]

5. Cetak: LOC, MAX. 6. Selesai.

Kompleksitas Algoritma

Menganalisa suatu algoritma adalah tugas dari ilmu komputer. Agar dapat membandingkan algoritma, perlu dimiliki beberapa kriteria untuk mengukur efisiensi algoritma.

Misalnya M adalah sebuah algoritma, dan n adalah ukuran dari data input. Waktu dan ruang yang diperlukan oleh algoritma M adalah 2 hal yang akan diukur untuk menentukan efisiensi algoritma M. Waktu diukur dari berapa banyak operasi yang dilakukan, misalnya dalam algoritma sorting dan searching, jumlah permbandingannya. Oleh karena itu, operasi utama harus didefinisikan dengan baik agar operasi lain hanya membutuhkan sedikit operasi atau mendekati proporsi untuk operasi utama. Ruang di-ukur dengan menghitung berapa banyak memori yang diperlukan untuk kondisi maksimum dari algoritma tersebut.

Kompleksitas algoritma M adalah fungsi f(n) dari waktu untuk menjalankan algoritma dan/atau ruang yang diperlukan oleh algoritma, yaitu ukuran n data input. Pada umumnya ruang penyimpanan yang diperlukan oleh algoritma adalah sederhana, yaitu dengan mengalikan ukuran data n. Oleh karena itu, jika tidak dinyatakan, maka istilah ‘kompleksitas’ lebih banyak merujuk pada waktu yang diperlukan untuk menjalankan suatu al-goritma.


Kadwi Suharsono 21

1. Cari nilai dari: ⌊3,4⌋, ⌊−3,4⌋, ⌊−7⌋, ⌊√75 ⌋,⌊√753

⌋, ⌊𝑒⌋

⌈3,4⌉, ⌈−3,4⌉, ⌈−7⌉, ⌈√75 ⌉,⌈√753

⌉, ⌈𝑒⌉ 2. Cari nilai: 48 (mod 5), 48 (mod 7), 1397 (mod 11), 2468 (mod 9)

Cari nilai: -48 (mod 5), -152 (mod 7), -358 (mod 11), -1326 (mod 13)

3. Cari nilai: |3 + 8|, |3 − 8|, |−3 + 8|, |−3 − 8|

7!, 8!, 14!12!⁄ , 15!

16!⁄

4. Tuliskan sebuah function (subprogram) DIV(J, K), dengan J dan K ada-lah bilangan positif, function tersebut akan bernilai 1, jika K habis diba-gi dengan J, dan bernilai 0 jika K tidak habis dibagi dengan J. Contoh: DIV(3, 15) = 1 dan DIV(3, 16) = 0.

5. Tulis program dengan menggunakan function DIV(J, K) untuk memba-ca bilangan positif N, yang > 10, dan menentukan apakah bilangan N tersebut adalah bilangan prima. Kunci: N adalah bilangan prima jika, (1) DIV(2, N) = 0 (untuk N = bilangan ganjil), dan (2) DIV(K, N) = 0,

untuk semua bilangan ganjil K, dengan kondisi 1 < 𝐾2 ≤ 𝑁 6. Tulis procedure berikut ke dalam bahasa pemrograman komputer, mi-

salnya program untuk mencari lokasi LOC1, elemen terbesar dan loka-si LOC2, elemen terbesar kedua dalam array DATA dengan N > 1 elemen. Untuk menguji program gunakan angka-angka: 70, 30, 25, 80, 60, 50, 30, 75, 25 dan 60. FIND(DATA, N, LOC1, LOC2) 1. PERTAMA := DATA[1], KEDUA:= DATA[2], LOC1 := 1, LOC2:= 2. 2. [Apakah PERTAMA dan KEDUA sudah tepat inisialisasinya?]

Jika PERTAMA < KEDUA, maka a. Tukar PERTAMA dengan KEDUA b. LOC1 :=2 dan LOC2 := 1

[Akhir dari Struktur Jika]

3. Ulangi untuk K = 3 sampai N Jika PERTAMA < DATA[K], maka

a. KEDUA := PERTAMA dan PERTAMA := DATA[K]. b. LOC2 := LOC1 dan LOC1 := K.

Lainnya Jika KEDUA < DATA[K], maka

KEDUA := DATA[K] dan LOC2 := K.

[Akhir dari Struktur Jika] 4. Selesai

7. Sebuah bilangan bulat n > 1 disebut bilangan prima jika hanya habis dibagi dengan angka 1 dan n. Berikut ini adalah bilangan prima lebih kecil dari 20: 2, 3, 5, 7, 11, 13, 17, 19. Jika N > 1 dan bukan bilangan prima, maka N mempunyai pembagi

𝑘 ≠ 1, sehingga 𝑘 ≤ √𝑛 atau 𝑘2 ≤ 𝑛 Jika akan dicari semua bilangan prima yang lebih kecil dari m, misal-nya 30. Ini dapat dilakukan dengan menggunakan ‘metode saringan’, yang terdiri dari beberapa langkah. Pertama, tampilkan 30 angka terse-but:


Kadwi Suharsono 22

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30

Coret angka 1 dan angka kelipatan 2 dari daftar angka tersebut:

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

16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30

Karena 3 adalah angka setelah 2, yang tidak tercoret, maka berikutnya coret angka-angka kelipatan 3:

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

16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30

Karena 5 adalah angka setelah 3, yang tidak dicoret, maka berikutnya coret angka kelipatan 5:

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

16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30

Sekarang 7 adalah angka setelah 5 yang tidak dicoret, tetapi 72 > 30. Ini berarti algoritma selesai dan angka yang tertinggal adalah angka prima yang lebih kecil dari 30: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 Mengubah metode saringan menjadi sebuah algoritma untuk mencari bilangan prima yang lebih kecil dari n adalah sebagai berikut: 1. Definisikan array A sebagai berikut: A[1]=1, A[2]=2, A[3]=3,…..

A[N-1] = N-1, A[N]=N 2. Coret angka L dari daftar dengan A[L] := 1. Procedure CrossOut

menguji apakah A[K] = 1, jika tidak maka semua indeks kelipatan K dicoret dengan memberi nilai 1: A[2K]=1, A[3K]=1, A[4K]=1, .... CrossOut(A, N, K) 1. Jika A[K] = 1, maka selesai. 2. Ulangi untuk L = 2K sampai N dengan kelipatan K

A[L] := 1 [Akhir dari Perulangan]

3. Selesai 3. Algoritma untuk metode saringan tersebut adalah:

Algoritma untuk mencetak semua bilangan prima yang lebih kecil dari N 1. [Inisialisasi array A] Ulangi untuk K = 1 sampai N

A[K] := K.

2. [Eliminasi kelipatan K] Ulangi Untuk K = 2 sampai √𝑁 Panggil CrossOut(A, N, K)

3. [Cetak bilangan primanya] Ulangi untuk K = 2 sampai N Jika A[K] ≠ 1 maka Tulis: A[K].

4. Selesai Tulis program untuk mencari bilangan prima yang lebih kecil dari N. Uji program dengan menggunakan: a. N = 1000 b. N = 10.000

buku ajar struktur data

Documents