Algoritma/Software/Hardware: Algoritma

Algoritma

Algoritma dan struktur data merupakan fondasi ilmu komputer. Bidang ini kaya dengan teknik dan analisis yang elegan. Algoritma atau struktur data yang bagus memungkinkan meyelesaikan persoalan dalam beberapa detik di mana cara lain memerlukan waktu bertahun tahun.

4.1 Penyelesaian Persoalan

Struktur data adalah gudang perbendaharaan konsep dasar, kecerdikan , kemampuan abstraksi, beragam algoritma dan teknik untuk evaluasi dan membandingkan alternatif alternatif. Setiap mahasiswa ilmu komputer harus memahaminya.

Struktur data mengumpulkan item item data dan mengelompokan dalam satu cara tertentu. Struktur umum di sediakan bahasa misalnya array. Struktur lain misalnya set, list, stack, queue, deque, tree, binary tree, graph, string dan sebagainya.Penggunaan struktur seharusnya nyaman, pemprogram tidak perlu peduli memikirkan bagaimana struktur tsb di presentasi di mesin.

4.1.1 Penyelesaian Persoalan

Pemprogram bertanggung jawab atas implementasi solusi. Pembuatan program menjadi lebih sederhanajika persoalan dapat di pecah menjadi sub persoalan yang dapat di kelola.

Penyelesaian persoalan dengan komputer berhadapan dengan empat hal :

1. Pemehaman hubungan elemen elemen data yang relevan terhadap solusi secara menyeluruh.

2. Pengambilan keputusan mengenai operasi operasi terhadap elemen elemen data.

3. Perancangan representasi elemen elemen data di memori sehinggga memenuhi kriteria berikut:

(a) Memenuhi hubungan logic antara antara elemen elemen data.

(b) Operasi operasi terhadap elemen elemen data dapat di lakukan secara mudah dan efisien.

4. Pengambilan keputusan bahasa untuk menerjemahkan solusi persoalan menjadi program.

4.1.2 Kompleksitas Sistem Perangkat Lunak

Saat ini, persoalan yang harus di selesaikan dengan komputer semakin kompleks. Pernagkat secara inheren kompleks. Fred Broks menyatakan “Kompleksitas perangkat lunak merupakan properti esensi, bukan properti aksiden”. Sistem berbasis komputer telah menjadi besar, rumit dan kompleks. Perangkat lunak sekala besar disebut industrial strenght software.

Kompleksitas aplikasi (C_app) merupakan penjumlah dua komponen yaitu :

1. Kompleksitas persoalan (C_prb)

2. Kompleksitas solusi (C_sol)

Sehingga kompleksitas aplikasi dapat di eksperimen sebagai berikut :

C_app = C_prb+C_sol

Kopleksitas persoalan C_prbtidak dapat di reduksi kecuali dengan mereduksi daftar kebutuhan. Kita seharusnya dapat melakukan minimasi kompleksitas solusi C_sol. Kita menulis solusi dengan bahasa Asembly adalah sangat lebih rumit di banding menulis solusi dalam bahasa tingkat tinggi seperti Object Pascal, java atau C++. Beberapa rancangan solusi lebih kompleks di banding lainya. Kebanyakan kerja perancangan adalah mencari pendekatan lebih sederhana dalam mempresentasi solusi sehingga kompleksitas solusi menurun.

Setelah kompleksitas solusi C_sol dapat direduksi sebanyak mugkin, jika kompleksitas persoalan C_prb masih besar maka kompleksitas C_app akan tetap besar. Kompleksitas aplikasi C_app ini harus diimplementasi. Untuk mengelola kompleksitas, kita harus menemukan cara untuk mereduksi secara setempat, yaitu kita harus mampu membagi masalah menjadi potongan potongan yang kurang kompleks di banding keseluruhan.

Pemprograman berdisiplin mengendapkan prinsip prinsip rekayasa perangkat lunak yang bagus seperti modularitas dan kehandalan akan memperoleh manfaat penurnan C_sol secara drastis. Bukuini hendak menuntun pemprograman berdisiplin tersebut. Uraian lebih lengkap mengenai prinsip prinsip yang pantas untuk di ikuti para pemprogram berdisiplin di bahas di buku penulis : Rekayasa Sistem Berorientasi Objek.

4.2 Algoritma

Algoritma adalah prosedur untuk melekuken suatu tugas spesifik. Algoritma merupakan gagasan di balik suatu program komputer. Suatu algoritma harus menyelesaikan suatu persoalan yang dispesifikasi dengan bagus.

4.2.1 Algoritma Untuk Suatu Kelas Persoalan

Suatu persoalan algorima dispesifikasi dengan mendeskripsi kumpulan lengkap instan dimana algoritma harus bekerja dan juga di nyatakan mengenai properti properti keluaran yang harus di miliki sebagai hasil dari menjalankan pada instan instan itu. Algoritma adalah satu prosedur yang masuknya suatu instan masukan yang mungkin dan mentransformasi menjadi keluaran yangdi kehendaki.

Contoh :

Persoalan pengurutan :

Masukan : satu sekuen n kunci a₁, a₂, a₃, … , a_n

Keluaran : permutasi (penyusunan ulang) sekuen masukan sehingga

a1, ‘< a₂’< a₃’< … < a_n’

Instan pesoalan dapat berupa array nama nama seperti {mangga, apel, durian, semangka}, atau daftar angka seperti {98, 8, 7, 101, 99}.

Saat membuat program di suatu bidang, kita harus mengetahui algoritma dan struktur data yang telah di kenal di bidang itu.

4.2.2 Ciri Dan Properti Algoritma

Algoritma adalah metode pretisi untuk menyelesaikan persoalan. Algoritma di susun dari sekumpulan langkah berhingga, masing masing masing langkah mungkin memerlukan satu operasi atau lebih. Algoritma di rancang untuk menyelesaikan persoalan spesifik dengan usaha paling minimal.

Ciri ciri algoritma adalah sebagai berikut: [KNU-69, HOR-90]

1. Input – masukan, terdapat nol masukan atau lebih yang diberikan secara exsternal.

2. Output – keluaran, sedikitnya terdapat satu keliaran di hasilkan.

3. Definite – jelas, harus secara sempurna menyatakan apa yang di lakukan.

Contoh :

1. Hitung 5/0

2. Tambahkan 6 atau 7 ke x

Contoh contoh di atas tidak di ijinkan di algoritma karena alasan berikut :

Pada Kasus Pertama :

Tidak jelas apa yang di peroleh dari hasil operasi itu.

Pada Kasus Kedua :

Tidak jelas apa yang harus di lakukan.

4. Efective – efektif, setiap instruksi harus dapat di lakukan secara manual menggunakan pensil dan kertas selama sejumlahwaktu yang berhingga.

5. Terminate – berakhir, harus berhenti setelah sejumlah operasi.

Persoalan di sebut dapat di selesaikan secara algoritma jika dapat di tulis program komputer yang dapat menghasilkan jawaban benar untuk sembarang masukan (yang di spesifikasi) dalam waktu berhingga danmenggunakan waktu ruang memori yang tersedia.

Properti properti algoritma :

1. Kebenaran algoritma adalah properti yang harus secara hati hati di tunjukan.

2. Algoritma dapat di pahami dan di pelajari ecara tidak bergantung mesin.

3. Notasi “-O” dan analisis kasus terburuk merupakan sarana yang secara mudah menyederhanakan pembandingan efisiensi algoritma algoritma.

4. Kita mencari algoritma algoritma yang memiliki waktu berjalan yang tumbuh secara logaritmik karena logaritma berbasis 2 tumbuh sangat perlahan dengan meningkatnya masukan.

5. Memodelkan program dengan struktur data dan algoritma yang terdefinisi bagus adalah satulangkah paling penting menuju solusi yang bagus.

4.2.3 Perancangan Algoritma

Perancangan algoritma merupakan satu seni “seni”. Terdapat sejumlah strategi umum untuk menuntun menghasilkan algoritma efektif dalam menyelesaikan satu kelas persoalan. Strategi perancangan algoritma yang popular antara lain :

1. Strategi greedy

2. Strategi divide-and-conquer

3. Strategi pemprograman dinamis (dynamic programming)

4. Strategi backtracking

5. Strategi branch-and-bound

6. Strategi pencarian dan penelusuran (search-and-traversal)

7. Strategi pemprograman linear

8. Strategi pemprograman integer

9. Strategi algoritma genetik

10. Strategi neural network

Pada satu persoalan dapat di terapkan lebih dari satu strategi. Masing masing strategi dapat membentuk beberapa algoritma. Pada saat awal penerapan strategi belum tentu di peroleh algoritma berkinerja bagus. Tahap analisis algoritma membuat analisis terhadap kinerja algoritma algoritma. Analisis algoritma dapat menentukan segmen/bagian algoritma yang paling banyak mengkonsumsi waktu. Dengan demikian dapat di arahkan usaha untuk membuat optimal algoritma.

Terdapat banyak contoh keberhasilan strategi divide-and-conquer.

1. Algoritma fast fourier transform Cooly dan Tukey, dengan waktu O(n²log n).

2. Algoritma perkalian bilangan bulat Schonhage dan Strassen, dengan waktu O(n ²log n ²log n ²log n).

3. Algoritma perkalian matriks Strassen, dengan waktu O(n^2,81)

4. Algoritma perkalian bilangan bulat Karasutba dan Ofman, dengan waktu O(n^1,59)

5. Aritmatika modular, dan interpolasi dan evaluasi polinom Moenck dan Borodin.

4.2.4 Pengukuran Kebaikan Algoritma

Analisis Kualitatif

Analisis kualitatif memeriksa kebenaran algoritma kebenaran algoritma dengan menelusuri algoritma. Penelusuran logik untuk membuktikan kebenaran atau implementasi algoritma. Kualitas algoritma mengharuskan kebenaran boolean, yaitu suatu algoritma adalah benar atau salah, tidak ada kondisi di tengah tengah.

Contoh :

Algoritma tidak dapat di sebut sebagai algoritma pengurutan bila algoritma tidak dapat mengurut sembarang barisan data.

Analisis Kuantitatif

Analisis kuantitatif adalah analisis efisiensi algoritma dengan menghitung kompleksitas komputasi (waktu) dan ruang. Aspek kuantitatif mengukur seberapa besar sumber daya yang di perlukan algoritma. Terdapat dua sumber daya yang penting yang biasanya di ukur, yaitu :

1. Seberapa cepat algoritma bekerja.

2. Seberapa ruang yang di perlukan agar algoritma bekerja.

Kedua sumber daya di ukur untuk menunjukan kompleksitas algoritma .

Kita memerlukan cara presisi namun menghilangkan rincian seperti kecepatan pemproses, kualitas kompilator (juga pemprogram). Kita ingin membandingkan kebutuhan waktu dan ruang yang di perlukan algoritma independen bahasa pemprograman, pemprograman, kompilator, arsitektur mesin, dan faktor faktorrumit lainya.

Pencarian algoritma yang paling efisien

Pencarian algoritma paling efisien merupakan usaha yang sangat melelahkan dan memerlukan waktu yang lama. Pada satu program aplikasi biasanya terdapat bagian utama yang mengambil mayoritas waktu komputasi . Prinsip 90/10 biasanya dapat di terapkan, yaitu program pada umumnya 90% waktu berjalanya berada di bagian 10% program. Mengoptimasi 90% bagian program yang jarang di eksekusi akan berdampak kecil bagi peningkatan kinerja program. Kita seharusnya lebih berfokus pada optimasi bagian 10% program yang paling sering di eksekusi. Untuk mengetahui bagian tersebut maka kakas profiler membantu untuk mengetahuinya.