積読していたアルゴリズムイントロダクション第3版を仕事が落ち着いて暇だったので読んでみることにした

1章 計算におけるアルゴリズムの役割

練習問題

• 1-1 ソートを必要とする実社会での応用あるいは凸包の計算を必要とする実社会での応用を説明せよ
  • ソート: ECや顧客管理などのデータベース
  • 凸包: GISや画像処理などの空間データの処理
• 1-2 実社会の枠組みの中で用いられる計算速度以外の効率の尺度をあげよ
  • メモリ使用量
  • 電力消費量
  • 転送速度
  • コスト
• 1-3 以前に見たことがあるデータ構造についてその長所と欠点を述べよ 配列
  • 長所: メモリ効率が良い、ランダムアクセスが高速
  • 欠点: サイズ変更が困難
• 1-4 最短経路問題と巡回セールスマン問題の類似点を説見せよ、またそれらの相違鐡は何か
  • 類似点: 両方ともグラフ理論に基づく問題で、最適な経路を求めることが目的
  • 相違点: 最短経路問題は単一の始点と終点を持ち、巡回セールスマン問題は全ての点を訪れる必要がある
• 1-5 最適解しか意味を持たない実社会の問題を示せ、また「近似解」でも十分に意味を持つ問題を示せ
  • 最適解しか意味を持たない問題: HTTPSなどの暗号化プロトコル
  • 近似解でも十分に意味を持つ問題: 配送ルートの最適化やスケジューリング問題
• 2-1 アプリケーションそうでアルゴリズムが必要になる応用の例を挙げ、必要とされるアルゴリズムの機能を議論せよ
  一覧ページ表示のソートアルゴリズム
• 2-2 同じ計算機上で挿入ソートとマージソートの実現を比較する サイズ n の入力に対して、挿入ソートの実行には8n^2ステップがかかり、一方、マージソートの実行には64nlgnステップかかるとする 挿入ソートがマージソートに優る n の値を調べよ

  find
    (\a -> 8 * a ^ 2 > 64 * a * logBase 2 a)
    [2 .. 1000]

  n <= 44 のとき、挿入ソートがマージソートに優る
• 2-3 同じ計算機上で、実行時間が100n^2のアルゴリズムが、実行時間が2^nのアルゴリズムより高速に実行できる最小の n の値を求めよ

  find
    (\a -> 100 * a ^ 2 < 2 ^ a)
    [2 .. 1000]

  n >= 15 のとき、実行時間が100n^2のアルゴリズムが、実行時間が2^nのアルゴリズムより高速に実行できる

章末問題

• 1-1.実行時間の比較 以下の表の各関数f(n)と時間tに対して、アルゴリズムが問題を解くのにf(n)マイクロ秒かかるとき、t時間で解くことができる最大の問題サイズnを求めよ

  	1秒	1分	1時間	1日	1ヶ月	1年	1世紀
  lg n	2^1000000	2^60000000	2^3600000000	2^86400000000	2^259200000000	2^3153600000000	2^3.15e15
  √n	1000000000000	3.60e15	1.30e19	7.46e21	6.72e24	9.95e26	9.95e30
  n	1000000	60000000	3600000000	86400000000	2592000000000	31536000000000	3.15e15
  n lg n	62746	2801417	133378058	2755147513	71870856404	797633893349	68610956750570
  n^2	1000	7745	60000	293938	1609968	5615692	56156922
  n^3	100	391	1532	4420	13736	31593	146645
  2^n	19	25	31	36	41	44	51
  n!	9	11	12	13	15	16	17