計算機数学

概要

「この問題は計算機でも計算できないなぁ」「君は実に…計算が下手なんだなぁ」「そうじゃなくて計算できないことが証明できるんだよ」「え?どゆこと?」 「計算」とは何か,「計算できるか/できないか」というような問いに対して,数学では,「計算機が行なうこと」を「計算」と考え,計算機が行なえることを「計算モデル」として定式化することによって「計算」を定義し,明確に答えることを可能にしてきた。本講義では,代表的な計算モデルを取り上げながら,計算の理論・アルゴリズムの概念・計算量の理論の初歩を紹介し,計算の可能性・効率について論ずると共に,具体的な例として幾つかの基礎的な数理アルゴリズムについて触れる。 講義中心で行なう。数学の講義では,一つ一つの主張について「本当にそうか」「具体例ではどうか」「何故そうか」など常に主体的批判的に考えながら納得し理解することが重要である。そのように講義中心の授業にアクティブに取組むための留意点について注意し,授業内で取組みを適宜促す。 初回授業までに履修登録の上,Loyola授業掲示板を確認して,moodleコースに登録すること。 ・Loyola授業掲示板・moodleを通じて解説資料・演習問題を事前に提示することがあるので,目を通した上,必要に応じて予め手元において受講されたい。 ・指示された演習課題について,清書した答案を,授業終了後にmoodleを通じて提出する。提出方法の詳細についてはmoodleで指示する。 ・Loyola授業掲示板・moodleを通じて,まとめや自習課題,より進んだ学修に向けての補足などのプリントを配布することがある。 (授業開始後の状況により,変更することもあり得る。) この科目は情報理工学科CP5の前半「全ての情報分野における基礎的理論を理解するため,数学の基礎科目を通じて,最低限の知識を学生全員に身に付けさせる」科目に相当するに加え,CP2〜4の理論的基礎ともなる科目であり,「情報理工学Ⅲ(計算と情報の理論)」に引続く科目である。

目標

・有限オートマトン・プッシュダウンオートマトン・チューリング機械などの計算モデルについて理解する ・上記のような計算モデルによる計算と計算可能性について理解する ・計算量の概念を理解する ・上記のような内容を数学の言葉で定式化し論じられるようになる などにより,情報理工学科DP1に掲げる「現代社会の広い意味での「情報」に関して,その意味づけや原理・理論さらには(略)を理解」するとともに,DP5に掲げる「情報科学を含むすべての現代科学の理解に不可欠な数学の知識を学び,現代社会の情報技術におけるさまざまな問題を主体的に解決できる能力」の基礎を身に着ける。

授業外の学習

事前:「情報理工学Ⅲ(計算と情報の理論)」(特に後半の計算理論)の復習をしておくことが予習になるだろう(週１時間程度)。 予習:事前に提示された解説資料・練習問題などがあれば取り組んでおくこと(週１時間程度)。 復習:内容の確認とともに,配布する演習問題にも意欲的に取り組んでもらいたい(週２時間程度)。

所要時間: ３〜４時間程度