講義情報

離散アルゴリズム理論

• 講義計画
  
  
• 期末試験 7/25(木) 10:30～12:00 総合研究7号館 W1講義室（教室変更注意）

• 参考書
• アルゴリズムの基礎知識
• T. Cormen, C. Leiserson, R. Rivest, and C. Stein: “Introduction to Algorithms (third edition)”, MIT Press, 2009.
• （上記第2版の日本語訳） 浅野哲夫他訳：「アルゴリズムイントロダクション」1～3巻, 近代科学社, 1995.
• 茨木俊秀：「Cによるアルゴリズムとデータ構造」, 昭晃堂, 1999.
• 形式言語理論
• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: "Introduction to Automata Theory, Languages, and Computation: Pearson New International Edition (third edition)", Pearson Education Limited, 2013.
• （上記第2版の日本語訳） 野崎昭弘他訳：「オートマトン言語理論 計算論I（第2版）」, 近代科学社, 2003.
• （上記第2版の日本語訳） 野崎昭弘他訳：「オートマトン言語理論 計算論II（第2版）」, 近代科学社, 2003.
• SATソルバ
• 番原睦則他: 「特集　SAT技術の進化と応用」, 情報処理学会誌「情報処理」, Vol.57, No.8, 2016.
• D. E. Knuth:  "Satisfiability", In "The Art of Computer Programming", Vol. 4-6, Addison-Wesley, 2015.
• BDD/ZDD
• 湊 真一(編), ERATO 湊離散構造処理系プロジェクト(著): "超高速グラフ列挙アルゴリズム－〈フカシギの数え方〉が 拓く，組合せ問題への新アプローチ－," ISBN: 978-4627852617, 森北出版, Apr. 2015.
• D. E. Knuth: "The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams,"Addison-Wesley Professional, ISBN 978-0321580504, 2009.  
  （世界中で読まれているKnuthの名著の最新巻。後半はBDDに関する章。湊が考案したZDDも詳しく書かれている。）
• Shin-ichi Minato: "Data Mining  Using Binary Decision Diagrams," In T. Sasao and J. Butler, editor, "Progress in Representation of Discrete Functions (Synthesis Lectures on Digital Circuits and Systems)," chapter 5, pp. 97-109, Morgan & Claypool Publishers, May 2010.
• Shin-ichi Minato: "The Power of Enumeration - BDD/ZDD-Based Algorithms for Tackling Combinatorial Explosion," In T. Sasao and J. Butler, editor, "Applications of Zero-Suppressed Decision Diagrams (Synthesis Lectures on Digital Circuits and Systems)," chapter 3, pp. 49-62, Morgan & Claypool Publishers, Nov. 2014.
• その他、インターネットで「BDD」をキーワード検索すると最近の情報が多数ヒットする。