Saya telah membaca Aljabar Linier dan Aplikasinya untuk membantu memahami materi sains komputer (terutama pembelajaran mesin), tetapi saya khawatir bahwa banyak informasi yang tidak berguna bagi CS. Misalnya, mengetahui cara memecahkan sistem persamaan linear secara efisien sepertinya tidak terlalu berguna kecuali Anda mencoba memprogram pemecah persamaan baru. Selain itu, buku ini telah berbicara banyak tentang rentang, ketergantungan linier, dan kemandirian, ketika sebuah matriks memiliki kebalikan, dan hubungan antara ini, tetapi saya tidak dapat memikirkan aplikasi ini dalam CS. Jadi, apa bagian dari aljabar linier yang digunakan dalam CS?
15
Jawaban:
Bagian-bagian yang Anda sebutkan adalah konsep dasar aljabar linier. Anda tidak dapat memahami konsep yang lebih maju (katakanlah, nilai eigen dan vektor eigen) sebelum terlebih dahulu memahami konsep dasar. Tidak ada jalan pintas dalam matematika. Tanpa pemahaman intuitif tentang konsep rentang dan kemandirian linier, Anda tidak akan bisa jauh dalam aljabar linier.
Beberapa algoritma hanya bekerja dengan matriks peringkat penuh - Apakah Anda tahu artinya? Apakah Anda tahu apa yang bisa membuat matriks tidak peringkat penuh? Bagaimana cara mengatasinya? Anda tidak akan memiliki petunjuk jika Anda tidak tahu apa itu kebebasan linear.
Algoritma eliminasi Gaussian yang digunakan untuk menyelesaikan persamaan linier sebenarnya dapat menjadi tidak stabil secara numerik jika diterapkan secara tidak benar, dan ini adalah sesuatu yang mungkin perlu Anda khawatirkan dalam beberapa kasus. Tanpa memahami algoritma Anda tidak akan tahu dari mana masalah itu berasal dan apakah ada sesuatu yang dapat Anda lakukan - tidak pada level algoritma untuk menyelesaikan persamaan linier, tetapi pada level mencari persamaan linear yang benar untuk dipecahkan.
Singkatnya, jangan malas, dan percayailah bahwa hal-hal ini berguna.
sumber
Aljabar linier terkadang sangat berguna dan kuat dalam algoritma grafik. Dengan teorema matrix-tree, Anda dapat menghitung jumlah spanning tree secara efisien (Anda perlu memahami nilai eigen). Aplikasi yang lebih menantang, di mana Anda membutuhkan pemahaman aljabar linier yang lebih kencang adalah algoritma FKT untuk menghitung jumlah pencocokan sempurna dalam grafik planar dalam waktu polinomial.
Ada banyak contoh yang lebih menarik tentang penggunaan aljabar linier dalam teori grafik aljabar dan teori grafik spektral . Algoritma yang muncul tidak hanya untuk menghitung masalah seperti dua contoh yang saya berikan. Misalnya, Anda juga dapat memeriksa konektivitas , atau menghitung diameter grafik .
sumber
Salah satu penggunaan aljabar linier yang paling terkenal adalah dalam algoritma Pagerank Google :
sumber
Hampir semua hal yang melibatkan grafik komputer, animasi, visi komputer, pemrosesan gambar, komputasi ilmiah, atau simulasi fenomena fisik akan melibatkan penggunaan luas vektor dan matriks (aljabar linier) dari hal-hal sederhana seperti mewakili transformasi dan orientasi spasial, hingga algoritma yang sangat kompleks. Hal-hal ini dulunya merupakan domain superkomputer, tetapi sekarang bidang yang sama ini adalah inti dari semua aplikasi paling keren di desktop, ponsel, dan di mana saja, mulai dari video game, fotografi komputasi, hingga mobil self-driving. Aljabar linier ada di mana-mana.
sumber
Ada banyak algoritma dan teknik berbasis aljabar matriks di luar sana. Dan itu bagus. Analisis komponen utama adalah contoh dari beberapa aljabar linier terapan yang cukup berguna. Hal yang sama dapat dikatakan tentang analisis Fourier, yang juga berakar pada ortogonalitas dan produk dalam. Jadi ada aplikasi langsung.
TETAPI , yang lebih penting lagi, mengambil kelas aljabar linier sangat berharga karena mengajarkan Anda untuk berpikir dengan cara tertentu. Kebanyakan kelas aljabar linier yang baik menekankan pada generalisasi, logika, dan bukti. Apakah sesuatu itu benar secara umum, atau hanya kasus-kasus tertentu tertentu, umum? Bagaimana Anda bisa yakin? Mampu memikirkan bagaimana membuktikan asumsi Anda itu baik karena itu membantu Anda menjaga diri dari membuat asumsi yang buruk dan menulis kode yang tidak menyamaratakan dengan cara yang Anda anggap benar. Ini juga membantu Anda berpikir tentang cara menggeneralisasi hal-hal yang mungkin sulit digeneralisasi, dan memungkinkan Anda memecahkan masalah yang lebih besar.
Singkatnya, ada baiknya untuk diingat bahwa aljabar linier itu baik karena itu mengangkat beban untuk bagian otak Anda yang berguna dalam ilmu komputer.
sumber
Memecahkan sistem persamaan linear (yang dapat dilakukan dengan metode eliminasi Gaussian), pemrograman linier (yang dapat diselesaikan dengan metode simpleks), kuadrat terkecil, dan penginderaan terkompresi (lihat artikel Wikipedia) adalah masalah praktis yang muncul dalam banyak area aplikasi. Aljabar linier membantu mengembangkan algoritma yang benar dan efisien untuk masalah ini.
Lihat teks [Cormen, Leiserson, Rivest dan Stein, "Pengantar Algoritma, Edisi Ketiga"], di mana Bab 28 tentang operasi matriks dan Bab 29 tentang pemrograman linier.
sumber