ロゴ
ユニオンペディア
コミュニケーション
Google Play で手に入れよう
新しい! あなたのAndroid™デバイスでユニオンペディアをダウンロードしてください!
ダウンロード
ブラウザよりも高速アクセス!
 

ランダウの記号

+ コンセプトを保存する

ランダウの記号(ランダウのきごう、Landau symbol)は、関数の極限における値の変化度合いに、おおよその評価を与えるための記法である。 ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O (オーもしくはオミクロン Ο。数字の0ではない)を用いることから(ランダウの)O-記法、ランダウのオミクロンなどともいう。 記号 O は「程度」の意味のオーダー(Order)から。 なおここでいうランダウはエドムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。 ランダウの記号は数学や計算機科学をはじめとした様々な分野で用いられる。.

56 関係: AKS素数判定法力まかせ探索同値関係多項式多項式時間定数時間対数巡回セールスマン問題一次関数二分探索位相群微分ノルム線型空間バブルソートユニフィケーションリーマン予想レフ・ランダウロナルド・リベストワーシャル–フロイド法ヒープソートビットテイラー展開ドナルド・クヌースアルゴリズム解析アッカーマン関数イプシロン-デルタ論法エトムント・ランダウクイックソートゴッドフレイ・ハロルド・ハーディジョン・エデンサー・リトルウッド因数分解固有値理論物理学教程積分変換素集合データ構造素数素数定理階乗計算複雑性理論計算機科学高速フーリエ変換論理式関数 (数学)離散フーリエ変換離散ウェーブレット変換逆写像ΟKd木NP完全問題暗号理論...極限正方行列漸近展開挿入ソート有向点族数学 インデックスを展開 (6 もっと) »

AKS素数判定法

AKS素数判定法(-そすうはんていほう)は、与えられた自然数が素数であるかどうかを決定的多項式時間で判定できる、世界初のアルゴリズムである。ここで、素数判定法が多項式時間であるとは、与えられた自然数 n が素数であるかどうかを判定するのにかかる時間が\log(n) の多項式を上界とすることをいう。n の多項式ではないことに注意する必要がある。 AKS素数判定法は2002年8月6日に "PRIMES is in P" と題された論文で発表された。Agrawal-Kayal-Saxena 素数判定法としても知られ、論文の著者であるインド工科大学のマニンドラ・アグラワル教授と、2人の学生ニラジュ・カヤル、ナイティン・サクセナ(Nitin Saxena)の3人の名前から付けられた。 この素数判定法が発見される以前にも、素数の判定方法は多数知られていたが、リーマン予想などの仮説を用いずに、決定的多項式時間で判定できるアルゴリズムは存在しなかった。 素数判定という重要な問題が実際にクラスPに属することを示した点で理論的には大躍進であった。しかし実用的には、多項式の次数が高すぎるので、今まで判定できなかった素数を高速に判定できるようになったわけではない(まだ「一般数体ふるい法」で因数分解した方がよい)。.

新しい!!: ランダウの記号とAKS素数判定法 · 続きを見る »

力まかせ探索

力まかせ探索(ちからまかせたんさく、Brute-force search)またはしらみつぶし探索(Exhaustive search)は、単純だが非常に汎用的な計算機科学の問題解決法であり、全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法である。 バックトラッキングと混同されやすいが、バックトラッキングでは解候補の大部分を明示的に探索することなく捨てることができる。例えば、エイト・クイーンは、8個のクイーンをチェスボード上で互いに取り合えない状態で配置するものである。力まかせ探索では 64! / 56!.

新しい!!: ランダウの記号と力まかせ探索 · 続きを見る »

同値関係

数学において、同値関係(どうちかんけい、equivalence relation)は反射的、対称的かつ推移的な二項関係を言う。これらの性質の帰結として、与えられた集合において、一つの同値関係はその集合を同値類に分割(類別)する。 同値関係にあることを表す記法は文献によって様々に用いられるけれども、与えられた集合上の同値関係 に関して二元 が同値であることを "" や "" で表すのがもっともよく用いられる記法である。 に関して同値であることを明示する場合には、"" や "" あるいは "" などと書かれる。.

新しい!!: ランダウの記号と同値関係 · 続きを見る »

多項式

数学における多項式(たこうしき、poly­nomial)は、多数を意味するpoly- と部分を意味する -nomen あるいは nomós を併せた語で、定数および不定元(略式ではしばしば変数と呼ぶ)の和と積のみからなり、代数学の重要な対象となる数学的対象である。歴史的にも現代代数学の成立に大きな役割を果たした。 不定元がひとつの多項式は、一元多項式あるいは一変数多項式 と呼ばれ、不定元を とすれば のような形をしている。各部分 "", "", "", "" のことを項(こう、)と呼ぶ。一つの項だけからできている式を単項式 (monomial)、同様に二項式 (binomial)、三項式 (trinomial) などが、-nomial にラテン配分数詞を付けて呼ばれる。すなわち、多項式とは「多数」の「項」を持つものである。単項式の語が頻出であることに比べれば、二項式の語の使用はやや稀、三項式あるいはそれ以上の項数に対する語の使用はごく稀で一口に多項式として扱う傾向があり、それゆえ単項式のみ多項式から排他的に分類するものもある。また多項式のことを整式 (integral expression) と呼ぶ流儀もある。 多項式同士の等式として与えられる方程式は多項式方程式と呼ばれ、特に有理数係数の場合において代数方程式という。多項式方程式は多項式函数の零点を記述するものである。 不定元がふたつならば二元 (bivariate), 三つならば三元 (trivariate) というように異なるアリティを持つ多元多項式が同様に定義できる。算術あるいは初等代数学において、数の計算の抽象化として実数(あるいは必要に応じてより狭く有理数、整数、自然数)を代表する記号としての「文字」変数を伴う「」およびその計算を扱うが、それは大抵の場合多変数の多項式である。 本項では主として一元多項式を扱い、多元の場合にも多少触れるが、詳細は多元多項式の項へ譲る。.

新しい!!: ランダウの記号と多項式 · 続きを見る »

多項式時間

多項式時間(たこうしきじかん)とは計算理論において多項式で表される計算時間。 多項式時間のアルゴリズムとは、解くべき問題の入力サイズnに対して、処理時間の上界としてnの多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。 たとえばバブルソートの処理時間は要素数nに対して要素の比較・交換を行う回数は高々 \frac n(n-1) である。したがって、この場合の最悪計算量のオーダーは''O''記法を用いてO()と表される。 またクイックソートの期待計算量のオーダーはO(n \log n)、最悪計算量のオーダーはO()である。.

新しい!!: ランダウの記号と多項式時間 · 続きを見る »

定数時間

定数時間(ていすうじかん、Constant time)は、計算複雑性理論における用語で、問題の計算にかかる時間が入力として与えられるデータの大きさに依存せず一定であることを指す。O(1) で表される。 例えば、配列のひとつの要素にアクセスするのにかかる時間は、その場所を指定する1つの命令(操作)だけでよいため、一般に定数時間である。しかし、ソートされていない配列から最小の要素を探す問題は定数時間ではなく、検索にそれなりの時間を要する。アルゴリズム(選択アルゴリズム)を工夫しない場合、その処理には線形時間すなわち O(n) の時間を要する。要素数が既知で変化しないなら、アルゴリズムによっては定数時間となるものもある。.

新しい!!: ランダウの記号と定数時間 · 続きを見る »

対数

対数(たいすう、logarithm)とは、ある数 を数 の冪乗 として表した場合の冪指数 である。この は「底を とする の対数(x to base; base logarithm of )」と呼ばれ、通常は と書き表される。また、対数 に対する は(しんすう、antilogarithm)と呼ばれる。数 に対応する対数を与える関数を考えることができ、そのような関数を対数関数と呼ぶ。対数関数は通常 と表される。 通常の対数 は真数, 底 を実数として定義されるが、実数の対数からの類推により、複素数や行列などの様々な数に対してその対数が定義されている。 実数の対数 は、底 が でない正数であり、真数 が正数である場合この条件は真数条件と呼ばれる。 について定義される。 これらの条件を満たす対数は、ある と の組に対してただ一つに定まる。 実数の対数関数 はb に対する指数関数 の逆関数である。この性質はしばしば対数関数の定義として用いられるが、歴史的には対数の出現の方が指数関数よりも先であるネイピア数 のヤコブ・ベルヌーイによる発見が1683年であり、指数関数の発見もその頃である。詳細は指数関数#歴史と概観や を参照。。 y 軸を漸近線に持つ。.

新しい!!: ランダウの記号と対数 · 続きを見る »

巡回セールスマン問題

巡回セールスマン問題を総当たりで解く場合のイメージ。左側で一つずつ探していき、より効率のいいルートが見つかった場合、右側のグラフが更新される。 巡回セールスマン問題(じゅんかいセールスマンもんだい、traveling salesman problem、TSP)は、都市の集合と各2都市間の移動コスト(たとえば距離)が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路の総移動コストが最小のものを求める(セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める)組合せ最適化問題である。.

新しい!!: ランダウの記号と巡回セールスマン問題 · 続きを見る »

一次関数

y-切片を持つ。 数学、特に初等解析学における(狭義の)一次関数(いちじかんすう、linear function)は、(の)一次()、つまり次数 の多項式が定める関数 をいう。ここで、係数 は に依存しない定数であり、矢印は各値 に対して を対応させる関数であることを意味する。特に解析幾何学において、係数および定義域は実数の範囲で扱われ、その場合一次関数のグラフは平面直線である。 より広義には、係数や定義域として複素数やその他の環を考えたり、多変数の一次多項式函数や、あるいは一次式をベクトル空間や作用を持つ加群の文脈で理解することもある。 一次関数は線型関数( の直訳)やアフィン関数 とも呼ばれ、この場合しばしば定数関数 も含む。ベクトルを変数とする広義の一次関数はアフィン写像と呼ばれ、これはベクトルにベクトルを対応させる写像であるが、ふつう線型写像はその特別な場合 で斉一次函数で与えられる。 以下、解析幾何学における実函数としての一次函数について述べる。.

新しい!!: ランダウの記号と一次関数 · 続きを見る »

二分探索

二分探索(にぶんたんさく、binary search、BS)や二分検索やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。.

新しい!!: ランダウの記号と二分探索 · 続きを見る »

位相群

数学における位相群(いそうぐん、topological group)は、位相の定められた群であって、そのすべての群演算が与えられた位相に関して連続となるという意味において代数構造と位相構造が両立する。したがって位相群に関して、群としての代数的操作を行ったり、位相空間として連続写像について扱ったりすることができる。位相群のは、連続対称性を調べるのに利用でき、例えば物理学などにも多くの応用を持つ。 文献によっては、本項に言うところの位相群を連続群と呼び、単に「位相群」と言えば位相空間として T2(ハウスドルフの分離公理)を満たす連続群すなわちハウスドルフ位相群を意味するものがある。.

新しい!!: ランダウの記号と位相群 · 続きを見る »

年越し

年越し(としこし)は1年の最後の日、グレゴリオ暦で12月31日であり、多くの地域ではシルヴェスターの日と呼ぶ。多くの国で、年越しの夜の会合で多くの人が踊り、食べ、酒を飲んで、新年を迎える花火で祝う。年越しの礼拝に行く人たちもいる。祝祭は通常、深夜0時を過ぎ1月1日(元日)まで続く。キリバスとサモアが最も早く新年を迎える国であり、ハワイ州ホノルルが最後の地域である。.

新しい!!: ランダウの記号と年越し · 続きを見る »

年末年始

年末年始(ねんまつねんし)は、厳密な定義はないが、1年の終わりから翌年の初頭の期間の総称である(具体的な期間は使用する場面によって異なる)。 当項目では日本における年末年始を主題として解説している。.

新しい!!: ランダウの記号と年末年始 · 続きを見る »

クリスマス

リスマス()は、イエス・キリストの降誕(誕生)を祝う祭である(誕生日ではなく降誕を記念する日)『キリスト教大事典 改訂新版』350〜351頁、教文館、1977年 改訂新版第四版。毎年12月25日に祝われるが、正教会のうちユリウス暦を使用するものは、グレゴリオ暦の1月7日に該当する日にクリスマスを祝う()。ただし、キリスト教で最も重要な祭と位置づけられるのはクリスマスではなく、復活祭である正教会の出典:()カトリック教会の出典:(カトリック中央協議会)聖公会の出典:(日本聖公会 東京教区 主教 植田仁太郎)プロテスタントの出典:『キリスト教大事典』910頁、教文館、1973年9月30日 改訂新版第二版。 キリスト教に先立つユダヤ教の暦、ローマ帝国の暦、およびこれらを引き継いだ教会暦では日没を一日の境目としているので、クリスマス・イヴと呼ばれる12月24日夕刻から朝までも、教会暦上はクリスマスと同じ日に数えられる。教会では降誕祭といった表記もある。 一般的年中行事としても楽しまれ、ジングルベルなどのクリスマスソングは多くの人に親しまれている。.

新しい!!: ランダウの記号とクリスマス · 続きを見る »

クリスマス・イヴ

リスマス・イヴ』1904年 - 1905年、 スウェーデン人画家のカール・ラーション(1853年 - 1919年)による水彩画。 クリスマス・イヴ()、クリスマス・イブは、クリスマスの前夜、すなわち12月24日の夜を指す英語の音訳である。「イヴ」() は「(夜、晩)」と同義の古語「」の語末音が消失したものである。 転じて、俗に12月24日全体を指すこともある。日常会話では単に「イヴ」と呼ばれることが多い。.

新しい!!: ランダウの記号とクリスマス・イヴ · 続きを見る »

元日

元日(がんじつ)は年の最初の日。日付はグレゴリオ暦では1月1日(改暦前は旧暦正月一日)。元旦(がんたん)ともいうが、この場合は特にその日の朝を指すこともある日本国語大辞典第二版編集委員会・小学館国語辞典編集部編『日本国語大辞典』第二版、小学館。.

新しい!!: ランダウの記号と元日 · 続きを見る »

微分

数学におけるの微分(びぶん)、微分係数、微分商または導函数(どうかんすう、derivative)は、別の量(独立変数)に依存して決まるある量(函数の値あるいは従属変数)の変化の感度を測るものである。微分は微分積分学の基本的な道具である。例えば、動く物体の位置の時間に関する導函数はその物体の速度であり、これは時間が進んだときその物体の位置がどれほど早く変わるかを測る。 一変数函数の適当に選んだ入力値における微分係数は、その点における函数のグラフの接線の傾きである。これは導函数がその入力値の近くでその函数の最適線型近似を記述するものであることを意味する。そのような理由で、微分係数はしばしば「瞬間の変化率」として記述される。瞬間の変化率は独立変数に依存する従属変数である。 微分はにも拡張できる。この一般化において、導函数はそのグラフが(適当な変換の後)もとの函数のグラフを最適線型近似する線型変換と解釈しなおされる。ヤコビ行列はこの線型変換を独立および従属変数を選ぶことで与えられる基底に関して表現する行列であり、独立変数に関する偏微分を用いて計算することができる。多変数実数値函数に対して、ヤコビ行列は勾配に簡約される。 導函数を求める過程を微分あるいは微分法、微分演算 (differentiation) と言い、その逆の過程(原始函数を求めること)をという。微分積分学の基本定理は反微分が積分と同じであることを主張する。一変数の微分積分学において微分と積分は基本的な操作の二本柱である。.

新しい!!: ランダウの記号と微分 · 続きを見る »

ノルム線型空間

数学におけるノルム線型空間(ノルムせんけいくうかん、normed vector space; ノルム付きベクトル空間、ノルム付き線型空間)または短くノルム空間は、ノルムの定義されたベクトル空間を言う。 各成分が実数の、二次元あるいは三次元のベクトルからなる空間では、直観的にベクトルの「大きさ」(長さ)の概念が定義できる。この直観的アイデアを任意有限次元の実数ベクトル空間 に拡張するのは容易い。ベクトル空間におけるそのようなベクトルの大きさは以下のような性質を持つ.

新しい!!: ランダウの記号とノルム線型空間 · 続きを見る »

バブルソート

バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。(単に交換法と言う場合もある).

新しい!!: ランダウの記号とバブルソート · 続きを見る »

ユニフィケーション

ユニフィケーション(unification)は数理論理学や計算機科学の用語であり、問題を解く際のアルゴリズム的プロセスである。ユニフィケーションは、見た目の異なる2つのが同一または同等であることを示すを求めるのが目的である。ユニフィケーションは自動推論、論理プログラミング、プログラミング言語の型システムの実装などに幅広く用いられている。 なお、ユニフィケーションを単一化あるいは統一化とも呼ぶ。 主なユニフィケーションは数種類ある。等号を持たない論理(理論)において、2つの項が同一であることを示すためのユニフィケーションは統語論的ユニフィケーションと呼ばれる。空でない等号を持つ論理(理論)で2つの項の同等性を示す場合、それを意味論的ユニフィケーションと呼ぶ。置換は順序集合として順序付けられるので、ユニフィケーションは束における結びを求める手続きとして解釈できる。 ユニフィケーションを初めて形式的に研究したのはで、一階述語論理の導出手続きを構築する際に一階のユニフィケーションを基盤として使い、組合せ爆発の原因の1つ(項を例化したものの探索)を排除することで自動推論技術への大きな一歩とした。.

新しい!!: ランダウの記号とユニフィケーション · 続きを見る »

リーマン予想

1.

新しい!!: ランダウの記号とリーマン予想 · 続きを見る »

レフ・ランダウ

レフ・ダヴィドヴィッチ・ランダウ(、1908年1月22日 - 1968年4月1日)はロシアの理論物理学者。絶対零度近くでのヘリウムの理論的研究によってノーベル物理学賞を授与された。エフゲニー・リフシッツとの共著である『理論物理学教程』は、多くの言語に訳され、世界的にも標準的な教科書としてよく知られている。.

新しい!!: ランダウの記号とレフ・ランダウ · 続きを見る »

ロナルド・リベスト

ナルド・リン・リベスト(Ronald Linn Rivest、1947年5月6日 - )は、暗号の研究者。現在はMITの計算機科学の教授で、MITコンピュータ科学・人工知能研究所の所員である。通称はロン・リベスト (Ron Rivest)。アメリカ合衆国選挙支援委員会の技術ガイドライン開発委員会の委員を務めており、Voluntary Voting System Guidelines の起草を助けた, from the National Institute of Standards and Technology。.

新しい!!: ランダウの記号とロナルド・リベスト · 続きを見る »

ワーシャル–フロイド法

ワーシャル–フロイド法(Warshall–Floyd Algorithm)は、重み付き有向グラフの全ペアの最短経路問題を多項式時間で解くアルゴリズムである。名称は考案者であるとロバート・フロイドにちなむ(二人はそれぞれ独立に考案)。フロイドのアルゴリズム、ワーシャルのアルゴリズム、フロイド-ワーシャル法とも呼ばれる。.

新しい!!: ランダウの記号とワーシャル–フロイド法 · 続きを見る »

ヒープソート

ヒープソート (heap sort) とはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムである(ヒープ領域とは無関係であることに注意する)。 アルゴリズムは、以下のように2つの段階から構成される。.

新しい!!: ランダウの記号とヒープソート · 続きを見る »

ビット

ビット (bit, b) は、ほとんどのデジタルコンピュータが扱うデータの最小単位。英語の binary digit (2進数字)の略であり、2進数の1けたのこと。量子情報科学においては古典ビットと呼ばれる。 1ビットを用いて2通りの状態を表現できる(二元符号)。これらの2状態は一般に"0"、"1"と表記される。 情報理論における選択情報およびエントロピーの単位も「ビット」と呼んでいるが、これらの単位は「シャノン」とも呼ばれる(詳細は情報量を参照)。 省略記法として、バイトの略記である大文字の B と区別するために、小文字の b と表記する。.

新しい!!: ランダウの記号とビット · 続きを見る »

テイラー展開

数学において、テイラー級数 (Taylor series) は関数のある一点での導関数たちの値から計算される項の無限和として関数を表したものである。そのような級数を得ることをテイラー展開という。 テイラー級数の概念はスコットランドの数学者ジェームズ・グレゴリーにより定式化され、フォーマルにはイギリスの数学者ブルック・テイラーによって1715年に導入された。0 を中心としたテイラー級数は、マクローリン級数 (Maclaurin series) とも呼ばれる。これはスコットランドの数学者コリン・マクローリンにちなんでおり、彼は18世紀にテイラー級数のこの特別な場合を積極的に活用した。 関数はそのテイラー級数の有限個の項を用いて近似することができる。テイラーの定理はそのような近似による誤差の定量的な評価を与える。テイラー級数の最初のいくつかの項として得られる多項式はと呼ばれる。関数のテイラー級数は、その関数のテイラー多項式で次数を増やした極限が存在すればその極限である。関数はそのテイラー級数がすべての点で収束するときでさえもテイラー級数に等しいとは限らない。開区間(あるいは複素平面の開円板)でテイラー級数に等しい関数はその区間上の解析関数と呼ばれる。.

新しい!!: ランダウの記号とテイラー展開 · 続きを見る »

ドナルド・クヌース

ドナルド・エルビン・クヌース(Donald Ervin Knuth, 1938年1月10日 -)は数学者、計算機科学者。スタンフォード大学名誉教授。 クヌースによるアルゴリズムに関する著作 The Art of Computer Programming のシリーズはプログラミングに携わるものの間では有名である。アルゴリズム解析と呼ばれる分野を開拓し、計算理論の発展に多大な貢献をしている。その過程で漸近記法で計算量を表すことを一般化させた。 理論計算機科学への貢献とは別に、コンピュータによる組版システム TeX とフォント設計システム METAFONT の開発者でもあり、Computer Modern という書体ファミリも開発した。 作家であり学者であるクヌースは、文芸的プログラミングのコンセプトを生み出し、そのためのプログラミングシステム WEB / CWEB を開発。また、MIX / MMIX 命令セットアーキテクチャを設計。.

新しい!!: ランダウの記号とドナルド・クヌース · 続きを見る »

アルゴリズム解析

アルゴリズム解析とは、アルゴリズムの実行に必要とされるリソース(時間や記憶領域)量を見積もることである。多くのアルゴリズムは任意長の入力を受け付けるよう設計されている。アルゴリズムの「効率」や「複雑さ」は一般に、入力長からそのアルゴリズムを実行するのに必要なステップ数(時間複雑性)や記憶領域サイズ(空間複雑性)への関数として表される。 アルゴリズム解析は計算複雑性理論の重要な一分野である。計算複雑性理論では、与えられた計算問題を解くアルゴリズムが必要とするリソースを理論的に見積もる。この見積もりにより効率的なアルゴリズムを設計する指針が得られることがある。 アルゴリズム解析ではふつう、漸近的(asymptotic)な意味で複雑性を見積もる。すなわち、ある程度大きな入力長の際の複雑性関数を見積もる。このためにO記法、Ω記法、Θ記法が用いられる。例えば、二分探索のステップ数は入力サイズの対数に比例し、これを O(log(n)) と表記したり、「対数時間」と称したりする。このような漸近的な見積もりを用いるのは、同じアルゴリズムでも実装の違いにより差が出るのを捨象するためである。異なる妥当な実装による効率の違いは定数倍に留まる。この定数を隠れた定数(hidden constant)と呼ぶ。 漸近的でない正確な効率がわかる場合もあるが、そのためには「計算モデル」と呼ばれるアルゴリズムの特定の実装を仮定する必要がある。計算モデルはチューリング機械のような抽象化された機械を使うか、個々の命令の実行時間が変化しないと仮定することが多い(例えば実際のコンピュータではキャッシュにヒットするかしないかでは大きく実行時間が異なるが、アルゴリズム解析では一般にそれを無視する)。例えば、二分探索で N 個のソートされた数から探索する場合、1回の参照を一定の単位時間でできるとした場合、回答を得るまでに最大で log2 N+1 単位時間を要する。.

新しい!!: ランダウの記号とアルゴリズム解析 · 続きを見る »

アッカーマン関数

アッカーマン関数(アッカーマンかんすう、Ackermann function、Ackermannfunktion)とは、非負整数 m と n に対し、 \end によって定義される関数のことである。 与える数が大きくなると爆発的に計算量が大きくなるという特徴があり、性能測定などに用いられることもある。 また、数学的な意味として、原始再帰関数でないμ再帰関数の実例として有名である。これを(再帰のない手続き型の)プログラミング言語の言葉で言えば、whileループを使えばアッカーマン関数をプログラミングできるが、whileを使わずにforループだけでは実現不能だということである。 なお、アッカーマン関数のグラフは原始再帰的である。.

新しい!!: ランダウの記号とアッカーマン関数 · 続きを見る »

イプシロン-デルタ論法

ε-δ 論法(イプシロンデルタろんぽう、(ε, δ)-definition of limit)は、解析学において、(有限な)実数値のみを用いて極限を議論する方法である。.

新しい!!: ランダウの記号とイプシロン-デルタ論法 · 続きを見る »

エトムント・ランダウ

エトムント・ゲオルク・ヘルマン・ランダウ(Edmund Georg Hermann Landau, 1877年2月14日 - 1938年2月19日)は、ドイツの数学者。主な業績は、解析的整数論におけるもの。ランダウの記号を広めた。 ベルリンの裕福なユダヤ系の家庭に生まれ、ベルリン大学で数学を学ぶ。1901年にベルリン大学で教授資格を得、1908年までここで講師として教えた。1905年にはパウル・エールリヒの娘マリアンネと結婚。 1909年、ヘルマン・ミンコフスキーの後任として、ゲッティンゲン大学に招聘される。ダフィット・ヒルベルト、フェリックス・クラインといった著名な同僚たちと対等な立場で教鞭をとったが、1933年になり、ユダヤ系の出自のためにナチス寄りの学生たちから講義をボイコットされ、1934年には引退を強要されるまでに至った。死の直前まで、散発的ではあるが、ブリュッセルやケンブリッジで教鞭をとっていた。ベルリンにて没。 教科書を数多く執筆。多くは英訳されている。 Category:ドイツの数学者 Category:数論学者 770214 -770214 Category:ゲオルク・アウグスト大学ゲッティンゲンの教員 Category:ユダヤ系ドイツ人 Category:ベルリン出身の人物 Category:1877年生 Category:1938年没 Category:数学に関する記事.

新しい!!: ランダウの記号とエトムント・ランダウ · 続きを見る »

クイックソート

イックソート (quicksort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。 n個のデータをソートする際の最良計算量および平均計算量はO(n\log n)である。他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はO(n^2)である。また数々の変種がある。 安定ソートではない。.

新しい!!: ランダウの記号とクイックソート · 続きを見る »

ゴッドフレイ・ハロルド・ハーディ

ッドフレイ・ハロルド・ハーディ(Godfrey Harold Hardy, 1877年2月7日 - 1947年12月1日)は、イギリスの数学者。.

新しい!!: ランダウの記号とゴッドフレイ・ハロルド・ハーディ · 続きを見る »

ジョン・エデンサー・リトルウッド

ョン・エデンサー・リトルウッド(John Edensor Littlewood, 1885年6月9日 - 1977年9月6日)は、イギリスの数学者。ゴッドフレイ・ハロルド・ハーディとの共同研究でよく知られる。.

新しい!!: ランダウの記号とジョン・エデンサー・リトルウッド · 続きを見る »

因数分解

数学における因数分解(いんすうぶんかい、factorization)は(数、多項式、行列といったような、積の定義される)代数的対象を、(それらを掛け合わせると元に戻る)別の対象、つまり因数 (factor) の積に分解することである。たとえば、15 という数は 3 × 5 という因数の積に分解され、多項式 x2 − 4 は (x − 2)(x + 2) という因数の積に分解される。このようにより単純な対象の積になっている。 因数分解の反対は、因数を掛け合わせてもとの展開された対象を得る過程であるところの、展開である。 因数分解の目的はふつう、何らかのものを(自然数ならば素数、多項式ならば既約多項式といったような)「基本的な構成要素」に帰着させることである。1でない自然数が素数の積で表せることは算術の基本定理で、定数でない一変数複素係数多項式が一次式の積で表せることは代数学の基本定理で保障されている。ヴィエタの公式は多項式の根と係数の関係を記述するものである。 巨大整数の素因数分解は困難な問題で、これを一般に短時間に行う方法は知られていない。この複雑性はRSA暗号のような公開鍵暗号によるセキュリティの信頼性の基礎になっている。 行列も(応用に際して利用しやすい)特別な種類の行列の積に分解することができる。よく用いられるのはたとえば、直交行列やユニタリ行列あるいは三角行列などである。ほかに、QR, LQ, QL, RQ, RZ のような分解が知られる。 他の例としては、写像を特定の性質を持つ写像の合成の形に分解することが挙げられる。たとえば、任意の写像は全射と単射の合成と見ることができる。これはによって一般化される。.

新しい!!: ランダウの記号と因数分解 · 続きを見る »

固有値

線型代数学において、線型変換の特徴を表す指標として固有値 (eigenvalue) や固有ベクトル (eigenvector) がある。この2つの用語を合わせて、固有対 (eigenpair) という。与えられた線型変換の固有値および固有ベクトルを求める問題のことを固有値問題 (eigenvalue problem) という。ヒルベルト空間論において線型作用素 あるいは線型演算子と呼ばれるものは線型変換であり、やはりその固有値や固有ベクトルを考えることができる。固有値という言葉は無限次元ヒルベルト空間論や作用素代数におけるスペクトルの意味でもしばしば使われる。.

新しい!!: ランダウの記号と固有値 · 続きを見る »

新年

新年(しんねん、)は世界各地で使われている暦年の新しい年の始めをいう。学年、会計年度上の新年という場合もある。.

新しい!!: ランダウの記号と新年 · 続きを見る »

理論物理学教程

『理論物理学教程』(りろんぶつりがくきょうてい、Курс теоретической физики; Course of Theoretical Physics)は、レフ・ランダウ、エフゲニー・リフシッツおよびらによる物理学の教科書。『ランダウ=リフシッツの理論物理学教程』とも呼ばれる。様々な言語に翻訳されており、標準的な教科書として使用されている。日本では個々の巻を指して「ランダウの力学」「ランダウの統計」などと称されることが多い。「ランダウの〜」と呼ばれるものの文章を書くことが不得手であったランダウに代わり実際に『教程』を執筆したのはリフシッツである。リフシッツはランダウが交通事故に遭遇した時点で未完だった10巻のうち3巻をピタエフスキーに協力を仰ぎつつ『教程』を完成させた。『教程』が全巻完結した後も最新の知見を盛り込むなど改訂を続け、個々の巻は初期の版に比べ大幅にページ数が増加している。.

新しい!!: ランダウの記号と理論物理学教程 · 続きを見る »

積分変換

数学の分野における積分変換(せきぶんへんかん、)とは、次の形をとるような変換 T のことである: この積分変換の入力は関数 f であり、出力は関数 Tf である。積分変換は作用素の一種である。 多くの便利な積分変換が存在する。個々の積分変換は、その変換の核関数 (kernel function) あるいは核 (kernel, nucleus) と呼ばれる二変数関数 K を定めれば決まる。 いくつかの核関数には逆 K−1(u, t) が存在し、それは(大まかに言えば)次のような逆変換を満たす: このような公式は反転公式と呼ばれる。二変数の順番が変わっても変化しないような核は対称核と呼ばれる。.

新しい!!: ランダウの記号と積分変換 · 続きを見る »

素集合データ構造

素集合データ構造(そしゅうごうデータこうぞう、英: disjoint-set data structure)は、データの集合を素集合(互いにオーバーラップしない集合)に分割して保持するデータ構造。このデータ構造に対する以下の2つの便利な操作をUnion-Findアルゴリズムと呼ぶ。.

新しい!!: ランダウの記号と素集合データ構造 · 続きを見る »

素数

素数(そすう、prime number)とは、 より大きい自然数で、正の約数が と自分自身のみであるもののことである。正の約数の個数が である自然数と言い換えることもできる。 より大きい自然数で素数でないものは合成数と呼ばれる。 一般には、素数は代数体の整数環の素元として定義される(そこでは反数などの同伴なものも素数に含まれる)。このため、有理整数環 \mathbb Z での素数は有理素数(ゆうりそすう、rational prime)と呼ばれることもある。 最小の素数は である。素数は無数に存在する。したがって、素数からなる無限数列が得られる。 素数が無数に存在することは、紀元前3世紀頃のユークリッドの著書『原論』で既に証明されていた。 自然数あるいは実数の中での素数の分布の様子は高度に非自明で、リーマン予想などの現代数学の重要な問題との興味深い結び付きが発見されている。 分散コンピューティング・プロジェクト GIMPS により、史上最大の素数の探求が行われている。2018年1月現在で知られている最大の素数は、2017年12月に発見された、それまでに分かっている中で50番目のメルセンヌ素数 であり、十進法で表記したときの桁数は2324万9425桁に及ぶ。.

新しい!!: ランダウの記号と素数 · 続きを見る »

素数定理

素数定理(そすうていり、、)とは自然数の中に素数がどのくらいの「割合」で含まれているかを述べる定理である。整数論において素数が自然数の中にどのように分布しているのかという問題は基本的な関心事である。しかし、分布を数学的に証明することは極めて難しく、解明されていない部分が多い。この定理はその問題について重要な情報を与える。.

新しい!!: ランダウの記号と素数定理 · 続きを見る »

階乗

数学において非負整数 の階乗(かいじょう、factorial) は、1 から までのすべての整数の積である。例えば、 である。空積の規約のもと と定義する。 階乗は数学の様々な場面に出現するが、特に組合せ論、代数学、解析学などが著しい。階乗の最も基本的な出自は 個の相異なる対象を一列に並べる方法(対象の置換)の総数が 通りであるという事実である。この事実は少なくとも12世紀にはインドの学者によって知られていた。は1677年にへの応用として階乗を記述した。再帰的な手法による記述の後、Stedman は(独自の言葉を用いて)階乗に関しての記述を与えている: 感嘆符(!)を用いた、この "" という表記は1808年にによって発明された。 階乗の定義は、最も重要な性質を残したまま、非整数を引数とする函数に拡張することができる。そうすれば解析学における著しい手法などの進んだ数学を利用できるようになる。.

新しい!!: ランダウの記号と階乗 · 続きを見る »

計算複雑性理論

計算複雑性理論(けいさんふくざつせいりろん、computational complexity theory)とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性(計算問題の困難さ)などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。.

新しい!!: ランダウの記号と計算複雑性理論 · 続きを見る »

計算機科学

計算機科学(けいさんきかがく、computer science、コンピュータ科学)とは、情報と計算の理論的基礎、及びそのコンピュータ上への実装と応用に関する研究分野である。計算機科学には様々な下位領域がある。コンピュータグラフィックスのように特定の処理に集中する領域もあれば、計算理論のように数学的な理論に関する領域もある。またある領域は計算の実装を試みることに集中している。例えば、プログラミング言語理論は計算を記述する手法に関する学問領域であり、プログラミングは特定のプログラミング言語を使って問題を解決する領域である。.

新しい!!: ランダウの記号と計算機科学 · 続きを見る »

高速フーリエ変換

速フーリエ変換(こうそくフーリエへんかん、fast Fourier transform, FFT)は、離散フーリエ変換(discrete Fourier transform, DFT)を計算機上で高速に計算するアルゴリズムである。高速フーリエ変換の逆変換を逆高速フーリエ変換(inverse fast Fourier transform, IFFT)と呼ぶ。.

新しい!!: ランダウの記号と高速フーリエ変換 · 続きを見る »

論理式

論理式.

新しい!!: ランダウの記号と論理式 · 続きを見る »

関数 (数学)

数学における関数(かんすう、、、、、函数とも)とは、かつては、ある変数に依存して決まる値あるいはその対応を表す式の事であった。この言葉はライプニッツによって導入された。その後定義が一般化されて行き、現代的には数の集合に値をとる写像の一種であると理解される。.

新しい!!: ランダウの記号と関数 (数学) · 続きを見る »

離散フーリエ変換

離散フーリエ変換(りさんフーリエへんかん、discrete Fourier transform、DFT)とは離散化されたフーリエ変換であり、信号処理などで離散化されたデジタル信号の周波数解析などによく使われる。また偏微分方程式や畳み込み積分を効率的に計算するためにも使われる。離散フーリエ変換は(計算機上で)高速フーリエ変換(FFT)を使って高速に計算することができる。 離散フーリエ変換とは、複素関数 f(x)を複素関数F(t)に写す写像であって、次の式で定義されるものを言う。 ここで、Nは任意の自然数、 e はネイピア数、i は虚数単位 (i^2.

新しい!!: ランダウの記号と離散フーリエ変換 · 続きを見る »

離散ウェーブレット変換

離散ウェーブレット変換(りさんウェーブレットへんかん、Discrete wavelet transform, DWT)は、数値解析や関数解析において、離散的にサンプリングされたウェーブレットを用いたウェーブレット変換のアルゴリズムである。本来は異なる物だが、多くのソフトウェアでは多重解像度解析の事を離散ウェーブレット変換と呼んでいる。本項では本来の定義の方をふれ、多重解像度解析に関してはそちらの項目を参照。.

新しい!!: ランダウの記号と離散ウェーブレット変換 · 続きを見る »

逆写像

数学における逆写像(ぎゃくしゃぞう、inverse mapping)は一口に言えば写像の与える元の対応関係を「反対」にして得られる写像である。すなわち、写像 が を に写すならば、 の逆写像は を に写し戻す。 函数と呼ばれる種類の写像の逆写像は、逆函数 (inverse function) と呼ばれる。.

新しい!!: ランダウの記号と逆写像 · 続きを見る »

Ο

(オミクロン、希: /, 英: )は、ギリシア文字の第15字母。数価は 70、音価は /o/。ラテンアルファベットのO、キリル文字のОはこの文字に由来する。「オ・ミークロン」とは小さい「O」という意味で、「オメガ」(Ω)と対になる名前である。  数学では、ランダウの記号などに用いられている。またこの一字でギリシャ語の男性主格単数の定冠詞を表す。例)(神).

新しい!!: ランダウの記号とΟ · 続きを見る »

Kd木

3次元の''k''d木。根セル(白)をまず2つの部分セルに分割(赤)し、それぞれをさらに2つに分割(緑)している。最後に4つのセルそれぞれを2つに分割(青)している。それ以上の分割はされていないので、最終的にできた8つのセルを葉セルと呼ぶ。黄色の球は木の頂点を表している。 kd木(kd-tree, k-dimensional tree)は、k次元のユークリッド空間にある点を分類する空間分割データ構造である。kd木は、多次元探索鍵を使った探索(例えば、範囲探索や最近傍探索)などの用途に使われるデータ構造である。kd木はBSP木の特殊ケースである。 kd木は、座標軸の1つに垂直な平面だけを使って分割を行う。BSP木では分割平面の角度は任意である。さらに一般的には、kd木の根ノードから葉ノードまでの各ノードには1つの点が格納される。この点もBSP木とは異なり、BSP木では葉ノードのみが点(または他の幾何学的プリミティブ)を含む。つまり、kd木の各分割平面は必ず1つの点を通る。葉ノードのみがデータを格納する派生データ構造を''k''dトライと呼ぶ。また、特記すべきkd木の別の定義として、各分割平面が1つの点を通るよう決定されるものの、点を葉ノードでのみ記憶するという定義もある。.

新しい!!: ランダウの記号とKd木 · 続きを見る »

NP完全問題

NP完全(な)問題(エヌピーかんぜん(な)もんだい、NP-complete problem)とは、(1) クラスNP(Non-deterministic Polynomial)に属する決定問題(言語)で、かつ (2) 任意のクラスNPに属する問題から多項式時間還元(帰着)可能なもののことである。条件 (2) を満たす場合は、問題の定義が条件 (1) を満たさない場合にも、NP困難な問題とよびその計算量的な困難性を特徴づけている。多項式時間還元の推移性から、クラスNPに属する問題で、ある一つのNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の証明の多くはこの推移性によって充足可能性問題などから導かれている。充足可能性問題がNP完全であることは1971年、スティーブン・クック(Stephen Cook (1971).

新しい!!: ランダウの記号とNP完全問題 · 続きを見る »

暗号理論

暗号理論(あんごうりろん)の記事では暗号、特に暗号学に関係する理論について扱う。:Category:暗号技術も参照。.

新しい!!: ランダウの記号と暗号理論 · 続きを見る »

極限

数学においては、数列など、ある種の数学的対象をひとまとまりに並べて考えたものについての極限(きょくげん、limit)がしばしば考察される。数の列がある値に限りなく近づくとき、その値のことを数列の極限あるいは極限値といい、この数列は収束するという。収束しない場合は、発散するという。 極限を表す記号として、次のような lim (英語:limit, リミット、ラテン語:limes)という記号が一般的に用いられる。.

新しい!!: ランダウの記号と極限 · 続きを見る »

正方行列

正方行列(せいほうぎょうれつ、square matrix)とは、行要素の数と列要素の数が一致する行列である。サイズが n × n つまり、n 行 n 列であるとき、n 次正方行列という。 \end.

新しい!!: ランダウの記号と正方行列 · 続きを見る »

漸近展開

漸近展開(ぜんきんてんかい、Asymptotic expansion)とは、与えられた関数を、より簡単な形をした関数列の級数として近似することをいう。テイラー展開は漸近展開の特別な場合であるが、漸近展開で得られた級数の値は、必ずしも元の関数の値に収束するとは言えない。しかし、関数の性質を調べる際、元の関数の形では扱いが難しい場合、漸近展開によって元の関数を級数の形で近似することにより、関数の性質が得られることがある。漸近展開は解析学では重要な手法の一つであり、確率論の基礎として用いることがある。.

新しい!!: ランダウの記号と漸近展開 · 続きを見る »

挿入ソート

挿入ソート(インサーションソート)は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである。 挿入ソートを高速化したソート法として、シェルソートが知られている。.

新しい!!: ランダウの記号と挿入ソート · 続きを見る »

有向点族

有向点族(ゆうこうてんぞく、directed family of points)とは、点列を一般化した概念で、ムーア (Eliakim Hastings Moore) とスミス (H. L. Smith) により1922年に定義された。有向点族はネット (net)、有向点列、 Moore-Smith 列などとも呼ばれる。 点列との違いは添え字にあり、点列が自然数という可算な全順序集合の元で添え字付けられるのに対し、有向点族はより一般的な順序集合である(可算または非可算な)有向集合の元で添え字付けられている。 有向点族の概念の利点として以下の2つがある:.

新しい!!: ランダウの記号と有向点族 · 続きを見る »

数学

数学(すうがく、μαθηματικά, mathematica, math)は、量(数)、構造、空間、変化について研究する学問である。数学の範囲と定義については、数学者や哲学者の間で様々な見解がある。.

新しい!!: ランダウの記号と数学 · 続きを見る »

2018年

この項目では、国際的な視点に基づいた2018年について記載する。.

新しい!!: ランダウの記号と2018年 · 続きを見る »

2019年

この項目では、国際的な視点に基づいた2019年について記載する。.

新しい!!: ランダウの記号と2019年 · 続きを見る »

ここにリダイレクトされます:

''O''記法O-記法O記法ランダウの記法ランダウ記法オーダー記法オミクロン記法

出ていきます入ってきます
ヘイ!私たちは今、Facebook上です! »