授業科目一覧
プログラム
メニューここまで

計算論('16)

※印刷用にはシラバスPDF版新規ウィンドウ をご利用ください
主任講師
隈部 正博 (放送大学教授)
放送メディア
ラジオ
放送時間(平成29年度)
第1学期:(木曜)1時30分~2時15分
第2学期:(火曜)13時00分~13時45分

講義概要

最初に、言語、文法とは何かを考える。次に現代言語学の父といわれるチョムスキーの定義した様々な形の文法を学び、それによってどんな言語が生成されるかをみる。次に計算という概念について考える。言語を構成(計算)するための機械であるオートマトンを定義し、様々な種類のオートマトンの形を学ぶ。その後、計算機科学の父といわれるチューリングの定義したチューリング機械を理解し、多くの計算がチューリング機械をつかって表現できることをみる。最後にアルゴリズムとは何かを考える。
※詳しくはシラバス

開設年度
平成28年度
科目区分
自然環境科学プログラム
科目コード
8960631
単位数
2単位
単位認定試験
試験日・時限
平成29年度 第1学期:平成29年7月21日(金曜)3時限(11時35分~12時25分)
平成29年度 第2学期:平成30年1月20日(土曜)4時限(13時15分~14時05分)
単位認定試験
平均点
(平成28年度 第1学期)80.4点
(平成28年度 第2学期)80.6点
備考
「計算論('10)」の単位修得者は履修不可
このページのトップへ本文ここまで

授業の目標

計算とは何か? コンピューターの動作はもちろん計算といえる。また人間の話す(考える)言語やその文法も計算の1つの形である。このように計算という概念を幅広く捉え、様々な種類に分けて解説する。そして最終的には、計算機の数学的モデルといわれるチューリング機械がどのような構造を持っているかを理解する。また文法によって生成される(形式)言語がどのようなものか理解し、様々な文法と言語との関わりを理解する。その際、文法によって生成される言語と、オートマトンによって計算される言語、これらの関連性を理解することが目標となる。

履修上の留意点

予備知識は仮定しない。計算や言語、文法という概念について、論理的立場から解説するが、数学のみならず、コンピューターや言語に興味のある学生向けの授業でもある。

シラバス

テーマ 内容 執筆担当講師名
(所属・職名)
放送担当講師名
(所属・職名)
1 準備 これから授業を進めるにあたって必要な予備知識を解説する。

【キーワード】
数学的帰納法、集合、直積、記号列
隈部 正博
(放送大学教授)
隈部 正博
(放送大学教授)
2 言語 言語、文法とは何か、定義する。そして様々な例を通して、理解を深める。

【キーワード】
言語、文法
隈部 正博
(放送大学教授)
隈部 正博
(放送大学教授)
3 チョムスキーの階層 チョムスキーの階層といわれる、様々な文法や言語の階層について、例を挙げながら学ぶ。

【キーワード】
チョムスキーの階層、文脈依存文法、文脈自由文法、正規文法
隈部 正博
(放送大学教授)
隈部 正博
(放送大学教授)
4 有限オートマトン 言語を計算する一つの形であるオートマトンとは何か、その定義を述べ、簡単な例を学ぶ。

【キーワード】
オートマトン、遷移関数
隈部 正博
(放送大学教授)
隈部 正博
(放送大学教授)
5 オートマトンによって受理される言語 様々なオートマトンの例を通して、どのような言語が作られるかをみる。

【キーワード】
受理される言語
隈部 正博
(放送大学教授)
隈部 正博
(放送大学教授)
6 非決定性オートマトン 機械が次のステップで行う動作が一つに限らない、非決定性オートマトンを定義し、いくつかの例を考える。

【キーワード】
決定性オートマトン、非決定性オートマトン
隈部 正博
(放送大学教授)
隈部 正博
(放送大学教授)
7 決定性オートマトンと非決定性オートマトン 非決定性オートマトンによって受理される言語は、決定性オートマトンによっても受理されることを示す。

【キーワード】
等価、状態の道
隈部 正博
(放送大学教授)
隈部 正博
(放送大学教授)
8 正規文法とオートマトン 正規文法で生成される言語と、オートマトンによって受理される言語が等しいことを例を挙げながら解説する。

【キーワード】
正規文法
隈部 正博
(放送大学教授)
隈部 正博
(放送大学教授)
9 2方向有限オートマトン 今まで定義したオートマトンを改良し、機械のヘッドが左右に動く2方向オートマトンについて、その定義を述べ、幾つかの例を学ぶ。

【キーワード】
2方向オートマトン、ループ
隈部 正博
(放送大学教授)
隈部 正博
(放送大学教授)
10 1方向オートマトンと2方向オートマトン 2方向オートマトンによって受理される言語は、1方向オートマトンによっても受理されることを、例を挙げながら解説する。

【キーワード】
状態の列、適合、重ね合わせ
隈部 正博
(放送大学教授)
隈部 正博
(放送大学教授)
11 ε-動作を含む非決定性オートマトン 非決定性オートマトンの定義をさらに改良して、ヘッドが動かず機械の状態のみを変化させるような動作を追加したオートマトンを定義する。このε-動作を含む非決定性オートマトンと、含まない非決定性オートマトンが等価であることをみる。

【キーワード】
ε-動作
隈部 正博
(放送大学教授)
隈部 正博
(放送大学教授)
12 正規表現 言語を式で表すことを考え、正規表現を解説する。そして正規表現で定義される言語がオートマトンによって受理される言語に等しいことを見る。

【キーワード】
正規表現
隈部 正博
(放送大学教授)
隈部 正博
(放送大学教授)
13 チューリング機械 コンピューターの数学的モデルである、チューリング機械とはどういうものか考える。幾つかの例を通して理解を深める。

【キーワード】
チューリング機械、時点表示
隈部 正博
(放送大学教授)
隈部 正博
(放送大学教授)
14 様々なチューリング機械 チューリング機械の様々な例を考える。また複数のテープを備えた多テープチューリング機械を定義する。そして、多テープチューリング機械と1テープチューリング機械が等価であることを示す。さらに非決定性チューリング機械を定義する。

【キーワード】
多テープチューリング機械、非決定性チューリング機械
隈部 正博
(放送大学教授)
隈部 正博
(放送大学教授)
15 アルゴリズムの概念 非決定性チューリング機械と決定性チューリング機械は等価であることを示す。次にチューリング機械と文法の概念が等しいことをみる。最後にアルゴリズム、計算とは何か、考察する。

【キーワード】
P=NP問題、アルゴリズム、計算、チャーチの提唱
隈部 正博
(放送大学教授)
隈部 正博
(放送大学教授)
このページのトップへ本文ここまで
授業科目案内 大学院 放送大学