Saya mulai terlibat dengan Optimalisasi Matematika baru-baru ini dan saya menyukainya. Tampaknya banyak masalah pengoptimalan dapat dengan mudah diekspresikan dan dipecahkan sebagai program linier (misalnya aliran jaringan, tepi / simpul penutup, penjual keliling dll.) Saya tahu bahwa beberapa di antaranya NP-hard, tetapi intinya adalah bahwa mereka dapat 'dibingkai sebagai program linier' jika tidak diselesaikan secara optimal.
Itu membuat saya berpikir: Kami selalu diajarkan sistem persamaan linear, aljabar linear di seluruh sekolah / perguruan tinggi. Dan melihat kekuatan piranti lunak untuk mengekspresikan berbagai algoritma itu agak menarik.
Pertanyaan: Meskipun kita memiliki sistem non-linear yang lazim di sekitar kita bagaimana / mengapa sistem linear sangat penting untuk ilmu komputer? Saya mengerti bahwa mereka membantu menyederhanakan pemahaman dan sebagian besar waktu dapat ditata secara komputasional tetapi apakah itu? Seberapa baik 'perkiraan' ini? Apakah kita terlalu menyederhanakan dan apakah hasilnya masih berarti dalam praktik? Atau apakah itu hanya 'sifat' yaitu masalah yang paling menarik memang linier?
Apakah aman untuk aman bahwa 'aljabar linier / persamaan / pemrograman' adalah batu penjuru dari CS? Jika tidak, apa yang akan menjadi kontradiksi yang bagus? Seberapa sering kita berurusan dengan hal-hal non-linier (saya tidak harus berarti secara teoritis tetapi juga dari sudut pandang 'kemampuan memecahkan' yaitu hanya mengatakan itu NP tidak memotongnya, harus ada perkiraan yang baik untuk masalah dan apakah itu akan mendarat menjadi linier?)
Jawaban:
Premis dari pertanyaan ini sedikit cacat: ada banyak yang akan berpendapat bahwa kuadrat adalah "batas" nyata untuk trabilitas dan pemodelan, karena masalah kuadrat-kuadrat hampir semudah masalah linier. Ada orang lain yang berpendapat bahwa konveksitas (atau bahkan submodularitas dalam kasus-kasus tertentu) adalah batas kemampuan penelusuran.
Memori ini memberikan efisiensi: Saya dapat memecah-mecah barang, atau bekerja secara iteratif, dan saya tidak kehilangan karena melakukannya. Saya masih bisa membuat keputusan yang buruk (cf algoritma serakah) tetapi tindakan memecah hal-hal itu sendiri tidak menyakiti saya.
Ini adalah salah satu alasan mengapa linearitas memiliki kekuatan seperti itu. Mungkin ada banyak lainnya.
sumber
" Meskipun kita memiliki sistem non-linear yang lazim di sekitar kita bagaimana / mengapa sistem linear sangat penting untuk ilmu komputer?"
Berikut adalah jawaban parsial dalam pikiran saya: Saya pikir itu karena alam dipenuhi dengan objek / fenomena - yang diwakili oleh fungsi-fungsi yang walaupun tidak linier pada operan mereka, sebenarnya adalah anggota ruang linear. Gelombang berfungsi dalam ruang Hilbert, komponen dalam spektrum empat tingkat, cincin polinomial, proses stokastik - mereka semua berperilaku dengan cara itu. Bahkan definisi yang sangat umum dari ruang lengkung dibangun dari menyusun grafik kecil dari ruang datar (manifold, permukaan Riemann, ..). Selain itu, alam penuh dengan simetri dan mempelajari simetri selalu masuk ke dalam studi operator linear (teori representasi, dalam pikiran saya, merayap ke banyak bidang ilmu komputer di mana-mana).
Ini adalah tambahan untuk kasus di mana operator itu sendiri bersifat linier.
Sebagian besar masalah yang kita butuhkan program komputer, muncul baik secara langsung, atau disarikan dari, fenomena yang terjadi secara alami. Mungkin mempelajari / menyelesaikan sistem linier seharusnya bukan kejutan besar?
sumber