Moh Edi Wibowo ALGORITMA DALAM KAITANNYA DENGAN KOMPUTER
I. Pendahuluan Algoritma digunakan dalam banyak hal, mulai dari hal-hal kecil dalam kehidupan seharihari sampai pada ilmu pengetahuan modern. Saat ini, algoritma sangat sering dikaitkan dengan penyelesaian masalah menggunakan komputer, misalnya algoritma Quicksort, algoritma FFT (Fast Fourier Transform), algoritma Genetika, algoritma Metropolis, dan lain sebagainya.
II. Definisi Algoritma dalam Kaitannya dengan Komputer Algoritma adalah suatu urutan langkah-langkah (steps) yang disusun secara logis untuk menyelesaikan masalah dengan menggunakan komputer, dengan kriteria sebagai berikut : 1. Setiap langkah/step harus jelas dan pasti (definite). Contoh : Tambahkan nilai X dengan 1 atau 2
X = X + (1 atau 2)
Langkah di atas tidak definite, agar definite (1 atau 2) dipilih secara RANDOM X = X + (random(2) + 1) 2. Diperbolehkan tanpa ada input, tetapi minimal harus ada 1 output. 3. Jumlah langkah harus berhingga atau dengan kata lain harus ada stopping criteria. Berikut ini adalah contoh algoritma yang dibuat untuk dijalankan (dieksekusi) pada komputer :
procedure menampilkan_luas_lingkaran {Algoritma yang akan menampilkan luas lingkaran jika diberikan input berupa nilai dari jari-jari lingkaran} r baca input l 3,1415926535897932384626433832795*r*r tulis output l
Algoritma di atas langkah-langkahnya definite, memiliki input maupun output, dan memiliki jumlah langkah yang berhingga (3 langkah).
1
Moh Edi Wibowo III. Algoritma sebagai Salah Satu Subbidang dalam Ilmu Komputer Ilmu Komputer (Computer Science) adalah ilmu pengetahuan yang berisi tentang teori, metodologi, desain dan implementasi, yang berhubungan dengan komputasi, komputer, dan algoritmanya dalam perspektif perangkat lunak (software) maupun perangkat keras (hardware) [1]. Ilmu Komputer sangat berkaitan erat dengan algoritma, hampir semua bidang dari Ilmu Komputer (Computer Science) tidak terlepas dari algoritma. Bahkan pada saat ini, studi tentang algoritma telah menjadi subbidang khusus dalam Ilmu Komputer. Studi atau ilmu yang mempelajari tentang algoritma sering disebut dengan istilah algorithmics [2]. Salah satu pengklasifikasian Ilmu Komputer yang ada diilustrasikan dalam bentuk Matriks Dennings yang diciptakan oleh Peter J. Dennings[3][4]. Matriks Dennings ini mengalami beberapa perbaikan, dimana versi terakhir adalah versi tahun 1999 [4][5]. Dalam versi terakhir ini Ilmu Komputer terbagi dalam 12 subbidang (versi sebelumnya adalah 9 subbidang) yaitu : Algoritma dan Struktur Data (Algorithms and Data Structures) Arsitektur (Architecture)
Bahasa Pemrograman (Programming Languages) Sistem Operasi dan Jaringan (Operating Systems and Networks) Database dan Sistem Retrieval Informasi Software Engineering (Database and Information Retrieval Systems) Grafik Artificial Intelligence and Robotics (Graphics) Ilmu Komputasi Human Computer Interaction (Computational Sciences) BioInformatika Organizational Informatics (BioInformatics) Diambil dari IlmuKomputer.Com 2003 Dennings memberi catatan khusus untuk bidang BioInformatika sebagai bidang baru yang merupakan gabungan antara Ilmu Komputer dan Biologi, dan saat ini mengalami perkembangan yang cukup signifikan. Pengklasifikasian Ilmu Komputer yang lain dibuat oleh Association for Computing Machinary (ACM) dan dapat dilihat melalui http://www.acm.org.
IV. Analisis Algoritma Ketika menyelesaikan suatu masalah, seringkali tersedia berbagai algoritma yang berbeda. Untuk memilih salah satu di antara algoritma-algoritma tersebut maka perlu diketahui terlebih dahulu efisiensi dari masing-masing algoritma yang ada. Analisis 2
Moh Edi Wibowo algoritma (analysis of algorithms) merupakan suatu alat yang dapat digunakan untuk mengetahui efisiensi tersebut. Untuk melakukan analisis terhadap algoritma, tidak ada suatu formula yang tetap, mudah, dan ringkas. Proses analisis lebih bertumpu pada pertimbangan (judgement), intuisi, dan pengalaman [2]. Contoh : Dengan analisis algoritma, dapat diketahui bahwa pengurutan bilangan dapat dilakukan secara lebih efisien dengan menggunakan algoritma Heapsort dibanding dengan algoritma Bubblesort. Analisis algoritma menjadi bagian yang tidak terpisahkan dari algorithmics.
V. Pemrograman Pemrograman berarti : Memberikan instruksi kepada komputer agar dapat bekerja seperti yang kita kehendaki. Dengan demikian, program berarti : Rangkaian instruksi yang dapat dijalankan oleh komputer beserta data yang diolah untuk menyelesaikan masalah. • •
Instruksi yang dapat ‘dipahami’ dan kemudian dijalankan oleh komputer adalah bahasa mesin yang berbentuk biner (rangkaian bit-bit bernilai 0 atau 1). Data yang dapat ‘dipahami’ oleh komputer ialah data yang berbentuk biner pula.
Jadi, program berbeda dengan algoritma. Program berupa urutan instruksi yang harus dapat ‘dipahami’ dan dijalankan oleh komputer, sedangkan instruksi (langkah) pada algoritma tidak harus dapat ‘dimengerti’ oleh komputer. Dapat dikatakan bahwa program adalah realisasi algoritma dalam bentuk suatu bahasa yang dapat ‘dimengerti’ oleh komputer. Seperti telah dijelaskan di atas bahwa instruksi yang dapat ‘dipahami’ oleh komputer ialah instruksi dalam bahasa mesin. Padahal manusia sangat kesulitan ketika harus menyusun sebuah program dalam bahasa mesin. Manusia terbiasa dengan bahasa yang lebih verbal seperti bahasa Inggris, bahasa Indonesia, notasi aritmetika, diagram, dan sebagainya. Oleh karena itu, dibuatlah bahasa pemrograman yang berfungsi untuk menjembatani apa yang dikehendaki/dimengerti oleh manusia dengan apa yang dimengerti oleh komputer. Orang yang menulis suatu program dengan menggunakan bahasa pemrograman tertentu disebut programmer. Berdasarkan kedekatannya kepada ‘bahasa manusia’, maka bahasa pemrograman dikelompokkan menjadi 3, yaitu : a. Bahasa pemrograman tingkat rendah Bahasa pemrograman tingkat rendah merupakan ‘bahasa ibu’ dari komputer, yaitu bahasa yang tidak memerlukan penterjemah untuk dapat dipahami dan dimengerti
3
Moh Edi Wibowo oleh komputer. Atau dengan kata lain untuk berkomunikasi secara langsung dengan komputer orang perlu menggunakan bahasa tingkat rendah. Contoh dari bahasa pemrograman tingkat rendah ialah bahasa mesin (machine language). Sebagai catatan, bahasa rakitan (assembly) juga sering dimasukkan ke dalam bahasa pemrograman tingkat rendah. Meskipun demikian, bahasa assembly tidak dapat ‘dipahami’ secara langsung oleh komputer, bahasa assembly tersebut perlu diterjemahkan ke dalam bahasa mesin oleh suatu program penerjemah yang disebut assembler. b. Bahasa pemrograman tingkat tinggi Bahasa ini memiliki kedekatan dengan bahasa dan cara berpikir manusia. Bahasa pemrograman tingkat tinggi mempunyai ciri bahwa penulisannya mirip dengan bahasa sehari-hari (bahasa Inggris). Contoh bahasa pemrograman tingkat tinggi adalah bahasa BASIC, Cobol, FORTRAN, Pascal, dan lain-lain. c. Bahasa pemrograman tingkat menegah Merupakan bahasa yang terletak di antara bahasa pemrograman tingkat tinggi bahasa pemrograman tingkat rendah, contohnya adalah bahasa C.
dan
Program yang ditulis dengan bahasa pemrograman tingkat tinggi maupun tingkat menengah tidak dapat langsung ‘dimengerti’ oleh komputer, dan harus diterjemahkan dahulu ke dalam bahasa mesin oleh sebuah ‘penerjemah’ yang disebut kompiler. Untuk lebih jelasnya perhatikan gambar berikut :
Algoritma
Algoritma
translasi (oleh programmer) Program dalam bahasa tingkat tinggi/menengah
translasi (oleh programmer) Program dalam bahasa assembly
kompilasi (oleh kompiler)
penerjemahan (oleh assembler)
Program dalam bahasa mesin
Selain pembagian menjadi kelompok-kelompok di atas, bahasa pemrograman dapat diklasifikasikan berdasarkan kriteria-kriteria yang lain, misalnya berdasarkan terapannya bahasa pemrograman dapat dibagi menjadi bahasa pemrograman bertujuan khusus dan bahasa pemrograman bertujuan umum.
4
Moh Edi Wibowo Berikut ini adalah contoh algoritma dan programnya yang ditulis dengan bahasa Pascal dan C. Algoritma : procedure menampilkan_luas_lingkaran {Algoritma yang akan menampilkan luas lingkaran jika diberikan input berupa nilai dari jari-jari lingkaran} r baca dari perangkat input l 3,1415926535897932384626433832795*r*r tulis ke perangkat output l
Bahasa Pascal : lingkaran.pas program menampilkan_luas_lingkaran; var r, l: real; begin write(’Masukkan jari-jari lingkaran : ’); readln(r); l := 3.1415926535897932384626433832795*r*r; writeln(’Luas lingkaran : ’, l); end.
Bahasa C : lingkaran.c #include <stdio.h> int main() { float r, l; printf("Masukkan jari-jari lingkaran : "); scanf("%f", &r); l = 3.1415926535897932384626433832795*r*r; printf("\nLuas lingkaran : %f\n", l); }
Perhatikan bahwa kedua program di atas ditulis pada file yang bernama lingkaran.pas dan lingkaran.c. Program yang belum diterjemahkan ke dalam bahasa mesin seperti file lingkaran.pas dan lingkaran.c sering disebut sebagai program sumber (source program). Ketika diterjemahkan oleh kompiler pada sistem operasi DOS, kedua program sumber tersebut akan menjadi file lingkaran.exe. File lingkaran.exe adalah program
5
Moh Edi Wibowo dalam bahasa mesin yang dapat langsung dijalankan oleh komputer. Program yang merupakan hasil penerjemahan program sumber seperti file lingkaran.exe sering disebut sebagai program obyek (object program).
Algoritma
program sumber
Program dalam bahasa tingkat tinggi/menengah (lingkaran.pas/lingkaran.c)
program obyek
Program dalam bahasa mesin (lingkaran.exe)
VI. Kompiler dan Interpreter Kompiler (compiler), merupakan program yang menerjemahkan program yang ditulis dalam bahasa pemrograman tingkat tinggi/menengah menjadi suatu himpunan instruksi mesin spesifik yang disimpan dalam bentuk file. Selain kompiler, perlu diketahui pula bahwa terdapat program penerjemah yang lain yaitu interpreter. Interpreter digunakan untuk menerjemahkan program yang ditulis dalam bahasa tingkat tinggi ke dalam bahasa mesin, dan menjalankannya per-instruksi. Perbedaan antara kompiler dan interpreter antara lain sebagai berikut : Kompiler
Interpreter
Kompiler menerjemahkan keseluruhan program sumber menjadi program obyek.
Interpreter menerjemahkan program sumber baris demi baris. Interpreter akan menerjemahkan sebuah instruksi kemudian mengeksekusi instruksi tersebut kemudian dilanjutkan ke baris selanjutnya.
Penerjemahan bersifat tetap dalam arti menghasilkan suatu program obyek.
Penerjemahan bersifat sementara dalam arti hasil penerjemahan baris-perbaris tidak disimpan sebagai program obyek.
6
Moh Edi Wibowo Kompiler
Interpreter
Program sumber pada umumnya hanya cocok di-compile untuk satu jenis mesin saja. Program sumber harus disesuaikan lagi isinya ketika di-compile pada mesin yang lain.
Program sumber pada umumnya cocok untuk semua jenis mesin.
Eksekusi program obyek hasil kompilasi pada umumnya lebih cepat dibanding eksekusi program sumber oleh interpreter.
Eksekusi program sumber per-instruksi pada umumnya lebih lambat dibanding eksekusi program obyek hasil kompilasi.
Berikut ini adalah gambar eksekusi program menggunakan kompiler maupun interpreter :
Program sumber
Baca satu instruksi
Terjemahkan ke bahasa mesin
Laksanakan instruksi
a) Dengan interpreter
Program sumber
Terjemahkan seluruhnya
Program obyek Eksekusi program obyek
b) Dengan kompiler
[1] Wahono, R. S., “Apa Itu Ilmu Komputer”, http://www.ilmukomputer.com (20/9/2005) [2] Brassard G. and Bratley P., “Fundamentals of Algorithmics”, Prentice Hall, New Jersey, 1996 [3] Peter Denning, et al., "Computing as a Discipline," Communications of ACM, 32, 1 (January), 9-23, 1989 [4] Peter Denning, "Computer Science: the Discipline," In Encyclopedia of Computer Science (A. Ralston and D. Hemmendinger, Eds), 1999 [5] A. Tucker, Jr. and P. Wegner, "Computer Science and Engineering: the Discipline and Its Impact," In Handbook of Computer Science and Engineering, CRC Press, Chapter 1, 1996 7
