Komputasi dan Automata (Tugas 1)

BAB I
PENDAHULUAN

           1.1.  LATAR BELAKANG

             Seiring kemajuan zaman yang semakin canggih, semua pekerjaan manusia saat ini berhbungan dengan menggunkan komputerisasi, oleh maka itu penulis akan membahasa dasar dasar dari komputer sehingga pembaca dapat memahami sedikit tentang komputer

           1.2.  RUMUSAN MASALAH

             Bermula dari latar belakang masalah tersebut, kami akan mencoba menyampaikan permasalahan antara lain :

1. Apa itu teori komputasi ?
2. Apa itu komputasi modern ?
3. Bagaimana sejarah komputasi modern ?
4. Apa itu teori automata dan bahasa?
5. Apa pengertian dari finate state machine ?
6. Apa itu mesin turing ?

           1.3.  TUJUAN

 Tujuan dari pembahasan tersebut adalah untuk mengetahui seberapa penting pendahuluan dalam karya ilmiah, yaitu untuk mengetahui :

1. Pengertian dari teori komputasi
2. Pengertian dari komputasi modern
3. Sejarah komputasi modern
4. Pengertian teori automata
5. Pengertian finate state mechine
6. Pengertian mesin turing

BAB II
PEMBAHASAN

2.1.   KOMPUTASI

            2.1.2.  TEORI KOMPUTASI

Teori komputasi adalah suatu sub-bidang dari ilmu komputer dan matematika. Selama ribuan tahun, perhitungan dan komputasi umumnya dilakukan dengan menggunakan pena dan kertas, atau kapur dan batu tulis, atau dikerjakan secara mental, kadang-kadang dengan bantuan suatu tabel. Namun sekarang, kebanyakan komputasi telah dilakukan dengan menggunakan komputer, sehingga mempercepat dalam proses perhitungan.Secara umum iIlmu komputasi adalah bidang ilmu yang mempunyai perhatian pada penyusunan model matematika dan teknik penyelesaian numerik serta penggunaankomputer untuk menganalisis dan memecahkan masalah-masalah ilmu (sains). Dalam penggunaan praktis, biasanya berupa penerapan simulasi komputer atau berbagai bentuk komputasi lainnya untuk menyelesaikan masalah-masalah dalam berbagai bidang keilmuan, tetapi dalam perkembangannya digunakan juga untuk menemukan prinsip-prinsip baru yang mendasar dalam ilmu. Teori komputasi adalah cabang ilmu komputer dan matematika yang membahas apakah dan bagaimanakah suatu masalah dapat dipecahkan pada model komputasi, menggunakan algoritma. Bidang ini dibagi menjadi dua cabang: teori komputabilitas dan teori kompleksitas, namun kedua cabang berurusan dengan model formal komputasi. 

2.1.3.  KOMPUTASI  MODERN

Komputasi modern merupakan sebuah konsep sistem yang menerima intruksi-intruksi dan menyimpannya dalam sebuah memory, memory disini bisa juga dari memory komputer. Oleh karena pada saat ini kita melakukan komputasi menggunakan komputer maka bisa dibilang komputer merupakan sebuah komputasi modern. Konsep ini pertama kali digagasi oleh John Von Neumann (1903-1957). Beliau adalah ilmuan yang meletakkan dasar-dasar komputer modern. Von Neumann telah menjadi ilmuwan besar abad 21. Von Neumann memberikan berbagai sumbangsih dalam bidang matematika, teori kuantum, game theory, fisika nuklir, dan ilmu komputer yang di salurkan melalui karya-karyanya . Beliau juga merupakan salah satu ilmuwan yang terkait dalam pembuatan bom atom di Los Alamos pada Perang Dunia II lalu. Kegeniusannya dalam matematika telah terlihat semenjak kecil dengan mampu melakukan pembagian bilangan delapan digit (angka) di dalam kepalanya. 

2.1.4.  SEJARAH KOMPUTASI MODERN

Dalam perkembangan komputasi modern, kita tidak bisa melupakan begitu saja orang dibalik perkembangan komputasi modern yang merubah semua pekerjaan jadi lebih mudah. Sejarah komputasi dimulai dari seseorang ilmuan yang ternama di bidang teknologi. Permulaan komputasi modern dimulai pada saat tahun 1926 oleh ilmuan yang berasal dari hungaria yang bernama John Von Neumann.

Von Neuman

Von Neumann seorang ilmuan yang belajar dari Berlin dan Zurich dan mendapatkan diploma pada bidang teknik kimia pada tahun 1926. Pada tahun yang sama dia mendapatkan gelar doktor pada bidang matematika dari Universitas Budapest. Berkat keahlian dan kepiawaiannya Von Neumann dalam bidang teori game yang melahirkan konsep seluler automata, teknologi bom atom, dan komputasi modern yang kemudian melahirkan komputer. Kegeniusannya dalam matematika telah terlihat semenjak kecil dengan mampu melakukan pembagian bilangan delapan digit (angka) di dalam kepalanya. Setelah mengajar di Berlin dan Hamburg, Von Neumann pindah ke Amerika pada tahun 1930 dan bekerja di Universitas Princeton serta menjadi salah satu pendiri Institute for Advanced Studies. Dipicu ketertarikannya pada hidrodinamika dan kesulitan penyelesaian persamaan diferensial parsial nonlinier yang digunakan, Von Neumann kemudian beralih dalam bidang komputasi. Sebagai konsultan pada pengembangan ENIAC, dia merancang konsep arsitektur komputer yang masih dipakai sampai sekarang. Arsitektur Von Nuemann adalah komputer dengan program yang tersimpan (program dan data disimpan pada memori) dengan pengendali pusat, I/O, dan memori. berdasarkan beberapa definisi di atas, maka komputasi modern dapat diartikan sebagai suatu pemecahan masalah berdasarkan suatu inputan dengan menggunakan algoritma dimana penerapannya menggunakan berbagai teknologi yang telah berkembang seperti komputer.

            2.2.  AUTOMATA
2.2.1.  TEORI AUTOMATA

        Teori otomata mempelajari tentang mekanisme komputer abstrak atau mesin abstrak. Jauh sebelum ada komputer, tahun 1930, Alan Turing mempelajari mesin abstrak yang punya kemampuan seperti komputer sekarang, dikenal dengan nama Mesin Turing. Tujuan Turing adalah menggambarkan secara jelas apa yang dapat dan yang tidak dapat dilakukan mesin komputing.  Kemudian pada tahun 1940 an dan 1950-an, ditemukan mesin abstrak yang lebih sederhana, yaitu “finite automata”. Automata ini, asalnya diperuntukkan untuk membentuk fungsi kecerdasan, berubah secara drastis untuk keperluan lain yang sangat beragam. Tahun 1950-an juga Chomsky mempelajari tentang “tata bahasa” formal, yang sangat berguna untuk pengembangan compiler.

        Semua pengembangan teori ini secara langsung melahirkan ilmu-ilmu komputer yang sekarang ini. Beberapa konsepnya, seperti “Finite Automata” dan “grammar”, digunakan untuk perancangan dan pembuatan bermacam software penting, seperti Pascal dan C. Konsep lainnya, seperti Mesin Turing, membantu kita memahami apa yang dapat kita harapkan dari perangkat lunak kita.

Beberapa Pengertian Dasar :

• Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah huruf atau sebuah angka adalah contoh simbol.
• String adalah deretan terbatas (finite) simbol-simbol. Sebagai contoh, jika a, b, dan c adalah tiga buah simbol maka abcb adalah sebuah string yang dibangun dari ketiga simbol tersebut.
• Jika w adalah sebuah string maka panjang string dinyatakan sebagai w dan didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut. Sebagai contoh, jika w = abcb maka w= 4.
• String hampa adalah sebuah string dengan nol buah simbol. String hampa dinyatakan dengan simbol  (atau ^) sehingga = 0. String hampa dapat dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol.
• Alfabet adalah hinpunan hingga (finite set) simbol-simbol

2.2.2.  TEORI BAHASA

          Teori bahasa membahas tentang bahasa formal (formal language), terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor). 

• Bahasa formal adalah kumpulan kalimat. Semua kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama. 
• Sebuah bahasa formal bisa dibangkitkan oleh dua atau lebih tata bahasa berbeda.
•  Dikatakan bahasa formal karena grammar diciptakan mendahului pembangkitan setiap kalimatnya. 
• Bahasa Natural/manusia bersifat sebaliknya; grammar diciptakan untuk meresmikan kata-kata yang hidup di masyarakat. Dalam pembicaraan selanjutnya ‘bahasa formal’ akan disebut ‘bahasa’ saja.

           2.2.3.  FINITE STATE MACHINE

        Finite State Machines (FSM) adalah sebuah metodologi perancangan sistem kontrol yang menggambarkan tingkah laku atau prinsip kerja sistem dengan menggunakan tiga hal berikut: State (Keadaan), Event (kejadian) dan Action (aksi). Pada satu saat dalam periode waktu yang cukup signifikan, sistem akan berada pada salah satu state yang aktif. Sistem dapat beralih atau bertransisi menuju state lain jika mendapatkan masukan atau event tertentu, baik yang berasal dari perangkat luar atau komponen dalam sistemnya itu sendiri (misal interupsi timer). Transisi keadaan ini umumnya juga disertai oleh aksi yang dilakukan oleh sistem ketika menanggapi masukan yang terjadi. Aksi yang dilakukan tersebut dapat berupa aksi yang sederhana atau melibatkan rangkaian proses yang relative kompleks. Berdasarkan sifatnya, metode FSM ini sangat cocok digunakan sebagai basis perancangan perangkat lunak pengendalian yang bersifat reaktif dan real time. Salah satu keuntungan nyata penggunaan FSM adalah kemampuannya dalam mendekomposisi aplikasi yang relative besar dengan hanya menggunakan sejumlah kecil item state. Selain untuk bidang kontrol, Penggunaan metode ini pada kenyataannya juga umum digunakan sebagai basis untuk perancangan protokol-protokol komunikasi, perancangan perangkat lunak game, aplikasi WEB dan sebagainya.

      Ada beberapa definisi mengenai Finite  State Machine (FSM) atau sering juga disebut dengan Finite State Automata (FSA). 

1. FSM didefenisikan sebagai perangkat komputasi yang memiliki input berupa string dan output yang merupakan satu dari dua nilai yang dapat di-accept dan reject (Rich : 2009). 
2. Finite Automata adalah model matematika sistem dengan masukan dan keluaran diskrit. Sistem dapat berada di salah satu dari sejumlah berhingga konfigurasi internal disebut state (Hariyanto : 2004). 
3. FSM adalah sebuah metodologi perancangan sistem kontrol yang menggambarkan tingkah laku atau prinsip kerja sistem dengan menggunakan tiga hal berikut: State (Keadaan), Event (kejadian) dan action (aksi). Pada satu saat dalam periode waktu yang cukup signifikan, sistem akan berada pada salah satu state yang aktif. Sistem dapat beralih atau bertransisi menuju state lain jika mendapatkan masukan atau event tertentu, baik yang berasal dari perangkat luar atau komponen dalam sistemnya itu sendiri. Transisi keadaan ini umumnya juga disertai oleh aksi yang dilakukan oleh sistem ketika menanggapi masukan yang terjadi. Aksi yang dilakukan tersebut dapat berupa aksi yang sederhana atau melibatkan rangkaian proses yang relatif kompleks (Setiawan : 2006). 

       2.3.   MESIN TURING

        Mesin Turing adalah model komputasi teoritis yang ditemukan oleh Alan Turing, berfungsi sebagai model ideal untuk melakukan perhitungan matematis. Walaupun model ideal ini diperkenalkan sebelum komputer nyata dibangun, model ini tetap diterima kalangan ilmu komputer sebagai model komputer yang sesuai untuk menentukan apakah suatu fungsi dapat selesaikan oleh komputer atau tidak (menentukan computable function). Mesin Turing terkenal dengan ungkapan " Apapun yang bisa dilakukan oleh Mesin Turing pasti bisa dilakukan oleh komputer."

      Sebuah mesin turing terdiri atas barisan sel tersusun berupa pita yang dapat bergerak maju mundur, komponen aktif baca/tulis pita yang memiliki status perhitungan serta dapat mengubah/menulisi sel aktif yang ada di pita tadi, dan suatu kumpulan instruksi bagaimana komponen baca/tulis ini harus melakukan modifikasi terhadap sel aktif pada pita, serta bagaimana menggerakkan pita tersebut. Pada setiap langkah dalam komputasi, mesin ini akan dapat mengubah isi dari sel yang aktif, mengubah status dari komponen baca/tulis, dan mengubah posisi pita kekiri atau kekanan.

       Mesin Turing menggunakan notasi seperti ID-ID pada PDA untuk menyatakan konfigurasi dari komputasinya. 

       Mesin terdiri dari sebuah finite control, yang dapat berada dalam sebuah himpunan berhingga dari state. Terdapat sebuah tape yang dibagi ke dalam kotak-kotak atau sel-sel. Setiap sel dapat menampung sebuah dari sejumlah berhingga dari simbol.

       Pada awalnya, input yang merupakan string dari simbol dengan panjang berhingga dipilih dari input alphabet, ditempatkan pada tape. Sel-sel tape yang lain, perluasan secara infinite ke kiri dan ke kanan, pada awalnya menampung simbol khusus yang dinamakan blank. Blank bukan sebuah input symbol, dan mungkin terdapat simbol tape yang lain disamping input symbol dan blank. Terdapat sebuah tape head yang selalu ditempatkan pada salah satu dari sel-sel tape. Mesin turing dikatakan men-scan sel tersebut. Pada awalnya, tape head berada pada sel paling kiri yang menampung input. Sebuah pergerakan mesin Turing adalah sebuah fungsi dari state dari finite control dan tape symbol yang di-scan. Dalam satu pergerakan, mesin Turing akan merubah state. Next state dapat sama dengan current state. Menulis sebuah tape symbol dalam sel yang di-scan. Tape symbol ini mengganti symbol apapun yang ada dalam sel tersebut. Secara opsional, simbol yang dituliskan dapat sama dengan simbol yang sekarang ada dalam tape. Memindahkan tape head ke kiri atau ke kanan.

BAB III
PENUTUP

A.  KESIMPULAN

           Teori komputasi adalah suatu sub-bidang dari ilmu komputer dan matematika. Selama ribuan tahun, perhitungan dan komputasi umumnya dilakukan dengan menggunakan pena dan kertas, atau kapur dan batu tulis, atau dikerjakan secara mental, kadang-kadang dengan bantuan suatu tabel. Komputasi modern merupakan sebuah konsep sistem yang menerima intruksi-intruksi dan menyimpannya dalam sebuah memory, memory disini bisa juga dari memory komputer. Konsep ini pertama kali digagasi oleh John Von Neumann (1903-1957). Beliau adalah ilmuan yang meletakkan dasar-dasar komputer modern. Von Neumann telah menjadi ilmuwan besar abad 21. Finite State Machines (FSM) adalah sebuah metodologi perancangan sistem kontrol yang menggambarkan tingkah laku atau prinsip kerja sistem dengan menggunakan tiga hal berikut: State (Keadaan), Event (kejadian) dan Action (aksi). Mesin Turing adalah model komputasi teoritis yang ditemukan oleh Alan Turing, berfungsi sebagai model ideal untuk melakukan perhitungan matematis.

DAFTAR PUSTAKA

http://www.beritanet.com/Education/John-Von-Neumann.html
http://id.wikipedia.org/wiki/Teknologi_komputasi
https://dwijati.wordpress.com/komputasi-modern
https://niamoraa.wordpress.com/softskill-project-2/definisi-dan-penerapan-komputasi-modern/
https://docs.google.com/document/d/1I0xXbqOamefTskoeHmL4bhVvKA4YxCbPBTDTCMceE8U/edit?hl=in
http://situz-go.blogspot.co.id/2011/04/teori-bahasa-dan-otomata.html
http://www.k-oneteknologi.tk/2014/04/fsm-finite-state-machine.html
http://pasuruan.stiewalisongo.web.id/id3/2544-2436/Mesin-Turing_50985_pasuruan-stiewalisongo.html
http://rudihadjo.blogspot.co.id/2015/09/mesin-turing.html

Read More