本文へジャンプ

学科概要
  • HOME
  • 学科概要
  • 学生による学科紹介

学生による学科紹介

3年生冬学期

コンピュータネットワーク | 加藤 朗(かとう あきら) 東京大学情報基盤センター准教授
開講時間:水曜2限 | 必修科目
シラバス
コンピュータネットワークの基礎について、特に現在のインターネット環境で良く使われているネットワーク技術を中心に紹介する。 Layer-2 に関しては、 Ethernet や Bridge、Spanning Tree について述べ、Layer-3/-4 に関して TCP/IP を中心に経路制御や IPV6、TCP のアルゴリズムを紹介する。なお、可能であればネットワークプログラミングについてもそのさわりを紹介し、多少のプログラム作成を課す予定である。
要約
現在のワールドワイドウェブの根幹を成しているコンピュータネットワークの講義です。コンピュータ間の通信に使われるケーブルや規格、ネットワークで用いられるアルゴリズムなどを含め、過去のものから現在運用されているものまでネットワークのあらゆる技術を学習します。
学習すること
講義では、OSI参照モデル(図)の最低層である物理層からトランスポート層までを順に具体的に見ていきます。

物理層では、先生が教室にイーサネット(データリンク層の1つで、皆さんのコンピュータもイーサネットを使っていると思います)で使用する光ファイバーケーブルや、今では日常生活で余り目にすることの無い同軸ケーブルの実物を持ってきてくださり、それを手にとって見ることができます。

データリンク層では、スイッチの機能であるスパニングツリー(スイッチを環構造に繋いだときにループしないようにうまく制御する)や仮想LAN(複数のLANを仮想的に実現する)の詳細を学習しながらイーサネットの基本的な知識を得ます。

ネットワーク層では、今日おもに使われているIPというプロトコルについて、IPv4とIPv6を比較することによって基本を抑えながら、RIPや OSPFなどの経路制御プロトコルについて学習します。経路制御というのは、例えば皆さんが家から学校のサーバにアクセスしたいときに、途中でどういう道順で通信しようかな、というのを決めることです。また、皆さんはpingというコマンドを打ったことがあるかもしれませんが、それに使われているICMPというプロトコルについても軽く触れます。

最後にトランスポート層では、皆さんがWebサイトを見たりメールを送受信したりするのに使用しているTCPプロトコルと、ストリーミング配信を受信したりIP電話をするのに使用しているUDPプロトコルについて学びます。途中で通信内容が抜け落ちてしまった時などにどのように対処されているのか、というのを学ぶのがこの項目です。

このように本講義では、普段何気なく使っているインターネットにおいて普段見えている層(アプリケーション層)の下ではどのようなことが行われていて、どういう技術が使われているのか、エラーが起きるとどういうことが起きて、どのように対処しているのか、を学びます。

講義の流れ
講義はスライドを説明する形で進められます。スライドは公開されていないので、自分でメモを取ったりします。(ただしスライドで使用している図・グラフなどはプリントとして配布されます) この講義の一番面白いところは先生の小話でした。WIDEプロジェクトに所属していらっしゃる加藤先生は、当学科の平木教授らとともに10ギガビットネットワークを利用したインターネット速度記録で新記録を達成されました。情報基盤センターでネットワークの管理を担当なさっていたり、以前プロトコルの策定に携わっていたりするので、そこでの小話を講義中に聞くことができます。
評価方法
出席状況と試験で成績が決まります。筆者が受講した2007年冬学期には小レポートが課せられるかも、と初回の講義の際におっしゃられましたが、結局レポートは課せられませんでした。試験後の加藤先生によるレビューメールによると、出席:試験が1:3の割合でした。出席点は上の計算では少なめですが、試験の成績が良くなかった場合の助け舟になります。本番に弱い人はが講義をサボってしまうと大変なことになりますので注意しましょう。遅刻した場合もしっかり遅刻とカウントされてしまうので、午前中ですが開始時刻に遅れないように講義に出席しましょう。
試験の傾向
講義で勉強したネットワークの知識を使って実際のネットワークの経路の決定や、与えられた数値から通信速度の理論値を計算する問題が出題されるようです。光ファイバーケーブルの種類などの細かい話も講義で紹介されますが、そういった細かい知識よりも考案されたアルゴリズムなど、実際にコンピュータやルータの中でどのような計算がされているのかを重点的に復習しておくのが良いと思われます。筆者が受講した時は「持ち込み可で難しい試験」と「持ち込み無しで比較的易しい試験」のどちらがいいかを講義中に先生が受講者にアンケートをとって、多数決の結果後者になりました。
まとめ
本講義ではコンピュータネットワークにおける基礎知識や、現在の技術がどのような経緯で誕生したのかを学習します。講義中には、いざネットワークでトラブルが起こったときにどこに着目すれば問題点が見つけ出せるのかも少しお話してくださいますし、試験でそういう実践的な内容が出題されたりもしますが、自分で手を動かして経験することが何よりも重要です。このコンピュータネットワークはそういった分野に入っていくための入門的な講義です。
言語モデル論 | 米澤 明憲
開講時間:月曜2限 | 必修科目
シラバス
プログラミング言語の基礎理論、プログラミング言語のモデル、意味論について講義する。
授業細目: (1)計算とは、 (2)帰納的関数とプログラミング、 (3)ラムダ計算、 (4)プログラム言語の意味論、 (5)作用型プログラミングと並列処理、 (6)型推論
概要
プログラミング言語について基本的なことを学びます。
前半にはプログラムによる計算について、理論的な面白い話が聴けます。
後半では型理論の片鱗を垣間見ることができます。
本講義には lambda 計算をはじめとする、基本的かつ重要な話題が盛り沢山で、
すべて消化するのは大変ですが、プログラミング言語を自作したいという意欲的な人には勿論、
そうでない場合も情報科学者の常識としてきっと役に立つ、聴いておいて損はない講義であると言えます。
Church の提唱
私たちがコンピュータを使って何かしようというとき、
多くの場合、望みの動作を記述したプログラムというものを用います。
言うなればプログラムはコンピュータに対する指令書であり、
その指令書を書くための言語がプログラミング言語です。
あなたがパソコンを使うときにお世話になってる OS だって、立派なプログラムの一つです。
プログラムに記述された動作の手順をアルゴリズムと言います。
簡単に言ってしまうと、アルゴリズムは何らかの関数を計算する手順のことです。
OS が関数・・・。変だと感じる人が多いのではないでしょうか?
とりあえず、ゲーデルの算術化を考えれば大丈夫なんだ、と難しそうなことを言って誤魔化しておきます。
(興味のある人は首を突っ込んでみて、その真偽を確認してみて下さい)
さてそうすると、計算可能な関数を考えるとアルゴリズムがどんなものなのか分かりそうです。
それでは計算可能な関数って何でしょうね?
上の考えをひっくり返すと、それがどんなアルゴリズムかはさておいて、
(実行可能な) アルゴリズムが存在する関数のことではないかと考えられます。

ここまで読んで、「いったい何が言いたいんだ?」と思った人もいるでしょう。
噛み砕いて言うと、アルゴリズムと計算可能な関数を同一視できそうですね、ということです。

話は変わって、ちょっとだけ歴史の話をしましょう。
偉大なる先人達は様々な計算モデルを考案してきました。
チューリングマシン、lambda 計算、帰納的関数などなど。
これらのモデルは実は等価なものであるということが分かり、
これを計算可能な関数であると考えよう、という主張をする人物が現れたのでした。
こうして計算可能な関数は厳密な定義を与えられることになりました。
(実際のところ、筆者はこの辺りの話に明るくないので、インターネット上でサラッと調べたものです。本当にお話程度に考えて下さい。)

話を戻しましょう。
アルゴリズムと計算可能関数を同一視することで、
アルゴリズムを厳密な計算モデルを用いて定義することができます。
こうした主張は Church の提唱と呼ばれており、本講義の始まりを飾ることになります。
講義とは無関係ですが、先の計算可能関数を超える関数を考える場合、Hypercomputing という分野になります。
興味のある人は調べてみて下さい。
プログラムの意味
ところで、アルゴリズムが厳密に定義されると何が嬉しいのでしょうか?
それはプログラムの意味を扱えることにあるのかもしれません。
話が飛躍してしまったように感じるかもしれませんが、
アルゴリズムが決定されればプログラムの動作は自然に決まりますので、
アルゴリズムとプログラムを同一視できることになります。

詳しくは説明しませんが、本講義では次の三つの意味論をとりあげます。

* 操作的意味論
o プログラムを解釈・実行する抽象機械を定義する
* 公理的意味論
o プログラムの性質・機能の仕様を記述し、証明する
* 表示的意味論
o プログラムに対応する数学的なモデルを与える


こうした意味論を用いることで、
プログラムの仕様記述を厳密にできたり、
プログラムの動作を明確に表現したりできます。
lambda 計算
先に述べたように、アルゴリズムを定義する方法として計算モデルがあります。
本講義では帰納的関数と lambda 計算について勉強します。
ここでは lambda 計算について紙面を割いてみようと思います。

参考までに帰納的関数についても簡単に触れておきます。
講義では実際に帰納的関数を定義し、
それが N プログラムというプログラム (で記述されたアルゴリズム) によって計算可能であることを示し、
続いて N プログラムで計算可能な関数が帰納的関数であることを示すという手法で、
N プログラムにより計算可能な関数の全体が帰納的関数に一致するということを証明します。
帰納的関数については 3 年生夏学期の情報論理でも勉強すると思いますが、
情報論理とは少し見方が違いますので、良い復習になると同時に帰納的関数の重要性を再確認する機会にもなります。

さて lambda 計算についてですが、
Scheme とか ML とかいったプログラミング言語をご存知でしょうか?
Scheme は 2 年生冬学期に、ML についてはその方言である OCaml を 3 年生夏学期に勉強するはずです。
これらは関数型のプログラミング言語と呼ばれますが、
この関数型言語の基底概念こそ、ここで学ぶ lambda 計算なのです。
簡単に言ってしまうと、lambda 計算とは記号の書き換えが計算とみなされる、シンプルな体系です。
例えば

x + 1

という式を考えます。
このとき x + 1 の意味するものは x を変数とする関数のことでしょうか?それとも x という値に 1 を加えた結果のことでしょうか?
lambda 計算においてはこれらははっきりと区別されます。

x + 1

というのは x という値に 1 を加えた結果を表し、

lambda x. x + 1

というのは x を変数とする x + 1 という関数を表します。
つまり式の前に lambda x と書くことで x が変数であることを明示しているのです。
このことを x に関する lambda 抽象と言います。
また

(lambda x. x + 1) 1

と書くと、変数 x の値を 1 にするということを意味します。
このことを関数適用といいます。
この関数適用についてですが、
すぐ上で「変数 x の値を 1 にする」と書きました。
これは x + 1 を 1 + 1 にするということです。
つまり

(lambda x. x + 1) 1



1 + 1

と (直観的な意味としては) 等しいということになります。
実はこの変換操作は lambda 計算における基本的かつ唯一の計算操作にあたり、beta 変換と呼ばれます。
少しだけ一般的に書くと、beta 変換は

(lambda x. f x) y

という形の式を

f y

という形に変換する操作であり、
この操作こそが lambda 計算が計算 たる所以であると言えます。
式を記号列であるとみなせば、前述した通り lambda 計算は記号の置き換えが計算にみなされる体系である、となる訳です。

上では 1 とか何も考えずに書いてきた訳ですが、
厳密に言うと整数は lambda 式ではありません。
(lambda 式自体は lambda 抽象と関数適用を用いて再帰的に定義されるものです)
lambda 記法では lambda 式以外は許されないので、何も考えずに使ってはいけないのです。
「なんだ、整数も使えないのか」と思ったかもしれませんが、
整数などは lambda 式で符号化することで表現可能です。
例えば 0 は、lambda 計算の考案者 Church に従うと、

0 := lambda f. lambda x. x

となります。
やっぱり講義とは直接関係ありませんが、
集合論をご存じの方は自然数の定義方法に共感を覚える場合もあるのではないでしょうか。

型理論
上で述べた lamdba 計算ですが、
世の中には型付き lambda 計算というものがあります。
その名の通り型が付いた lambda 計算なのですが、
型とは何でしょう?

という訳で、本講義の最後には、型理論について基本的なことを学びます。
型とは値の集合ですが、
式の値に対する制約、
もしくは対象領域に登場する実体をモデル化した表現であると考えることができます。
後者をクラスと呼ぶこともあります。
型を使うことで、
型検査によるエラーの発見ができたり、
型情報を用いたプログラムコードの最適化が可能になったりします。
例えば変数 x と y があり、

x + y

という式を考えているとします。
x や y が自然数であれば算術的な加算ですし、
文字列であれば連結かもしれません。
そんなとき x が自然数であると明示してあれば x + y は加算であると考えられます。
もしも y が文字列であると明示してあればプログラマの間違いである可能性があります。
つまり自然数であるとか文字列であるとかが明示してあれば、それだけでエラーの発見につながる訳です。
このような自然数とか文字列とかを型といい、x の型は自然数である、と表現します。
上手く利用すれば色々と嬉しい型ですが、
プログラムの随所に型を指定することは、冗長で煩雑なコーディングにつながる可能性があります。
そこで登場するのが型推論です。
例えば

x - 1

という式があれば、何も指定がなくとも x は数であると考えるのが妥当です。
型推論を使うことで無用な記述を省くことができます。
まとめ
以上、講義の流れを簡単に追いかけてみましたが、
紙幅の都合で記述できなかった部分も多々ありますし、
回りくどい文章で伝わりにくかったところもあることでしょう。
是非ご自分の目で見、耳で聞き、興味を追求し、本講義を通じて情報科学の深淵へと踏み出してみて下さい。
進行
本講義では内容豊富なレジュメが配布され、基本的にはそれに従って進行していきます。
板書も少しありますが、米澤先生のご説明をよく聞き、理解に傾注した方が実り多いのではないかと思われます。
レジュメの随所には課題が記されています。
なかなか頭を使う課題もあるので、復習の意味合いも込めてチャレンジしてみると良いでしょう。
評価
基本的には試験で、出来が悪いときのボーナスとして課題レポートが評価される、という形式のようです。
原則として講義内容がそのまま出題されますので、
しっかり覚えていればそれほど難しい試験ではないと思います。
また、試験対策の意味でも保険の意味でも、課題はやるに越したことはないです。
中でも、年の変わり目辺りで出題される、lambda 計算をシミュレートするプログラムを Scheme で実装せよ、という課題はなかなか楽しめると思います。
是非チャレンジを。
知能システム論 | 辻井 潤一
開講時間:木曜2限 | 必修科目
授業内容
人工知能の基本的な技法に関する講義を行う。具体的には、以下の項目に関して解説を行う。
(1)発見的探索手法、プランニング手法、 (2)知識表現と非単調論理、 (3)フレーム型知識表現と型付素性構造、 (4)機械学習、 (5)言語理解
概要
人間の知能をコンピュータに模倣させることができるかどうかを気にする人は、コンピュータができたかできなかったか、そのくらいの昔から、学問の世界でも、あるいはSFの世界でも、大勢いました。知能システム論の講義では、知能を持っているらしい振る舞いをコンピュータにさせるためにこれまでに考え出された、数多くの手法とその裏にある考え方を、学ぶことができます
人工知能
「知能とはなにか」なんていきなり考えはじめると、よくわかりません。「知能を持っているらしい振る舞い」にどんなものがあるかなら、すぐに例をいくつか思いつきます。

* 言われた指示を理解して行動する。
* 言葉を理解したり発したりする。
* チェスや囲碁のようなゲームをする。
* たくさん候補がある中から、いいやりかたを見つける


人間はどうやって知能を持っているらしい行動をするのでしょうか。これに関しては、古代の哲学者から現代の心理学者に至るまで、いろいろな人がいろいろなことを言っています。

哲学は考えます。しかし、考えたとおりのやりかたほんとうに知能が働くのか実験して確かめるわけではありません。心理学は人間を使って実験をして、知能がどんなふうにどのくらい速く働くのかつきとめようとします。しかし相手が人間なので、実験結果に影響する状況を完全にコントロールできるわけではありません。コンピュータを使えば、知能らしきものを一から作って、それがどのくらいうまく働くのかを、実験して確かることができます。対象となる知能らしきものは人工物なので、しくみはわかっているし、改造することもできます(人間相手ではこれができません)。実は、作ろうとしてみると意外なところが難しいことがわかります。

もちろん、人工知能を作る動機は知能のしくみを知りたいということだけではありませんコンピュータがもっと賢くなればもっと便利になることでしょう。

人工知能にはおおざっぱに分けると二つの手法があります。コンピュータに規則を教え込んで、教えた規則に従って考え(推論)させるやり方と、実例をたくさん見せて、規則性を見つけさせるやり方です。推論させるのを論理っぽい手法、たくさんの実例を見せるのは統計っぽい手法と呼ぶことにしましょう。
論理っぽい手法
論理っぽい手法、というと避けて通れないのが論理プログラミングです論理プログラミングのための代表的な言語、Prologを例として、どんなものだか見てみます。

Prologでは、コンピュータに

プログラミングは楽しい
fun(programming).

楽しいものは時間食いだ
time_consuming(X) :- fun(X).

ということを教えてあげると、下記のような問答ができます。

プログラミングは時間食い?
?- time_consuming(programming).
→ Yes

言われたことをそのまま返しているわけではなくて、一段考えています。もっと複雑な知識を与えておいても、ちゃんと動きます。確かに論理っぽいし、知能のかけらっぽいかも知れません。が、いつでも賢いやりとりができるわけではありません。たとえば:

楽しいXといえば?
?- fun(X).
→ X = programming
→ Yes

釣りは時間食い?
?- time_consuming(fishing).
→ No

楽しいことってプログラミングだけなのでしょうか。
釣りは時間食いではないのでしょうか。

Prologは根拠が見つからなければNoと返事をします。正しいことはすべて教えてもらったはずだという思い込み(閉世界仮説)をわざと持って返事をしている、とも言えます。

論理プログラミングの手法で、頑張って人間の常識をすべてコンピュータに教え込んでしまおうという試みがありました。しかしうまくいっていません。そこで、「そんなに難しい常識を使いこなせる人間って偉いんだな」と思うのが正しいのかもしれないし、「人間の常識ってぜんぜん厳密でも論理的でもないらしいな」と思うのが正しいのかもしれません。

では、論理プログラミングは役に立たないか、というとそんなことはなくて、問題の範囲を限定してやれば、十分役に立ちます。たとえば、台の上の積み木の配置について、現状を質問したり、目標となる状況を指定して達成する手順を答えさせたりする、というくらい狭い世界に話を限定すれば、1970年代にできるようになっていました。また、英語の文を読ませたときに文法的構造を判断させることは、論理プログラミングの延長として、できるようになっています。人間の常識にまでは届かないが、インターネット上のリソース同士の関連を論理プログラミングっぽく記述するRDFという言語は実用に供されている。 RSSリーダであちこちの記事を集めて読んでいる人がいたら、舞台裏ででRDFのやりとりが行われているかもしれません。インターネット上の情報を、人間が読まないと意味がわからないものだけではなくてコンピュータが読んでも意味がわかるものも含めてやれば、インターネット上の情報の整理整頓の一部をコンピュータが肩代わりできるかも知れないという発想です。

知能システム論では、論理プログラミングの基盤である導出原理から、制限であるフレーム問題、応用であるセマンティックウェブまで、幅広く学びます。
統計っぽい手法
さきほど、論理っぽい手法で、英語の文の構造をだいたい解析できる、と書きました。しかし、文の構造をひとつに定められないことがあります。文の構造がぜんぜん違っても、単語の並びとして偶然おなじになってしまうことがあるからです。陳腐な例を挙げます:

* Time flies like an arrow. (時は矢のように飛ぶ。)
* Time flies like an arrow. (時間バエは矢が好きだ。)
* Time flies like an arrow. (矢のようにハエを計時せよ。)


人間なら、どれが妥当な解釈か、すぐにわかります(というより、最初から妥当な解釈しか頭に浮かびません)。コンピュータに、どれがいちばんありそうな解釈か判断させるにはどうすればいいのでしょうか。どの単語がどのような使い方をされることが多いのか、実際に使われている英語を大量に読ませて学習させるという手があります(時間とハエで時間バエという複合名詞になることはまれだ、とか)。実例をたくさん読ませて学習させた後に、別の例を問題として与えて、どのくらいの正答率が出るのか見てみると、学習に効果があったのかどうかわかります。シャノンのエントロピーという、情報の量を測る単位があるので、学習したり答を出したりするときに、何が役に立って何があまり役に立たないのか、定量的に議論することができます。

メモリが安くなってきて、速いCPUも安くなってきているので、統計っぽい手法の可能性はどんどん広がっています。

知能システム論では、主に隠れマルコフモデルに関して、確率文脈自由文法などのモデルの形や、モデルの形が決まった上でのViterbiアルゴリズムやEMアルゴリズムといったパラメタ推定法や、自然言語の理解を中心とした応用を学びます。
探索
論理っぽい手法も、統計っぽい手法も、なにかを探しているところは共通しています。論理っぽい手法では、教えられた規則の中から、答えを導くものを探しています統計っぽい手法では、学習用のデータをうまく説明する規則性を探した上で、その規則性を使って、テスト用のデータのうまい説明を探します。

これらにも増して探索らしい探索といえば、チェスや将棋のようなゲームをプレイするプログラムです。そういうゲームでは、次にできることの候補の中から、一番都合がよいものを選ぶのです。次の手の選択には、次の次に相手ができることの候補の中から都合がよいものを選ぶことも大きく関係していて、要するに、今後可能なゲーム展開の中から、両方ができるだけ上手にプレイしているのはどんなゲーム展開なのかを絞り込んでいく作業が必要となります。可能なゲーム展開の数は莫大で、その中から見つけたいものの数は多くはないので、探索らしい探索問題です。

知能システム論では、幅優先探索や深さ優先探索、反復深化法、A*アルゴリズムなどの探索手法や、ゲームについてのminimax法やalpha-beta枝刈りを学びます。
授業の進行
スクリーン上のスライドを使って行われます。映されるスライドを印刷した資料は、毎回分厚かったです。
試験について
指定されたなかから論文を選んで読んで、要旨をレポートにする課題がありました。
次のステップへ
演習でオセロをプレイするプログラムを書き、競技会で競います。コンピュータを使って現実世界の問題に取り組もうと思うと、なにがどのくらい難しいのか、知能システム論の講義を受けていれば、だいたいの見当がすぐにつくようになります。
計算量理論 | 今井 浩
開講時間:火曜2限 | 必修科目
シラバス
TM、計算量、NP 完全、近似アルゴリズム。
概要
計算量理論の授業では、ある問題をコンピュータで解くことがどれだけ難しいのかということを議論していく。この議論の中で、いくつかの問題が「同じくらい難しい問題のグループ」に分けられること、そしてそれらに対するいくつかのアプローチを紹介する。
授業の内容について
計算量理論では、問題を計算することの難しさに関することを学びます。つまりは、コンピュータでその問題を解くのが、簡単なのか、難しいのかだとか、解くのにどれくらいの時間かかるのか、というようなことについて学びます。

例えば、「n個の数字を小さい順に並べる」というようなソートの問題を考えて見ます。こうしたソートのアルゴリズムにはいろいろなものが考え出されており、(2年生冬学期必修の「アルゴリズムとデータ構造」で習います)バブルソート、挿入ソートだったら、O(n^2)時間かかるだとか、クイックソート、ヒープソートだったら、O(nlogn)時間かかるということがわかっています。上記にあげた中では、O(nlogn)時間が最も短いということになりますが、今度は果たしてそれがベストな解かということが問題になってきます。つまり、「どういうアルゴリズムを考えてもソートはO(nlogn)時間以下では計算できない」ということを確かめていく(つまり、その問題の難しさを決定していく)のが、計算量理論の問題のひとつです。

※O(N)時間というのは計算量がオーダーNの時間であることを意味し、問題を解くのにNの定数倍の関数で抑えられる計算時間がかかることを意味します。 ()内は問題サイズn(ソートの問題ならば、並べ替える数字の個数が問題のサイズになります。)の関数によって表されます。

そして、この「O(N)時間以下では計算できない」という計算時間のオーダーによって、問題の難しさが定義され、その難しさによって問題が分類されます。この分類は大きく、「決定不能」「決定可能」に分けられ、決定可能なものの中では「指数時間」(サイズnの問題を解くのにO(M^n)時間かかる)と「多項式時間」(サイズnの問題を解くのにO(n^M)時間かかる)に分けることができます。講義の中では、この「指数時間」の問題と「多項式時間」の問題について詳しく扱っていきます。

この指数時間の問題は、問題サイズが大きくなると「指数爆発」(爆発的な関数値の増加。指数関数のグラフを思い出してみてください。)を起こしてしまいます。そのため、問題サイズの大きい指数時間の問題を解くには、何十万、何百万以上もの時間が必要になるため、指数時間の問題は実際には「解けない」問題になってしまいます。そこで、指数時間の問題(解けない)と多項式時間の問題(解ける)を区別していくことが、問題の難しさを考える上で大事になってきます。

こうした問題の計算時間は、Turing Machine(以下TM)(既出ですか?説明必要?)を用いて定義されます。そして、TMを用いて多項式時間で計算できる問題クラス(=「多項式時間の問題」)を「P」と表現します。情報科学に関連する話題の中で、時折耳にするであろう「NP」「NP完全」という言葉は、こういった問題クラスの名前です。 NP、NP完全の具体的な定義や、その意義については、授業のなかでメイントピックとして詳しく扱っていきますので、お楽しみに!

この授業の軸になる計算時間の定義はTMによって行われるので、TMの復習や、また、グラフ理論との関連も深いので、3年夏学期必修の「離散数学」の復習もしておくと理解が楽になると思います。

「情報科学演習2」(3年冬学期 必修)では、この計算量理論と、連続系アルゴリズムの講義に関する演習を行います。この演習によって、計算量理論の講義の理解を深めることができます。


授業の進行
授業は板書で進んでいくので、しっかりノートをとることが大切です。先生いわく、板書のスピードで説明できる量がちょうど良い授業内容の量なんだとか?また、口頭での説明も詳しく行ってくれるので、その説明をしっかり聞いて、必要に応じてメモを取るとよいでしょう。

授業はじめのお話は、授業内容には関係ありませんが、きちんと聞いておくとためになります。
試験について
授業に加えて演習までしっかり消化しておくと良いと思います。重要な概念を理解しているかということはもちろんのこと、問題のNP完全性を示せ、というようなものや、問題に対する多項式時間のアルゴリズムを与えよ、といったものが出題されます。
参考書
参考書として、以下の本が挙げられています。中身が英語なので読むのは楽ではありませんが、内容はわかりやすい、と思います。

Computers and Intractability: A Guide to the Theory of Np-Completeness
Michael R. Garey and David S. Johnson \\
W H Freeman & Co (Sd) (1979/06)

情報科学演習 II | 各教官
開講時間:月曜3限 | 必修科目
演習内容
計算量理論の演習、連続系アルゴリズムの演習、等。
概要
連続系アルゴリズム
計算量理論
連続系アルゴリズム
連続系アルゴリズムの授業の演習

前半はMPI および OpenMP を用いたプログラムの高速化・並列化。
MPI ではソートを、OpenMP は N queens 問題の高速化を行った。

前半の課題では、まず、あまりさわったことのないクラスターを使用する。
オーバーヘッドは何か、遅い原因がどこにあるのかを把握し、効率よく並列化をできるようにするのを考えるのが難しかった。
ソートの場合の遅い原因は、ソートして、結果をマージするのに実はオーバーヘッドが沢山かかっていたことがわかった。
個々でソートした場合は、普通にやると遅いが、マージしたり、ソートするタイミングをうまくチューニングするとすると速くなる。
チューニングの内容としては、自分は、バケツソートが使えるようにしたり、ノード間での転送を少なくなるようにしたが、思ったほど速くならなかった。

ただ、「速くしろ」という課題は、「これが動くようにしろ」という課題よりは面白いと自分は思う。

ただ、、、、CPU 実験と同じ時期の授業なので、N queen 問題は動くようにはしたけど、同時期にやっていたCPU 実験がおもしろすぎて、あんまり時間を割かなかった。


連続系アルゴリズムの実装は
* LU分解
* 加速法
* FFTを用いた多倍長整数乗算
* 常微分方程式

授業で習った内容を、授業で習っただけでは、どういうふうに値が動いてくかイメージしづらいため、それを勉強をするのには、役にたったと思う。

授業を聞いていても、式が並んでいて、こうやると答えがでてくる、というように習う。
式の中身は、あくまで、変数でこういう式って書いてあるだけなのが、たとえば、実際に、プログラムを組むと、デバッグしているときに、変数に数値が入って、値が変わっていくのが見えたりして、内容を理解するのがとても分かりやすくなった。
計算量理論
具体的には、ある問題がナップザック問題であるとか、3-SAT であるとか、そういう問題が NP に属することを示したり、計算量を評価したりする。

コンピュータを使わない演習で、紙と鉛筆を使う。
紙を配られて、その場で、鉛筆で書いて提出。
解けた人は黒板で発表する。