Kompleksitas Teknologi Komputasi Modern(Tugas Softskill Pengantar Komputasi Modern)

Kompleksitas Teknologi Komputasi Modern

Definisi Komputasi Modern

Komputasi modern terdiri dari dua kata yaitu komputasi dan modern. Komputasi dapat diartikan sebagai cara untuk menemukan pemecahan permasalahan dari data input dengan suatu algoritma. Komputasi merupakan subbagian dari matematika. Selama ribuan tahun, perhitungan dan komputasi menggunakan pena dan kertas, atau kapur dan batu tulis, atau dikerjakan secara mental dan kadang-kadang menggunakan tabel. disebut modern karena menggunakan alat canggih saat menyelesaian masalah. Maka dapat di simpulkan Komputasi modern adalah perhitungan yang menggunakan computer canggih dimana pada computer tersebut tersimpan sejumlah algoritma untuk menyelesaikan masalah perhitungan secara efektif dan efisien. Komputasi modern digunakan untuk memecahkan masalah antara lain untuk menghitung:

* Akurasi (bit, floating point)

* Kecepatan (dalam satuanHz)

* Problem volume besar (paralel)

* Modeling (NN dan GA)

* Kompleksitas (menggunakan Teori Bog O)

Secara umum iIlmu 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.

Karakteristik Komputasi Modern

Karakteristik komputasi modern ada 3 macam, yaitu :

1. Komputer-komputer penyedia sumber daya bersifat heterogenous karena terdiri dari berbagai jenis perangkat keras, sistem operasi, serta aplikasi yang terpasang.

2. Komputer-komputer terhubung ke jaringan yang luas dengan kapasitas bandwidth yang beragam.

3. Komputer maupun jaringan tidak terdedikasi, bisa hidup atau mati sewaktu-waktu tanpa jadwal yang jelas.

Jenis-jenis komputasi modern ada 3 macam, yaitu :

1. Mobile Computing atau Komputasi Bergerak

Mobile computing (komputasi bergerak) merupakan kemajuan teknologi komputer sehingga dapat berkomunikasi menggunakan jaringan tanpa menggunakan kabel serta mudah dibawa atau berpindah tempat, tetapi berbeda dengan komputasi nirkabel. Berdasarkan penjelasan tersebut, untuk kemajuan teknologi ke arah yang lebih dinamis membutuhkan perubahan dari sisi manusia maupun alat. Contoh dari mobile computing adalah GPS, smart phone, dan sebagainya.

2. Grid Computing

Komputasi grid memanfaatkan kekuatan pengolahan idle berbagai unit komputer, dan menggunakan kekuatan proses untuk menghitung satu pekerjaan. Pekerjaan itu sendiri dikontrol oleh satu komputer utama, dan dipecah menjadi beberapa tugas yang dapat dilaksanakan secara bersamaan pada komputer yang berbeda. Tugas-tugas ini tidak perlu saling eksklusif, meskipun itu adalah skenario yang ideal. Sebagai tugas lengkap pada berbagai unit komputasi, hasil dikirim kembali ke unit pengendali, yang kemudian collates itu membentuk keluaran kohesif. Keuntungan dari komputasi grid adalah dua kali lipat: pertama, kekuatan pemrosesan yang tidak digunakan secara efektif digunakan, memaksimalkan sumber daya yang tersedia dan, kedua, waktu yang dibutuhkan untuk menyelesaikan pekerjaan besar berkurang secara signifikan.

Idealnya kode sumber harus direstrukturisasi untuk membuat tugas-tugas yang saling eksklusif adalah sebagai mungkin. Itu tidak berarti bahwa mereka tidak bisa saling bergantung, tetapi pesan yang dikirim antara tugas-tugas meningkatkan faktor waktu. Satu pertimbangan penting saat membuat pekerjaan komputasi grid adalah bahwa apakah kode dijalankan serial atau paralel tugas, hasil dari keduanya harus selalu sama di setiap situasi.

3. Cloud Computing atau Komputasi Awan

Cloud computing adalah perluasan dari konsep pemrograman berorientasi objek abstraksi. Abstraksi, sebagaimana dijelaskan sebelumnya, menghapus rincian kerja yang kompleks dari visibilitas. Semua yang terlihat adalah sebuah antarmuka, yang menerima masukan dan memberikan output. Bagaimana output ini dihitung benar-benar tersembunyi.

Kompleksitas

Kompleksitas komputasi adalah cabang dari teori komputasi dalam ilmu komputer yang berfokus pada mengklasifikasikan masalah komputasi sesuai dengan kesulitan inheren mereka. Dalam konteks ini, sebuah masalah komputasi dipahami sebagai tugas yang pada prinsipnya setuju untuk menjadi dipecahkan oleh komputer. Informal, sebuah masalah komputasi terdiri dari contoh-contoh masalah dan solusi untuk masalah ini contoh. Sebagai contoh, primality pengujian adalah masalah menentukan apakah nomor yang diberikan perdana atau tidak. Contoh-contoh masalah ini adalah bilangan asli, dan solusi untuk sebuah contoh adalah ya atau tidak didasarkan pada apakah nomor perdana atau tidak.

Masalah ini dianggap sebagai secara inheren sulit jika memecahkan masalah yang memerlukan sejumlah besar sumber daya, tergantung pada algoritma yang digunakan untuk memecahkan itu. Teori ini formalizes intuisi, dengan memperkenalkan matematika model komputasi untuk mempelajari masalah ini dan kuantitatif jumlah sumber daya yang dibutuhkan untuk memecahkan mereka, seperti waktu dan penyimpanan. Ukuran kompleksitas lain juga digunakan, seperti jumlah komunikasi (digunakan dalam kompleksitas komunikasi), jumlah gerbang dalam rangkaian (digunakan dalam rangkaian kompleksitas) dan jumlah prosesor (digunakan dalam komputasi paralel). Secara khusus, teori kompleksitas komputasi menentukan batas-batas praktis tentang apa yang komputer bisa dan tidak bisa lakukan.

Bidang-bidang terkait erat dalam ilmu komputer teoritis analisis algoritma dan teori computability. Perbedaan utama antara teori kompleksitas komputasi dan analisis algoritma adalah bahwa yang terakhir ditujukan untuk menganalisis jumlah sumber daya yang dibutuhkan oleh algoritma tertentu untuk memecahkan masalah, sedangkan yang pertama mengajukan pertanyaan yang lebih umum tentang semua kemungkinan algoritma yang dapat digunakan untuk memecahkan masalah yang sama. Lebih tepatnya, hal ini mencoba untuk mengklasifikasikan masalah yang dapat atau tidak dapat diselesaikan dengan tepat sumber daya terbatas. Pada gilirannya, memaksakan pembatasan pada sumber daya yang tersedia adalah apa yang membedakan kompleksitas komputasi dari computability teori: teori yang terakhir bertanya apa jenis masalah dapat diselesaikan pada prinsipnya algorithmically.

Pemecahan Masalah Kompleksitas (Menggunakan teori Big O)

Komputasi modern dirancang untuk menangani masalah yang kompleks, sehingga diterapkan pada komputer. Dengan menggunakan teori Big O, maka komputasi modern dapat melakukan perhitungan untuk memecahkan masalah kompleksitas yang kerap dihadapi.

Apa itu teori Big O?

Notasi  Big O merupakan suatu notasi matema tika untuk menjelaskan batas atas dari  magnitude suatu fungsi dalam fungsi yang lebih sederhana. Dalam dunia ilmu komputer, notasi ini sering digunakan dalam analisis kompleksitas algoritma. Notasi  Big O pertama kali diperkenalkan pakar teori bilangan Jerman, Paul Bachman tahun 1894, pada bukunya yang berjudul  Analytische Zahlentheorie edisi kedua. Notasi tersebut kemudian dipopuler kan oleh pakar teori bilangan Jerman lainnya, Edmund Landau, dan oleh karena  itu, terkadang disebut sebagai symbol Landau.

Notasi  Big O sangat berguna saat menganalis is efisiensi suatu algoritma. Sebagai contoh, waktu (atau jumlah langkah) yang diperlukan oleh suatu algoritma untuk menyelesaikan tugas dengan ukuran n adalah T( n) = 4 n -2 n+2. Untuk n yang besar, hasil perhitungan  n² menjadi dominan, sehingga  perhitungan yang lain dapat diabaikan (misalnya saat  n=500, 4n² 1000 kali lebih besar dari 2 n, sehingga mengabaikan 2n+2 tidak akan membawa efek yang besar pada tujuan utama pada umumnya). Kemudian koefisien pada polinomial pun dapat dihilangkan dengan alasan yang sama, sehingga dengan notasi big O, dapat disimpulkan:  T(n) E O(n²) bahwa algoritma di atas memiliki kompleksitas waktu dengan orde  O(n²).

Untuk membandingkan kompleksitas algoritma yang satu dengan yang lain, dapat digunakan tabel jenis kompleksitas di bawah, yang diurutkan berdasarkan kompleksitas yang paling baik ke yang paling buruk.

Diberikan f dan g suatu fungsi dari himpunan bilangan integer atau himpunan bilangan real pada suatu himpunan bilangan real. Dikatakan f(x) adalah O(g(x)) jika terdapat sebuah konstanta C dan k sedemikian sehingga :

| f(x) | < C | g(x) |

Dimana x > k, dibaca f(x) adalah “big-oh” pada g(x).

Penjelasan :

Untuk menunjukkan f(x) adalah O(g(x)), hanya dibutuhkan untuk menemukan satu pasangan konstanta C dan k sedemikian sehingga | f(x) | < C|g(x)| jika x > k. Pasangan C, k yang memenuhi definisi tidak pernah tunggal. Selanjutnya, jika satu pasangan ada, maka terdapat tak terbatas pasangan yang lain. Sebuah cara sederhana untuk melihat hal tersebut adalah, jika C, k adalah satu pasangan, pasangan yang lain C’, k’ dengan C < C’ dan k < k’ juga memenuhi definisi, jika :

| f(x) | < C|g(x)| < C’ | g(x) | dimana x > k’ > k.

Contoh :

Tunjukkan bahwa f(x) = x2 + 2 x + 1 adalah O(x2).

Penyelesaian :

Jika 0 < x2 + 2 x + 1 < x2 + 2 x2 + x2 = 4 x2 dimana x > 1, mengikuti f(x) adalah O(x2) untuk menerapkan definisi pada notasi big-O, ambil C = 4 dan k = 1. disini tidak perlu menggunakan nilai absolute jika semua fungsi pada persamaan ini adalah positif ketika x bernilai positif.

Pendekatan yang lain adalah jika x > 2, maka 2 x < x2. akibatnya jika x > 2, terlihat bahwa :

0 < x2 + 2 x + 1 < x2 + x2 + x2 = 3 x2

Dari definisi didapat C = 3 dan k = 2.

Pengamatan pada relasi f(x) adalah O(x2), x2 dapat diganti dengan sebarang fungsi yang lain dengan nilai yang lebih besar dari x2, misalnya f(x) adalah O(x3), f(x) adalah O(x2+2x+7) dan seterusnya. Hal ini juga benar bahwa x2 adalah O(x2+2x+1), jika x2 < x2 + 2x +1 dimana x > 1. Dari contoh tersebut diperoleh dua fungsi, f(x) = x2 + 2 x + 1 dan g(x) = x2, sedemikian sehingga f(x) adalah O(g(x)) dan g(x) adalah O(f(x)).

Pernyataan terakhir dari pertidaksamaan x2 < x2 + 2 x + 1, dimana untuk semua x bilangan real tidak negative. Dikatakan kedua fungsi f(x) dan g(x) bahwa keduanya mengikuti relasi big-O dengan order atau pangkat yang sama.

Penjelasan :

Kenyataan bahwa f(x) adalah g(x) kadang-kadang ditulis f(x) = O(g(x)). Bagaimanapun, tanda sama dengan pada notasi tersebut tidak dapat dipresentasikan dengan sebuah persamaan sesungguhnya.

Selanjutnya, notasi tersebut mengambarkan bahwa pertidaksamaan yang diperoleh menghubungkan nilai pada fungsi f dan g untuk bilangan yang cukup besar pada domain fungsi tersebut.

Notasi big-O digunakan pada bidang matematika, khususnya pada ilmu Komputer untuk analisa algoritma. Matematikawan jerman yang memperkenalkan pertama kali notasi big-O pada tahun 1892 pada sebuah buku tentang teori Bilangan. Notasi big-O kadang – kadang disebut juga dengan Simbol Landau.

Ketika f(x) adalah O(g(x)), dan h(x) adalah sebuah fungsi yang mempunyai nilai absolute lebih besar dari pada g(x) untuk bilangan x yang cukup besar, mengikuti definisi diatas maka f(x) adalah O(h(x)). Dengan kata lain, fungsi g(x) pada relasi f(x) adalah O(g(x)) dapat dipresentasikan dengan sebuah fungsi dengan nilai absolute yang lebih besar.

| f(x) | < C |g(x)| jika x > k

Dan jika | h(x) | > | g(x) untuk semua x > k, maka :

| f(x) | < C |h(x)| jika x > k

Oleh karena itu f(x) adalah O(h(x)).

Ketika notasi big-O digunakan, fungsi g pada relasi f(x) adalah O(g(x)) dipilih dari nilai terkecil yang mungkin. Kadang – kadang dari sebuah himpunan fungsi tertentu, misalnya fungsi tersebut pada bentuk xn , dimana n adalah bilangan integer positif.

Contoh Masalah :

Sebuah masalah komputasi dapat dilihat sebagai sebuah koleksi yang tak terbatas kasus bersama-sama dengan solusi untuk setiap contoh. Input string untuk sebuah masalah komputasi disebut sebagai contoh masalah, dan tidak boleh bingung dengan masalah itu sendiri. Dalam teori kompleksitas komputasi, masalah mengacu pada pertanyaan abstrak yang harus dipecahkan. Sebaliknya, sebuah contoh dari masalah ini adalah ucapan yang agak konkret, yang dapat digunakan sebagai masukan untuk masalah keputusan. Sebagai contoh, perhatikan masalah primality pengujian. contoh adalah nomor dan solusinya adalah "ya" jika nomor perdana dan "tidak" sebaliknya. Bergantian, yang contoh adalah input tertentu untuk masalah, dan solusinya adalah output sesuai dengan input yang diberikan.

Untuk lebih menyoroti perbedaan antara masalah dan sebuah contoh, pertimbangkan contoh berikut versi keputusan dari pedagang keliling masalah: Apakah ada rute dengan panjang maksimal 2000 kilometer melewati semua di Jerman 15 kota terbesar? Jawaban untuk masalah khusus ini misalnya tidak banyak digunakan untuk menyelesaikan contoh-contoh lain dari masalah, seperti meminta untuk pulang-pergi melalui semua pemandangan di Milan yang jumlah paling banyak panjangnya 10km. Untuk alasan ini, teori kompleksitas komputasi alamat masalah dan bukan masalah tertentu.

• Nama               : Eko Prasetiawan
• NPM                : 52409909
• Kelas                : 4IA19
• Mata kuliah       : Pengantar Komputasi Modern
• Dosen               : Kuwat Setiyanto

|