勉強内容まとめ

お勉強 試験

これまで勉強した内容をとりあえずまとめてみる。

全工程の中で、もっとも長い(日数がかかる)経路

  • 待ち行列(ケンドール記号)
    • Ｍ／Ｍ／１
    • 最初のＭ・・・トランザクション(一定時間に来店した客数)数(ポワソン分布であらわす)
    • 次のＭ　・・・サービス時間(指数分布であらわす)
    • 次の１　・・・窓口は１つである
      • 到着順に処理を行なう
      • 割り込みは無し
      • 客は立ち去らない
      • 待ち行列の長さに制限無し
  • スタック(LIFO)

線形リストへの要素の追加と削除を先頭で行なう

線形リストへの要素の追加は最後尾、削除は先頭で行なう

  • ヒープ領域

未使用領域、使用領域をそれぞれポインタで繋いリスト構造

f(x)の近似値を求める。って感じらしい。なんのこっちゃ。

両方とも、平均値からどれほど実データが離れている(ぱらついている)のかをあらわすもの。対象のデータをN倍すると、分散はNの2乗、標準偏差はN倍になるらしい。

  • 持論について
    • 演繹とは「猫Ａは鼠を追いかける、猫Ｂも猫Ｃも鼠を追いかける、したがって猫は鼠を追いかける」
    • 帰納とは「人は必ず死ぬ、ソクラテスは人である、したがってソクラテスは死ぬ」
    • 類比とは「Ａ君は勤勉だ、Ｂ君はＡ君に似ている、したがってＢ君は勤勉だ」

って感じなんだって。
要するに、演繹はもしかしたら違う事例が発生するかもしれなくて、帰納はほとんど発生しない。類比は全くの予想。って感じかな。

  • 確立問題

特に問題なし→掛け算できればいいかな。

知ってる

  • BNF
    • 特に大丈夫
  • 最短木

訳わかんないよ、これ。

  • 経路を辿る本数

数学で習った記号(Cみたい記号の両側に小さい数字)を使って、あるＡ地点からＢ地点までのルート数を計算。
これも訳わかんない、というより記号の意味を忘れた。訳わかんないのは何とか調べないと。

うーん、絶対知ってると思ってた排他的論理和をびみょーに忘れてた。

  • 基数変換(１０進→２進など)
  • 補数とは
  • Cという記号が組み合わせだった事が判明！

6C3ならば、6種類の中から3つ取り上げる組み合わせ数。式は6*4*3/3*2*1って感じ。

  • 2部グラフ

端を2つにグループ分けして、どうグループ内は接しないよう、他グループは接するようにしたグラフ。あってんのか？
わかったよーな、わかんないよーな。

  • log久々に登場！(高校以来)

対数ってやつだね。log3５ならば、log2５/log2３が出来る。

  • Ｏ記法

その式で一番影響が大きい(計算量を支配している)物を見つけ、Ｏ()にセットするといいらしい。はぁ？　

  • ＣＭＯＳ

低消費電力、高い集積度だが、動作は比較的遅い

  • バイポーラ

動作は比較的速いが、消費電力は高く、集積度も低い

  • 命令の実行順序

命令の取り出し→命令解読→アドレス計算→データ取り出し→実行

アドレス修飾に用いるレジスタ、基準からの増減分

  • ２分探索

データがキー順になっているのが前提で、中央のデータと探索するキーを比較し、前か後かで探索していく方法。
２のx乗 <= 要素数 < ２のx+1乗 となる。

  • 線形探索

データの端から順に一致する要素を探索する方法。整列されていなくても問題なく、平均比較回数は要素の半分。

未整列の部分を大きい要素と小さい要素に分けてソート。

  • 選択ソート

未整列部分の端と各要素を比較し、大小によって分けるソート。

  • 挿入ソート

整列済みの配列の適切な部分に入れていくソート。

整列済みの配列を複数作成してからマージするソート。

隣り合う要素比較して入れ替えていくソート。

  • 巡回法

深さ優先と、幅優先がある

  • Ｂ木

根以外はn個以上の要素をもつ
各点にはたかだか2n個の要素をもつ
各点は要素数に1加えた数の子をもつ
根からすべての葉までの深さは等しい
キー順である

  • ハッシュ表探索

データ値そのものから計算して格納位置を決定