Saya seorang jurusan matematika yang tertarik pada TCS.
Saya ingin mempelajari sendiri algoritme, dan kompleksitasnya untuk menyelesaikan masalah teoretis kelompok seperti urutan elemen, penghitungan coset, menemukan generator, menguji apakah subset yang diberikan menghasilkan grup.
Buku apa yang harus saya baca?
ds.algorithms
reference-request
gr.group-theory
books
ricardorr
sumber
sumber
Jawaban:
Jika Anda tertarik pada teori grup yang relevan untuk Graph Isomorphism, maka selain buku Seress yang David Eppstein sebutkan, saya akan sangat merekomendasikan
Di atas adalah sebuah buku tentang teori kelompok "hanya", tetapi dari buku-buku tentang teori kelompok murni, itu mungkin yang paling relevan dengan Graph Isomorphism.
Sebuah buku yang lebih langsung tentang algoritma untuk graf isomorfisme, yang menempatkan algoritme grup-teoretis di tengah panggung, adalah:
Yang terakhir (bersama-sama dengan tesis Paolo Codenotti) saat ini adalah salah satu dari sedikit tempat yang dapat diakses secara luas di mana Anda dapat benar-benar menemukan akun lengkap dari beberapa algoritma kelompok-teoretis yang lebih untuk isomorfisme grafik.
sumber
Itu benar-benar membuat perbedaan apa input untuk algoritma: bagaimana Anda menentukan grup?
Jika Anda ingin grup yang diberikan oleh generator dan relator, saya akan menyarankan Combinatorial Group Theory , oleh Magnus, Karrass, dan Solitar (tetapi algoritma ada yang jarang karena terlalu banyak masalah penting tidak dapat ditentukan).
Jika Anda ingin grup otomatis (grup yang elemen-elemennya adalah rangkaian simbol dan yang grup operasinya dijalankan oleh finata automata, dengan aplikasi dalam topologi dimensi rendah), saya akan menyarankan Word Processing in Groups oleh Epstein (bukan saya!), Cannon, Holt , Levy, Paterson, dan Thurston.
Jika Anda menginginkan grup permutasi (jenis grup-teoritik algoritma yang paling relevan misalnya untuk graf isomorfisme) maka Seress memiliki buku Algoritma Permutasi Grup tetapi saya tidak memiliki salinan jadi saya tidak dapat memberi tahu Anda apakah itu bagus.
Seharusnya ada paragraf keempat di sini tentang algoritma kelompok matriks tapi saya tidak tahu buku tentang topik itu. Ada sedikit liputan dalam buku Seress.
sumber
Referensi paling modern dan komprehensif mungkin adalah "Buku Pegangan Teori Grup Komputasi" oleh Holt, Eick dan O'Brien (tautan)
Referensi klasik adalah "Komputasi dalam Grup yang Dipresentasikan dengan Sempurna" oleh Charles Simms.
sumber
Bukan buku tapi mungkin A. Catatan Hulpke tentang Teori Grup Komputasi menarik?
sumber
Jika Anda hanya khawatir tentang grup permutasi terbatas, saya menemukan buku "Algoritma Fundamental untuk Grup Permutasi" oleh Gregory Butler sangat mudah dibaca. Ini hanya untuk grup permutasi terbatas tetapi merupakan satu-satunya buku yang memberikan kode pseudo dan deskripsi algoritmik yang dapat saya pahami (untuk Schreirer-Sims, perangkat pembangkit kuat, dll.). Buku Seress yang direkomendasikan oleh orang lain adalah layak tetapi untuk beberapa alasan dia memiliki keengganan untuk kode semu sehingga sangat sulit bagi saya untuk mengerti. Secara pribadi, saya menggunakan buku Butler untuk pemahaman konkret tentang algoritma dan buku Seress sebagai bantuan dalam memahami bukti kebenaran.
Buku Butler sudah cukup tua sekarang tapi saya masih belum menemukan pengantar yang lebih baik pada algoritma grup permutasi terbatas.
sumber
Saya memotong gigi pada Pencarian Pencacahan Generasi Algoritma Kombinatorial, http://www.math.mtu.edu/~kreher/cages.html .
Saya akan sangat merekomendasikannya. Anda belajar algoritma pengodean grup yang jauh lebih cepat karena contoh tangan akan rusak dengan sangat cepat. Juga ambil sistem seperti Sage atau Magma untuk digunakan sebagai kalkulator bangku.
sumber