Cabang yang berorientasi aljabar ilmu komputer teoretis

Saya memiliki basis aljabar yang sangat kuat, yaitu

• aljabar komutatif,
• aljabar homologis,
• teori medan,
• teori kategori,

dan saya sedang belajar geometri aljabar.

Saya seorang jurusan matematika dengan kecenderungan untuk beralih ke ilmu komputer teoretis. Mempertahankan bidang yang disebutkan di atas dalam pikiran, bidang mana yang akan menjadi bidang yang paling tepat dalam ilmu komputer teoritis untuk beralih? Artinya, di bidang mana teori dan kematangan matematika yang diperoleh dengan mengejar bidang di atas dapat digunakan untuk keuntungan seseorang?

Ada perkembangan terbaru dalam teori tipe dependen yang menghubungkan sistem tipe dengan tipe homotopy .

Sekarang ini adalah bidang yang relatif kecil, tetapi ada banyak pekerjaan menarik yang dilakukan sekarang, dan berpotensi banyak buah tergantung rendah, terutama di port hasil dari algebraic topology dan homological aljabar dan meresmikan gagasan jenis induktif yang lebih tinggi .

Geometri aljabar banyak digunakan dalam teori kompleksitas aljabar dan khususnya dalam teori kompleksitas geometri. Teori representasi juga penting untuk yang terakhir, tetapi itu bahkan lebih berguna ketika dikombinasikan dengan geometri aljabar dan aljabar homologis.

Pengetahuan Anda tentang teori lapangan akan berguna dalam kriptografi, sementara teori kategori banyak digunakan dalam penelitian tentang bahasa pemrograman dan sistem pengetikan, yang keduanya terkait erat dengan dasar matematika.

Teori lapangan dan geometri aljabar akan berguna dalam topik yang berkaitan dengan kode koreksi kesalahan, baik dalam pengaturan klasik maupun dalam mempelajari kode yang dapat didekode secara lokal dan daftar decoding. Saya percaya ini kembali bekerja pada kode Reed-Solomon dan Reed-Muller, yang kemudian digeneralisasikan ke kode geometri aljabar. Lihat misalnya, bab buku ini tentang pandangan teori pengkodean klasik dari kode geometri aljabar, survei singkat tentang kode yang dapat didekodekan secara lokal, dan makalah terkenal ini tentang daftar-decoding Reed-Solomon dan, lebih umum, kode geometri aljabar-geometri.

Ada beberapa masalah dalam teori pembelajaran komputasi, pembelajaran mesin dan visi komputer yang dapat diselesaikan dengan menggunakan aljabar komutatif dan geometri aljabar. Sebagai contoh, konvergensi dari algoritma Propagasi Belief, sebuah algoritma passing pesan untuk inferensi Bayesian, dapat dirumuskan dalam hal mengkarakterisasi variasi affine dari sistem persamaan polinomial .

Pernahkah Anda berpikir tentang melihat aljabar komputer? Aksioma adalah sistem aljabar komputer tempat sistem tipe dimodelkan setelah Kategori Teori (atau Aljabar Universal, tergantung pada tampilan Anda). Ada dua turunan lebih lanjut dari Aksioma FriCAS dan OpenAxiom .

Jika Anda tertarik pada Kategori Teori, maka sistem jenis mungkin menjadi satu hal untuk dilihat.

Dalam Aksioma, setiap "item" (mis. "1", "5 * x ** 2 + 1") adalah elemen dari suatu Domain. "Domain" adalah objek Aksioma yang dinyatakan sebagai anggota dari Kategori tertentu (misalnya Integer, Polinomial (Integer). Kategori Aksioma adalah objek Aksioma yang dinyatakan sebagai anggota simbol "Kategori" yang dibedakan (misalnya Ring, Polynomial (PUTARAN)).

Ada kisi pewarisan untuk pewarisan berganda di antara Kategori. mis. Kategori Monad mewarisi dari SetCategory, Monoid dari Monad, Grup dari Monoid, dll., dll.

Ada juga polimorfisme tingkat tinggi, sedikit seperti Generics in Java.

Beberapa aksi dalam Aksioma dapat dilihat sebagai Functors, tapi itu akan lebih banyak untuk masuk ke sini!

Jika Anda hanya ingin menggunakan Aksioma tanpa khawatir tentang Kategori Teori, sebagai pengguna akhir biasa, maka sistem perhitungan simbolis adalah bagian yang tepat dari perangkat lunak untuk melihat aljabar individu.

Berikut ini banyak jawaban yang menarik, tetapi tidak ada yang menyebutkan setiap bahasa $L \subseteq X^{\ast}$ secara alami dikaitkan dengan struktur monoid melalui hubungan kongruensi Nerode-Myhill.

Orang-orang berikut telah menggunakan pandangan aljabar ini dalam kasus bahasa reguler: Samuel Eilenberg pada Teori Automata, Jean Berstel , pin Jean-Eric , Marcel Schützenberg dan Teori Krohn-Rhodes .

Juga ada aljabar nontrivial yang terlibat dalam pekerjaan di sekitar dugaan Cerny , sebagian besar cukup kombinatorial. Tetapi baru-baru ini saya telah melihat lebih banyak dilakukan dengan aljabar linier, teori cincin dan teori representasi, mencari pekerjaan Benjamin Steinberg dan Jorge Almeida .

Ngomong-ngomong, Anda bisa tampil cukup baik di area ini dengan teori Semigroup-, Monoid- dan Group, tetapi teori Kategori dan Teori Homotopy tidak banyak digunakan di area ini. Tetapi mungkin menarik untuk dicatat bahwa S. Eilenberg adalah salah satu pendiri dari Teori Kategori, meskipun ini sebelum ia terlibat dalam Teori Automata.

Tesis Brent Yorgey , walaupun masih berupa konsep, melakukan pekerjaan yang luar biasa dalam menjelaskan mengapa minat Anda relevan dengan TCS.

Berikut ini adalah pembicaraan Joyal April lalu tentang materi terkait.

Saya tidak tahu apakah Anda telah mempertimbangkan industri, tetapi perusahaan Ayasdi melakukan pekerjaan luar biasa menerapkan banyak homotopy dan metode topologi terapan lainnya dalam ilmu data. Mereka memadukan banyak teori dengan aplikasi. Pada dasarnya, untuk melihat apa yang mereka lakukan, lihat situs web Stanford Comptop. (Mayoritas orang berasal dari sana).

Selain apa yang dikatakan orang lain (saya kira aplikasi terbesar dari cabang-cabang ini memang dalam sistem tipe):

• Teori kisi dan perintah parsial pada umumnya diterapkan sedikit untuk analisis perilaku sistem terdistribusi, dan untuk analisis aliran data dalam kompiler.
• Saya juga melihat koneksi Galois diterapkan pada pembelajaran mesin (khususnya klasifikasi teks: koneksi Galois antara himpunan bagian dari simpul kiri dan kanan dari dokumen bipartit / grafik kata yang memungkinkan untuk secara dramatis mempercepat suatu algoritma).

Koneksi antara Aljabar dan Ilmu Komputer Teoritis sangat kuat. Nic Doye sudah menyebutkan Computer Aljabar, tetapi ia tidak secara eksplisit memasukkan teori sistem penulisan ulang, yang merupakan bagian penting dari Aljabar Komputer, dengan aplikasi dalam penyelesaian persamaan otomatis dan penalaran otomatis. Sistem penulisan ulang string adalah sub-area penting, dengan aplikasi dalam teori grup komputasi. Lihat buku "String Rewriting Systems", karya Ronald Book dan Friedrich Otto, misalnya.

Ada juga hubungan antara teori grafik dan aljabar, yang mencakup misalnya teori spektral grafik dan jaringan kompleks yang berkembang dengan baik, dan juga teori simetri grafik (grafik Cayley, grafik transek-simpul, dan jenis grafik simetris lainnya) , yang banyak digunakan sebagai model untuk jaringan interkoneksi di komputer paralel). Periksa buku "Teori Grafik Aljabar", oleh Chris Godsil dan Gordon Royle, untuk ikhtisar topik yang berbeda.

Lihatlah situasi dalam visi komputer. Ada banyak topik, khususnya, tentang tipe algoritmik, yang mana tiga area pertama yang Anda daftarkan sangat berguna.