到達目標
・計算問題の分類を説明できる
・計算問題の性質を説明できる
・形式言語の概念について説明できる
・チューリングマシンの概念を説明できる
・オートマトンの概念を説明できる
・有限オートマトンと正規表現の関係を説明できる
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 計算問題 | 等価な計算問題どうしを還元できることを理解できる | 計算問題を分類できる | 計算問題とは何か理解していない |
| チューリングマシン | チューリングマシンがいくつかのプログラミング言語と等価であることを説明できる | チューリングマシンの汎用性を理解できる | チューリングマシンとは何か理解していない |
| オートマトン | 特定の言語を受理するオートマトンを自分で構成できる | 与えられた言語をオートマトンが受理するかどうか判断できる。 | オートマトンとは何か理解していない |
| 有限オートマトンと正規表現 | 任意の有限オートマトンと対応する正規表現との変換ができる | 任意の有限オートマトンと対応する正規表現との変換方法を知っている | 有限オートマトンと正規表現の関係性を理解していない |
学科の到達目標項目との関係
学習・教育到達度目標 B① 専門分野における工学の基礎を理解できる。
学習・教育到達度目標 B② 自主的・継続的な学習を通じて、専門工学の基礎科目に関する問題を解くことができる。
JABEE SB① 共通基礎知識を用いて、専攻分野における設計・製作・評価・改良など生産に関わる専門工学の基礎を理解できる。
JABEE SB② 自主的・継続的な学習を通じて、専門工学の基礎科目に関する問題を解決できる。
教育方法等
概要:
計算問題の分類、基本的な計算モデルを学び、計算可能性理論について議論する。
授業の進め方・方法:
授業では講義と演習を組合せて進める。
注意点:
すべての課題レポートを提出しなければ、不合格とする。
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
ガイダンス |
|
| 2週 |
「プログラム」の定式化 |
プログラムをどのように定式化できるか説明できる
|
| 3週 |
不可能なプログラム |
問題の計算不能性を証明するパターンを説明できる
|
| 4週 |
計算問題 |
計算問題そのものおよび計算問題を解くことの形式的な定義を示すことができる
|
| 5週 |
チューリングマシン（1） |
等価なチューリングマシンどうしの関係を説明できる
|
| 6週 |
チューリングマシン（2） |
チューリングマシンとプログラムが「解ける計算問題が何か」ということについて等価であることを説明できる
|
| 7週 |
万能コンピュータプログラム（1） |
万能な計算モデルについて説明できる
|
| 8週 |
万能コンピュータプログラム（2） |
万能な計算モデルに基づき、計算不能問題について議論できる
|
| 2ndQ |
| 9週 |
還元（1） |
還元の概念を説明できる
|
| 10週 |
還元（2） |
計算不能性の証明のパターンを説明できる
|
| 11週 |
非決定性（1） |
プログラムの非決定性について説明できる
|
| 12週 |
非決定性（2） |
非決定性と計算問題の関係を説明できる
|
| 13週 |
有限オートマトン（1） |
有限オートマトンについて説明できる
|
| 14週 |
有限オートマトン（2） |
正規表現とオートマトンについて説明できる
|
| 15週 |
計算モデル |
プログラミング言語は計算モデルによって分類されることを説明できる。
|
| 16週 |
|
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | プログラミング | プログラミング言語は計算モデルによって分類されることを説明できる。 | 4 | 前15 |
| 主要な計算モデルを説明できる。 | 4 | 前5,前6,前7,前8,前11,前12,前13,前14,前15 |
| システムプログラム | 形式言語の概念について説明できる。 | 4 | 前4 |
| オートマトンの概念について説明できる。 | 4 | 前13,前14 |
| コンパイラの役割と仕組みについて説明できる。 | 4 | 前4 |
| 形式言語が制限の多さにしたがって分類されることを説明できる。 | 4 | 前4 |
| 正規表現と有限オートマトンの関係を説明できる。 | 4 | 前14 |
| 情報数学・情報理論 | 集合に関する基本的な概念を理解し、集合演算を実行できる。 | 4 | 前4 |
| 集合の間の関係(関数)に関する基本的な概念を説明できる。 | 4 | 前4 |
評価割合
| 小テスト等 | 課題・レポート等 | 合計 |
| 総合評価割合 | 40 | 60 | 100 |
| 基礎的能力 | 0 | 0 | 0 |
| 専門的能力 | 40 | 60 | 100 |
| 分野横断的能力 | 0 | 0 | 0 |