院試対策 メモ
極限
重要公式
$$
\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乗と上は右が-×-で+2なってcos^2+sin^2 = 1
$$
(\frac{1}{tan})' = -\frac{1}{sin^2}
$$
(cos / sin)' を商の微分で下の2乗と上は左が-で右が-(+)で-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 は,まあ無問題.
アキト
微分積分
うさぎでも分かる解析シリーズ
疑問点:
1.置換積分のdxとdtの関係の求め方
2.二重積分のときの空間の分け方→再度Part27を読もう
3.T大R1の冪級数展開とはなんだ→複素解析も読もう
4.H大R4に微分方程式あるぞ→ヨビノリ見よう
補足
微分方程式
ヨビノリ
複素関数論
ヨビノリ
線形代数
線形写像
https://www.momoyama-usagi.com/entry/math-linear-algebra21
応用編
編入数学
1次従属であるための必要十分条件⇔行列式=0
線形計画法
オートマトンと言語理論
ももやまうさぎ塾
補足:
[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部グラフの彩色指数は必ず「最大次数」となる。
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】 命令パイプラインは条件分岐命令があると乱れるが、それを回避する工夫を2つ以上挙げて説明せよ。
【3】 フォンノイマンボトルネックとは何かを説明せよ。またそれを改善するため工夫の例をできるだけ多く挙げよ。
【4】 ノイマン型計算機の主記憶アクセスの 2 種類の局所性について、それぞれ例を挙げて説明せよ。
【5】 メモリインターリーブで一括アクセスを行う場合に、最大の効果が得られるのはどのようなアクセスパターンのときかを述べよ。
また、ほとんど効果が得られないアクセスパターンを挙げ、その理由を述べよ。
【6】 キャッシュメモリにデータを書き込む方法として、write-through 法と write-back 法の違いを述べ、それぞれの利点欠点を説
明せよ。
https://art.ist.hokudai.ac.jp/~horiyama/lecture/ex_csit/ARCex4-Q.pdf
メモリリークとガーベッジコレクション
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
関数と写像:
関数の定義、合成関数、逆関数。
単射、全射、全単射の定義と例。
数理論理学:
二項関係
数論の基礎:
整数の性質、ユークリッドの互除法、最大公約数と最小公倍数。
素因数分解の一意性。
プログラミング・漸化式
情報数学
編入数学過去問対策
過去問(T大含む)
この記事が気に入ったらサポートをしてみませんか?