BAB 1 - PENDAHULUAN
Komputer merupakan pengetahuan yang sangat penting karena membahas mengenai bagaimana cara pembuatan mesin yang mampu melakukan proses-proses intelektualyang mulanya hanya dapat dilakukan manusia. Kita mengetahui bahwa proses intelektual apapunyang dapat dilakukan secara mekanis oleh manusia dapat dilakukan oleh komputer digital. Saat ini kita mengetahui batasan-batasan yang dapat dilakukan komputer adalah berasal dari kelemahan kita sebagai pemrogram, bukan dari batasan-batasan intrinsik yang dilmiliki mesin komputer. Kita berharap batasan-batasan ini dapat direduksi dengan mengembangkan teori kompiutasi.
Teori komputasi telah dimulai sejak rancangan algoritma Euclid dan penggunaan komplesitas aksiomatik oleh bangsa Babilonia. Kepentingan teori komputasi saat ini dibentuk oleh kelahiran komputer digital yang mampu melakukan jutaan opersi per detik seta kehendak formalisasi konsep prosedur efektif yang berkonsekkuensi pada pembuatan keberadaan fungsi yang tidak dapat dikomputasi.
1.1. Komponen Ilmu Informatika
Ilmu informatika/konputer mempunyai dua komponen, yaitu:
§ Gagasan dan model fundamen tal yang mendasari komputasi
§ Teknik rekayasa untuk perangcangan sistem komputasi
Salah satu gagasan dan model fundamental penting adalah model komputasi.
Gagasan dasar finite automata adalah sangat umum yaitu sistem pada satu saat berada di salah satu state dari sejumlah state, bergerak di antara state-statesecara dapat diprediksi yang bergantung pada masukan ke sistem.
Salah satu penerapan penting model komputasi yang paling dekat adalah kompilasi atau translasi bahasa pemrograman tingkat tinggimenjadi bahasa mesin yang ekivalen. Penerapan model komputasi tidak hanya terbatas untuk kompilasi. Bahkan dapat dikatakan bahwa sistem diskrit apapun merupakan wadah yang tepat untuk penerapan model komputasi. Program dan file di sistem komputer adalah sistem diskrit sehingga seluruh sistem berbasis komputer dapat dipandang sebagai sistem diskrit.
1.2. Model Komputasi
1.2.1. Tiga Model Komputasi
Teori ototmata mempelajari model mesin komputer menggunakan model matematika. Namun Matematika yang digunakan benar-benar berbeda dibanding matematika klasik dan kalkulus. Model yang digunakan adalah model mesin state (statemachine model) atau model transisi state (state transition model). Terdapat tiga topik utama di teori otomata, yaitu:
1. Finite automata (FA) atau atau disebut finite state automata (FSA). FSA terbagi menjadi deterministic finite automata (DFA) dan nondeterministic finite automata (NDFA)
2. Pushdown automata (PDA) terbagi deterministic pushdown automata (DPDA atau DPA) nondeterministic pushdown automata (NDPDA)
3. Turing machine (TM)
Finite automata dan ekspresi reguler
Di tangan ahli, finite automata dan ekspresi regular menjadi kakas sangat berguna dalam perencangan lexical analyzer, yaitu bagian kompilator yang bertugas mengelompokkan karakter-karakter menjadi token-token, yaitu unit bahasa terkecil seperti keyword, identifier dsb., bertindak sebagai bahasa di bahasa sehari-sehari. Sejumlah kakas pengembangan kompilator dapat membangkitkan program lexical analyzer dari ekspresi reguler secara otomatis. Ekspresi reguler dan finite automata dapat ditemukan misalnya pada editor teks, pengenalan/pencarian pola,pengolahan teks dan masih banyak lagi aplikasi yang menggunakan ekspresi ini.
Pushdown automata dan context free grammar
Chomsky menunjukkan bahasa context free grammer ekivalin mesin abstrak pushdown automata. Maksud ekivalen adalah untuk sembarang context free grammer terdapat pushdown automata yang dapat mengenali bahasa hasil context free grammer itu. Pushdown automata mengolah sembarang string dan menentukan apakah string itu termasuk bahasanya. Kebalikannya pun berlaku yaitu untuk sembarang pushdown automaton maka bahasa yang dikenalinya dapat dibangkitkan dengan satu context free grammer. Keduanya dapat digunakan dalam spesifikasi bahasa komputer (pemrograman, markup, kamus dat , query, perintah, script, printer dsb.)
Mesin Turing
Mesin turing merupakan pemodelan mesin komputasi yang ampuh. Berdasar mesin turing dapat diidentifikasi ketidakmungkinan penulisan program. Bila dinyatakan tidak dapat dikomputasi mesin turing berarti persoalan tidak mungkin dapat diselesaikan secara komputasi dengan mesin komputasi apapun. Namun bila dikatakan persoalan dapat dikomputasi mesin turing bukan berarti dapat dijamin terdapat algoritma penyelesaian efisien. Mesin turing sangat penting mengidentifikasi ketidakmungkinan komputasi sehingga kita tidak bersusah payah berusaha memperoleh solusi 100% terdapat fungsi yang diidentifikasi tidak mungkin dikomputasi.
1.3. Pemanfaatan Otomata dan Teori Bahasa
Penerapan teori otomata sangat luas tidak untuk komputer saja. Pemanfaatannya antara lain:
§ Dibidang linguistik digunakan sebagai sarana mendiskripsikan bahasa manusia;
§ Dibidang komputer digunakan untuk pengembangan komputer lebih lanjut dalam segi bahasa, dimana dewasa ini banyak bahasa pemrograman komputer yang berkembang, belum ditambah bahasa komputer lain seperti bahasa markup, typesetting, query, printer,dsb.
Seluruh bidang aplikasi yang berkehendak menyatakan keteraturan sesuatu (struktur) atau kejadian atau rentetan kejadian sebagai mengikuti suatu kumpulan aturan tertentu dalam pembentukan barisan sesuatu yang berhingga atau tidak berhingga merupakan peluang penerapan teori otomata dan teori bahasa formal.
1.4. Teori Komputasi
Agar tidak bergantung pada komputer atau teknologi tertentu, teori mengusulkan mesin dan bahasa abstrak yang dipandang sebagai model komputasi. Mesin absstrak ini meendefinisikan “arti mengkomputasi”. Segala sesuatu yang dapat dikomputasi dengan mesin abstarak disebut “computable”. Dengan ini membentuk teori komputabilitas (computability theory), atau menyatakan kebalikan, yaitu menunjukkan apa yang tidak dapat diselesaikan dengan komputasi.
Komputasi sangat erat hubungannya dengan algoritma. Algoritma A adalah resep mengenai cara mengkomputasi fungsi f:X à Y dalam jumlah langkah berhingga. Resep komputasi ini sendiri harus diekspresikan secara berhingga. Sedikit lebih umumkita mengasumsikan bahwa untuk semua xÎX, prosedur A menspesifikasikaneksekusi sebarisan operasi berhingga atau tidak berhingga. Jika untuk x adalah berhingga maka prosedur A disebut berhenti (stop/terminate). Dalam hal ini prosedur mengirim nilai f(x) pada saat terminasi. Jika prosedur A berhentiuntuk semua xÎX, maka prosedur disebut total atau disebut algoritma, selain itu disebut parsial (partial)atau disebut prosedur. Algoritma adalah prosedur yang untuk persoalan yangdidefinisikan mengalami perhentian.
Fungsi A f:XàY disebut dapat dikomputasi (computable), jka terdapat prosedur total A untuk fungsi itu. Himpunan f(X) = {f(x)|xÎX} Í Y disebut dapat dikomputasi (computable).
Referensi :
• Bambang Hariyanto. Teori Bahasa, Otomata, dan Komputasi serta terapannya. Penerbit Informatika Bandung, 2004
Nama : Hidayatul Ilmiyah
Kelas : IF'09 - A
NIM : 120911072
Tidak ada komentar:
Posting Komentar