Apa perbedaan antara algoritma, bahasa, dan masalah?

Tampaknya di situs ini, orang akan sering mengoreksi orang lain karena membingungkan "algoritma" dan "masalah." Apa perbedaannya? Bagaimana saya tahu kapan saya harus mempertimbangkan algoritma dan mempertimbangkan masalah? Dan bagaimana ini berhubungan dengan konsep bahasa dalam teori bahasa formal?

Untuk kesederhanaan, saya akan mulai dengan hanya mempertimbangkan masalah "keputusan", yang memiliki jawaban ya / tidak. Masalah fungsi bekerja kira-kira dengan cara yang sama, kecuali alih-alih ya / tidak, ada kata output spesifik yang terkait dengan setiap kata input.

Bahasa : bahasa hanyalah seperangkat string. Jika Anda memiliki alfabet, seperti , maka Σ * adalah himpunan semua kata-kata yang hanya berisi simbol dalam Σ . Sebagai contoh, { 0 , 1 } ∗ adalah himpunan semua urutan biner dengan panjang berapa pun. Alfabet tidak harus berupa biner. Itu bisa unary, ternary, dll.$\Sigma$$\Sigma^*$$\Sigma$$\{0,1 \}^*$

Bahasa di atas alfabet adalah setiap bagian dari Σ ∗ .$\Sigma$$\Sigma^*$

Masalah : Masalah adalah beberapa pertanyaan tentang beberapa masukan yang ingin kami jawab. Secara khusus, masalah keputusan adalah pertanyaan yang menanyakan, "Apakah input yang kami berikan memenuhi properti ?$X$

Bahasa adalah realisasi formal dari suatu masalah. Ketika kami ingin memberi alasan secara teoritis tentang masalah keputusan, kami sering memeriksa bahasa yang sesuai. Untuk masalah , bahasa yang sesuai adalah:$X$

adalah penyandian input y ke masalah X , dan jawaban untuk input y untuk masalah X adalah "Ya" $L = \{w \mid w$$y$$X$$y$$X$$\}$

Menentukan apakah jawaban untuk input ke masalah keputusan adalah "ya" sama dengan menentukan apakah pengkodean input tersebut pada alfabet dalam bahasa yang sesuai.

Algoritma : Suatu algoritma adalah cara selangkah demi selangkah untuk menyelesaikan suatu masalah. Perhatikan bahwa ada suatu algoritma yang dapat diekspresikan dalam banyak cara dan banyak bahasa, dan bahwa ada banyak algoritma berbeda yang memecahkan masalah yang diberikan.

Mesin Turing : Mesin Turing adalah analog formal dari suatu algoritma. Mesin Turing atas alfabet yang diberikan, untuk setiap kata, baik akan atau tidak akan berhenti dalam keadaan menerima. Jadi untuk setiap Mesin Turing , ada bahasa yang sesuai:$M$

berhenti dalam kondisi penerimaan pada input w } .$L(M) = \{w \mid M$$w\}$

(Ada perbedaan halus antara Mesin Turing yang berhenti pada semua input dan berhenti pada input ya, yang mendefinisikan perbedaan antara kelas kompleksitas dan R E. )$\mathsf{R}$$\mathsf{RE}$

Hubungan antara bahasa dan Mesin Turing adalah sebagai berikut

1. Setiap Mesin Turing menerima tepat satu bahasa

2. Mungkin ada lebih dari satu Mesin Turing yang menerima bahasa yang diberikan

3. Mungkin tidak ada Mesin Turing yang menerima bahasa yang diberikan.

Kita dapat mengatakan kira-kira hal yang sama tentang algoritma dan masalah: setiap algoritma memecahkan satu masalah, tetapi mungkin ada 0, atau banyak, algoritma yang memecahkan masalah yang diberikan.

Kompleksitas Waktu : Salah satu sumber paling umum kebingungan antara algoritma dan masalah adalah sehubungan dengan kelas kompleksitas. Alokasi yang tepat dapat diringkas sebagai berikut:

• Algoritma memiliki kompleksitas waktu
• Masalah milik kelas kompleksitas

Suatu algoritma dapat memiliki kompleksitas waktu tertentu. Kami mengatakan suatu algoritma memiliki kompleksitas batas atas kasus terburuk jika algoritme berhenti pada paling banyak langkah f ( n ) untuk setiap input ukuran n .$f(n)$$f(n)$$n$

Masalah tidak memiliki run-times, karena masalah tidak terkait dengan algoritma spesifik yang sebenarnya berjalan. Sebagai gantinya, kami mengatakan bahwa masalah milik kelas kompleksitas, jika ada beberapa algoritma yang memecahkan masalah dengan kompleksitas waktu tertentu.

dll adalah semua kelas kompleksitas. Ini berarti mereka mengandung masalah, bukan algoritma. Algoritme tidak pernah bisa dalam P , tetapi jika ada algoritma polinomial waktu menyelesaikan masalah X , maka X ada di$\mathsf{P}, \mathsf{NP}, \mathsf{PSPACE}, \mathsf{EXPTIME}$$\mathsf{P}$$X$$X$$\mathsf{P}$ . Ada juga bisa menjadi sekelompok algoritma eksponensial-waktu menerima , tapi karena ada sebuah algoritma tunggal polinomial-waktu menerima X , itu adalah dalam P .$X$$X$$\mathsf{P}$