素因数分解の一意性とその証明について | 高校数学の美しい物語
「素数」とは 111 と自分自身以外の約数を持たない数のことです。 素因数分解が可能であることの証明は簡単です。当たり前のことをきちんと書いただけです。 背理法で証明する。素因数分解不可能な正の整数が存在すると仮定する。その最小のものを nnn とする。 素数（および 111 ）はもちろん素因数分解可能なので nnn は素数ではない。 よって，nnn は 111 より大きく nnn より小さい約数を持つ。よって n=abn=abn=ab ( a,ba,ba,b は 111 より大きく nnn より小さい正の整数）と表せる。 最小性の仮定より aaa と bbb は素数の積で表せる。よって nnn も素数の積で表せるので矛盾。
二部グラフの最大マッチングと増加道 | 高校数学の美しい物語
グラフとは，点の集合と枝の集合からなる「つながり方」を表すモデルです。 二部グラフとは，点が 222 グループにわかれていて，同じグループ間はつながっていないようなグラフです。→グラフ理論の基礎
Hallの結婚定理とその証明 | 高校数学の美しい物語
まず，条件1を理解するためにマッチングについて説明します。 （追記：二部グラフの最大マッチングと増加道） マッチングとは端点がかぶらないように辺をいくつか取ってきたものです。また，マッチングの端点に属する頂点を「マッチングでカバーされている」と言います。 例えば，図では緑の辺がマッチングの一例です。頂点集合 UUU の中で上三つはカバーされていますが，一番下はカバーされていません。 VVV は全てカバーされています。 UUU の各頂点を男性，VVV の各頂点を女性，男性 aaa が女性 bbb とお互いに結婚してもよいと思うとき (a,b)(a,b)(a,b) に辺を引いたグラフを考えてみます。このときマッチングは結婚成立の一例を表しています。 すなわち条件1は， 「うまいマッチングを選べば男がみんな結婚できる」という条件になります。 次は条件2について説明します。 UUU の部分集合 A
フランク・モーリーの定理の証明 | 高校数学の美しい物語
QRQRQR の長さを三角形 ABCABCABC の情報（角度，長さ）で表したときに，A,B,CA, B, CA,B,C に関して対称であることを示せれば PQ=QR=RPPQ=QR=RPPQ=QR=RP が言えます。そこで，三角形 ARQARQARQ に余弦定理を使いたくなります。そのためには，AR,AQAR,AQAR,AQ を三角形 ABCABCABC の情報で表す必要があるので，三角形 ARBARBARB に注目します。 また，辺の情報と角度の情報が混在していると複雑になるので，辺の情報は正弦定理で角度の情報に変換します。（外接円の半径 RRR は A,B,CA, B, CA,B,C に関して対称なので扱いやすいです) ARARAR の形を見て三倍角の公式の発展形（因数分解した形）がひらめくとよいです（→三倍角の公式：基礎からおもしろい発展形まで）。ここがこの証明一番の難所です。 三
P≠NP予想の主張の解説 | 高校数学の美しい物語
P≠NP予想は計算量理論の話になります。 問題の集合（クラス）PとNPが等しくないという予想です。 「P」というのは，多項式時間で解ける問題のクラス，つまり「パソコンで解きやすい」問題です。 「NP」というのは，多項式時間で正解が本当に正しいか判定できる問題のクラスです。 もし，P=NPなら今まで解けなかったNPの問題が全て多項式時間で解けるようになってしまうので，そんな都合の良いことはないだろうという予想です。ちなみに，P=NPだと素因数分解の難しさを利用した現代の主要な暗号は破られてしまいます。 Pというのは，入力サイズに対して多項式時間で解ける問題のクラスです。 多項式時間かどうかというのは，四則演算や比較などのコンピュータ上での基本的な演算の回数で見積もります。 コンピュータを用いて指数時間かかってしまうような問題は現実的な時間で解くことができないのです。 例えば，n2n^2n2
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
