試験日

2020年4月第三日曜日.

前回

メモ

アルゴリズム

整列アルゴリズム

参考文献
- トップページ | Programming Place Plus アルゴリズムとデータ構造編
- ソート - Wikipedia

基本的には上記サイトの解説とコードをみながら計算量を確認. wikiも整理されていています. 以下の計算量は」全て平均計算時間を記したもの.

交換ソート
- 単純ソート：一つずつ比較, O(n**2)
- バブルソート：隣り合う要素を比較して一つずつ位置を確定させる, O(n**2), 安定.
  - シェーカーソート：バブルソートの比較を二方向に行う. ほとんど整列ずみのデータに対して高速なソートになる.
  - 奇偶転置ソート：奇数・偶数インデックスの比較↔️偶数・奇数インデックスの比較を繰り返す.
  - ノームソート：隣接する要素を比較しつつ, 比較した時に順序がおかしくなるのは直後のみを確認し, 正しい順序になるようにする.
選択ソート
- 単純選択ソート：最小をリストから探し先頭に設置, O(n**2), 不安定.
- ヒープソート：二分ヒープ木を用いたソート. O(nlogn).
  - イントロソート：クイックソートの再帰回数が閾値を越えるとヒープソートに切り替えるアルゴリズム.
- クイックソート：ピボットを選びその大小で二分することを繰り返し, 最後に全て連結する.

未整列のリストから要素を取り出し、順にヒープに追加する。すべての要素を追加するまで繰り返し。

ルート（最大値または最小値)を取り出し、整列済みリストに追加する。すべての要素を取り出すまで繰り返し。

挿入ソート
- 単純挿入ソート
- シェルソート
- 図書館ソート：図書館ソート - Wikipedia
マージソート

www.ics.kagoshima-u.ac.jp

安定・不安定ソート
- ソートアルゴリズムのうち値が同じ要素は元の配列に含まれていた順番で保持されているものを安定ソートと呼ぶ. アルゴリズムを適用した後で, どのような順番で出現するかわからないものを不安定ソートと呼ぶ.
- 不安定ソートも元の配列の順序を記憶しておき, それを参照すれば安定にできる. ただし, この場合 O(n) の外部メモリが必要になる.
- つまり, 内部ソートである不安定ソートを安定にしようとすると外部ソートになってしまう. 出典：ヒープソート - Wikipedia
局所性
- 時間的局所性：最近アクセスされたものはまた参照されやすい
- 空間的局所性：最近アクセスされたリソースの近くが参照されやすい
- 逐次的局所性：メモリが逐次的にアクセスされやすい

文字列探索

文字列検索のいろいろ from Kazuma Mikami

www.slideshare.net

developer.hatenastaff.com

コンピューター構成要素

参考文献
- 名古屋大学, 計算機システム概論 (2011年度)

基本的な内容は上記講義のスライドて事足りると思われます.

コンピュータの構成要素
- 入力＋出力＋記憶＋制御＋演算
プロセッサ
- パイプライン処理：複数の処理をオーバーラップ、ベルトコンベアのように流していく.
  - パイプラインストールが発生すると処理が止まってしまう.
  - 構造ハザード
  - 制御ハザード
  - データハザード：処理に必要なデータが届いていない状態
    - データフォワーディング：データハザードをなるべく回避するためにレジスタを介さずにデータを渡す
- スーパースカラ：パイプラインを複数持つ
- マルチプロセッサ
- VLIW：複数の演算を定義できる命令を使用する
- RISC：一つの機械語命令を一クロックで
- CISC：一つの機械語命令で複数の処理を行う
マルチプロセッサ：マルチプロセッサ（MP）とは - IT用語辞典 e-Words
- 対称と非対称；各プロセッサが対等な立場で処理するかどうか
- 密結合と疎結合：各プロセッサがメモリやリソースを共有するか, それぞれが分離して保持しているか
メモリ
- 参考文献：（主記憶に用いられる）メモリの種類Page 7
- 読みだし専用か読み書き可能か
- 揮発性か不揮発性か
  - 揮発：半導体メモリ
    - 永続性：半導体メモリの中で的的なリフレッシュが必要かどうか
      - ダイナミックメモリ＝リフレッシュが必要
- 読み書き可能か
  - 読み出し専用（ROM）：ROM/PROM/EPROM
  - 読み書き可能（RAM）：SRAM/DRAM
    - コンデンサに1ビットを持つ場合はリフレッシュが必要(DRAM)/Dフリップフロップに保存する場合はリフレッシュがいらない(SRAM)