＝＝＝必須課題１＝＝＝
受付開始日時	2015-04-22 11:25
受付終了日時	2015-04-27 18:00

●必須課題1-1[論述(pdf)] 階乗関数と指数関数
ｎ！は指数関数でないにも関わらず指数時間かかるアルゴリズムに含まれている理由を、２のｎ乗とｎ！の関係に注意しながら説明しなさい。

●必須課題1-2[論述(pdf)] 階乗計算量への空間的対応
(1)
20!の階乗を正確に求めなさい（ないし調べなさい）。
調べた場合は出典を正確に記述すること。出典が不明瞭な場合は提出せずとみなします。
（ＴＡが確認できるレベルで出典を記載すること）
(2)
現在、地球上にあるプロセッサの総数を調べて求めなさい。
使用した資料・数値の根拠になる出典は明記すること。
計算過程も示すこと。
(3)
上記(2)のプロセッサが全て3GHzで１命令を実行できるとします。
20!回の命令を上記(2)のプロセッサを全部並列実行したとして、実行時間を求めなさい。
有効数字は３桁で構いません。

●必須課題1-3[論述(pdf)] グラフの表現

(1) 
下記の4x4行列で示される隣接行列のグラフを図示しなさい。
0 1 1 0
0 0 0 1
1 1 0 1
0 0 0 0
(2)
これが有向グラフか無向グラフかを論じなさい。


◆発展課題1-A[論述(pdf)] 計算量の空間的拡張
(1)
地球・月のラグランジュ点L4,L5にコンピュータセンタを置くことを考えます。
サイズは月の100分の1の球状で、内部までプロセッサを並べます。
１プロセッサには１立方メートル必要です。
プロセッサは何台用意できるか、有効数字３桁で求めなさい。
(2)
この数字を1-2-(2)と比較したときの感想を述べなさい。


以上