専門学校52日目(情報工学)6月25日(火)

1時限～3時限
情報リテラシー実習　　　情報利活用　文書作成Word2021対応

本日は情報リテラシーのWordのテストでした。
来週からExcelを学ぶそうです。

解答はファイルをフォルダにまとめて圧縮して提出。
フォルダ名はWordテスト_名前、にする。

全部で4問ありました。
1問目だけ配られたプリントを参考に自分で打ち込んでから文書を整える形式でした。
他の3問はすでに用意された文書を編集するという内容です。
ビジネス文書の体裁の整え方、敬称の付け方、インデント、タブ位置調整、均等割り付け、ルビ、記号の挿入、PDF形式での保存、ページのテーマ、テーマの配色、置換、独自スタイルの定義と適用、段組みの設定、スマートアート、テキストボックス、ヘッダー、ワードアート、書式のコピー、組み込みの表紙、ページ番号の挿入、目次の挿入、見出し1のスタイルに設定の追加、改ページ、グラフの挿入、コメントなどが出題されました。

---

4時限～6時限
国家試験対策　　　　コンピュータ概論
　　　　　　　　　　アルゴリズムとデータ構造

前回6月20日はキューとスタック、木構造、擬似言語によるアルゴリズムを学びました。
今日は整列の項目から学びます。

■整列
データを一定の規則で並べ替えること。昇順や降順があるが、アルファベットや漢字だと文字コード順に並ぶ。
いくつかアルゴリズムがあります。7つくらい。
■バブルソート(隣接交換法、基本交換法)
隣り合う要素を比較し逆順であれば要素を交換して並べ替える。
4、2、1、5、3の順で並んでいるとする。
まず先頭の4と隣りの2を比べ交換して
24153
次に2番目に移った4と隣りの1を比べ交換して
21453
4と5を比べ交換しない。
5と3を比べ交換して
21435
これで一番大きな値が確定する。
この先頭から順に比較と交換の操作を繰り返し、最終的に
12345と並ぶ。

5件のデータを並べ替える場合の比較回数は4+3+2+1=10となる。n個のデータならn(n-1)/2で比較回数が求まる。
nとn-1は隣り合った数なのでどちらかは必ず偶数になり、2で割り切れるので出てくる答えは少数になることはない。
オーダー記法ではO(n^2)と書く。

■基本選択法
先頭の要素から順に値を決めて並び替える。昇順に並べる場合、先頭に来る最小値を確定させ、範囲を狭めて並び替えていく。
4、3、1、5、2の順で並んでいるとする。
4と3を比べ3が小さい、次に3と1を比べ1が小さい。1と5を比べ1が小さい。1と2を比べ1が小さい。この時点でデータすべてを比較し終わり、1が最小値と分かった。それで1を先頭にもっていき、
1、4、3、5、2
と並び替える。次に4から始めて比較していき、2番、3番目に小さい値を確定させていく。
基本選択法の計算量(比較回数)もバブルソートと同じくn個のデータを並び替えるときはn(n-1)/2回である。
オーダーはO(n^2)

■基本挿入法
基本〇〇法は3つあり、これが3つ目。
整列済みのデータに値を挿入しながら並び替えていく。昇順、降順になるように挿入位置を調べて挿入する。
4、2、1、5、3
と並んでいるデータがあるとする。
ここで先頭の4は整列済みとする。
4>2なので、2を4の前に挿入する。
2、4
次に2>1なので、1を2の前に挿入する。
1、2、4
次は5>4なので5は4の次に挿入する。
1、2、4、5
そして最後の3を4と比較して4>3なので3を4の前に挿入する。
1、2、3、4、5
となる。
オーダーはO(n^2)

■シェルソート
基本挿入法を改良したものです。
一定間隔で(例えば4つ間隔など)取り出した部分列をソートし、ソートが終わるとその間隔を狭めていき(次は2間隔)、並べ替えることを繰り返す。4間隔でソートするとデータの数が奇数の場合、真ん中はペアになるデータが存在しないが、それはそのままの順にしてつぎの間隔のソートへ移る。
教科書では間隔4、間隔2、間隔1で狭めていっている。先生の解説だとデータの数を超えない2の累乗の数を最初の間隔と設定するそうです。
9 7 6 10 6 4 1
という並びだと、9と8を比較し交換する。
次に7と4を比較し交換する。という具合です。
オーダーはO(n^2)

■マージソート
マージには併合、合併、合流の意味がある。
データが一つの要素になるまで分割を繰り返し、並び替えながらマージしていく。クイックソートと雰囲気が似てる部分があり間違えないようにしてほしい。マージソートは何となく分割して合併していくものだと覚えておけばいいそうです。
オーダー記法では(nlogn)となる。

■クイックソート(Sマーク、試験で出やすい記号)
基準値を決めて、基準値より小さいグループと大きいグループに分け並び替えをする。分割したグループ内でも基準値を決めてさらに分割していく。基準値の決め方は教科書では無作為とあるが、ある程度のルールはあるようです。

基準値が4なら4未満と4以上とに分け、データを交換してグループ分けします。それで2つのグループに分かれたところで、それぞれのグループ内で基準値を決め例えばそれぞれ2と6が基準値なら、2以上と2未満、6以上と6未満と、その基準値でグループ分けできるようにデータを交換していく。基準値によるグループ分けで交換していくと、最終的に全体の並び替えができているというソートです。
オーダーはO(nlogn)

■ヒープソート
木構造のヒープ(どの親子関係を見ても、親<子の関係が成り立つもの)を利用して基本選択法で並べ替える。選択法の改良版になります。木構造のルートから左部分木、右部分木と順番に入れ、親子関係を入れ替えながらヒープ木を作っていく。ルートにあるデータは一番小さな値となる。取り出すときはルートから取り出すが、その際にヒープ木の再構築が行われる。それで再びルートに一番小さな値が来るとヒープ木は完成し、またルートからデータを取り出し、並べ替える。
オーダーはO(nlogN)

●探索
配列などのデータ構造に格納されたデータから目的のデータを探し出す操作のこと。
■線形探索
先頭から順にデータを探す方法。
探索にかかる回数は最小で1回、最大でn回、平均は(n+1)/2回となる。
フローチャートだとAは配列(A(i)で配列のi番目のデータを指す)、wを探索したいデータとして
開始
i←1
終了条件(w=A(i)またはi>n)
i←i+1
分岐条件(i<=n)
で分岐で真なら見つかったことになり、偽ならデータは見つからなかったことになる。

番兵法
線形探索の一種でデータの最後に目的のデータを追加してから線形探索を行う。これで最後には必ずデータが見つかり、繰り返しの終了判定を簡潔にできる。
4、2、1、5、3というデータの並びがあって、そこの最後に探したい6というデータを追加する。
4、2、1、5、3、6として線形探索する。


■二分探索法(Sマークがついている。もう一つSを付けてよいくらい重要です)
この探索にはデータが整列済みであることが求められる。通常は昇順で並び替えしてあること。
中央のデータと目的のデータを比較し、一致しなければ大小関係から中央から見て前半、後半部分の中央値と比較していくことで探索する。一致したら見つかったということ。
中央値を求めるには配列の先頭と末尾の番号を足して2で割る。探したい値と配列の中央値番目の値を比較する。
中央値>探す値、ならば中央値を除いた前半部分の中央値を求め((先頭の番号+(中央値-1))/2)、また比較する。比較が<でも同じようにする。比較が中央値<探す値、の場合は((中央値+1)+末尾の番号)/2で中央値を求める。中央値を求めるときに1.5などのように端数が生じたら少数は切り捨てる。大なり小なりで比較したが、中央値=探すデータ、というように等しい場合はデータが見つかったことを意味する。
n個のデータの二分探索法での探索回数は
平均回数は底2のlog2回
最大回数は底2のlog2+1回
となる。
よく出てくるので必ず覚えておいてください。

■ハッシュ探索法
データの格納場所をデータ値とハッシュ関数を用いて計算で求める探索方法。データ値にハッシュ関数を適用すると格納されるアドレスが求まる。探索回数は基本的に1回となります。別々なデータで計算したのに同じアドレスになることがある。そうしてアドレスが衝突することをシノニムという。シノニムが発生するとチェーン法やオープンアドレス法などで対処してデータを格納する。

●再帰(リカーシブ)
処理の途中で自分自身を呼び出して実行すること。4つあったプログラム属性(リエントラント、リロケータブルなど)の1つ。階乗を求めるなどの場合は
5!= 5*4!
4!= 4*3!
3!= 3*2!
2!= 2*1!
1!= 1
と関数を呼び出していき、最後の1!まで来たら今度は逆順に2!= 2*1!の階乗に1を、3!= 3*2!の2!に代入していくといった処理。

第8章のまとめノートもやりました。
ここまででコンピュータ概論の教科書は終わりです。
次回からアルゴリズムとデータ構造の教科書を使います。時間があるので内容を少し見ました。
プログラムを作成するには3つのステップが必要です。
①与えられた問題を分析し、解決方法を考える。
②利用するアルゴリズムとデータ構造を決める。
③アルゴリズムとデータ構造をプログラミング言語で表現する。

■データ型
数値型には整数型、実数型があり、整数型は正負を扱える符号ありと扱えない符号なしの2種類ある。文字型は一文字だけ扱え、文字列型(String型)は複数の文字を扱える。真偽を扱う論理型もあり、これはboolean型である。言語によって具体的な型は異なります。