ソフトウェア基礎II 氏 名 山城 光 学籍番号 065761B 提出日 2006/12/25

 ソフトウェア基礎II
レポート１
氏 名 山城 光
学籍番号 065761B
提出日 2006/12/25
問1、問2は手書きなので別図参照
問3
固定小数点とは文字通り小数位置を固定した表記法で、一般に、データの保存単位である
wordごとに最下位ビットの右側を小数点位置として整数を表す。
負数は2の補数表現を使う事が多い。1wordを16ビットとした場合、最上位ビットは
符号ビットとして使用され、残りの15ビットで数値部を表現する
浮動小数点とは実数型のデータを表現する時に使われ、主に科学技術計算などの
高精度の計算をする時に使われる表現法で、数値を符号、仮数、底、指数で正規化した
表現で2進数に割り当てる。正規化とは仮数の値がある一定範囲に収まる様に調節して
指数で実際の大きさを調節する表現法で、一般には小数点の次に有効数字がくる様に表
現する。
問4
MIPSとは一秒間に実行できる命令数を百万命令単位で表したもので1MIPSとは一秒間に
100万回命令つまり1命令を平均1マイクロ秒で実行する性能ということになる。
MFLOPSとは処理速度を表す単位の一つで1秒間に100万回の浮動小数点
数演算(実数計算)を実行できることを意味する
問5
補助単位とは処理する数の桁数を減らすため二使われるもので1000倍ごとに補助単位が
存在する補助単位には以下のもの等が存在する
T(テラ)10の12乗
G(ギガ)10の9乗
M(メガ)10の6乗
K(キロ)10の3乗
m(ミリ)10の?3乗
μ(マイクロ)10の?6乗
n(ナノ)10の?9乗
p(ペタ)10の?9乗
問6
補数表現とは与えられた数をある数から引く事によって得られる数の事で補数にはn進数
のnに対する補数である基数の補数とn?1に対する減数基数の補数がある。
コンピュータのデータ表現では、負の数を表現するのに補数を用いるのが一般的である
(手書きで後の方にに追記あり)
問7
論理シフトとはビット全体を左右にシフトする演算の事をいう。
特徴として全ビットを移動する。シフトの結果はみ出したビットは切り捨てる。
シフトの結果開いたビットには0が格納されるという特徴がある
算術シフトとは数値の演算に利用する為に、負の数を2の補数で表現する形式に対応した
シフト演算のことを言う。特徴としては
符号ビットはシフトしない。シフトの結果はみだしたビットは切り捨てる。
シフトの結果あいたビットには左シフトの場合0右シフトの場合符号ビットと同じ値
が入るという特徴がある。
論理シフトで左に2シフトした場合
論理シフトで右に2シフトした場合
1010 => 1000
1010 =>
0010
算術シフトで左に2シフトした場合
算術シフトで右に2シフトした場合
1010 => 1000
1010 =>
1110
問8(問8、9は手書きなので別図参照)
線形探索法とは配列の最初のデータから1つづつ順に比較して探索していく方法でこの
探索法の場合あらかじめ最後に探索データを配置しておくと必ず最後に探索データを
見つける事ができるのでデータ件数を気にする事なく終了の判定ができるこの最後におく
探索データの事を番兵という。データ件数がNの時平均探索回数はN+1/2回で
最大検索回数はN回になる
二分探索法とは配列のデータを次々に二等分して検索範囲を狭めていく方法で、二分探索
を行う為には配列データがこう降順または昇順に並んでないといけない。データ件数が
Nの時平均探索回数はlog2N回最大検索回数はlog2N+1回となる
ハッシュ探索とは高速検索のうちの一つではじめから検索しやすくする為データを格納
する時に格納位置をハッシュ関数という計算式を使って決める。この計算法には除算法
乗算法、基数変換法等がある。異なるデータが同じ格納位置になる事を衝突が発生した
といい、この衝突が頻繁におこると探索効率が低下するのでハッシュ関数はなるべく
衝突しないような工夫が必要になる。
問9
バブルソートとは隣り合うデータ同士を比較し、大小関係が逆の場合にそれらのデータ
を並べ替えるという作業を繰り返す方法のことで比較回数はn(n-1)/2となる
選択ソートとはデータの中で最小値(最大値)を選び出し、最後のデータと入れ替える
という作業を繰り返す方法で比較回数はn(n-1)/2となる
挿入ソートとは配列データにおいて、挿入するデータより手前までのデータが整列済み
であるという前提で行う方法で挿入データの手前から順次にデータを比較し、適当な
場所にそのデータを挿入するのを繰り返す。比較回数は最小でn回でn(n-1)/2回となる
クイックソートとは全データから基準値を選び出し、その値より大きいデータデータと
小さいデータに振り分けるといった作業をくりかえし行う方法で基準値は通常、中央の
データを使う事が多く、整列処理速度は速くなる。
問10は手書きなので別図参照