情報理工学III(計算と情報の理論)

概要

本講義では，計算と情報の理論について講義します． 全14回を7回ずつに分け，前半の「情報理論」を澁谷，後半の「計算理論」を宮本が担当します．情報理論，計算理論の概要は以下の通りです． [情報理論] テキストや音声，画像などの様々な情報をコンピュータで扱うためには，これらの情報を“0”，“1”などの記号によって表現されるディジタルデータに変換しなければなりません．これを情報の「符号化」といい，もとの情報を損失なく符号化するための，符号化が満たすべき条件が知られています．また，情報のコンパクトな表現(情報圧縮)には，これよりコンパクトには表現できないという理論的な限界があります．本講義では，このような，情報の表現に関する「数理的」な枠組み − 情報理論 − の基礎について学びます． [計算理論] 何か問題を解く手法を考えたとして，その手法の良さはどう評価するのでしょうか?また，その手法を実行するときに，現在世界中に普及している「普通の」コンピューターを使う場合とそうでない場合では何が異なるのでしょうか?本講義では，そのようなことを数理的道具を用いてきちんと評価する方法を学びます．まず最初に「普通の」コンピューターを数理的に表現する方法を学び，次に計算の困難性を見極める手法を学びます．本講義では，このような，計算に関する「数理的」な枠組み − 計算理論 − の基礎について学びます． この講義は情報理工学科のカリキュラムポリシーの1「現代科学を理解するために共通に必要な基礎学力を講義，演習，実験を中心とした共通科目を通じて，主に1,2年次の間に修得させる」科目に相当します。

目標

情報理工学科のディプロマポリシー1に掲げる「幅広い一般教養と倫理観,国際化の進展に対応できる素養」を身に着けることを目標とします。また，各テーマにおける目標は以下のとおりです。 [情報理論] ・情報を損失なく圧縮するためには，満たさなければならない約束事があること ・ファイルの圧縮サイズには，これより小さくできないという限界があること．また，これが情報の「量(情報エントロピー)」としての側面を持つこと． ・この限界を達成する具体的な圧縮アルゴリズムが存在すること を理解することが目標です．さらに「情報理論が情報に関する諸分野の基礎となる理論である」ことを知っていただければと思います。 [計算理論] ・コンピューターの能力を論理的に表現できるようになること ・計算の方法の定量的な評価方法を使いこなすこと ・問題の難しさの階層を知り，将来自分が直面した問題の困難さ(あるいは容易さ)を適切に説明できるようになること が目標です．そして，これらを通じて論理的にものを考える面白さも感じてもらえれば良いと思います．

授業外の学習

[情報理論] 本講義では，ほとんどの学生にとって初めて接する概念が多く登場します．このため，事前に配布する講義資料(スライド,講義録)の予習が必要です．また，講義内容に関する理解を深めるための演習問題を毎回出題します．以降の講義やレポート課題の出題内容に関わる重要な問題を含みますので，次回講義までに必ず理解しておいてください．さらに，内容の区切りに合わせてレポート課題を何回か出題します．それぞれ復習を兼ねて授業時間外に取り組んでください．予習・復習に要する時間は授業回により異なりますが,両方合わせて各回190分程度です． [計算理論] 本講義では，ほとんどの学生にとって初めて接する概念が多く登場します．そして計算理論独特の言葉遣いも登場するため，独学での予習では誤解が生じる可能性もあります．このため，事前の予習は特に求めません．一方で，講義内容に関する理解を深めるための演習問題あるいはレポート課題を毎回出題します．復習として毎回授業時間外に190分程度かけてこれらの演習問題あるいはレポート課題に取り組んでください．

所要時間: 190分