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 yaitu:
a. Teori komputabilitas.
b. Teori kompleksitas.
Komputasi sebetulnya bisa diartikan sebagai cara untuk menemukan pemecahan masalah dari data input dengan menggunakan suatu algoritma. Inilah yang disebut dengan teori komputasi, 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.
Secara umum ilmu komputasi adalah bidang ilmu yang mempunyai perhatian pada penyusunan model matematika dan teknik penyelesaian numerik serta penggunaan komputer 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.
Bidang ini berbeda dengan ilmu komputer (computer science), yang mengkaji komputasi, komputer dan pemrosesan informasi. Bidang ini juga berbeda dengan teori dan percobaan sebagai bentuk tradisional dari ilmu dan kerja keilmuan. Dalam ilmu alam, pendekatan ilmu komputasi dapat memberikan berbagai pemahaman baru, melalui penerapan model-model matematika dalam program komputer berdasarkan landasan teori yang telah berkembang, untuk menyelesaikan masalah-masalah nyata dalam ilmu tersebut.
Untuk melakukan studi komputasi dengan ketat, ilmuwan komputer bekerja dengan abstraksi matematika dari komputer yang dinamakan model komputasi. Ada beberapa model yang digunakan, namun yang paling umum dipelajari adalah mesin Turing. Sebuah mesin Turing dapat dipikirkan sebagai komputer pribadi meja dengan kapasitas memori yang tak terhingga, namun hanya dapat diakses dalam bagian-bagian terpisah dan diskret.
Ilmuwan komputer mempelajari mesin Turing karena mudah dirumuskan, dianalisis dan digunakan untuk pembuktian, dan karena mesin ini mewakili model komputasi yang dianggap sebagai model paling masuk akal yang paling ampuh yang dimungkinkan. Kapasitas memori tidak terbatas mungkin terlihat sebagai sifat yang tidak mungkin terwujudkan, namun setiap permasalahan yang "terputuskan" (decidable) yang dipecahkan oleh mesin Turing selalu hanya akan memerlukan jumlah memori terhingga. Jadi pada dasarnya setiap masalah yang dapat dipecahkan (diputuskan) oleh meisn Turing dapat dipecahkan oleh komputer yang memiliki jumlah memori terbatas.
Model Komputasi
Teori komputasi mempelajari model mesin komputer menggunakan model matematika. namun matematika yang digunakan benar-benar berbeda bila dibandingkan dengan matematika klasik dan kallkulus. model yang digunakan adalah model mesain state atau model transisi state. terdapat 3 model komputasi yang utama dalam teori komputasi yaitu :
1. Finite State Automata (contoh : Mesin jaja/ vending machine)
2. Push Down Automata (Contoh : Running text)
3. Turing Machine (Contoh : netbook)
Pengenalan TBO
Terminologi dasar yang penting dalam meamahami teori bahasa adalah alpabet, penyambungan (concatenation) dan string pada alpabet V. alpabet adalah himpunan simbol (karakter) tak kosong yang berhingga. Alpabet digunakan untuk membentuk kata-kata (string-string) di bahasa.
Istillah huruf, karakter dan simbol adalah sinonim menunjukkan elemen alpabet. jika kita meletakkan barisan ssebelah-menyebelah maka diperoleh string simbol.
Finite Automata
Salah satu alasan memulai studii teori komputasi melalui bahasa adalah pendekatan ini menuntun cara alami untuk permulaan. dimulai dari bahasa sederhana, kemudian mempertimbangkan kebutuhan-kebutuhan minimum mesin yang dapat mengolahnya.
Bahasa paling sederhana adalah bahasa reguler. Mesin yang dapat mengenali bahasa kelas ini adalah Finite State Automata . Finite Automata merupakan model komputasi. Sebutan Finite Automata untuk menyebut Deterministic Finite Automata atau bahkan gabungan deterministic finite automata dan nondeterministic finite automata.
2. Manfaat Dunia Biner Untuk Grafi Dan Jaringan
• Pengertian Internet
Internet adalah berbagai jaringan komputer di seluruh dunia yang saling terhubung tanpa mengenal batas teritorial, hukum dan budaya. Secara fisik dianalogikan sebagai jaring laba-laba (The Web) yang menyelimuti bola dunia dan terdiri dari titik-titik (node) yang saling berhubungan.Node bisa berupa komputer, jaringan lokal atau peralatan komunikasi/perangkat akses/ interkoneksi jaringan, pusat informasi dan database. Garis penghubung antar simpul disebut backbone (tulang punggung) bisa berupa infrastruktur komunikasi terestrial (kabel, serat optik, microwave, radio link) maupun satelit.
Menurut Lani Sidharta (1996), walaupun secara fisik Internet adalah interkoneksi antar jaringan komputer namun secara umum Internet harus dipandang sebagai sumber daya informasi. Isi Internet adalah informasi, dapat dibayangkan sebagai suatu database atau perpustakaan multimedia yang sangat besar dan lengkap. Bahkan Internet dipandang sebagai dunia dalam bentuk lain (maya) karena hampir seluruh aspek kehidupan di dunia nyata ada di Internet seperti bisnis, hiburan, olah raga, politik dsb.
• Standar Komputasi Terbuka
Isu terpenting di Internet pada masa awalnya adalah penerapan Standar Komputasi Terbuka (Open Computing Standard). Karena Internetwork dan Internet mengintegrasikan hampir semua sistem, jenis dan tipe komputer yang ada di dunia, maka harus ada standar yang menjamin komputer dapat saling berbicara satu sama lain dalam bahasa yang sama.
Menurut Drew Heywood (1996), standar bahasa komputer universal dikembangkan sejak 1969, terdiri dari serangkaian protokol komunikasi disebut Transfer Control Protocol (TCP) yang bertugas mengendalikan transmisi paket data, koreksi kesalahan dan kompresi.
Kemudian Internet Protocol (IP) yang bertugas sebagai pengenal (identifier) dan pengantar paket data ke alamat yang dituju. Protokol TCP / IP menyatukan bahasa dan kode berbagai jenis komputer di dunia sehingga disepakati sebagai standar utama jaringan komputer. TCP / IP berkembang cepat dan kaya fasilitas karena bersifat terbuka, bebas digunakan, ditambahkan kemampuan baru oleh siapapun dan gratis karena tidak dimiliki oleh siapapun.
Sekilas HTML Semula tampilan Internet masih berupa teks murni, revolusi terjadi ketika Web atau World Wide Web (WWW - tampilan grafis dan multimedia di Internet) diperkenalkan. Menurut Sampurna (1996), Web adalah kumpulan kode berbasis teks yang sederhana dan universal, disebut Hypertext Markup Language (HTML). Karena berbasis teks, HTML diterjemahkan segala jenis komputer dalam bentuk tampilan informasi yang sama.
HTML adalah kreasi Tim Berners Lee, ilmuwan European Laboratory for Particle Physics (CERN - organisasi penelitian 18 negara Eropa) di Geneva Swiss. Maret 1989 Tim memperkenalkan Web dan HTML sebagai standar antar muka distribusi informasi di Internet yang mampu menggabungkan teks, grafik dan multimedia dengan metode navigasi menu pada mesin UNIX.
HTML adalah kode pemrograman yang menjadi dasar terwujudnya Web. Dengan HTML semua sistem komputer yang saling berbeda dapat mengenali format yang ditampilkan dalam situs Internet tanpa perbedaan yang berarti, termasuk didalamnya penampilan multimedia (grafik, suara dan citra video).
HTML adalah bahasa pemrograman berbasis teks yang sangat sederhana dan praktis sehingga dapat dipahami oleh berbagai jenis komputer dalam platform sistem yang berbeda. Pendeknya, tidak ada sistem komputer yang tidak mampu membaca kode teks murni, semua pasti bisa.
Dokumen HTML mengandung kode perintah teks yang disebut tag untuk menampilkan tulisan, gambar, warna, suara, video, animasi serta link yang menghubungkan berbagai topik. Dengan bentuk hypertext maka halaman Internet (Web Site - Kios / Situs Internet) akan dapat dibangun dengan cepat. Dalam konsep hypertext ini pembacaan suatu dokumen tidak harus urut namun bisa meloncat antar topik bahkan di print maupun dicopy ke media penyimpan lokal (harddisk misalnya). Format hypertext juga memungkinkan pemakai mesin sederhana untuk mengakses dokumen dalam bentuk teks saja. Perbedaannya hanya terletak pada tidak ditampilkannya gambar, grafik, animasi, video, suara dan warna.
• Portal
Portal adalah web site yang menjadi pintu gerbang, starting point bagi pengunjung untuk memulai aktivitasnya di Internet. Portal yang bersifat horizontal menyediakan berbagai informasi dan layanan umum. Sedangkan portal vertical menyediakan informasi dan layanan yang spesifik untk bidang tertentu saja, sehingga bisa bersifat personal bagi pengunjungnya.
Layanan umum yang tersedia biasanya adalah search engine, berita, pooling, berbagai macam rubrik dan fasilitas seperti SMS serta chat room. Yang bersifat personal bisa berupa personal diary dan calender, account e-mail bahkan personal web. Portal vertical bahkan bisa bersifat eksklusif dan hanya menampilkan informasi yang dikehendaki komunitasnya. Misalnya portal yang bersifat religius seperti scientology, namun bisa saja sebaliknya bersifat terbuka meskipun membahas hal spesifik seperti toko buku amazon.
• Internet Service Provider (ISP)
Koneksi langsung ke Internet memerlukan biaya sangat tinggi yang tidak mungkin ditanggung perorangan. Sebagai solusi didirikanlah perusahaan penyedia jasa yang membangun infrastruktur koneksi ke Internet dan kemudian membagi kapasitas yang dimilikinya kepada pelanggan. Biaya koneksi menjadi ringan karena ditanggung bersama oleh sejumlah pelanggan melalui registrasi dan iuran, kecuali biaya pulsa ditanggung sendiri oleh pengguna. Seiring dengan makin berkurangnya dominasi dan monopoli telekomunikasi, pada saatnya biaya koneksi ISP akan termasuk pulsa.
ISP selain memperoleh keuntungan dari iuran biaya koneksi, juga menjual jasa yang lain seperti layanan Virtual Private Networking (VPN - saluran WAN khusus intern perusahaan melalui Internet), koneksi dedicated (24 jam), pembuatan (desain) dan hosting (penempatan - Web Hosting) situs Internet, konsultan jaringan komputer bahkan ada yang berjualan komputer.
ISP adalah lembaga komersial yang memiliki ijin operasional dari Pemerintah. ISP juga harus terdaftar dalam lembaga Internet internasional serta memiliki alokasi IP address (alamat Internet) yang diatur oleh Internet Address Network Authority (IANA) dan memiliki domain yang terdaftar dan diakui oleh komunitas Internet.
3. Teori Komputasi Parallel Untuk Rendering Film
3D Rendering merupakan salah-satu proses yang sangat penting dalam melakukan pengolahan gambar 3D. Tanpa dirender suatu gambar yang diolah oleh perangkat lunak animasi 3D hanya akan tampil dalam bentuk kumpulan point dan wireframe sederhana. Proses render melakukan “pembungkusan” tekstur pada objek yang bersesuaian sesuai cahaya yang datang pada objek tersebut. Namun proses render membutuhkan daya komputasi yang sangat besar karena banyaknya titik koordinat yang harus dikomputasi, terutama jika data 3D yang diolah cukup rumit.
Salah satu cara untuk memecahkan masalah tersebut adalah dengan menggunakan algoritma Divide and Conquer yang diterapkan kedalam metode Parallel Computing. Divide and Conquer merupakan salah satu strategi algoritma yang memecah suatu masalah besar menjadi beberapa bagian untuk kemudian dikerjakan satu persatu.
Dalam Parallel Computing tiap-tiap bagian dikerjakan oleh unit pemrosesannya masing-masing, sesuai dengan kesepakatan Divide pada awal komputasi. Parallel Computing terbukti jauh lebih efektif untuk melakukan rendering objek 3D dibanding hanya menggunakan sebuah unit komputasi. Sebagai contoh suatu perusahaan animasi asal Jepang, membutuhkan waktu 165 tahun jika proses render yang dilakukan untuk membuat animasi berdurasi 100 menit hanya menggunakan sebuah unit komputasi, namun karena perusahaan tersebut menggunakan metode Parallel Computing proses tersebut hanya membutuhkan waktu 1 tahun saja.
Salah satu masalah kompleks yang hingga kini masih membutuhkan kemampuan komputasi yang besar adalah melakukan proses render terhadap objek 3D. Proses render objek 3D sendiri membutuhkan waktu yang cukup lama, terlebih jika objek yang diberikan cukup rumit. Salah satu cara yang digunakan untuk mempercepat penyelesaian proses render adalah dengan menggunakan teknik Parallel Computing.
Parallel Computing merupakan teknik menggabungkan beberapa unit komputasi sekaligus untuk mengerjakan proses yang telah dibagi-bagi secara bersamaan. Ide untuk Parallel Computing muncul dari suatu algoritma yang cukup dikenal di dunia informatika, yaitu algoritma Divide and Conquer. Algoritma Divide and Conquer merupakan teknik pemecahan masalah dengan membagi suatu masalah menjadi beberapa bagian baru kemudian bagian-bagian tersebut dikerjakan satu persatu.
Sebenarnya operasi render objek 3D hanya merupakan kumpulan dari beberapa operasi primitif, namun operasi primitif yang dilakukan pada proses render sangatlah banyak. Untuk itu digunakan metode Parallel Computing sehingga tiap-tiap operasi primitif yang dilakukan dapat dikerjakan dengan menggunakan algoritma Divide and Conquer agar tiap bagian dari operasi Divide pada perhitungan yang dilakukan dapat dikerjakan oleh masing-masing unit komputasi.
Beberapa operasi primitif yang digunakan dalam 3D Rendering adalah operasi penghitungan jarak antara 2 titik,operasi perkalian bilangan bulat yang besar. Tentunya hampir kesemua operasi primitif tersebut dapat dipecahkan dengan menggunakan algoritma Divide and Conquer sehingga menjadikan proses 3D Rendering sangat cocok untuk diselesaikan dengan algoritma Divide and Conquer.
Pengertian 3D Rendering
3D Rendering merupakan proses untuk membentuk sebuah gambar dari sebuah model yang dibentuk oleh perangkat lunak animasi, model tersebut berisi data geometri, titik pandang, tekstur dan cahaya yang diperlukan untuk membuat gambar yang utuh.
3D Rendering merupakan proses yang sangat penting dan telah digunakan untuk berbagai macam penggunaan, seperti program permainan komputer, efek spesial pada film dan program simulasi.
Hasil Proses 3D Rendering
Terdapat banyak hasil yang dapat diperoleh dan ditampilkan dari proses 3D Rendering pada suatu sketsa wireframe, diantaranya :
1. Shading ; “Variasi warna dan kecerahan yang timbul pada suatu permukaan berdasarkan pencahayaan yang dilakukan”
2. Texture-Mapping ; “Detail yang muncul pada suatu permukaan”
3. Bump-Mapping ; “Kontur yang muncul pada suatu permukaan”
4. Fogging / Participating Medium ; “Bagaimana berkas cahaya berubah jika melewati udara yang tidak murni”
5. Shadows ; “Efek dari cahaya yang terhalang”
6. Soft Shadows ; “Variasi efek dari cahaya yang terhalang tidak sempurna”
7. Reflection ; “Refleksi yang tampak pada permukaan kaca atau gelas”
8. Transparency ; “Transmisi cahaya yang berbeda-beda jika melewati medium tertentu”
9. Translucency ; “Transmisi cahaya yang berbeda-beda jika memantul pada medium tertentu”
10. Refraction ; “Cahaya yang berubah arahnya karena efek transparency”
11. Indirect Illumination ; “Cahaya yang datang pada suatu objek namun tidak berasal dari sumber cahaya yang sebenarnya melainkan refleksi dari permukaan objek lain”
12. Caustics ; “Pantulan cahaya menyilaukan yang timbul pada suatu objek”
13. Depth Of Field ; “Objek yang berada jauh di depan maupun di belakang objek yang menjadi fokus akan tampak buram”
14. Motion Blur ; “Objek yang bergerak dengan kecepatan tinggi atau objek yang direkam oleh kamera yang berada dalam kecepatan tinggi akan tampak buram”
15. Photorealistic Morphing ; “Teknik yang memungkinkan hasil proses render objek 3D menjadi tampak terlihat lebih nyata”
16. Non-Photorealistic Rendering ; “Teknik yang memungkinkan hasil proses render objek 3D menjadi terlihat seperti hasil lukisan atau gambar”
Pengertian Parallel Computing
Parallel Computing merupakan teknik menjalankan program untuk menjalankan suatu proses dengan menggunakan lebih dari satu unit komputasi. Parallel Computing mempunyai prinsip yang bersesuaian dengan algoritma Divide and Conquer, yaitu membagi-bagi proses menjadi bagian-bagian yang cukup kecil dan memungkinkan untuk dikerjakan oleh sebuah unit komputasi.
Terdapat 2 klasifikasi parallel computer yang penting, yaitu :
1. Sebuah komputer dengan banyak unit komputasi internal, atau lebih dikenal sebagai Shared Memory Multiprocessor.
2. Beberapa komputer yang terhubung melalui sebuah jaringan, atau lebih dikenal sebagai Distributed Memory Multicomputer
Kesimpulan
Melakukan 3D Rendering tentu akan merupakan masalah yang sangat merepotkan jika tidak menggunakan algoritma memadai, dikarenakan banyaknya point dan polygon yang harus dikalkulasi setiap proses. Penggunaan algoritma Divide and Conquer tentu sangat membantu agar pekerjaan penghitungan yang sangat banyak dalam proses render dapat dikerjakan oleh beberapa unit komputasi sekaligus secara bersamaan. Hal ini juga telah dibuktikan dengan banyaknya perusahaan animasi dan film yang sering melakukan pekerjaan proses render menggunaan sistem parallel computing di dalam perusahaan mereka.