コース情報 | 知能情報処理特論(99MD009)

知能情報処理特論(99MD009)

授業科目名	知能情報処理特論(99MD009)	授業科目名(英）
教員名	熊澤　努
開講年度学期	2026年度前期
曜日時限	火曜6限
開講学科	大学院工学研究科数理情報科学専攻・機械工学専攻

単位	2.0	学年	修士課程1年
科目区分・授業形態	専門科目講義・演習	単位区分	選択

授業概要	数理情報科学を修めるには，基礎的な事項の理解を深めることが大変重要である．この授業では，数理情報科学の情報科学的な側面側面に着目し，オートマトン理論とアルゴリズムを修得することを目的とする．の最新の教科書を輪講して，．授業は，以下に示すオートマトン理論に関する最新の教科書から、各回1から2章を選び、輪講形式で授業を行う． Javier Esparza, Michael Blondin, "Automata Theory An Algorithmic Approach", MIT Press, 2023. この授業では、教科書で扱われている様々なトピックの数理的な基礎付けとアルゴリズムを学ぶだけでなく，学んだ内容を人に伝えるプレゼンテーションを積極的に行う姿勢が求められる．【実務経験教員による授業】 ■本科目の担当教員である熊澤努は，2001年度から2004年度まで、株式会社アドバンテストで産業用機器のソフトウェア開発に携わった。また、2011年度から現在にかけて、株式会社SRAにてソフトウェアシステムの研究並びに開発に従事しており、その業務で養った経験を活かし、数理情報科学に関する実用上重要な内容を講義する．
達成目標	・有言長の語の上のオートマトンに関する基礎理論と代表的な応用を理解することができる。　・無限長の語の上のオートマトンに関する基礎理論と代表的な応用を理解することができる。　・オートマトン理論で用いられる代表的なアルゴリズムを説明することができる。
DPとの関連性	DP1：〇 DP2： DP3：
成績評価方法	達成目標事項についての演習・小問・レポート課題を行い、その成績の合計に応じて以下のように評価を与える。評価は質的評価(60%)，量的評価(40%)を併用する．質的評価に用いるルーブリックをMoodle上で履修者に公開する． S：90～100点、A：80～89点、B：70～79点、C：60～69点、D：59点以下　不合格再試験：無
教科書	必要に応じて資料を配布する．輪講を行う教科書については教員の指示に従うこと．
参考書	Javier Esparza, Michael Blondin, "Automata Theory An Algorithmic Approach", MIT Press, 2023.
履修上の注意

授業計画

授業計画

第１回：授業ガイダンス、輪講の進め方の説明を行う。

第２回：1章 Automata Classes and Conversionsの輪講を行う。
有限長語上で定義される有限オートマトン，正規言語とそれらの間の変換について理解する。

第３回：2章 Minimization and Reductionの輪講を行う。
　有限オートマトンの最小化，簡約について学習する。

第４回：3章 Operations on Setsの輪講を行う。
オートマトンに関するアルゴリズムと，それらの計算量を修得するために必要な集合演算の実装に関して学ぶ。

第５回：4章 Application I: Pattern Matchingの輪講を行う。
オートマトン理論の応用例として，パターン照合の技法を学習する。

第６回：5章 Operations on Relations: Implementationsの輪講を行う。
オートマトンに関するアルゴリズムと，それらの計算量を修得するために必要な関係演算の実装に関して学ぶ。

第７回：6章 Finite Universes and Decision Diagramsの輪講を行う。
有限オートマトンを計算機で効率的に扱うデータ構造について学習する。

第８回：7章 Application II: Verificationの輪講を行う。
有限オートマトンの形式検証への応用を学ぶ．

第９回：8章 Automata and Logicの輪講を行う。
　　　　有限オートマトンと記号論理学との関係を学習する。

第１０回：9章 Application III: Presburger Arithmeticの輪講を行う。
　有限オートマトンの第3の応用例として，プレスバーガー算術を学習する。

第１１回：10章 Classes of ω-Automata and Conversionsの輪講を行う。
無限長語上で定義される言語とオートマトンを学習する。ω-正規言語と代表的なトω-オートマンを理解する。

第１２回：11章 Boolean Operations: Implementationsの輪講を行う。
　　　　ω-オートマンを計算機で実装する際に必要なデータ構造を学ぶ。

第１３回：12章 Emptiness Check: Implementationsの輪講を行う。
無言語を受理するオートマンの空性検査アルゴリズムの計算機での実装とその活用について学ぶ。

第１４回：13章 Application I: Verification and Temporal Logicの輪講を行う。
無言語を受理するオートマンの第一の応用として，時相論理を用いた形式検証を学習する。

第１５回：14章 Application II: Logics on ω-Words and Linear Arithmeticの輪講を行う。
無言語を受理するオートマンの第二の応用として，有限長語上の様相2階論理を学習する。

----
[授業外学習]

授業は輪講形式で行う．教科書の担当個所について，授業前に概要を調査した資料を作成しておくこと．また，各回の授業後には教科書を読み，Moodleのフォーラム等を使用して不明点を履修者並びに教員と議論をして理解を深めること．
予習と復習には90分程度かけることが期待される．　

注意