Sejarah Algoritma dan Pemograman

SEJARAH ALGORITMA

Dalam MATEMATIKA dan KOMPUTASI, algoritma atau algoritme merupakan kumpulan perintah untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria, dalam hal ini berbeda dengan HEURISTIK. Algoritma sering mempunyai langkah pengulangan (ITERASI) atau memerlukan keputusan (LOGIKA BOOLEAN dan PERBANDINGA) sampai tugasnya selesai.

Desain dan analisa algoritma adalah suatu cabang khusus dalam ilmu komputer yang mempelajari karakteristik dan performa dari suatu algoritma dalam menyelesaikan masalah, terlepas dari implementasi algoritma tersebut. Dalam cabang disiplin ini algoritma dipelajari secara abstrak, terlepas dari sistem komputer atau bahasa pemrograman yang digunakan. Algoritma yang berbeda dapat diterapkan pada suatu masalah dengan kriteria yang sama.

Kompleksitas dari suatu algoritma merupakan ukuran seberapa banyak komputasi yang dibutuhkan algoritma tersebut untuk menyelesaikan masalah. Secara informal, algoritma yang dapat menyelesaikan suatu permasalahan dalam waktu yang singkat memiliki kompleksitas yang rendah, sementara algoritma yang membutuhkan waktu lama untuk menyelesaikan masalahnya mempunyai kompleksitas yang tinggi.

Kata algoritma berasal dari latinisasi nama seorang ahli matematika dari Uzbekistan Al Khawarizmi (hidup sekitar abad ke-9), sebagaimana tercantum pada terjemahan karyanya dalam bahasa latin dari abad ke-12 "Algorithmi de numero Indorum". Pada awalnya kataAlgorisma adalah istilah yang merujuk kepada aturan-aturan aritmetis untuk menyelesaikan persoalan dengan menggunakan bilangan numerik arab (sebenarnya dari India, seperti tertulis pada judul di atas). Pada abad ke-18, istilah ini berkembang menjadialgoritma, yang mencakup semua prosedur atau urutan langkah yang jelas dan diperlukan untuk menyelesaikan suatu permasalahan.

SEJARAH PEMOGRAMAN

Pada tahun 1822, Charles Babbage seorang mahasiswa di Universitas Cambridge Inggris mengembangkan sebuah mesin untuk mengelola data-data agar mudah digunakan, mesin tersebut diberi nama ‘Difference Enggine’.

Setelah bekerja selama 10 tahun pada mesinnya, Charles Babbage menyadari bahwa mesin yang dia ciptakan ini merupakan sebuah mesin yang bersifat single-purpose machine artinya hanya bisa menghasilkan satu jenis keluaran (output). Selanjutnya ia mengembangkan mesin lain yang bersifat multi-purpose. Mesin ini diberi nama ‘Analytical Engine’. Pekerjaan untuk membuat ‘Analytical Engine’ ini ia lakukan sampai dengan tahun 1842.

ada tahun 1847, Charles Babbage kembali menyempurnakan ‘Difference Engine’ hingga pada tahun 1849 ia berhasil membuat versi keduanya. Pekerjaan menyempurnakan hasil-hasil karyanya terus ia lakukan, bahkan dilanjutkan oleh anaknya, Henry Prevost. Charles Babbage sendiri meninggal pada tahun 1871. Untuk melindungi karya-karya ayahnya, Henry Prevost membuat beberapa kopian unit perhitungan aritmatika sederhana dari mesin yang dihasilkan ayahnya dan mengirimkannya ke beberapa institusi di dunia, termasuk ke Universitas Harvard.

Perkembangan dunia komputasi berlanjut pada tahun 1854, ketika seseorang bernama Charles Boole berhasil menciptakan sebuah sistem logika simbolik yang diberinama Logika Boole. Sistem ini mencakup pula logika untuk menyatakan hubungan lebih besar, lebih kecil, sama dengan dan tidak sama dengan. Sistem logika ini masih digunakan sampai dengan saat ini.

Pada tahun 1890, Amerika Serikat ingin melakukan sensus penduduk. Namun kendala yang muncul adalah keterbatasan alat yang ada pada waktu itu, mengingat jumlah penduduk yang semakin meningkat setiap tahunnya, maka diadakanlah sebuah kompetisi komputasi untuk mencari solusinya. Kompetisi ini dimenangkan oleh Herman Hollerith, yang akhirnya ia mendirikan sebuah perusahaan Hollerith Tabulating, Co. yang akhirnya berubah nama menjadi CTR (Calculating Tabulating Recording Company) setelah 3 perusahan lain ikut bergabung. Sepuluh tahun berikutnya perusahaan ini berganti nama lagi menjadi IBM (International Business Machine) hingga saat ini.

Selanjutnya perkembangan komputasi digital mulai berjalan pelan dan jarang digunakan dalam dunia bisnis sampai dengan pertengahan tahun 1920-an. Hingga pada tahun 1925, MIT (Massachusette Institute of Technology) mengembangkan sebuah mesin yang mampu menganalisis perhitungan differensiasi dan integrasi. Mesin yang didanai oleh Yayasan Rockefeller ini dapat dikatakan sebagai komputer terbesar di dunia pada tahun 1930.

Pada tahun 1935, seorang ilmuan Jerman bernama Konrad Zuse mengembangkan komputer Z-1, komputer inilah yang menjadi awal mula diterapkannya sistem biner dalam kinerjanya. Selain itu, Zuse juga berjasa dalam komputasi komputer digital ketika ia menciptakan bahasa pemrograman komputer pertama ‘Plankalkul’.

Pada tahun 1945, terjadi pula peristiwa penting dalam sejarah perkembangan komputasi komputer digital yaitu ketika terjadi kerusakan pada mesin Mark II yang ada di Universitas Harvard. Seseorang yang bernama Grace Murray Hopper yang mengetahui hal ini langsung menyelidiki sebab kerusakannya. Akhirnya dia menemukan seekor ngengat yang terjebak dalam mesin tersebut. Dalam catatan hariannya, Hopper menuliskan: “First actual case of bug being found”. Dia menyebut ngengat ini sebagai sebuah kutu busuk (bug), selanjutnya kata ‘bug’ ini sering digunakan untuk menunjukkan adanya ketidakberesan dalam program. Dari kata ‘bug’ ini muncul pula istilah ‘debugging’ yang artinya proses pembetulan kesalahan program.

Pada tahun 1954, IBM mulai mengembangkan bahasa pemrograman FORTRAN (FORmula TRANslator). Bahasa FORTRAN merupakan bahasa pemrograman level tinggi pertama yang dikomersialkan. Pemrograman level tinggi maksudnya adalah perintah atau kodenya mudah dibaca dan dipahami oleh manusia.

Pada tahun 1958, FORTRAN II dan ALGOL dipublikasikan bersamaan dengan diluncurkannya LISP. Sedangkan pada tahun 1959, bahasa pemrograman COBOL juga diluncurkan. Sejak saat itu perkembangan bahasa pemrograman berkembang sangat cepat.

Pada tahun 1970, bahasa PASCAL mulai dipublikasikan dan hingga saat ini masih banyak digunakan untuk keperluan pendidikan. Selain itu muncul pula dua bahasa pemrograman yang dianggap sangat penting yaitu SMALLTALK dan B-Languange. SMALLTALK penting karena merupakan bahasa pemrograman berbasis obyek yang pertama. Sedangkan B-Languange dikatakan penting karena merupakan cikal bakal munculnya bahasa C. Dengan bahasa C, pemrograman akan lebih mudah, efisien, dan fleksibel.

Pada tahun 1975, Dr. Wong merilis bahasa pemrograman hasil ciptaannya bernama TinyBASIC. TinyBASIC merupakan bahasa pemrograman pertama yang bersifat free alias tidak membayar dalam penggunaannya. Pada tahun yang sama, Bill Gates dan Paul Allen juga membuat bahasa pemrograman yang diberi nama BASIC. BASIC ini selanjutnya mereka jual ke MIT.

Bahasa pemrograman terus berkembang demikian pesat hingga saat ini. Hal ini ditandai dengan semakin banyaknya bahasa pemrograman yang bermunculan.

REFERENSI:

http://id.wikipedia.org/wiki/Algoritma

http://id.wikipedia.org/wiki/Algoritma

REKURSI

Apa itu REKURSI ???

Suatu obyek disebut sebagai rekursif apabila sebagian berisi atau didefinisikan sebagai dirinya sendiri. Dengan demikian rekursif adalah suatu proses berupa pemanggilan diri berupa statement perulangan. Proses rekursif juga memungkinkan terjadinya komputasi yang tidak berkesudahan sampai memory yang digunakan tidak dapat menampung lagi, sehingga perlu diperhatikan akan adanya kondisi untuk menghentikan proses eksekusi program . Sebagai contoh sederhana mengenai proses rekursif adalah proses menghitung nilai faktorial dari bilangan bulat positif dan mencari deret fibonnaci dari suatu bilangan bulat, permainan menara hanoi dan sebagainya. II-12

Rekursi adalah konsep pengulangan yang penting dalam ilmu komputer. Konsep ini dapat digunakan untuk merumuskan solusi sederhana dalam sebuah permasalahan yang sulit untuk diselesaikan secara iteratif dengan menggunakan loop for, while do. Pada saat tertentu konsep ini dapat digunakan untuk mendefinisikan permasalahan dengan konsisten dan sederhana. Pada saat yang lain, rekursi dapat membantu untuk mengekspresikan algoritma dalam sebuah rumusan yang menjadikan tampilan algoritma tersebut mudah untuk dianalisa.

Cara lain untuk menyelesaikan permasalahan di atas adalah dengan cara rekursi, dimana n! adalah hasil kali dari n dengan (n-1)!. Untuk menyelesaikan (n-1)! adalah sama dengan n!, sehingga (n-1)! adalah n-1dikalikan dengan (n-2)!, dan (n-2)! adalah n-2 dikalikan dengan (n-3)! dan seterusnya sampai dengan n = 1, kita menghentikan penghitungan n! Cara rekursif untuk permasalahan ini, secara umum dapat kita detailkan sebagai berikut:

1 jika n=0, n=1

F(n) =

nF(n-1) jika n>1

dua fase dasar dari sebuah proses rekursi: fase awal dan fase balik. Dalam fase awal, masing-masing proses memanggil dirinya sendiri. Fase awal ini berhenti ketika pemanggilan telah mencapai kondisi terminal. Sebuah kondisi teminate adalah kondisi dimana sebuah fungsi rekursi kembali dari pemanggilan, artinya fungsi tersebut sudah tidak memanggil dirinya sendiri

dan kembali pada sebuah nilai. Sebagai contoh, dalam penghitungan faktorial dari n, kondisi terminal adalah n = 1, n = 0. Untuk setiap fungsi rekursi, minimal harus ada satu kondisi terminal. Setelah fase awal selesai, kemudian proses melanjutkan pada fase balik, dimana fungsi sebelumnya akan dikunjungi lagi dalam fase balik ini. Fase ini berlanjut sampai pemanggilan awal, hingga secara lengkap proses telah berjalan.

Rekursi Tail

Sebuah proses rekursi dikatakan rekursi tail jika pernyataan terakhir yang akan dieksekusi berada dalam tubuh fungsi dan hasil yang kembali pada fungsi tersebut bukanlah bagian dari fungsi tersebut. Ciri fungsi rekursi tail adalah fungsi tersebut tidak memiliki aktivitas selama fase balik. Ciri ini penting, karena sebagian besar compiler modern secara otomatis membangun kode untuk menuju pada fase tersebut. Ketika kompiler mendeteksi sebuah pemanggilan yang mana adalah rekursi tail, maka kompiler menulis aktivitas yang ada sebagai sebuah record yang dimasukkan ke dalam stack. Kompiler dapat melakukan hal tersebut karena pemanggilan rekursi adalah pernyataan terakhir yang dieksekusi dalam aktivitas yang sedang berlangsung, sehingga tidak ada aktivitas yang harus dikerjakan pada saat pemanggilan kembali. Untuk memahami bagaimana sebuah rekursi tail bekerja, kita akan kembali membahas tentang penghitungan komputasi dari faktorial secara rekursi. Sebagai langkah awal, akan sangat membantu jika kita memahami alasan dalam definisi awal yang bukan rekursi tail. Dimana dalam definisi tersebut, penghitungan n! adalah dengan mengalikan n dengan (n-1)! dalam setiap aktivitas, yang mana hal tersebut terus diulang dari n = n –1 sampai n = 1. Definisi ini bukanlah rekursi tail karena nilai yang dikembalikan dalam setiap aktivitas bergantung pada perkalian n dengan nilai yang dikembalikan oleh aktivitas sesudahnya. Oleh karena itu, pencatatan aktivitas dari masing-masing pemanggilan harus diingat dalam stack sampai nilai-nilai yang dikembalikan dalam aktivitas-aktivitas sesudahnya telah terdefinisi. Sekarang marilah kita melihat bagaimana rekursi tail didefinisikan untuk menghitung n!, yang secara formal kita definisikan sebagai berikut:

a jika n=0, n=1

F(n,a) =

F(n-1,na) jika n>1

Pada definisi ini digunakan parameter kedua, yaitu a, yang mana merupakan nilaiutama dari penghitungan faktorial secara rekursif. Hal ini mencegah kita untuk mengalikan nilai yang dikembalikan dalam setiap aktivitas dengan n. Dalam masingmasing pemanggilan rekursi kita mendefinisikan a = na dan n = n – 1. Kita melanjutkan sampai n = 1, sebagai kondisi terminal. Dalam gambar 5.2 menggambarkan proses komputasi 4! dengan menggunakan rekursi tail. Perhatikan bahwa di sana tidak ada aktivitas selama fase balik.

Kesimpulan

1. Rekursi adalah kemampuan suatu rutin untuk memanggil dirinya sendiri.

2. Penggunaan sebuah rekursi harus mendefinisikan kondisi terminal, jika tidak

eksekusi program tidak pernah berhenti, sehingga penggunaan memori

tumpukan habis dan komputer akan hang.

3. Dalam beberapa situasi, pemecahan secara rekursif mempunyai keuntungan

dan kekurangan yang dapat diperbandingkan dengan cara iteratif.

Referensi:

http://lecturer.eepis-its.edu/~entin/Struktur%20Data%20&%20Algoritma/buku/Data%20Structure%20-%20Bab%205.pdf

SUBRUTIN

Ada dua macam subrutin pada Pascal, yaitu prosedur dan fungsi.

Prosedur adalah bagian dari program yang dibuat terpisah untuk melaksanakan sebagian dari tugas yang harus diselesaikan oleh suatu program. Sedangkan fungsi adalah bagian dari program yang dibuat terpisah untuk melakukan fungsi tertentu yang menghasilkan suatu nilai untuk dikembalikan ke program utama.

Keduanya mempunyai kegunaan yang sama, yaitu melakukan tugas tertentu. Perbedaannya kalau fungsi selalu mengembalikan suatu nilai setelah dipanggil sedangkan prosedur tidak.

Manfaat pembuatan SUBRUTIN:

• modularisasi: suatu program yang besar dan kompleks dapat dibagi ke dalam beberpa prosedur sehingga setiap prosedur merupakan bagian yang mudah dikerjakan. dengan demikian, program besar tersebut menjadi mungkin diselesaikan.
• simplifikasi: dalam suatu program, sering diperlakukan suatu tugas yang harus dikerjakan berulang-ulang dengan nilai-nilai variabel yang berbeda. Agar tidak merepotkan maka tugas ini cukup ditulis sekali saja dalam bentuk subrutin yang kemudian dipanggil berulang-ulang sesuai kebutuhan.

Selain itu, bila terjadi kesalahan dalam suatu program yang besar maka kita hanya cukup bekerja/memperbaiki program-program kecil (subrutin) tadi saja.

Prosedur dan fungsi merupakan sub program yang sangat bermanfaat dalam pemrograman, terutama untuk program atau proyek yang besar. Manfaat penggunaan sub program antara lain adalah :

Prosedur dan fungsi merupakan sub program yang sangat bermanfaat dalam pemrograman, terutama untuk program atau proyek yang besar. Manfaat penggunaan sub program antara lain adalah :

1. meningkatkan readibility, yaitu mempermudah pembacaan program
2. meningkatkan modularity, yaitu memecah sesuatu yang besar menjadi modul-modul atau bagian-bagian yang lebih kecil sesuai dengan fungsinya, sehingga mempermudah pengecekan, testing dan lokalisasi kesalahan.
3. meningkatkan reusability, yaitu suatu sub program dapat dipakai berulang kali dengan hanya memanggil sub program tersebut tanpa menuliskan perintah-perintah yang semestinya diulang-ulang.

Sub Program Rekursif adalah sub program yang memanggil dirinya sendiri selama kondisi pemanggilan dipenuhi.

adalah Dengan melihat sifat sub program rekursif di atas maka sub program rekursif harus memiliki :

1. kondisi yang menyebabkan pemanggilan dirinya berhenti (disebut kondisi khusus atau special condition)
2. pemanggilan diri sub program (yaitu bila kondisi khusus tidak dipenuhi)

Secara umum bentuk dari sub program rekursif memiliki statemen kondisional :

if kondisi khusus tak dipenuhi
then panggil diri-sendiri dengan parameter yang sesuai
else lakukan instruksi yang akan dieksekusi bila kondisi khusus dipenuhi

Sub program rekursif umumnya dipakai untuk permasalahan yang memiliki langkah penyelesaian yang terpola atau langkah-langkah yang teratur. Bila kita memiliki suatu permasalahan dan kita mengetahui algoritma penyelesaiannya, kadang-kadang sub program rekursif menjadi pilihan kita bila memang memungkinkan untuk dipergunakan. Secara algoritmis (dari segi algoritma, yaitu bila kita mempertimbangkan penggunaan memori, waktu eksekusi sub program) sub program rekursif sering bersifat tidak efisien .
Dengan demikian sub program rekursif umumnya memiliki efisiensi dalam penulisan perintah, tetapi kadang tidak efisien secara algoritmis. Meskipun demikian banyak pula permasalahan-permasalahan yang lebih sesuai diselesaikan dengan cara rekursif (misalnya dalam pencarian / searching, yang akan dibahas pada pertemuan-pertemuan yang akan datang).

Referensi:

http://jauharotul.wordpress.com/2010/12/22/subrutin/

http://ftikom-unmul.nstars.org/t403-prosedur-dan-fungsi-rekursif

STRUKTUR PENGULANGAN

BENTUK - BENTUK PERULANGAN

Dalam hampir setiap program yang kompleks mutlak memerlukan suatu perulangan dan percabangan. Tujuan perulangan disini adalah untuk mengulang statement atau blok statement berulang kali sesuai sejumlah yang ditentukan pemakai. Dalam materi ini akan memberikan gambaran konsep dasar dari pengertian diatas.

Perulangan FOR

Perulangan dengan statemen FOR digunakan untuk mengulang statemen atau suatu blok statemen berulang kali. Perulangan dengan statemen FOR dapat berupa perunlangan positif dan perulangan negatif.

Perulangan FOR positif

Contoh :
Perulangan positif untuk satu statement :
USES CRT;
VAR

i : INTEGER;

BEGIN

FOR i := 1 TO 5 DO WRITELN('STMIK GUNADARMA');

END.

Maka bila program diatas dicompile

hasilnya :
STMIK GUNADARMA
STMIK GUNADARMA
STMIK GUNADARMA
STMIK GUNADARMA
STMIK GUNADARMA

Penjelasan : Berati statemen STMIK GUNADARMA akan diulang sebanyak 5 kali yaitu

dengan menghitung nilai i dari i ke 1 sampai nilai i terakhir yaitu i ke 5.

Contoh dengan menggunakan blok statement:

Cara penulisannya dengan pada awal blok diawali dengan BEGIN dan pada

akhir blok diakhiri dengan END;

Perulangan FOR negatif

Perulangan negatif adalah perulangan dengan menghitung (counter) dari besar ke kecil. Statement yang digunakan adalah FOR-DOWNTO-DO

Contoh :
USES CRT;
VARi : INTEGER ;

BEGIN

FOR i := 10 DOWNTO 1 DO WRITE(i:3);

END.

Hasil :

10 9 8 7 6 5 4 3 2 1

Perulangan FOR berserang

Perulangan FOR berserang adalah perulangan FOR yang berada pada perulangan yang lainnya. Perulangan yang lebih dalam akan diproses terlebih dahulu sampai habis, kemudian perulangan yang lebih luar baru akan bertambah, mengerjakan perulangan yang lebih dalam lagi mulai dari nilai awalnya dan seterusnya.

Contoh :

VAR

a,b : INTEGER;

BEGIN

FOR a := 1 TO 3 DO

BEGIN
FOR b := 1 TO 2 DO WRITE(a :4,b:2);
WRITELN;
END;

END.

Hasil :

11 12 21 22 31 32

Perulangan WHILE

Penyeleksian kondisi digunakan untuk agar program dapat menyeleksi kondisi, sehingga program dapat menentukan tindakan apa yang harus dikerjakan, tergantung dari kondisi yang diseleksi tersebut. Perulangan WHILE-DO tidak dilakukan jika kondisi tidak terpenuhi.

Contoh :
USES CRT;
VAR i : INTEGER;
BEGIN
i := 0;
WHILE i < 5 do

Perulangan REPEAT-UNTIL

Pada pernyataan repeat-until dan while-do, pada dasarnya hampir sama yaitu digunakan jika jumlah pengulangan belum dapat ditentukan. Tetapi terdapat perbedaan yaitu pada pengecekan kondisi. Jika pada pernyataan while-do, kondisi dicek pada awal blok pengulangan, pada pernyataan repeat-until, kondisi dicek pada akhir blok pengulangan.

Pada pernyataan repeat-until dan while-do, pada dasarnya hampir sama yaitu digunakan jika jumlah pengulangan belum dapat ditentukan. Tetapi terdapat perbedaan yaitu pada pengecekan kondisi. Jika pada pernyataan while-do, kondisi dicek pada awal blok pengulangan, pada pernyataan repeat-until, kondisi dicek pada akhir blok pengulangan.

3.1.2 Pengulangan Repeat …. Until

Repeat ; …… ; ; until atau
Repeat

;
…….
…….
;

until

Referensi:

http://elib.unikom.ac.id/download.php?id=45364

http://www.scribd.com/doc/13854460/Modul-Pascal