4/7 イントロダクション(Introduction)

• 田中哲朗のWWWページ
• 普段の居場所は駒場情報教育棟3階 E33研究室
  
• メールでの質問は， 宛にメー ルを出すこと．回答を全体で共有した方が良いと思わ れる場合は，差出人を伏せた上で，教材に引用することがある．

• レポート(6回程度予定)
• レポートの提出は， ITC-LMS という学習支援システム で行なう．教育用計算機システムのアカウントを使ってログインして，「コース検索」で ，「コース名」で「情報数理科学」で検索すると他の先生の講義と田中の「情報数理科学II」が4つ見つかる．これらは，所属コースや教員アカウントが複数あるために4つ表示されるが，「08D1202 情報数理科学II[総合情報学コース]」に登録すること．
• 4/14から試験的に講義中の投票システムを導入することにしました．1回の講義中に1度でも投票すると出席点を加えます．1回の講義の出席点は全体の評 価の(1/100以下とします)

教科書

• Pat Morin: Open Data Structures, http://opendatastructures.org. C++ edition(Creative Commonsの「CC BY」ライセンスで公開)
• 今のところ(1,2,3,4,5,6,9,10,11,12章を扱う予定)

参考書/参考資料

• 石畑清: アルゴリズムとデータ構造, 岩波書店, ISBN 978-4000103435\\ アルゴリズムとデータ構造に関する教科書としては易しく読みやすく安い(3900円)．内容がちょっと古めになっている．
• J. Kleinberg, E. Tardos著，浅野孝夫他訳: アルゴリズムデザイン, 共立出版, ISBN- 978-4320122178.\\ 入門というよりは，上級者向けの内容．

4/7

イントロダクション(Introduction)

4/14

イントロダクション(Introduction)(2)

4/21

配列ベースのリスト(Array-Based Lists)(1)

4/28

配列ベースのリスト(Array-Based Lists)(2)

5/12

連結リスト(Linked Lists)

5/19

スキップリスト

5/26

ハッシュテーブル(Hash Tables)

6/9

二分木(Binary Trees)

6/16

赤黒木(Red-Black Trees)

6/23

ヒープ(Heaps)

6/30

総合情報学特論と時間帯が重なるため休講

7/7

ソートのアルゴリズム(Sorting Algorithms)

7/14

グラフ，その他

講義スライド

• ITC-LMS「情報数理科学II」
• Open Data Structures
  • 教科書HTML版
  • 教科書PDF
  • C++ ソースファイル, ここで公開されているプログラムはベータ版であり，コンパイルできないものも含まれている．講義で扱う部分に関しては改訂版を公開する予定．
• C++ Reference

演習(C++プログラムの速度計測)

void f(std::vector<int> &v, int n){
  for (int i = 0; i < n; i++) v.push_back(i);
  for (int i = 0; i < n; i++) v.pop_back();
}

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>

uint64_t cputime(){
  unsigned int ax,dx;
  asm volatile("rdtsc\nmovl %%eax,%0\nmovl %%edx,%1":"=g"(ax),"=g"(dx): :"eax","edx");
  return (uint64_t(dx)<<32)+uint64_t(ax);
}

void f(std::vector<int> &v, int n){
  for (int i = 0; i < n; i++) v.push_back(i);
  for (int i = 0; i < n; i++) v.pop_back();
}

int main(int ac, char **ag){
  int n = 1000;
  if (ac > 1) n = atoi(ag[1]);
  std::vector<int> v;
  clock_t clk1 = clock();
  uint64_t cpu1 = cputime();
  f(v, n);
  uint64_t cpu2 = cputime();
  clock_t clk2 = clock();
  std::cout << "cycle : " << cpu2 - cpu1 << std::endl;
  std::cout << "clock : " << clk2 - clk1 << std::endl;
  std::cout << "sec   : " << (double)(clk2 - clk1)/CLOCKS_PER_SEC << std::endl;
}

cd ~/mis2
g++ -O2 -o vector_speed vector_speed.cpp

./vector_speed 100000

cycle : 2639753
clock : 916
sec   : 0.000916

time ./vector_speed 100000

real	0m0.006s
user	0m0.001s
sys	0m0.003s

• atoi 「char *」型のCの文字列から，整数(int)に変換するC言語の関数．
• clock
  OSの内部のclockの間隔(CLOCKS_PER_SEC, /usr/include/time.hに定義されている．MacOSのセンターに入っているバージョンでは1,000,000なので，1/1000000秒に1回増える)に基いたプロセス起動からの実行時間．OSによって計測の細かさが変わる．
• cputime()
  アセンブリ言語命令 rdtsc(read time scamp counter) を用いて，CPU1サイクルにつき1カウントアップされるカウンタを読み出す．

自習問題

1. 上のプログラムを自分のMacで実行してみて，fに与えるnの値をどう変化させるかによって，実行時間がどう変わるかを考えて見て下さい．
2. 自分のMacで実行してみて，clockとcycleの関係から，CPUの速度が何GHzなのかを推計してみてください．
3. vectorに変えて，list, dequeを使うプログラムに書き換えてみて，同様に実行時間を計測してみてください．