院試対策 メモ
極限
重要公式
$$
\lim_{{x \to 0}} \frac{\sin x}{x} = 1
$$
$$
\lim_{{x \to 0}} \frac{e^x - 1}{x} = 1
$$
$$
\lim_{{x \to 0}} \frac{\log(1 + x)}{x} = 1
$$
$$
\lim_{{h \to 0}} \left( 1 + h \right)^{\frac{1}{h}} = e
$$
$$
\lim_{{x \to \pm\infty}} \left( 1 + \frac{1}{x} \right)^x = e
$$
$$
(arcsin)' = \frac{1}{\sqrt{1-x^2}}
$$
sinは微分するとcosになって、cosを√cos^2にして√1-sin^2にする
$$
(arccos)' = -\frac{1}{\sqrt{1-x^2}}
$$
cosは微分すると-sinになって、-sinを-√sin^2にして-√1-cos^2にする
$$
(arctan)' = \frac{1}{1+x^2}
$$
y = tan^-1 x からx = tan y にして、dx/dy = 1 / cos^2 yからdtan^-1 /dx = dy/dx = 1/ (dx/dy) = 1 / (1/cos^2 y) = 1 / (1 + tan^2 y) = 1 / (1 + x^2)
$$
(tan)' = \frac{1}{cos^2}
$$
(sin / cos)' を商の微分で下の２乗と上は右が-×-で+2なってcos^2+sin^2 = 1
$$
(\frac{1}{tan})' = -\frac{1}{sin^2}
$$
(cos / sin)' を商の微分で下の２乗と上は左が-で右が-(+)で-cos^2-sin^2 = -1
おまけ
セカント
$$
(sec)' = (\frac{1}{cos})' = \frac{0 - (-sin)}{cos^2} = \frac{sin}{cos^2} = sec *tan
$$
コセカント
$$
(csc)' = (\frac{1}{sin})' = \frac{0 - cos}{sin^2} = \frac{cos}{sin^2} = -csc *cot
$$
コタンジェント
$$
(cot)' = (\frac{1}{tan})' = \frac{0 - \frac{1}{cos^2}}{tan^2} = -\frac{1}{sin^2} = -csc^2
$$
$$
\int csc\theta d\theta = log|tan\frac{\theta}{2}| + C
$$
$$
\int sec\theta d\theta = log|tan(\frac{\theta}{2} - \frac{\pi}{4})| + C
$$
$$
\int cot\theta d\theta = log|sin \theta| + C
$$
csc は，sin の2倍角の公式を用いたり，分母分子にsin を掛けたりする方法があるのですが，右辺を覚えておいて微分するのが早いでしょう．csc は，tan(x/2) = t と置くのも有効．
sec は，cosθ = sin(π/2-x) = -sin(x-π/2) の利用が良い．
cot は，まあ無問題．
アキト
微分積分
うさぎでも分かる解析シリーズ
疑問点：
１．置換積分のdxとdtの関係の求め方
２．二重積分のときの空間の分け方→再度Part27を読もう
３．T大R1の冪級数展開とはなんだ→複素解析も読もう
４．H大R4に微分方程式あるぞ→ヨビノリ見よう
補足
微分方程式
ヨビノリ
複素関数論
ヨビノリ
線形代数
線形写像
https://www.momoyama-usagi.com/entry/math-linear-algebra21
応用編
編入数学
また、正則ではない⇔逆行列が存在なし⇔|A-λE|=0
解析的な解法では、２つ目の式をy_1 = y_2' + 2y_2にして、微分して、１つ目の式のy_1とy_1 'に代入し、y_2''を含んだy_2の二階線形微分方程式を解き、y_1を解く
解空間Wの次元は、連立１次方程式の解の自由度に一致する
[x]_2 実数係数の2次以下の多項式の集合。線形な自分自身から自分自身への写像＝線形変換。xをx+3に変えたものが出てくるので、1にxは含まれないために1がそのまま出てくる
(x, y)をパラメータ表示で１変数に絞ってf()に送る。または、f()に送ってから、f()をx, yで表して、その式をもとの図形の式に代入して動きをみる
tを動かしたらx=3k+tも動いちゃうから、自分自身に戻らなさそう。自分に戻るなら移した先もxが固定されていないといけない。3k+t=x', 4k+3t=y'としてtを消去すると斜めった直線が出てくる
本来はx=kとy=ax+bで場合分け必要だったが、誘導でその必要なくなった。
自分自身に移る写像なので、x', y'もy=ax+bという関係式を満たしているはず。
tに関する恒等式より、係数を比較して
1次従属であるための必要十分条件⇔行列式=０
線形計画法
オートマトンと言語理論
ももやまうさぎ塾
補足：
[X]は、特定のパターンが文字列の終わりに位置し、そのパターンの長さを正確に追跡する必要があるため、正規言語ではありません。
[Y]は、特定のパターンが文字列の任意の位置に現れるだけで認識できるため、正規言語です。
ポンピング補題
＋H大言語理論lec2, lec3
正規言語⇔有限の記憶で受理するかを判定することができる⇔文脈自由文法の中の正則文法（左正則文法 or 右正則文法）で書ける
→nが無限まで飛ばせそうだと無理そう
文脈自由言語⇔文脈自由文法で書ける⇔プッシュダウンオートマトンで書ける
→スタック回数＝プッシュの回数」になるならよい。a^i b^j c^k で、i = j ∨ j = kならPDAの記憶装置は憶えてられるが、i = j = kならkの頃には残っていない
文脈自由言語に対するp補題
CS関係
DSA
O(x!) > O(2^x) > O(x^2) > O(x log x) > O(x) > O(log x)
https://www.ci.seikei.ac.jp/yamamoto/lecture/algorithm/text.pdf
グラフ理論
12
幅優先探索BFS(Breadth First Search)…探索候補点の中から一番最初につくられた探索候補点を1つ取り出す、キュー
深さ優先探索DFS(Depth First Search)…一番最後につくられた探索候補点を1つ取り出す、スタック
13
全域木…もとのグラフのすべての点を含み、さらに選んだ辺が木となっているようなグラフを表します。（全域部分グラフが木となっているものを全域木）
重み付きグラフ
重み＝コスト
最小全域木
クラスカル法…閉路ができないように重みが小さい順番から辺を選び、追加していく。重みの最小は必ず1通りに決まりますが、辺の選び方は1つとは限らない
プリム法…つながっているすべての点からたどれる辺 かつ 追加しても閉路とならないような辺の中から一番重みが小さい辺を追加
14
ダイクストラ法…まずスタートに近い点から最短経路を決定し、徐々にゴールに近い点の最短経路を求めていく。確定距離、暫定経路。「確定距離が出た点と隣接している点の暫定距離を出す → 暫定距離が最小のものを確定させる」をゴール点の距離が確定するまで繰り返す。𝑂(𝑛2) 以下
A*アルゴリズム
動的計画法(Dynamic Programming・DP)…そのまま解くと難しい問題を手短に解ける簡単な問題に分割し、分割した簡単な問題の答えを使うことで徐々に複雑な問題を解いていく方法
ベルマン・フォードのアルゴリズム…負の値も扱える
14
フロー
最大フロー
重みつき有向グラフ＝ネットワーク
残余ネットワーク
増大道
カット
カットの容量 $${ U(S, \bar{S}) }$$や$${ c(S, \bar{S}) }$$
$${ f_max ≦ U(S, \bar{S}) }$$
最小カット(あるネットワークの中でカットの容量が最小となるようなカットを最小カットと呼ぶ。また、最小カット の容量と最大フローは必ず等しくなるので、最大フローを求めることで最小カットの容量を求めることができる。さらに最小カットはスタート点からたどれる点をすべて集めた集合となる。)
16
k-連結グラフ（k-頂点連結グラフ）
連結度（点連結度）𝜅(𝑥)
分離集合（点分離集合）𝑊={𝑏,ℎ}
k-辺連結グラフ（k-頂点連結グラフ）
辺連結度𝜆(𝐺)
分離集合（辺分離集合）𝑊={(𝑏,𝑒),(𝑒,ℎ)}
あるグラフ 𝐺 における連結度 𝜅(𝐺)、辺連結度 𝜆(𝐺)、最小次数 𝛿(𝐺)では、𝜅(𝐺)≦𝜆(𝐺)≦𝛿(𝐺)
関節点（カット点）
橋（橋辺）
点素（内素）
辺素
メンガーの定理
最小分離点数
2点 𝑠, 𝑡 を分離するために消す必要がある点の最小数は、𝑠, 𝑡 間の点素な道の数に等しくなる
最小辺分離集合
2点 𝑠, 𝑡 を分離するために消す必要がある辺の最小数は、𝑠, 𝑡 間の辺素な道の数に等しくなる
最小分離点数が最も少ないものが点連結度
最小分離辺数が最も少ないものが辺連結度
17
マッチング＝2つの頂点を1本の辺で結んだ部分グラフ
極大マッチング
最大マッチング
完全マッチング
$${ m(ペア数) = \frac{1}{2} n(頂点の数) }$$
増大道(交互道)
増大道がないような極大マッチングは最大マッチング
AからBへの完全マッチング
ホールの結婚定理(この2つの定理は両方とも完全マッチングを作れないことを示すのに役に立ちます。)
|𝑆|≦|𝑁(𝑆)|
タットの定理(ホールの定理を2部グラフでない普通のグラフでも使えるように拡張した)
偶成分
奇成分
奇成分𝑜(𝑋)
𝑜(𝐺−𝑆)≦|𝑆|
18
平面グラフ
平面的グラフ
オイラーの定理、連結な平面グラフの頂点の数を 𝑝、辺の数を 𝑞、面の数を 𝑟 とすると、𝑝−𝑞+𝑟=2
平面グラフであるための条件、連結な単純平面グラフの頂点の数を 𝑝、辺の数を 𝑞 とすると、𝑞≦3𝑝−6が成立する。（ただし 𝑝≧3 ）
連結で単純な平面的グラフであれば、次数5以下の点が必ず1つ以上存在する。
3辺で構成される領域がない（三角形の面がない）連結で単純な平面的グラフの頂点の数を 𝑝、辺の数を 𝑞 とすると、𝑞≦2𝑝−4が成立する。（ただし 𝑝≧3 ）
クラトフスキーの定理(ある単純グラフ 𝐺 が平面的グラフであるための必要十分条件は、完全グラフ 𝐾5 または 𝐾3,3 の一部分を含んでいないことである)
19
彩色問題(点彩色, 辺彩色)
n-頂点彩色(彩色数≦n≦頂点数)
彩色数
頂点数 𝑛 の完全グラフ 𝐾𝑛 の彩色数は 𝑛 である
2部グラフの彩色数は2である。
Welch-Powellの点彩色アルゴリズム
6色定理(平面グラフは必ず6-頂点彩色ができる。つまり、平面グラフの彩色数は必ず6以下となる。(どんな地図でも6色以内で彩色することができる。))
→頂点数n+1のときに成り立つことを数学的帰納法で示す
5色定理
4色定理
辺彩色
n-辺彩色(彩色指数≦n≦辺数)
あるグラフ 𝐺 の彩色指数は、必ずグラフ 𝐺 の最大次数以上になる
Vizingの定理…単純グラフ 𝐺 は （𝐺 の最大次数+1）色あれば必ず辺彩色できる。つまり、単純グラフ 𝐺 の彩色指数は必ず「最大次数-1」以下となる。
よって、単純グラフ 𝐺 の彩色指数は必ず「最大次数」もしくは「最大次数+1」となる。
頂点数 𝑛 の完全グラフ 𝐾𝑛 の彩色指数は以下の通りである。
𝑛 が偶数のとき：彩色指数は 𝑛−1
𝑛 が奇数のとき：彩色指数はn
Konigの定理…2部グラフ 𝐺 は 𝐺 の最大次数だけ色あれば必ず辺彩色できる。つまり、2部グラフの彩色指数は必ず「最大次数」となる。
※なぜ10個の点の重み付きグラフの最短経路をごり押しで求めると10!通りなのか？
これが「全ての点を訪れる順序の数」となる理由は以下の通りです：
最初の点の選択: 10個の点があるとき、最初に訪れる点を10通りの中から選ぶことができます。
2番目の点の選択: 最初の点を選んだ後、残りの9個の点から2番目に訪れる点を選びます。これは9通りあります。
3番目の点の選択: 2番目の点を選んだ後、残りの8個の点から3番目に訪れる点を選びます。これは8通りあります。
このプロセスはすべての点が選ばれるまで続きます。したがって、10個の点を訪れる全ての順序の数は10 × 9 × 8 × ... × 1、すなわち10!になります。これが10!（10の階乗）の意味であり、巡回セールスマン問題のような状況で全探索を行う場合の全ての順序の数を示しています。
それぞれの点から点までの距離が確定したものを確定距離、確定はしてないものの距離を計算している点を暫定距離とする。
スタート点からスタート点までの確定距離を0とする。
距離が確定した点と隣り合っている点までの暫定距離とたどる元の点を求める。
（暫定距離 ＝ 確定距離 ＋ 隣り合っている点までの移動距離）
ただし、隣り合っている点の暫定距離がすでに求まっている場合、より短い暫定距離が出た場合のみ上書きする。また、隣り合っている点の確定距離がすでに求まっている場合は無視する（すでに確定してるので更新されない）。
暫定距離が出ている点の中で、一番暫定距離が小さいものを確定距離とする。
すべての距離が確定するまで2, 3を繰り返す。距離が確定した際の経路は、ゴールから元の点をたどっていることで求めることができる。
A*アルゴリズム
A*のアルゴリズムの実装について説明します。この実装では、OPENリストが後述するように遅いことに注意しておきます。
１．スタートノード（S）を作成します。また計算中のノードを格納しておくための優先度付きキューOPENリストと、計算済みのノードを格納しておくCLOSEリストを用意します。（名前は「リスト」ですが、これらの実際のデータ構造は必ずしも連結リストである必要はありません。）
２．ゴールは必ずしも1つである必要はないので、ゴール条件を満たすノード集合をGと呼ぶことにします。
３．スタートノードをOPENリストに追加する。このときg(S) = 0でありf(S) = h(S)となります。また、CLOSEリストは空にします。
４．OPENリストが空なら探索は失敗とします（スタートからゴールにたどり着くような経路が存在しなかったことになります）。
５．OPENリストに格納されているノードの中で、最小のf(n)を持つノードnを1つ取り出します。同じf(n)を持つノードが複数ある場合は、タイブレーク手法によりどれかのノードを選択します。
６．n ∈ Gであるなら探索を終了します。それ以外の場合はnをCLOSEリストに移します。
７．nに隣接している全てのノード（ここでは隣接ノードをmとおきます）に対して以下の操作を行います。：
７－１f'(m) = g(n) + COST(n, m) + h(m)を計算します。ここでCOST(n, m)はノードnからmへ移動するときのコストです。またg(n)はg(n) = f(n) - h(n)で求めることができます。
７－２ mの状態に応じて以下の操作を行います。：
７－２－１ mがOPENリストにもCLOSEリストにも含まれていない場合は、f(m) ← f'(m)としてmをOPENリストに追加します。このときmの親をnとして記録します。
７－２－２ mがOPENリストにある場合、f'(m) < f(m)であるなら、mをOPENから削除し、f(m) ← f'(m)に置き換え、再びOPENに挿入します（OPENが正しくソートされていることを保証するため）。また、記録してあるmの親をnに置き換えます。
７－２－３ mがCLOSEリストにある場合、f'(m) < f(m)であるならf(m) ← f'(m)としてmをOPENリストに移動します。また、記録してあるmの親をnに置き換えます。
８．3以降を繰り返します。
９．探索終了後、発見されたゴールnGから親を順次たどっていくとSからゴールnGまでの最短経路が得られます。
あるネットワークのスタート 𝑠 からゴール 𝑡 までの最大フローは下のような手順で求めることができる。
１．全部のフローが0の状態をはじめの状態（初期フロー）とし、初期フローのときの残余ネットワーク（与えられたネットワークと同じ）を考える。
２．残余ネットワークで 𝑠 から 𝑡 までたどれるような道（ルート）を見つけ、その道に流せるだけのフローを流す。（この道のことを増大道と呼びます）
３．2を繰り返し、𝑠 から 𝑡 まで流せる道がなくなったときのフローが最大フローとなる。
なぜ 𝑞≦3𝑝−6 が成立するのかを説明していきます。
まず、連結な平面グラフにはオイラーの公式𝑝−𝑞+𝑟=2が成立しますね。（𝑝 は頂点数、𝑞 は辺数、𝑟 は面数、領域数）
ここで、𝐿 を領域を構成する辺の数の総和とします。
1つの領域を作るために、少なくとも3つの辺が必要ですよね。
グラフの領域数は全部で 𝑟 なので、グラフにあるすべての領域を表現するためには少なくとも 3𝑟 個の辺が必要ですね。なので 𝐿≧3𝑟 となります。
また、1つの辺は2つの領域を区切る境界となっていますよね。なので、𝐿=2𝑞 が成立します。
2つの式を連立させると、3𝑟≦2𝑞が成立しますね。
ここで、オイラーの公式 𝑟=2−𝑝+𝑞 に代入すると、3(2−𝑝+𝑞)=3𝑟≦2𝑞𝑞≦3𝑝−6となり、たしかに 𝑞≦3𝑝−6 が導出できますね。
頂点数 𝑝、辺数 𝑞 の連結で単純な平面グラフの次数がすべて6以上と仮定する。
すると、次数の合計は少なくとも 6𝑝 以上でなければならない。
ここで次数の総和はグラフの辺の数の2倍であるので（握手定理*2）、辺 𝑞 の数は少なくとも 3𝑝 個以上なくてはならない。つまり、𝑞≧3𝑝 である*3。… (1)
また、連結で単純なグラフなので頂点数と辺数の関係として 𝑞≦3𝑝−6 が必ず成立する。… (2)
(1), (2) より頂点数 𝑝 および辺数 𝑞 に対し、3𝑝≦𝑞≦3𝑝−6が成立する。
しかし、上の式を満たす 𝑝,𝑞 は存在しないため仮定に矛盾する。
よって、少なくとも1つは次数5以下の点が存在することが示された。
3辺で構成される領域がない（グラフに三角形の面がない）グラフにはより厳しい条件式を適用することができます。
3辺で構成される領域がないたため、領域はすべて4つ以上の辺で構成されていますね。
なのでグラフにあるすべての領域を表現するためには少なくとも 4𝑟 個の辺が必要となり、 𝐿≧4𝑟 が成立しますね。
1つの辺は2つの領域を区切る境界なので 𝐿=2𝑞 が成立しますね（ここは同じ）。
連立させると、4𝑟≦2𝑞が成立するのでオイラーの公式 𝑟=2−𝑝+𝑞 より4(2−𝑝+𝑞)=4𝑟≦2𝑞𝑞≦2𝑝−4となり、𝑞≦2𝑝−4 というより厳しい条件式が導出できます。
Welch-Powellの点彩色アルゴリズム
ループを持たないグラフの点彩色は以下のようにして求めることができる。
それぞれの頂点における次数を調べ、次数が大きい順に頂点を並び替える。
次数が一番大きい点に色 𝐶1 を塗る。さらに、次数が大きい順に色 𝐶1 を塗った点と隣接してない点に同じ色 𝐶1 を塗る。
まだ塗られていない点の中で次数が一番大きい点に別の違う色 𝐶2 を塗る。さらに次数が大きい順に色 𝐶2 を塗った点と隣接してない点に同じ色 𝐶2 を塗る。
すべての頂点が塗られるまで3を繰り返す。
※注意：次数が大きい順に点を選ぶ際に次数が同じ点がある場合、選んだ点によって正しく彩色数が求められないことがあります。
（どの点を選んでも必ず最小の色数になるとは限らない）
(i) 頂点数が6以下のとき
頂点数が6以下であれば、すべての頂点を異なる色で塗っても彩色数は6以下ですよね。なので頂点数が6以下であれば必ず6色定理が成立します。
(ii) 頂点数がn+1のとき
では頂点数
のときに6色定理が成り立つことを仮定してから頂点数が
個のときに6色定理が成り立つことを示しましょう。
まず、平面グラフには次のような定理がありましたね。
平面的グラフと次数
連結で単純な平面的グラフであれば、次数5以下の点が必ず1つ以上存在する。
（当然平面グラフも平面的グラフであるので成立する）
平面グラフには次数が5以下の点が必ず1つは存在しますよね。
頂点数が
の平面グラフ
から、次数が5（以下）の点
を削除したグラフ
を考えます。
すると、
の頂点数は1つ減って
となりますね。このグラフ
が平面グラフであると仮定します。（帰納法の仮定）
グラフ
に先程削除した点
を追加します（もとに戻します）。
は次数が5（以下）の点なので、
のまわりにあるどの点とも異なる色を彩色することでグラフ
も6色で彩色することができますね*2！
なのでどんな平面グラフであっても6色以内で彩色できる、つまり6-頂点彩色ができることが示されましたね！
(i) 頂点数が5以下のとき
頂点数が5以下であれば、すべての頂点を異なる色で塗っても彩色数は5以下ですよね。なので頂点数が5以下であれば必ず5色定理が成立します。
(ii) 頂点数がn+1のとき
先程と同じように、頂点数
のときに5色定理が成り立つことを仮定してから頂点数が
個のときに5色定理が成り立つことを示しましょう。
6色定理のときと同じように頂点数が
の平面グラフ
から、次数が5（以下）の点
を削除したグラフ
を考えます。
しかし、そのままでは5色以内で塗りわけることを示せないので、5色定理では6色定理の証明では使わなかった定理を1つ使います*3。
平面グラフには、次数5以下の点が存在するのに加え、次のような定理も成り立ちましたね。
頂点数5の完全グラフと平面的グラフ
頂点数5の完全グラフ
は平面的グラフではない。
（もちろん平面グラフでもない）
この定理から、頂点数5の平面グラフは必ずどこか隣り合っていない点があると言うことができます。
（完全グラフはどの頂点も隣り合っているグラフなので、完全グラフではないグラフは必ずどこかの2点は隣り合っていない）
なので次数5のまわりの点の中で、隣り合っていない2点を同じ色で塗ってから平面グラフ
から次数5の点
を一端消してグラフ
とします。
そして、頂点数
のグラフ
が平面グラフであると仮定します。
あとは6色定理と同じ流れで証明ができます。
先程消した次数5の点
を復活させ、まわりの5点（4色）とは異なる色で塗ることで頂点数
のグラフ
も5色で色分けすることができますね。
なのでどんな平面グラフであっても5色以内で彩色できる、つまり5-頂点彩色ができることが示されましたね！
http://www.iee.e.titech.ac.jp/~shioura/teaching/orf22/2022endterm-exam.pdf
http://www.iee.e.titech.ac.jp/~shioura/teaching/opt15/optim15-09.pdf
アーキテクチャ
予想問題
フォンノイマン・ボトルネック
時間的局所性、空間的局所性
バッチ処理・対話処理・リアルタイム処理
内部割込み？ 外部割込み？
ソフトウェア割込み？ ハードウェア割り込み？
システムコールとは
ウランドロビン方式や多重レベルフィードバックスケジューリングの説明
MMU(Memory Management Unit)の役割 hint:仮想ページ番号、物理ページ番号、ページ内変位、存在ビット。変換とページフォルトの検出・割込み
ページイン、ページアウト
スラッシング
フラッシュメモリ保護のためにウェアリング(分散して書き込み)、ランダムライト(ランダムな順序での書き込み)→ガーベッジコレクション(メモリリークも)→解決のためにライトアンプリフィケーションが増加→消耗
パーティションテーブル
プライマリーパーティション→実際にOS記号に利用するアクティブパーティション
ライトバック方式はコヒーレンシが保てないため、スヌープ方式によって、バス上のデータの流れを監視(バススヌープ)、変更に応じて最新データを取得してキャッシュメモリの該当データを更新
プリページング、デマンドページング
アロケーション、ファーストフィット方式(下位が頻繁に使われ上位があまり使われない→消耗)、ベストフィット方式(minimum)、ワーストフィット方式(maximum)
メモリの断片化(fragmenatation)→メモリコンパクション(実行中のプログラムを一時停止)、ガーベッジコレクション(実行中のプログラムが解放)
リロケーション
静的再配置 （static relocation）
プログラムをメインメモリに読み込む実行開始時（ストレージからのロード時）にまとめて論理アドレスから物理アドレスへの変換を行う方式を「静的再配置」という。実装が単純だが、実行中に別の位置へプログラムを移動することはできない。
動的再配置 （dynamic relocation）
メモリ位置を参照する命令を実行する瞬間にアドレス変換を行う方式を「動的再配置」という。オペレーティングシステム（OS）によって実行中のプログラムの位置を移動させることができ、断片化したメモリ上の空き領域を束ねて連続した空間を得る「メモリコンパクション」が可能となる。
メモリリーク→対応策
オブジェクト指向言語では、インスタンスの初期化時に資源の確保を行い、破棄時に解放を行う「RAII」（Resource Acquisition Is Initialization）という原則に基づいてコードを記述することでメモリリークを防止しやすくなるとされる。インスタンスの初期化（コンストラクタ呼び出し）とメモリの確保を、インスタンスの破棄（デストラクタ呼び出し）とメモリ解放を結びつけて、インスタンスが生成されたスコープを抜けると自動的に破棄と解放が行われるようにする。
プログラミング言語によっては、実行時に用いられる処理系（実行環境）の機能として、参照されなくなったメモリ領域を自動的に解放する「ガベージコレクション」（garbage collection）が提供されることがある。これにより、プログラマが明示的に解放処理のコードを記述しなくても、使用されなくなった領域をある程度自動的に判別して解放することができる。
プログラム上でそのような事態が生じうる箇所のことをクリティカルセクションという。クリティカルセクションは同時に実行されることがないよう、ロック機構などを用いて排他制御を行い、一度に一つのスレッドやプロセスしか資源にアクセスできないようにする必要がある。
デッドロック(他のプログラム待ち)対策＝ロック(排他ロック、共有ロック)、セマフォ、ミューテックスによる排他制御
ACKnowledgement
一度に連続して送るパケット量はウィンドウサイズと呼ばれ、広告ウィンドウ(advertised window)（相手のキャパシティ / 処理能力）
輻輳ウィンドウ(congestion window)（ネットワークの混雑具合）
の2つのうちの小さい方3になります4。広告ウィンドウを決定することをフロー制御、輻輳ウィンドウを決定することを輻輳制御
ウェルノウンポート
ブリッジ(流れてくるMACアドレス情報を確認、必要ならパケットを流す)
スイッチングハブ（レイヤ2スイッチ）
ルータは、パケットに書かれている宛先IPアドレス（手紙でいう住所）を確認し、目的のルータまでパケットを送る
プロトコル変換をすることによって、異なるプロトコル間でも通信を行えるようにするのがゲートウェイ
デュアルスタック(IPv4とIPv6のを同時で)、カプセル化(トンネリン)(IPv4ネットワークを通じてIPv6ノード同士の通信できる)
NIC(Network Information Center)、重複なきよう
NAT(Network Address Translation)、grobal IP 一対一 private IP
NAPT(Network Address Port Translation)・IPマスカレード 1 grobal IPにmultiple private IP対応、変換
ARP(Address Resolution Protocolo)IP address→MAC address
RAPR(Reverse Address Resolution Protocol)MAC address→IP address
DHCP(Dynamic Host Configuration Protocol)、APアドレスを自動的に割り振るプロトコル
DNS (Domain Name System)
ネットワークアドレス、ブロードキャストアドレス
サブネットマスク
CIDR表記
A 0で始まる。0xxx. - 0111.
0.0.0.0 - 127.255.255.255 (0 ~ 2^7 - 1)
10.xxx.xxx.xxxx
B 10で始まる。1000. - 1011.
128.0.0.0 - 191.255.255.255(2^7 ~ 2^7 + 2^6 -1)
172.16.xxx.xxx-172.31.xxx.xxx
C 110で始まる。1100. - 1111.
192.0.0.0 - 223.255.255.255(2^7 + 2^6 ~ 2^8)
192.168.xxx.xxx
(最初の8bitが01111111のローカル・ループバック・アドレス(プライベートIPアドレスではない))
【２】 命令パイプラインは条件分岐命令があると乱れるが、それを回避する工夫を２つ以上挙げて説明せよ。
【３】 フォンノイマンボトルネックとは何かを説明せよ。またそれを改善するため工夫の例をできるだけ多く挙げよ。
【４】 ノイマン型計算機の主記憶アクセスの 2 種類の局所性について、それぞれ例を挙げて説明せよ。
【５】 メモリインターリーブで一括アクセスを行う場合に、最大の効果が得られるのはどのようなアクセスパターンのときかを述べよ。
また、ほとんど効果が得られないアクセスパターンを挙げ、その理由を述べよ。
【６】 キャッシュメモリにデータを書き込む方法として、write-through 法と write-back 法の違いを述べ、それぞれの利点欠点を説
明せよ。
https://art.ist.hokudai.ac.jp/~horiyama/lecture/ex_csit/ARCex4-Q.pdf
メモリリークとガーベッジコレクション
(1) テキスト領域（プログラム領域）
テキスト領域には、プログラムの中で機械語の部分、つまりCPUの命令コードが格納されている領域です。
また、テキスト領域は読み出し専用となので、プログラム上でテキスト領域に書き込もうとすると割り込みが発生します。
(2-1) データ領域
プログラムの中で初期値をもつような変数に割り当てられる領域です。
C言語では、0以外の初期値をもつ静的変数・広域変数に割り当てられます。
(2-2) bss領域
プログラムの中で初期値をもたない（指定しない）ような変数に割り当てられる領域です。
C言語では、初期値が0の静的変数・広域変数に割り当てられます。
データ領域・bss領域の2つを合わせてデータ領域として考えることも多くあります。この場合、データ領域は静的変数や広域変数に割り当てられる領域となります。
(3) ヒープ領域
動的にメモリ領域の確保や解放を行うのがヒープ領域です。
C言語では、malloc() 、C++では new 演算子により確保されたメモリ領域がヒープ領域となります。
動的にサイズが確保されるため、実行中にヒープ領域のサイズが変化します。
また、ヒープ領域のアドレスは先に確保したものから小さい順に割り当てられます。
(4) スタック領域
関数内にある局所変数や、関数への引数、戻り値などに割り当てられるのがスタック領域です。
C言語では、static 変数でない局所変数、および関数への引数や戻り値に割り当てられます。
ヒープ領域と異なり、実行中にスタック領域のサイズは変化しません。
そのため、変数を宣言しすぎたり、あまりにも大きな配列などを宣言するとクラッシュし、Segmentation Fault が出ます。
また、スタック領域のアドレスは、ヒープ領域とは逆で、先に確保したものから大きい順に割り当てられます。
４．システムコール
最後にシステムコールについて簡単にですが説明したいと思います。
(1) システムコールとは
OSがプログラム（アプリケーション）に対して提供する機能を呼び出すことをシステムコールといいます。
少し言い換えると、OS側が提供している関数（API）をプログラムを使うことをシステムコールと呼びます。
(2) システムコールの種類
システムコールには、例えば以下のようなものがあります。ファイルの読み込み・上書き・生成・削除・名前の変更などのファイル操作
メモリの割り当て
スリープ操作（実行までxx秒待機させるなどの命令）
(3) システムコールを使う理由
システムコールを使う2つの理由としてハードウェアを操作するためのシンプルなインターフェースを使える
OSのリソースの保護
があります。
理由その1
ハードウェアを操作するためのシンプルなインターフェースを使えることで、プログラムを書く人はハードウェアの詳しい知識なしにシステムコールを使うことができます。
理由その2
ファイル操作やメモリ割り当てなどの操作は、失敗すると他のプロセス、さらにはOSまで影響が出てしまうことがあります。
そこでシステムコールを使うことにより、ファイル操作やメモリ割り当てなどの操作を安全に（OSを保護しながら）実現することができます。
(3) システムコールと割り込み
システムコールでは、「ファイル操作」や「メモリ割り当て」などの特殊な命令を行うこともあるため、非特権モードではシステムコールが実行できません。
そのため、割り込みを行い、非特権モードから特権モードに変更してからシステムコールが実行されます。
C言語
// 標準入力から配列データを読み込もう #include <stdio.h> #define N 20
int main(void)
{
char buf[100];
int n;
fgets(buf, sizeof(buf), stdin);
sscanf(buf, "%d", &n);
printf("データの個数：%d\n", n);
int data[N];
for (int i = 0; i < n; i++) {
int x;
fgets(buf, sizeof(buf), stdin);
sscanf(buf, "%d", &x);
data[i] = x;
}
for (int i = 0; i < n; i++) {
printf("%d\n", data[i]);
}
}
情報数学
集合
𝜙 は空集合なので要素を1つも持たない。よって 𝜙 も要素に持たず、𝜙∈𝜙 は誤りであることがわかる。
また、空集合はすべての要素の部分集合なので、𝜙⊆𝜙 は成立する。
よって答えは 𝜙⊆𝜙 となる。
𝜙には要素は存在しない。（箱の中身：空）
{𝜙} の要素は空集合である。（箱の中身：空の箱）
よって、𝜙∪{𝜙}={𝜙} となる。（中身：空の箱）
また、{1,𝜙,{𝜙}} の要素は1と空集合と空集合からなる集合である。
（中身：1、空の箱、空の箱が入っている箱の3つ）
「空の箱」と「1、空の箱、空の箱が入っている箱」の共通している箱の中身は「空の箱」となる。
よって、 {𝜙}∩{1,𝜙,{𝜙}}={𝜙} となる。
写像 𝑓 が全射・単射のどちらかでも満たしていない場合、逆写像 𝑓−1 が存在しない理由を簡単に説明したいと思います。
(1) 全射でない場合は、𝐵 側に矢印が向けられていない要素がある。逆写像の場合、矢印の向きが逆になるのでスタート地点に矢印がない要素が存在することになるので逆写像は存在しなくなる。
(2) 単射ではない場合、𝐵 側の要素に 𝐴 からの矢印が2箇所以上指されている要素がある。しかし逆写像の場合、矢印の向きは逆になるので2箇所以上の要素から矢印が出ることになり、これもおかしい。
この2つの理由から、写像 𝑓 は全単射の場合のみ逆写像 𝑓−1 は存在するといえます。
ちなみに合成写像 𝑔∘𝑓 の逆写像は 𝑓−1∘𝑔−1 となります。順番も変わるので要注意です。
例題3（証明）
集合 𝑋,𝑌,𝑍 に対して、写像 𝑓:𝑋→𝑌 、𝑔:𝑌→𝑍 と合成写像 𝑔∘𝑓 とする。このとき、つぎの(1)～(4)を証明しなさい。
(1) 写像 𝑓,𝑔 がともに全射ならば合成写像 𝑔∘𝑓 も全射である
(2) 写像 𝑓,𝑔 がともに単射ならば合成写像 𝑔∘𝑓 も単射である
(3) 合成写像 𝑔∘𝑓 が全射ならば写像 𝑔 も全射である
(4) 合成写像 𝑔∘𝑓 が単射ならば写像 𝑓 も単射である
ヒント：定義を使いましょう。
全射の定義
∀𝑏∈𝐵,∃𝑎∈𝐴 s.t. 𝑓(𝑎)=𝑏
単射の定義
(∀𝑎1,𝑎2∈𝐴)𝑎1≠𝑎2 ⟹ 𝑓(𝑎1)≠𝑓(𝑎2)
(∀𝑎1,𝑎2∈𝐴)𝑓(𝑎1)=𝑓(𝑎2) ⟹ 𝑎1=𝑎2
解説3
(1)
すべての 𝑧 に対して、𝑧=𝑔(𝑓(𝑥)) を満たすような 𝑥 が存在することを示せばよい。
𝑔 が全射であるので、すべての 𝑧∈𝑍 に対して、𝑧=𝑔(𝑦) となるような 𝑦 が存在する。
また、𝑦 が全射であるので、すべての 𝑦∈𝑍 に対して、𝑦=𝑓(𝑥) となるような 𝑥 が存在する。
よって、𝑧=𝑔(𝑦)=𝑔(𝑓(𝑥)) を満たせるので合成写像 𝑔∘𝑓 も全射であることが示された。
(2)
𝑥1,𝑥2∈𝑋 とする。
𝑥1≠𝑥2 ならば 𝑔(𝑓(𝑥1))≠𝑔(𝑓(𝑥2)) となることを示せばよい。
𝑓 は単射かつ 𝑥1≠𝑥2 なので 𝑓(𝑥1)≠𝑓(𝑥2) となる。
𝑔 も同様に、単射かつ 𝑓(𝑥1)≠𝑓(𝑥2) なので 𝑔(𝑓(𝑥1))≠𝑔(𝑓(𝑥2)) となる。
よって、合成写像 𝑔∘𝑓 も単射であることが示された。
(3)
合成写像 𝑔∘𝑓 が全射なので、すべての 𝑧 に対して、 𝑧=𝑔∘𝑓(𝑥) を満たすような 𝑥∈𝑋 が存在する。𝑦𝑖𝑛𝑌 となるように 𝑦=𝑓(𝑥) とおくと、𝑧=𝑔∘𝑓(𝑥)=𝑔(𝑓(𝑥))=𝑔(𝑦) と変形できる。
よって任意の 𝑧 に対して 𝑔 の像（終域）となるので題意が満たされた。
(4)
(2) と違って対偶を使うパターン。
𝑥1,𝑥2∈𝑋 とする。
𝑓(𝑥1)=𝑓(𝑥2) ならば 𝑥1=𝑥2 となることを示せばよい。
𝑓(𝑥1)=𝑓(𝑥2) なので、𝑔∘𝑓(𝑥1)=𝑔(𝑓(𝑥1))=𝑔(𝑓(𝑥2))=𝑔∘𝑓(𝑥2) と変形できる。ここで合成写像 𝑔∘𝑓 は単射なので 𝑥1=𝑥2 となり、題意は示された。
解答には東北大学のこちらのPDFを参考にさせていただきました。
練習3
集合 𝑆 を 𝑆={1,2,3,…,𝑛} とする。（問題1,2と同じ条件）
(1) 集合 {𝑎,𝑏,𝑐} から集合 𝑆 への全域関数は何個？
(2) 集合 𝑆 から集合 {𝑎,𝑏,𝑐} への部分関数は何個？
(3) 集合 𝑆 から集合 𝑆 への1対1対応（全単射）は何個？
(4) 集合 𝑆 からべき集合 2𝑆 への全域関数は何個？
(5) 直積集合 𝑆×𝑆 から集合 {1,2} へのうち、全射であるものは何個？
(6) 𝑆 から 𝑆 への関数 𝑓 で、𝑓(1)=1 かつ 𝑓(2)=2 を満たすのは全部で何個？
(7) 𝑆 から 𝑆 への関数 𝑓 で、任意の 𝑘∈𝑆 に対し、𝑓(𝑘)≦𝑘 を満たすものは全部で何個？
解説3
第6羽にある例題や練習問題と同じ問題を一部出しています。同じ問題の場合は解説を省略しています。解説がみたい人はこちらから飛んでください。
(1) 3つそれぞれの要素に 𝑛 通りの関係がある。つまり、𝑛⋅𝑛⋅𝑛=𝑛3 となり、𝑛3 個となる。
(2) (1)の逆パターン、さらに全域関数ではなく部分関数であることに要注意。
𝑛 個それぞれの要素に、𝑎,𝑏,𝑐 と未定義 𝐾 と合計4パターンの関係がある。つまり、4を𝑛 回掛けた個数だけ存在する。よって答えは 4𝑛 個。
(3) 𝑛! 個
(4) 𝑛 個の要素に対し、2のべき乗の要素数である 2𝑛 パターンの関係がある。よって ((2𝑛)𝑛=2𝑛2 個存在する。
(5) 直積集合 𝑆×𝑆 の要素数は 𝑛2 個あります。
𝑛2 個の要素に、1か2の2通りの関係がある。つまり、𝑆×𝑆 から集合 1,2 への関数の数は 2𝑛2 個ある。
つぎに前者について考えます。全射であるということは、「対応先の要素に矢印が向けられていない状態」にならないようにしないといけません。そのような場合は、
(i) すべての要素が 𝑎 に対応付けられている
(ii) すべての要素が 𝑏 に対応付けられている
この2パターン以外です。よって答えは 2𝑛2−2 個です。
(6) 𝑓(1)=1, 𝑓(2)=2 が確定しているため、この2つについては何も考える必要がありません。残りの 𝑛−2 個の要素に対して 𝑛 パターンの関係があるため、答えは 𝑛𝑛−2 個となります。
(7) 𝑓(1) の場合は、1通りのパターン、𝑓(2) の場合は2通りのパターン、3パターン、4パターン、… 𝑛 パターンとパターン数が増えていく。これらのパターンの積が条件を満たす個数となるので答えは 𝑛! 個。
過去問
r5は計算可能性、r4はオーダー記法
双方、コンピュータ科学で直感的に語られているものの数学的な意味を把握しないがち
→計算複雑性理論を抑えるべき？
・計算量→r4
・決定問題→r5
・計算資源
・複雑性クラス
→予想：複雑性クラスが出るのでは
実際、クラスNP完全の中の充足可能性はr3
ハミルトン閉路問題？ 線形不等式の判定（整数）？ 頂点クリーク問題？ 頂点彩色問題？
巡回セールスマン問題が解けたら、ハミルトン閉路の存在も確認(NP完全)できる→NP完全を含む問題なので、巡回セールスマン問題はNP困難
あるいは、集合論の基礎が出る？
組み合わせ？（C、Pの定義とか？ 多数決関数とかアッカーマン関数？ 鳩ノ巣原理？）
または、数理論理学に戻る？
彩色問題（n色を使って塗り分けできる？(Yes/No)、点彩色問題
ぷよぷよ（ぷよの組を与えたときにn連鎖以上組める？(Yes/No)
部分和問題 (整数の組からいくつか抜き取ってnを作れる？(Yes/No)
テトリス（テトリスの組を与えたときにn列以上消せる？(Yes/No)
時間割問題
頂点被覆問題
ナップサック問題
https://www.akita-pu.ac.jp/system/elect/ins/kusakari/japanese/teaching/InfoMath/2007/note/9.pdf
ありそうなのは部分和問題かなぁ
http://www.iee.e.titech.ac.jp/~shioura/teaching/ad10/ad10-09.pdf
決定問題(Yes/Noで答えられる問題)
以下は充足可能性とかも詳しい
ファジィ論理も要確認
その他の予想
ブール代数の基本概念：
ブール代数の公理、ブール関数、真理値表、基本演算（AND、OR、NOT）について。
ブール関数の簡約化（カルノー図を含む）。
https://www.ritsumei.ac.jp/ocw/se/2006-52509/lecture_doc/2006-52509-06.pdf
集合論の基礎：
集合の定義、部分集合、交差・和・補集合の操作。
ベン図による集合の視覚的表現。
https://www.math.is.tohoku.ac.jp/~obata/student/subject/file/2018-3_shugo-enzan.pdf
関数と写像：
関数の定義、合成関数、逆関数。
単射、全射、全単射の定義と例。
数理論理学：
二項関係
数論の基礎：
整数の性質、ユークリッドの互除法、最大公約数と最小公倍数。
素因数分解の一意性。
プログラミング・漸化式
情報数学
編入数学過去問対策
y=0より、x=0。よって固有ベクトルc(1, 1)^Tを持たない
x,yは何でもよくなっちゃう
３枚目の右上の⇔が成立することを示す。⇒は、k_1=1, k_2=0でf(vec_v_1)がWに含まれることが分かる、k_1=0, k_2=1でも同様。⇐は、前提が成り立てばWはベクトル空間なので、ベクトル空間の定義から、任意の線形結合がWに入っていることになる。
その後、(2)のp, q, rに代入すればよい。
過去問(T大含む)
この記事が気に入ったらサポートをしてみませんか？