13
票
Accepted
数学的帰納法での証明は実際に正しいかどうかはわからない?
数学的帰納法に限らず、一般に、「Aが成り立つと仮定する。このときBが成り立つ。」という論理 (ちゃんとした言葉を使えば命題) の正しさは、実際にAが成り立つ場合があるかどうかには関係ありません。この命題の意味するところは、「Aが成り立てば、必ずBも成り立つよ。Aが成り立たなかった場合のことは何も言っていない (ので、どうなるかわからない) よ。」ということです。
例えば、...
- 5,003
10
票
数学的帰納法での証明は実際に正しいかどうかはわからない?
G(k)が成り立ったからといってG(k+1)が成り立つとは限らない
G(k)が成り立つことを仮定したのでG(k+1)が成り立つ、のではないです。
「G(k)が成り立つという仮定の下G(k+1)が成り立つことを示す」のは、数学的帰納法の方法として証明者に要求されている1ステップです。
G(k+1)が成り立つことが示せなければ、数学的帰納法による証明はできないということになります。
前提として、...
- 1.2万
8
票
数値「1.54991569e+03-9.96587885e+03j」の「-9.96587885e+03j」の「-」と「j」ってなんでしょうか?
これは複素数です。a+bj の形をしていて、j が虚数単位です。1.54991569e+03-9.96587885e+03j は実部が 1.54991569e+03、虚部が -9.96587885e+03 の複素数です。
日本の高校数学などで使われる虚数単位は i で書かれていることが多いですが、分野によっては j が使われます。Python では標準で a+bj ...
- 2.3万
7
票
線形補間をLerpと呼ぶのはなぜ
Jargon Fileに意味用法が載っている
leap(跳ぶ)という一般語の発音に寄せ、「跳ぶ」ことと「二地点間を跳躍して埋める」ことの意味が似ていてイメージがしやすい
という単純な経緯から人口に膾炙して定着したのではないかと推測しています。
※特に後者は完全に私個人の空想です。
en.wikipedia.orgでは "In that field's jargon it is ...
- 1.1万
4
票
Accepted
フィボナッチ数列の計算量について
再帰ありの場合のアルゴリズム fibrecursive(n) の時間計算量が O( ((1 + sqrt(5)) / 2)ⁿ ) というのは正しいです。このアルゴリズムだと O(n) にはなりません。たとえば実際に n を大きくしながらプログラムの実行時間を測れば、O(n) じゃなさそうな結果が出ることでしょう。
質問者さんの間違えていそうな点として、まずはどういう計算に対して「時間 1」...
- 2.3万
4
票
Accepted
多項式と多項式時間の関係がわかりません
いくつかポイントがあるので、分けて説明します。
※より正確には「多項式時間」と呼ぶよりかは「多項式オーダー」とか「クラス P に属する」とか呼んだ方が良いですが、この回答では引用元に合わせて「多項式時間」と呼んでいます。
計算量の比較では関数同士を比べている
計算量の比較をするとき、我々は数学的な関数同士を比べています。たとえば N^2 と 2^N を比べているときには、関数 f(N) = N^2 ...
- 2.3万
4
票
Accepted
微分におけるゲーム数学と数学の違いについて知りたい。
特にゲームを作る上での数学と普通の数学に差があるわけではありません。連続的に変化する値をコンピュータの上で表現するときに近似をしたくなることがあるという話です。
実数 x を与えると実数を返す関数 f について考えましょう。色々な解説で書かれているように、この関数 f を x で微分した関数 f' は、以下の式で定義できます。
ここで、数学的には微分の定義として極限 (lim) ...
- 2.3万
3
票
Accepted
RSA の復号化を中国人剰余定理で高速化する際に、どうしてこれで正しく計算できているのかが分からない
1. C^d ≡ m1 mod p かつ C^d ≡ m2 mod q
まず、 C^d ≡ m1 mod p かつ C^d ≡ m2 mod qを示す。同様の証明となるため、p についてのみ示す。
1.1 C が p の倍数の場合
Cがpの倍数であれば、C^dPもpの倍数であるから、 m1 := C^dP ≡ 0 ≡ C^d mod p
1.2 C が p の倍数ではない場合
p は素数なので、C ...
- 1.6万
3
票
Accepted
float型による誤差に if (f <= 0.0f){ } は影響するのか知りたい 数式
浮動小数点数に関する誤差の扱いは非常にデリケートな問題です。「== 比較をしてはいけない」といった単純なルールで対応しきれるものではなく(実際 == で比較してもいい場合も稀にあります)、毎回ケースごとにどう処理するべきかをいちいち考えて対応しなくてはなりません。今回の場合にどうすればよいかをここで説明します。
今回のコードは2つのベクトルの位置関係で分岐を行うものだと思われます。具体的には、...
- 561
3
票
数式の変形の過程について
とりあえず高校で学んだことが理解出来てると仮定して説明をつくりました。
もし分からないことがあればまた質問してください。
【3/18 19:25追記】
説明の画像における3行目の最初のΣが1からn-1になっていますが0からn-1の間違いですね。申し訳ありません。
【3/20 07:40追記】
2つの質問の後者は恐らくこういうことを質問しているのではないかと想像して回答しました。
...
- 200
3
票
Accepted
pythonによるFFTの実装
すみません
先ほど自力で解決しましつ
バタフライ演算の肝をしらなかったからですね
正解を下にコピーします
(FFT_sort.pyの所は同じなので省略 FFT.pyだけの修正)
import FFT_sort as fs
import numpy as np
from numpy import pi
import matplotlib.pyplot as plt
N = input()...
- 71
3
票
Accepted
Zbuffer法以外の方法でポリゴンの描画順位を決定する方法
下記ページでいろいろな陰面消去法が簡単に解説されています。
メモリが潤沢ではなかった時代は、メモリが必要なZバッファ法よりもスキャンライン法がよく使われていました。
様々なレンダリング方式 < レンダリング < 知っておきたい機能 | Blender入門(2.8版)
- 1,111
2
票
数学的帰納法での証明は実際に正しいかどうかはわからない?
これはあくまでも仮定であり、G(k)が成り立ったからといってG(k+1)が成り立つとは限らないのではないのでしょうか?
その通りです。だからG(k+1)のとき成り立つことを証明しています。
1.G(k)が成り立つならG(k+1)成り立つ
2.G(0)が成り立つ
この2つを証明すると命題が成り立つと証明されます
- 446
2
票
Accepted
c++ cos関数に入れる引数でラジアンと角度について知りたい。
cos(angle) は b/h を返しますとありますが b と h はこの場合の数値?はどうなっているのでしょうか?
ということなので三角比の基本から教えます。fumu 7 さんの直角三角形を利用させていただきます。
余弦 cos の定義は cos(angle) = b/h であるからこの値はただの分数を計算した値です。
ところで「分数の計算」は今まで数えきれないほどしてきたことと思います。...
- 200
2
票
c++ cos関数に入れる引数でラジアンと角度について知りたい。
C++のcos関数の引数には、ラジアンを単位とする角度を与えます。
X度をラジアンに変換する式は、π * (X/180) ですから、45度のcosineを計算する式は、cos(π * 45 / 180)となります。
ですから、 float a = cos(PI / 180 * 45); で求めた aの値が 45度のcosineの値です。
cos(45)は、45度のcosineではなく、...
- 4,235
2
票
O(N/k)をk=1からk=Nまで計算したときの計算量
設問者が提示している級数(の部分和)には名前がついていて調和級数(の部分和)と呼びます。
概略的には積分∫[k=1,N+1]1/kdk = log(N+1) ⋍ logNであること及び級数の部分和がこの積分として近似しうることからオーダーはlogNであると私は理解しています。
より緻密な計算については、以下を参考にされたほうがよろしいと思います。
https://ja.wikipedia....
- 854
2
票
二分探索木の平均の計算量を示す方法について
回答がかなり長くかつ数式を含むものなので回答の PDF を作成しそれへのリンクを貼ります。
参考になれば
回答 PDF へのリンク
https://drive.google.com/open?id=1QHhrCu4-2Sn48rYnyawEruyxINansKCg
正直に申し上げるとこの書籍を読み続ける前に高校の数学の復習(今回は数列分野)...
- 200
2
票
二分探索木の平均の計算量を示す方法について
「解を仮定してその正しさを帰納法で示す方法をとる」という説明が理解できない、より具体的には『帰納法』が何なのかを十分に理解していらっしゃらないのだと思われます。
『1からnまでの自然数の和は(n*(n+1))/2 で求められる』という公式を例にして、帰納法による証明がどんなものか示します。
(自然数というのは、0より大きな整数の事。1,2,3,4,5,....というような数)
この公式が正しい(...
- 4,235
2
票
極座標における点の移動を計算したい
iステップ後の位置をp_iとしてベクトル表示をするとp_i=(sum(r_i*cos(D_i),sum(r_i*sin(D_i)))とかけます. ここでD_iはiステップめの進行方向のx軸からみた角度でとします. D_iはsum(pi-theta_i) とかけます. このp_iを使えばベクトルの長さ s_i は s_i=sqrt(p_i_x**2+p_i_y**2)とかけます. 角度はphi_i=...
- 702
2
票
Accepted
sympyで、円周率(piとmath.pi)の使い方の違いを教えて下さい。
pi は from sympy import * でインポートされたもので、元々は sympy.pi です。円周率を表します。 https://docs.sympy.org/latest/modules/core.html?highlight=pi#pi
math.pi は Python の標準ライブラリの math モジュールで定義されている定数です。...
- 422
2
票
Latexで"含まれる"を表す波括弧を表現するには?
一番簡単なのは、amsmathパッケージのcases環境を使うことだと思われます。
\documentclass{article}
\usepackage{amsmath}
\begin{document}
\begin{equation}
f(x) =
\begin{cases}
x & \text{if $x \ge 0$}, \\
- x & ...
- 426
1
票
2段上がる、3段上がる、5段上がる…というように素数段だけ上がることにするとき、n段の階段を上がる方法は何通りあるでしょうか?
お気づきのように、ある段数の上り方はそれより少ない段数の上り方から計算できます。
ですので、n までの自然数 x について小さい方から順番に、x 段の階段の上り方の数の表を作っていけばいいでしょう。
計算には素数が必要になりますから、同時に x までの素数のリストを作りながら進めます。
素数のリストは最初は空で始めて、もし x が素数なら追加していきます。
N = int(input("...
- 986
1
票
2段上がる、3段上がる、5段上がる…というように素数段だけ上がることにするとき、n段の階段を上がる方法は何通りあるでしょうか?
期待:フィボナッチ数列使えばいけると思った。例えば、11段の上がり方は、(11-1)段、(11-2)、(11-3)、(11-5)、(11-7)、(11-9)、(11-11)段までの上り方の総数の和。
実際:関数定義が禁止だから使えない
一旦、フィボナッチ数列は脇に置いて、DP(Dynamic Programming: 動的計画法)で解いてみます。
## prime numbers
...
- 4,461
1
票
Latexで"含まれる"を表す波括弧を表現するには?
以下ページの一覧にある「{ による場合わけ表示」が当てはまりそうです。
http://www1.kiy.jp/~yoka/LaTeX/latex.html
記述例:
\begin{equation}
f(x)= \left \{
\begin{array}{l}
1 (x=1のとき) \\
0 (x≠1のとき)
\end{array}
\right.
\end{equation}
表示例:
- 2万
1
票
Accepted
200回/1秒の頻度で取得した値を、24回/1秒の頻度のデータに落とすダウンサンプリングをするには
間引くだけで良いなら、high_fpsの回数を回す必要は無いのでは?
間引いて取得するための位置(添え字)は計算で求められるでしょう。
以下でlow_fpsの回数回せば、1秒分の添え字のリストが出来ます。
high_fps = 200.0
low_fps = 24.0
interval = high_fps / low_fps
sample_index = []
for i in range(...
- 1.7万
1
票
200回/1秒の頻度で取得した値を、24回/1秒の頻度のデータに落とすダウンサンプリングをするには
2000 : 24 のような大きな比でのダウンサンプリングであれば、線形補間など考慮する必要がありませんし、基本的な考え方はあなたのやり方であっているように思うのですが、浮動小数点を含む計算や切り捨てが絡んでくると話がややこしくなってきて、どこで差の1が出てくるのか検証するのは大変そうです。
例えば、以下のようにしてみてはどうでしょうか。
high_fps=200
low_fps=24
# ...
- 1.9万
1
票
Accepted
データの特性を判別するプログラムについて
Bの4番目に12を入れているので、それ以降はAとBの値が全く違うものになっています。
A =[ B = [
9.43 8.99
5.04 5
8.86 8
2.48 12
5.27 2.3
5.21 5.2
7.95 4.89
1.96 8.14
1.53 2
3.13] 1.2
2.86]
- 5,137
1
票
数学的帰納法での証明は実際に正しいかどうかはわからない?
G(k) = 0 + 1 + ••• + k = (k*(k+1))/2 [式1] が成り立つと仮定します。
そして、この仮定が成り立てば、
G(k+1) = 0 + 1 + ••• + k + (k+1) = ((k+1)*((k+1)+1))/2 が成り立つことを、証明します。
式1の右辺(((k+1) * ((k+1)+1))/2)は、次のように変形できます。
((k+1) * ((...
- 4,235
1
票
相関行列の計算の流れが理解できない
このソースコードは相関行列を求めているわけではありません。相関行列自体は、np.corrcoef 関数によって最初に求まっています。
相関行列の非対角成分は相異なる 2 つのデータの相関係数ですが、対角成分は必ず 1 になります。「最大相関係数をとるインデックスを取得」の部分では、この対角成分を除いた上で相関係数を最大にするインデックスを求めています。
- 2.3万
1
票
グラフ理論について、三次元空間における位置関係の情報をinvariantに保持する表現を計算したい
質問者様が、今考えているロジックを実装したとしても、「どの座標がどの座標にそれぞれ対応するか」の n! 通りある組み合わせの問題は解決しないのではないかと思っています。(もしかしたら、自分の理解が足りていないだけかもしれませんが、、)
そして、うまい一般的解法が思いつかなかったので、自分だったらこうする、という方針を記述いたします。
今やりたいことは、3次元座標の集合が与えられたときに、...
- 1.6万
Only top scored, non community-wiki answers of a minimum length are eligible