Apakah ada topik dalam CS teoretis yang lebih tentang matematika murni?

Saya seorang mahasiswa pascasarjana dalam ilmu komputer teoretis, dan khususnya, algoritma perkiraan. Sekarang saya menemukan bahwa saya lebih tertarik pada matematika murni (saya dapat mengatakan ini karena saya tampaknya lebih menikmati kursus matematika daripada kursus CS). Saya ingin bertanya apakah ada bidang dalam ilmu komputer teoretis yang cukup banyak matematika murni (lebih tepatnya, bidang yang menarik dalam matematika murni sendiri tanpa mempertimbangkan aplikasi untuk CS), atau jika saya perlu pertimbangkan peralihan besar. Saya sudah dua setengah tahun mengikuti program ini, jadi saya tidak yakin apakah peralihan akan menjadi ide bagus saat ini.

Satu-satunya hal yang dapat saya temukan adalah grafik teori minor, dari menelusuri daftar penerimaan konferensi top. Tapi itu tidak dihitung sebagai 'area' bagi saya yang bisa saya fokuskan.

Berikut adalah tiga bidang lagi yang sesuai dengan kriteria Anda.

• Teori kategori . Ini jelas menarik bagi sebagian besar bidang matematika murni, tetapi juga sangat berpengaruh dalam teori bahasa pemrograman (fungsional, berurutan).

• Logika , khususnya teori pembuktian. Koneksi dengan ilmu komputer terlalu banyak untuk disebutkan, tetapi logika bukan hanya bidang matematika murni yang kaya, tetapi juga fondasi matematika.

• Teori bilangan , "ratu matematika", yang dianggap tanpa aplikasi ... sampai kriptografi muncul.

Ya: Teori grafik, geometri komputasi, teori kompleksitas, kombinatorik adalah hal-hal yang saya teliti di CS. Ruang vektor dan teori ukuran bisa berguna dalam pembelajaran mesin teoretis juga.

Ada banyak matematika murni yang digunakan dalam CS teoretis, tetapi mereka tidak mencapai berita sesering AI dan pembelajaran mesin, itulah sebabnya Anda tidak terlalu banyak mendengarnya.

Saya pribadi beralih ke CS dari fisika dan matematika murni (ya, seperti matematika aljabar abstrak), dan tidak pernah berhenti menemukan masalah yang menarik.

• Teori kompleksitas geometris sangat "matematis" dan banyak simpatisan utamanya adalah lebih banyak ahli matematika. lihat misalnya Teori Kompleksitas Geometrik: pengantar untuk geometer / Landsberg
• Teori grup sedang terhubung ke TCS dalam banyak cara mendalam misalnya dalam studi masalah kata, isomorfisma, dan ketidakpastian. lihat misalnya MASALAH KATA DAN MASALAH ISOMORFISME UNTUK KELOMPOK / Stillwell
• beberapa teori automata sangat matematika misalnya sambungan semigroups untuk transduser negara yang terbatas dll lihat misalnya Yayasan Matematika dari Automata Teori / Pin

$\mathbb{B}$$\mathbb{F}_2$

Sebagai contoh, seseorang menggunakan semigroup (juga grup juga memainkan peran penting) dan banyak hasil pada semigroup terbatas dalam beberapa tahun terakhir pada awalnya dimotivasi oleh teori automata. Semiring juga digunakan (bukan cincin): misalnya, semiring tropis pertama kali diperkenalkan dalam teori automata sebelum digunakan dalam geometri tropis , area baru yang sukses dalam matematika. Topik lain yang terkait dengan automata termasuk teori logika dan model terbatas (pikirkan teorema pohon Rabin), topologi, dualitas dan (kuasi) ruang-seragam dan beberapa teori bilangan (terutama untuk pertanyaan yang berhubungan dengan sistem numerasi dan rangkaian daya formal), teori probabilitas ( terutama rantai Markov) dan teori permainan.

Untuk mengatakan lebih banyak tentang Geometric Complexity Theory (GCT): ini adalah penerapan teori aljabar dan teori representasi menuju program jangka panjang untuk menyelesaikan P versus NP. Pertanyaan yang diajukan dalam GCT cenderung pertanyaan matematika yang mendalam, beberapa di antaranya kembali lebih dari 100 tahun ke pelopor geometri aljabar dan teori representasi - tampaknya tidak ada hubungannya dengan perhitungan, tetapi melalui GCT kita melihat bahwa mereka sebenarnya terkait erat dengan kompleksitas komputasi - dan lainnya yang menimbulkan pertanyaan dan ide baru dalam matematika murni (sekali lagi, geometri aljabar dan teori representasi).

Bukan sepenuhnya topik CS teoritis tetapi menggunakan banyak hasil dari CS teoretis: Anda mungkin tertarik dengan verifikasi perangkat lunak yang tujuannya adalah untuk memastikan bahwa suatu program melakukan apa yang seharusnya dilakukan, dan tidak ada yang lain. Di antara berbagai teknik dalam topik itu, beberapa di antaranya berorientasi pada matematika. Banyak sistem kritis, khususnya avionik / spasial / nuklir, telah dibuktikan dengan cara itu untuk memastikan mereka bebas bug.

Banyak bidang matematika yang terlibat: logika, teori bukti, teori automata, teori himpunan, ...