Aljabar abstrak untuk Ilmuwan Komputer Teoritis

Saya memiliki pendidikan matematika tingkat sarjana yang masuk akal, tetapi tidak pernah 100% nyaman dengan aljabar abstrak (matematika kelompok, cincin, bidang, dll.). Saya pikir ini sebagian karena saya perlu melihat aplikasi dan semua yang saya temukan adalah dalam fisika, bukan CS. Karena minat saya benar-benar CS, apakah ada bahan yang tersedia sekarang (draft online, catatan kuliah, video, buku) yang mencakup aljabar abstrak dari sudut pandang aplikasi di CS dan khususnya algoritma / teori? Saya senang aplikasi ini sepenuhnya teoretis tetapi mereka seharusnya tidak mengasumsikan pengetahuan aljabar abstrak yang sudah ada sebelumnya.

Saya cukup yakin bahwa sumber daya ini ada, mereka akan dihargai oleh sejumlah besar peneliti CS.

Anda dapat mencoba catatan dari kursus Madhu Sudan: Aljabar dan Komputasi

Salah satu jalur yang mungkin menjadi aljabar abstrak adalah dengan melihatnya dari sudut pandang kriptografi, yaitu tentang algoritma pada bidang terbatas. Bidang adalah cincin, dan bidang juga dua kelompok yang digabungkan dengan hukum sederhana. Teori lapangan menggunakan ruang vektor dalam posisi yang menonjol (teori Galois), sehingga sudut ini harus mencakup banyak aljabar abstrak. Buku

Pengantar Komputasi untuk Teori Angka dan Aljabar oleh V. Shoup

karena itu dapat menarik.

Rekomendasi pribadi saya adalah mengabaikan aplikasi, dan mempelajari teks matematika sarjana dasar tentang aljabar abstrak. Tidak ada kekurangan dari itu. Hanya percaya bahwa semua hal ini bermanfaat, dan bahwa penggunaannya akan lebih mudah muncul begitu Anda sudah memahami dasar materi.

Kebanyakan aljabar dasar bersifat konstruktif dan Anda dapat dengan mudah menerapkan konsep dasar untuk mendapatkan pemahaman yang lebih baik, misalnya algoritma yang memeriksa apakah tabel perkalian adalah suatu kelompok, pemecah persamaan dalam suatu kelompok, program yang memeriksa apakah dua struktur aljabar isomorfik dll. Kebanyakan masalah ini memiliki solusi brute-force yang mudah diimplementasikan, tetapi lambat. Semakin banyak Anda belajar tentang aljabar, semakin banyak cara pintas algoritmik yang Anda buat, untuk mempercepat program Anda. Contohnya tes primality Miller-Rabin dan AKS yang terkenal .

Lihatlah buku ini oleh Rudolf Lidl dan Harald Niederreiter: Pengantar Bidang Hingga dan Aplikasinya (edisi ke-2, 1994) http://www.amazon.com/Introduction-Finite-Fields-their-Applications/dp/0521460948

Mengutip deskripsi buku di Amazon: "Teori bidang terbatas adalah cabang aljabar modern yang telah mengemuka dalam beberapa tahun terakhir karena aplikasi yang beragam di berbagai bidang seperti kombinatorik, teori pengkodean, kriptologi, dan studi matematika switching circuit. . "

Selain kriptografi, aplikasi praktis yang sangat bagus dari aljabar dalam ilmu komputer mungkin adalah implementasi fraksi, di mana pembilang dan penyebutnya adalah tipe integral atau "bilangan bulat besar" dan panjang pengkodean adalah kecil dengan mengurangi fraksi (yaitu, menghitung yang paling umum) pembagi pembilang dan penyebut).

Mengenai tipe data "bilangan bulat besar", hasil yang menarik adalah apa yang disebut "teorema sisa Cina" yang memungkinkan paralelisasi operasi bilangan bulat sekali representasi sebagai faktor utama dari argumen yang dikenal.

Selain itu, sebagian besar barang yang ditemukan dalam aljabar dapat menyenangkan secara estetika (hanya dari sudut pandang pribadi).