TUGAS 1:

KOMPUTASI dari sisi 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
Soal contoh
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. The 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 contoh
Keputusan masalah sebagai bahasa resmi
Keputusan masalah adalah salah satu objek pusat studi di teori kompleksitas komputasi. Keputusan masalah adalah tipe khusus masalah komputasi baik yang jawabannya adalah ya atau tidak, atau bergantian baik 1 atau 0. Keputusan masalah itu dapat dipandang sebagai bahasa resmi, di mana anggota-anggota bahasa adalah contoh yang jawabannya adalah ya, dan non-anggota adalah contoh-contoh output yang tidak. Tujuannya adalah untuk memutuskan, dengan bantuan dari suatu algoritma, apakah string masukan yang diberikan adalah anggota bahasa formal dalam pertimbangan. Jika algoritma memutuskan mengembalikan masalah ini jawabannya ya, algoritma dikatakan menerima masukan string, jika tidak dikatakan untuk menolak input.
Contoh masalah keputusan adalah sebagai berikut. Input adalah sembarang grafik. Masalahnya terdiri dalam menentukan apakah grafik yang diberikan terhubung, atau tidak. Bahasa formal yang terkait dengan masalah keputusan ini maka himpunan semua terhubung grafik-tentu saja, untuk mendapatkan definisi yang tepat bahasa ini, kita harus memutuskan bagaimana grafik biner dikodekan sebagai string.
Suatu masalah keputusan hanya memiliki dua kemungkinan output, ya atau tidak (atau bergantian 1 atau 0) pada setiap masukan.
Mesin kompleksitas model dan ukuran
Sebuah mesin Turing adalah model matematis dari sebuah mesin komputasi umum. Ini adalah perangkat teoretis yang memanipulasi simbol-simbol yang terdapat pada plester. Mesin turing tidak dimaksudkan sebagai teknologi komputasi praktis, tetapi lebih sebagai eksperimen pemikiran yang mewakili mesin komputasi. Hal ini diyakini bahwa jika masalah bisa diselesaikan dengan sebuah algoritma, terdapat sebuah mesin Turing yang memecahkan masalah. Memang, ini adalah pernyataan dari Gereja-Turing tesis. Selain itu, diketahui bahwa segala sesuatu yang dapat dihitung pada perhitungan model lain yang kita kenal sekarang, seperti mesin RAM, Conway’s Game of Life, selular automata atau bahasa pemrograman apapun dapat dihitung pada mesin Turing. Karena mesin Turing mudah untuk menganalisis secara matematis, dan diyakini sebagai kuat sebagai model lainnya komputasi, mesin Turing adalah model yang paling sering digunakan dalam teori kompleksitas
Untuk definisi yang tepat tentang apa artinya untuk memecahkan masalah dengan menggunakan jumlah tertentu ruang dan waktu, sebuah model komputasi seperti mesin Turing deterministik digunakan. Waktu yang dibutuhkan oleh sebuah mesin Turing deterministik M pada input x adalah jumlah total negara transisi, atau langkah, mesin membuat sebelum perhentian dan output jawaban ( “ya” atau “tidak”). Sebuah mesin Turing M adalah kata untuk beroperasi dalam waktu t (n), jika waktu yang dibutuhkan oleh M untuk setiap masukan dengan panjang n adalah paling banyak f (n). Keputusan masalah A dapat diselesaikan dalam waktu f (n) jika ada mesin Turing yang beroperasi di waktu f (n) yang memecahkan masalah. Sejak teori kompleksitas tertarik pada masalah mengklasifikasikan berdasarkan kesulitan, salah satu set mendefinisikan masalah didasarkan pada beberapa kriteria. Sebagai contoh, himpunan masalah dipecahkan dalam waktu f (n) pada mesin Turing deterministik kemudian dilambangkan dengan DTIME (f (n)).
Definisi analog dapat dibuat untuk kebutuhan ruang. Meskipun waktu dan ruang yang paling terkenal kompleksitas sumber daya, apapun ukuran kompleksitas dapat dipandang sebagai sumber daya komputasi. Langkah kompleksitas sangat umum didefinisikan oleh kompleksitas Blum aksioma. Ukuran kompleksitas lain yang digunakan dalam teori kompleksitas meliputi kompleksitas komunikasi, kompleksitas rangkaian, dan kompleksitas pohon keputusan.
Best, terburuk dan kasus rata-rata kompleksitas
Visualisasi dari quicksort algoritma yang memiliki kasus rata-rata kinerja Θ (n log n).
Yang terbaik, terburuk dan kasus rata-rata kompleksitas mengacu pada tiga cara yang berbeda untuk mengukur kompleksitas waktu (atau ukuran kompleksitas lainnya) dari input yang berbeda dengan ukuran yang sama. Sejak beberapa input berukuran n mungkin akan lebih cepat untuk memecahkan daripada yang lain, kita mendefinisikan kompleksitas berikut:
Kasus terbaik kompleksitas: Ini adalah kompleksitas pemecahan masalah yang terbaik dengan ukuran n input.
Terburuk kompleksitas: Ini adalah kompleksitas pemecahan masalah untuk yang terburuk dengan ukuran n input.
Kompleksitas kasus rata-rata: Ini adalah kompleksitas pemecahan masalah pada rata-rata. Kompleksitas ini hanya didefinisikan dengan hormat ke distribusi probabilitas atas masukan. Misalnya, jika semua masukan dengan ukuran yang sama diasumsikan memiliki kemungkinan yang sama untuk muncul, rata-rata kompleksitas kasus dapat didefinisikan yang berkaitan dengan distribusi seragam atas semua input berukuran n.
Sebagai contoh, perhatikan deterministik algoritma sorting quicksort. Hal ini memecahkan masalah menyortir daftar bilangan bulat yang diberikan sebagai input. Yang skenario terbaik adalah ketika input sudah disortir, dan membutuhkan waktu algoritma O (n log n) untuk input tersebut. Yang terburuk adalah ketika input diurutkan dalam urutan terbalik, dan membutuhkan waktu algoritma O (n 2) untuk kasus ini. Jika kita mengasumsikan bahwa semua kemungkinan permutasi dari daftar input sama-sama mungkin, rata-rata waktu yang dibutuhkan untuk menyusun adalah O (n log n).
Hulu dan batas bawah pada kompleksitas permasalahan
Dalam rangka untuk mengklasifikasi perhitungan waktu (atau sumber daya yang sama, seperti ruang konsumsi), orang yang tertarik dalam membuktikan batas atas dan bawah pada jumlah waktu minimum yang diperlukan oleh algoritma yang paling efisien untuk memecahkan masalah tertentu. Kompleksitas dari suatu algoritma biasanya dianggap sebagai yang terburuk kompleksitas, kecuali ditentukan lain. Analisis algoritma tertentu berada di bawah bidang analisis algoritma. Untuk menampilkan terikat atas T (n) pada waktu kompleksitas dari suatu masalah, orang perlu untuk menunjukkan hanya bahwa ada algoritma tertentu dengan waktu berjalan paling banyak T (n). Namun, membuktikan batas-batas yang lebih rendah jauh lebih sulit, karena batas-batas yang lebih rendah membuat pernyataan tentang semua kemungkinan algoritma yang memecahkan masalah tertentu. Ungkapan “semua kemungkinan algoritma” meliputi tidak hanya algoritma yang dikenal saat ini, tetapi setiap algoritma yang mungkin ditemukan di masa depan. Untuk menunjukkan terikat yang lebih rendah dari T (n) untuk suatu masalah memerlukan menunjukkan bahwa tidak ada algoritma dapat memiliki kompleksitas waktu lebih rendah dari T (n).

Batas atas dan bawah biasanya dinyatakan menggunakan notasi Oh besar, yang menyembunyikan faktor konstan dan istilah yang lebih kecil. Hal ini membuat batas-batas independen dari rincian spesifik model komputasi yang digunakan. Misalnya, jika T (n) = 7 n 2 + 15 n + 40, Oh besar orang akan menulis notasi T (n) = O (n 2).

Popularity: 1% [?]