Daftar Isi
i
ii
Desain & Analisis Algoritma
Daftar Isi
iii
DESAIN & ANALISIS ALGORITMA Oleh
: Intan Yuniar Purbasari
Edisi Pertama Cetakan Pertama, 2007 Hak Cipta © 2007 pada penulis, Hak Cipta dilindungi undang-undang. Dilarang memperbanyak atau memindahkan sebagian atau seluruh isi buku ini dalam bentuk apa pun, secara elektronis maupun mekanis, termasuk memfotokopi, merekam, atau dengan teknik perekaman lainnya, tanpa izin tertulis dari penerbit.
Candi Gebang Permai Blok R/6 Yogyakarta 55511 Telp. : 0274-882262; 0274-4462135 Fax. : 0274-4462136 E-mail :
[email protected]
Purbasari, Intan Yuniar DESAIN DAN ANALISIS ALGORITMA/Intan Yuniar Purbasari - Edisi Pertama Yogyakarta; Graha Ilmu, 2007 x +134 hlm, 1 Jil. : 23 cm. ISBN: 978-979-756-219-9 1. Komputer
iv
I. Judul
Desain & Analisis Algoritma
Kata Pengantar
S
yukur Alhamdulillah penulis panjatkan kepada Allah Subhanallahu Wataala atas segala limpahan Kekuatan-Nya sehingga dengan segala keterbatasan waktu, tenaga, dan pikiran yang dimiliki penulis, akhirnya buku Desain dan Analisis Algoritma ini bisa terselesaikan. Buku ini disusun dengan tujuan untuk membantu mahasiswa agar dapat memahami materi-materi yang terdapat dalam matakuliah Desain dan Analisis Algoritma. Materi pokok dalam buku ini sebagian besar penulis ambil dari dua referensi utama yang digunakan dalam pembuatan buku ini, sehingga diharapkan dapat memberikan gambaran umum mengenai materi desain dan analisis algoritma. Namun demikian, untuk mendapatkan pemahaman yang menyeluruh terhadap materi perkuliahan, penulis sangat menganjurkan mahasiswa untuk juga mempelajari buku referensi tersebut. Penulis sadar bahwa buku ini masih jauh dari sempurna. Oleh karena itu, penulis sangat mengharapkan saran dan masukan demi peningkatan kualitas buku ini. Penulis sangat berterima kasih kepada suami yang selalu mendukung terselesaikannya buku ini. Terima kasih juga penulis ucapkan kepada para dosen di Teknik Informatika ITS yang telah memberikan dasar pengetahuan Informatika yang baik Daftar Isi
v
kepada penulis. Tak lupa penulis berterima kasih khususnya kepada Ketua Jurusan Teknik Informatika UPN Veteran Jawa Timur yang selalu memotivasi penulis untuk menyelesaikan buku ini. Terima kasih pula kepada Penerbit Graha Ilmu Yogyakarta dan juga kepada para pembaca yang telah membaca buku ini. Akhir kata, semoga buku ini dapat bermanfaat, baik bagi mahasiswa maupun siapa saja yang membutuhkan. Surabaya, Maret 2007 Penulis
vi
Desain & Analisis Algoritma
Daftar Isi
KATA PENGANTAR DAFTAR ISI BAB 1 ALGORITMA1 1.1 Algoritma sebagai sebuah teknologi 1.2 Langkah-langkah Pembuatan Algoritma 1.2.1 Pernyataan Masalah 1.2.2 Pembuatan Model 1.2.3 Desain Algoritma 1.2.4 Kebenaran Algoritma 1.2.5 Implementasi 1.2.6 Analisis dan Kompleksitas Algoritma 1.2.6 Testing Program 1.2.8 Dokumentasi Latihan Rangkuman Referensi Soal-soal test BAB 2 TOP-DOWN DAN BOTTOM-UP PROGRAMMING 2.1 Top-Down Structured Programming 2.2 Bottom-Up Programming Daftar Isi
2 4 4 5 6 7 8 8 9 9 9 10 10 11 13 13 21 vii
Latihan Rangkuman Soal-soal Test
22 22 23
BAB 3
MODEL STRUKUTR DATA DAN ABSTRACT DATA TYPE 3.1 Model Network/Graph 3.2 Representasi Network 3.3 Algoritma Connect 3.4 Struktur Data 3.4.1 Array 3.4.2 Linked List 3.4.3 Tipe Data Abstrak (Abstract Data Type) Latihan Rangkuman Soal-soal test
25 25 25 28 29 29 30 31 39 41 43
BAB 4 METODE DESAIN ALGORITMA 4.1 Subgoal, Hill Climbing, dan Working Backward 4.2 Heuristic 4.3 Backtrack Programming 4.4 Rekursi Latihan Rangkuman Soal-soal Test
45 43 45 55 61 69 69 71
BAB 5 PERTUMBUHAN FUNGSI 5.1 Insertion Sort 5.2 Merge Sort 5.3 Notasi Asymptotic Latihan Rangkuman Soal-soal Test
73 73 77 82 88 88 91
viii
Desain & Analisis Algoritma
BAB 6
PENCARIAN MINIMUM SPANNING TREE PADA GRAPH 6.1 Pencarian MST dengan Algoritma Prim 6.2 Pencarian MST dengan Algoritma Kruskal Latihan Rangkuman Soal-soal Test
93 93 101 103 103 105
BAB 7 ALGORITMA PENGURUTAN 7.1 Quick Sort 7.2 Heap Sort Latihan Rangkuman Soal-soal Test
107 108 116 127 127 129
DAFTAR PUSTAKA
131
TENTANG PENULIS
Daftar Isi
-oo0oo-
133
ix
Desain & Analisis Algoritma
