概要 クラスPとは、決定性チューリングマシンにおいて、多項式時間で判定可能な問題のクラスであり、クラスNPは、Yesとなる証拠（Witnessという）が与えられたとき、多項式時間でWitnessの正当性の判定（これを検証という）が可能な問題のクラスである。多項式時間で判定可能な問題は、多項式時間で検証可能であるので、P⊆NPであることは明らかであるが、PがNPの真部分集合であるか否かについては明確ではない。証明はまだないが、多くの研究者はP≠NPだと信じている。そして、このクラスPとクラスNPが等しくないという予想を「P≠NP予想」という。 参考サイト : https://daigakudenki.com/np-hard/
以下は、指定された範囲内の素数を生成するシンプルなC言語のコードです。この例では、1からnまでの素数を列挙します。 #include <stdio.h>#include <stdbool.h> bool isPrime(int num) { if (num <= 1) return false; if (num <= 3) return true; if (num % 2 == 0 || num % 3 == 0) return false; for (int i = 5; i * i <= num; i += 6) { if (num % i == 0 || num % (i + 2) == 0) return false; } return true; } void printPrimes(int n) { printf("2 "); for (int i = 3; i <= n; i += 2) { if (isPrime(i)) { printf("%d ", i); } } printf("\n"); } int main() { int n; printf("素数を生成する範囲の最大値を入力してください: "); scanf("%d", &n); printf("1から%dまでの素数は以下の通りです:\n", n); printPrimes(n); return 0; } このコードは以下のように動作します：...
モンティ・ホール問題とは モンティ・ホール問題とは、アメリカのテレビ番組「Let’s Make a Deal」で行われていたゲームの一つで、以下のような問題です。 前提条件：3つのドアのうち1つに賞品が入っており、残りの2つにはハズレが入っている。 参加者は3つのドアのうち1つを選びます。 司会者は、参加者が選んだドア以外の2つのドアのうち、ハズレの1つのドアを開けます。 参加者には、選んだドアを変更するかどうかを尋ねます。 このとき、参加者はドアを変更するほうがよいか、変更しないほうがよいかを考える問題です。 解法 モンティ・ホール問題の解法は、以下のようになります。 参加者が最初に選んだドアを変更しない場合 当たりの確率：1/3 外れの確率：2/3 司会者がハズレのドアを開けた後 変更しない場合、当たりの確率：1/3 (1.の当たりの確率から変わらない) 変更する場合、当たりの確率：2/3 (1.の当たり以外の確率) したがって、参加者がドアを変更するほうが当たりの確率が高くなります。 参考 Wikipedia Monty Hall problem
数学の未解決問題 数学の未解決問題について説明します。問題自体はシンプルでも、証明されていない問題がまだまだたくさんあります。 完全数は無数にあるか？ 完全数とは、自分自身を除く正の約数の和が自分自身に等しい自然数です。 例えば、 6は約数は1,2,3となり、1+2+3=6なので完全数です。 28は約数は1,2,4,7,14となり、1+2+4+7+14=28なので完全数です。 現在51個しか発見されていませんが、無数にあると予想されていまが、 まだ、証明されていません。 ゴールドバッハの予想 ゴールドバッハの予想は、すべての2よりも大きな偶数は2つの素数の和として表すことができるという予想です。 （ここで素数とは、1と自分自身以外の約数を持たない自然数です。） 例えば、 4=2+2 6=3+3 8=3+5 10=3+7=5+5 問題自体は非常にシンプルですが、未だに証明されていません。 リーマン予想 リーマンゼータ関数の零点が、負の偶数と、実部が 1 / 2 の複素数に限られるという予想である。 リーマンゼータ関数は、$s$を複素数、$n$を自然数とするとき、 $$\zeta(s):=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=1+{\frac {1}{2^{s}}}+{\frac {1}{3^{s}}}+{\frac {1}{4^{s}}}+\cdots$$ で定義される関数$\zeta$のことをいう。
古代ギリシアの三大作図問題 円が与えられたとき、その円と同じ面積をもつ正方形を作る（円の方形化問題） 任意の角が指定されたとき、それを三等分する（角の三等分問題） 立方体が与えられたとき、その二倍の体積をもつ立方体を作る（立方体の倍積問題） アルキメデスの螺旋 平面上で、半直線OBを定点Oの周りに一様な速さで回転させます。初めの位置をOAとすると、 OAから動き始めると同時に点PがOから出発し、OBに沿って一定の速さで動くとき、点Pが描く 線がアルキメデスの螺旋です。 パップスの定理 サイクロイド ニコメデスのコンコイド ディオクレスのシソイド フェルマの接線法 デカルトの法線法 年表 年 出来事 紀元前3400頃 シュメール人が粘土製の代用硬貨で勘定を行う 紀元前3000年頃 エジプトでヒエログリフの数学が登場 紀元前2800年頃 インダス文明で１０進法に則った度量衡が使われる 紀元前2700年頃 エジプト人がロープとピタゴラス数を使って角度を確認 紀元前2500年頃 計算に使う道具、アバカスが発見される 紀元前2500年頃 参考 数学の歴史
エラトステネスの篩とは エラトステネスの篩とは、ある数以下の素数を列挙するアルゴリズムです。 アルゴリズムは単純で、以下の手順で実装できます。 Nの要素をもつbool値配列を作成し、全要素をtrueで初期化する 配列の0番目と1番目の要素をfalseにする(0と1は素数ではないため) 配列の2番目の要素がtrueなら、2を素数として出力する 配列の$2^2$以上の2の倍数番目の要素をすべてfalseにする※ 配列の3番目の要素がtrueなら、3を素数として出力する 配列の$3^2$以上の3の倍数番目の要素をすべてfalseにする 4番目、5番目、・・・、N番目の要素について、同様の処理を繰り返す ※2乗以上の要素をfalseの対象としているのは、2乗より小さい数についてはすでに処理済み(列挙が完了している)であるためです。 Rustでの実装 fn main() { let n = 1000; let mut is_prime = vec![true; n+1]; is_prime[0] = false; is_prime[1] = false; for i in 2..=n { if is_prime[i] { println!("{}", i); let mut j = i * i; while j <= n { is_prime[j] = false; j += i; } } } } 少し高速化版 下記の点を考慮して、少し高速化した実装を行います。 配列の初期化をtrueで初期化するのではなく、falseで初期化する（このほうが高速） 2の倍数は素数ではないので、2の倍数の要素をfalseにする処理を省略 nまでループする必要はなく、nの平方根までの素数を列挙すれば、n以下の素数を列挙できる fn main() { let n = 1000; let mut is_prime = vec!...
必要なもの Google アカウント 手順 https://colab.research.google.com/ にアクセス 「ファイル」→「ノートブックを新規作成」を選択 下記のコードを貼り付けて実行 import matplotlib.pyplot as plt import numpy as np x = np.linspace(0, 2*np.pi, 500) plt.plot(x, np.sin(x), label="sin curve") plt.plot(x, np.cos(x), label="cos curve") plt.legend() # 凡例の表示 plt.show() 実行結果 参考 matplotlib.pyplot — Matplotlib 3.5.3 documentation
KaTeXとは KaTeXは、LaTeX風の数式をHTMLで表示するためのjavascriptライブラリです。 具体的には下記のような数式を表示することができます。 $$f(x) = x^2 + x + 41$$ 他にもLaTeX風な数式表示ライブラリもあるようですが、KaTeXはシンプルで高速と定評があるようです。 hugoへの導入方法 hugoのフォルダ階層でlayouts/partials/math.htmlを新規作成します。 中身は下記の通りにしてください。 <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.16.4/dist/katex.min.css" integrity="sha384-vKruj+a13U8yHIkAyGgK1J3ArTLzrFGBbBc0tDp4ad/EyewESeXE/Iv67Aj8gKZ0" crossorigin="anonymous"> <script defer src="https://cdn.jsdelivr.net/npm/katex@0.16.4/dist/katex.min.js" integrity="sha384-PwRUT/YqbnEjkZO0zZxNqcxACrXe+j766U2amXcgMg5457rve2Y7I6ZJSm2A0mS4" crossorigin="anonymous"></script> <script defer src="https://cdn.jsdelivr.net/npm/katex@0.16.4/dist/contrib/auto-render.min.js" integrity="sha384-+VBxd3r6XgURycqtZ117nYw44OOcIax56Z4dCRWbxyPt0Koah1uHoK0o4+/RRE05" crossorigin="anonymous"></script> <script> document.addEventListener("DOMContentLoaded", function() { renderMathInElement( document.body, { delimiters: [ {left: "$$", right: "$$", display: true}, {left: "\\[", right: "\\]", display: true}, {left: "$", right: "$", display: false}, {left: "\\(", right: "\\)", display: false} ] }); }); </script> 次に既存のファイルlayouts/partials/extend_head.htmlに下記のコードを追加します。 {{ if or ....
