講義の目的 H27 情報数学特論第1回 ―講義計画とウォーミングアップ―  コンピュータ・サイエンスにおける諸問題を取り扱うための道具としての数学を学ぶ (基本)  それらの道具を用いて、データ構造やアルゴリズムを自分で設計する (応用)  設計した手法の効率を見積もる (解析) 坂本比呂志九州工業大学大学院情報工学研究院 1 講義の内容 (予定)  第1回：ウォーミングアップ講義の進め方と成績の評価  ―予備知識や例題―  第2回：動的計画法第3回：並列計算   第4回：情報の隠蔽第5回：通信量の削減  第6回：確率的アルゴリズム ―乱数の利用― 第9回：厳密アルゴリズム  演習課題を時間内に提出してください第10回：幾何学的アルゴリズム  提出された演習課題で成績を評価します ―監視員の配置―  ―協力して値を求める―  講義の後に演習時間を設けます ―厳密解をなんとか求めたい― ―相手に安全に情報を伝える―   第8回：近似アルゴリズム ―ほぼ最適に近い解― ―計算をみんなで分担する―  第7回：オンラインアルゴリズム ―現在における最適な選択― ―出来るだけ長い部分列を求める―  2 第11回：分散アルゴリズム ―信頼性の高い並列計算―  . . . 講義内容は増減あり九州工業大学情報工学部坂本比呂志 3 4 1 聴講する人へ  この講義で使用する概念  以下の行為を認めません    RAM (Random Access Machine) モデル  必要のない途中の入退室課題の提出のみを行う行為単位認定後の無意味なクレーム   必要な資料は配ります。教科書は必要なし。  アルゴリズムとデータ構造に関する科目を修得していることを前提とします。十分に大きな整数を保持できるメモリ、CPU、それらにランダムアクセスできる制御部（プログラムを格納）からなる機構単純化されているため、ハードウエアに依存しない純粋なアルゴリズムの性能を見積もることができる制御部 CPU メモリ RAM モデル 5 現実の計算機  データの読込速度の違いメモリ (一次記憶)    6  メモリ (一次記憶) の速度 6.4GB/s～12.8GB/s  ハードディスク (二次記憶) の速度 84MB/s ～133MB/s (連続領域を読み込む場合)  どの領域で計算するかでコストが大幅に異なるため、アルゴリズムの性能を測るための統一的な尺度が必要高速読み書きが高速容量が比較的小さい高価格メモリ(DRAM)  ハードディスク (二次記憶)     CPU メモリよりずっと遅いほぼ無制限の容量低価格低速 CPUも千差万別ハードディスク(内部) 7 ディスク内に分割配置されたデータ 8 http://ja.wikipedia.org/ 九州工業大学情報工学部坂本比呂志 2 RAM モデル  RAM モデルにおける演算      以下の命令を1単位時間で実行できる   時間計算量と領域計算量  if文の評価やgoto文の実行; 変数への値の代入(x=a); 論理演算と算術演算（ANDやa+bなど）; より厳しい仮定：一様コストと対数コスト   この講義で使用する計算量の概念  一様コスト：どの命令も1単位(時間/領域)で実行可能とする基準対数コスト：整数 n に対してlog n (時間/領域)で実行可能とする基準時間計算量：入力長 n に対してRAMが計算を終了するまでに実行した命令の回数（実時間ではない）領域計算量：計算を終了するまでに同時に占有したセルの最大個数  同一セルに m 回読み書きしても、そのセルしか使用しなければ領域計算量はO(1) (定数領域)となる。本講義では一様コストを仮定する 9 この講義で使用する計算量の概念  この講義で使用する計算量の概念オーダ(O)記法 (‘高々このくらい’という意味)     10  厳密な定義：ある関数 f(n), g(n) に対して、最悪計算量と漸近計算量  x2, x2 -10x に対して x2 =O(x2 -10x) O記法によって関数の支配的な項のみを考える  不等号の向きを逆にしたものは下限(Ω)を表す (‘少なくともこのくらい’)  11 九州工業大学情報工学部坂本比呂志最悪(時間)計算量：入力長 n に対する、あるRAMの最大命令回数 O(f(n)) 漸近計算量：最悪計算量の見積もりから支配的な項のみを取り出した計算量例：n 個の実数をソートするために nlogn +2logn+1 回の比較を行うRAM → O(nlogn) 時間 12 3 ウォーミングアップ  2進符号を順序よく並べる    2進符号の列挙  大小関係による整列グレイコードによる整列  グレイコードの生成方法   n 桁以下の2進数をすべて重複なく列挙したい  定義効率的な生成法右表は整数の2進表現と対応するグレイコードの列グレイコードは2進表現にはない特別な性質があるそれはなにか？ 13 グレイコードとその応用  隣り合うグレイコード同士は、ある1bitを反転させたもの (つまり1bitしか違わない)  2進数の場合(信号の変化) 数 2進コードグレイコード 0 0000 0000 1 0001 0001 2 0010 0011 3 0011 0010 4 0100 0110 5 0101 0111 6 0110 0101 7 0111 0100 8 1000 1100 9 1001 1101 10 1010 1111 11 1011 1110 12 1100 1010 13 1101 1011 14 グレイコードの生成  n 桁のグレイコードgnの定義ただしgnはn桁のグレイコードの列１０１１→１１１１→１１１０→１１００  光学センサーや画像認識で活用：放射線上の隣り合うパターンは1カ所しか変化しないため、入力が連続に変化する場合でも誤検出しないグレイコードを用いた光学センサーのスリット円盤 15  この方法では、n+1 桁のグレイコードの生成に n 桁のグレイコードの列を保持しなければならない他に方法はないか？ 16 http://www.e-sensor.omron.com/jp/index.cfm 九州工業大学情報工学部坂本比呂志 4 補足効率のよいグレイコードの生成  演習問題：   1-1：前述の定義で生成されるbit列がなぜグレイコードとなるのか？つまり、なぜ隣り合うコードが1bitだけ異なるのか？ 1-2：整数 n が与えられたとき、n 番目のグレイコードを高速に計算せよ [ヒント] 2進コードとそれを右に1bitシフトしたコードを用いる九州工業大学情報工学部坂本比呂志数 2進コードグレイコード 0 0000 0000 1 0001 0001 2 0010 0011 3 0011 0010 4 0100 0110 5 0101 0111 6 0110 0101 7 0111 0100 8 1000 1100 9 1001 1101 10 1010 1111 11 1011 1110 12 1100 1010 13 1101 1011 14 1110 1001 15 1111 1000  グレイコード→2進コードの計算    17 グレイコードと対応する2進コードの最上位bitは常に同じ上位桁から決定していくグレイコードの n 桁目とすでに確定した2進コードの n+1 桁目の XOR (排他的論理和) が2進コードへの n 桁目 18 http://www.image.esys.tsukuba.ac.jp/ 5