> Top   >> 神大集中講義（このページ）

レポート提出 （dropbox; 締切: 7/31; レポート課題（pdf））

• （zip等で）1ファイルにまとめてください．ファイルサイズは50MB以下．
• 学籍番号，氏名をレポート内に明記．不明の場合は成績評価されません．

参考書

1. Olle Häggström, Finite Markov Chains and Algorithmic Applications (London Mathematical Society Student Texts, Series Number 52), Cambridge University Press, 2002.
2. Alistair Sinclair, Algorithms for Random Generation and Counting: A Markov Chain Approach, Springer, 1993
3. David A. Levin and Yuval Peres, Markov Chains and Mixing Times, second edition, American Mathematical Society,2017. https://pages.uoregon.edu/dlevin/MARKOV/
4. Mark Jerrum, Counting, Sampling and Integrating: Algorithms and Complexity, Lectures in Mathematics. ETH Zuerich, Springer, 2013.

5. Bernhard Korte and Jens Vygen, Combinatorial Optimization: Theory and Algorithms,sixth edition, Springer, 2018.
6. Michael Sipser, Introduction to the Theory of Computation, third edition, Course Technology, 2012.

参考論文

7. Mark R. Jerrum, Leslie G. Valian and Vijay V. Vazirani, Random generation of combinatorial structures from a uniform distribution, Theoretical Computer Science, 43:169--188, 1986. https://doi.org/10.1016/0304-3975(86)90174-X
8. Martin Dyer and Catherine Greenhill, Polynomial-time counting and sampling of two-rowed contingency tables, Theoretical Computer Science, 246(1-2): 265--278, 2000. https://doi.org/10.1016/S0304-3975(99)00136-X
9. Shuji Kijima and Tomomi Matsui, Polynomial time perfect sampling algorithm for two-rowed contingency tables, Random Structures & Algorithms, 29(2):243--256, 2006. https://doi.org/10.1002/rsa.20087
10. Persi Diaconis and Daniel Stroock, Geometric bounds for eigenvalues of Markov chains, Annals of Applied Probability, 1(1):36-61, 1991. https://doi.org/10.1214/aoap/1177005980
11. Alistair Sinclair, Improved bounds for mixing rates of Markov chains and multicommodity flow, Combinatorics, Probability and Computing , 1(4):351--370, 1992. https://doi.org/10.1017/S0963548300000390
12. Mark Jerrum, Alistair Sinclair and Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Journal of the ACM, 51(4); 671--697, 2004.
    https://doi.org/10.1145/1008731.1008738
13. Takeharu Shiraga, Yukiko Yamauchi, Shuji Kijima and Masafumi Yamashita, Deterministic random walks for rapidly mixing chains, SIAM Journal on Discrete Mathematics, 32(3):2180--2193, 2018. https://doi.org/10.1137/16M1087667
14. Ei Ando and Shuji Kijima, An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution, Algorithmica, 76:4 (December 2016), 1245--1263. https://doi.org/10.1007/s00453-015-0096-5
15. Shuji Kijima, Nobutaka Shimizu and Takeharu Shiraga, How many vertices does a random walk miss in a network with a moderately increasing number of vertices?, Mathematics of Operations Research, to appear. https://doi.org/10.1287/moor.2023.0060

参考資料

16. MiraikanChannel, 『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！, YouTube, 2012.
    https://www.youtube.com/watch?v=Q4gTV4r0zRs
17. 渡辺治, 根上生也, 松井知己, Web鼎談：コンピュータ・サイエンスから生まれる新しい基礎科学，1999.
    https://tcs.c.titech.ac.jp/webteidan/index.html
18. 来嶋秀治, 松井知己, 完璧にサンプリングしよう！,
    1. 第一話 遥かなる過去から, オペレーションズ・リサーチ，50(3):169--174, 2005.
       https://orsj.org/wp-content/or-archives50/pdf/bul/Vol.50_03_169.pdf
    2. 第二話 天と地の狭間で, オペレーションズ・リサーチ，50(4):264--269, 2005.
       https://orsj.org/wp-content/or-archives50/pdf/bul/Vol.50_04_264.pdf
    3. 第三話 終わりある未来, オペレーションズ・リサーチ，50(5):329--334, 2005.
       https://orsj.org/wp-content/or-archives50/pdf/bul/Vol.50_05_329.pdf
19. 来嶋秀治, 乱択と計算, 応用数理, 27(3):15--23, 2017.
    https://doi.org/10.11540/bjsiam.27.3_15.
20. 来嶋秀治, 清水伸高, 白髪丈晴, 動的グラフ上のランダムウォーク, 応用数理, 32(1), 5--15, 2022.
    https://doi.org/10.11540/bjsiam.32.1_5.