ブラウザよりも高速アクセス！
25 関係: 多項式時間、実数、ロナルド・リベスト、ロバート・フロイド、ブーリアン型、アルゴリズム、クロード・シャノン、グラフ理論、ジョン・マッカーシー、無限、隣接行列、行列、論理和、論理積、Javaアプレット、Python、推移閉包、正則行列、正規表現、正規言語、木 (数学)、有限オートマトン、最短経路問題、擬似コード、2部グラフ。
多項式時間
多項式時間（たこうしきじかん）とは計算理論において多項式で表される計算時間。 多項式時間のアルゴリズムとは、解くべき問題の入力サイズnに対して、処理時間の上界としてnの多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。 たとえばバブルソートの処理時間は要素数nに対して要素の比較・交換を行う回数は高々 \frac n(n-1) である。したがって、この場合の最悪計算量のオーダーは''O''記法を用いてO()と表される。 またクイックソートの期待計算量のオーダーはO(n \log n)、最悪計算量のオーダーはO()である。.
新しい！!: ワーシャル–フロイド法と多項式時間 · 続きを見る »
実数
数学における実数（じっすう、 nombre réel, reelle Zahl, real number）は、様々な量の連続的な変化を表す数の体系である。実数全体の空間は、途切れのなさにあたる完備性とよばれる位相的な性質を持ち、代数的には加減乗除ができるという体の構造を持っている。幾何学や解析学ではこれらのよい性質を利用して様々な対象が定義され、研究されている。一方でその構成方法に自明でない手続きが含まれるため、実数の空間は数学基礎論の観点からも興味深い性質を持っている。また、自然科学における連続的なものの計測値を表すのに十分な数の体系だとも考えられている。 実数の概念は、その形式的な定義が19世紀に達成される前から数の体系として使われていた。「実数」という名前は複素数の概念が導入された後に「普通の数」を表現する言葉として導入されたものである。.
新しい！!: ワーシャル–フロイド法と実数 · 続きを見る »
ロナルド・リベスト
ナルド・リン・リベスト（Ronald Linn Rivest、1947年5月6日 - ）は、暗号の研究者。現在はMITの計算機科学の教授で、MITコンピュータ科学・人工知能研究所の所員である。通称はロン・リベスト (Ron Rivest)。アメリカ合衆国選挙支援委員会の技術ガイドライン開発委員会の委員を務めており、Voluntary Voting System Guidelines の起草を助けた, from the National Institute of Standards and Technology。.
新しい！!: ワーシャル–フロイド法とロナルド・リベスト · 続きを見る »
ロバート・フロイド
バート・W・フロイド（Robert W. Floyd、1936年6月8日 - 2001年9月25日）は、アメリカ合衆国の計算機科学者。 彼の貢献としてワーシャル-フロイド法の設計がある（とはそれぞれ独立に考案）。これはグラフ理論における最短経路問題の解法のひとつである。また、数列の循環を検出するフロイドの循環検出法があり、これらは構文解析にも利用できる。また、別の論文で彼は画像描画のための誤差拡散に関する重要な概念を提案しており、これがフロイド-スタインバーグ・ディザリングとして知られている（ただしフロイド自身は誤差拡散とディザリングは区別して考えていた）。特に有名な貢献は1967年の論文 Assigning Meanings to Programs（プログラムへの意味の割り当て）である。この中でプログラム検証を数理論理学の手法を使って行うという先駆的な試みがなされている。これは後のホーア論理につながる重要な貢献となった。.
新しい！!: ワーシャル–フロイド法とロバート・フロイド · 続きを見る »
ブーリアン型
ブーリアン型（ブーリアンがた、Boolean datatype）は、真理値の「真.
新しい！!: ワーシャル–フロイド法とブーリアン型 · 続きを見る »
アルゴリズム
フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム（algorithm ）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.
新しい！!: ワーシャル–フロイド法とアルゴリズム · 続きを見る »
クロード・シャノン
ード・エルウッド・シャノン（Claude Elwood Shannon, 1916年4月30日 - 2001年2月24日）はアメリカ合衆国の電気工学者、数学者。20世紀科学史における、最も影響を与えた科学者の一人である。 情報理論の考案者であり、情報理論の父と呼ばれた。情報、通信、暗号、データ圧縮、符号化など今日の情報社会に必須の分野の先駆的研究を残した。アラン・チューリングやジョン・フォン・ノイマンらとともに今日のコンピュータ技術の基礎を作り上げた人物として、しばしば挙げられる。.
新しい！!: ワーシャル–フロイド法とクロード・シャノン · 続きを見る »
グラフ理論
ラフ理論（グラフりろん、graph theory）は、ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフに関する数学の理論である。グラフ (データ構造) などの応用がある。.
新しい！!: ワーシャル–フロイド法とグラフ理論 · 続きを見る »
ジョン・マッカーシー
ョン・マッカーシー（John McCarthy, 1927年9月4日 - 2011年10月24日）は、アメリカ合衆国の計算機科学者で認知科学者。マービン・ミンスキーとならぶ初期の人工知能研究の第一人者。「人工知能; Artificial Intelligence」という用語は彼が1956年のダートマス会議のために1955年に出した提案書で初めて使用された。また、ALGOL言語の設計に触発され、LISPというプログラミング言語を開発し、タイムシェアリングの概念を一般化させた。.
新しい！!: ワーシャル–フロイド法とジョン・マッカーシー · 続きを見る »
無限
無限（むげん、infinity、∞）とは、限りの無いことである。 直感的には「限界を持たない」というだけの単純に理解できそうな概念である一方で、直感的には有限な世界しか知りえないと思われる人間にとって、無限というものが一体どういうことであるのかを厳密に理解することは非常に難しい問題を含んでいる。このことから、しばしば哲学、論理学や自然科学などの一部の分野において考察の対象として無限という概念が取り上げられ、そして深い考察が得られている。 本項では、数学などの学問分野において、無限がどのように捉えられ、どのように扱われるのかを記述する。.
新しい！!: ワーシャル–フロイド法と無限 · 続きを見る »
隣接行列
隣接行列（りんせつぎょうれつ、adjacency matrix）とは、における基本的な概念で、グラフの頂点と頂点の隣接関係を表わす正方行列である。 頂点集合を とする有限無向グラフ に対して、その隣接行列 とは（頂点集合によって添字づけられた） 次正方行列であって、その 成分 は頂点 と頂点 を結ぶ枝の数で定義される。これによりグラフ の固有多項式やスペクトルがそれぞれ隣接行列 の固有多項式やスペクトルとして定義される。これらはグラフの不変量である（隣接行列そのものは頂点集合上の置換を除いてしか定まらない）。 有向グラフの場合、 から に向かう枝があるときのみ 成分を 1 に、そうでないとき 成分を 0 にする。また、枝に重みがついているグラフの場合は、 成分を重みとする。.
新しい！!: ワーシャル–フロイド法と隣接行列 · 続きを見る »
行列
数学の線型代数学周辺分野における行列（ぎょうれつ、matrix）は、数や記号や式などを行と列に沿って矩形状に配列したものである。行の数と列の数が同じ行列はが成分ごとの計算によって与えられる。行列の積の計算はもっと複雑で、2 つの行列がかけ合わせられるためには、積の左因子の列の数と右因子の行の数が一致していなければならない。 行列の応用として顕著なものは一次変換の表現である。一次変換は のような一次関数の一般化で、例えば三次元空間におけるベクトルの回転などは一次変換であり、 が回転行列で が空間の点の位置を表す列ベクトル（1 列しかない行列）のとき、積 は回転後の点の位置を表す列ベクトルになる。また 2 つの行列の積は、2 つの一次変換の合成を表現するものとなる。行列の別な応用としては、連立一次方程式の解法におけるものである。行列が正方行列であるならば、そのいくつかの性質は、行列式を計算することによって演繹することができる。例えば、正方行列が正則であるための必要十分条件は、その行列式の値が非零となることである。固有値や固有ベクトルは一次変換の幾何学に対する洞察を与える。行列の応用は科学的な分野の大半に及び、特に物理学において行列は、電気回路、光学、量子力学などの研究に利用される。コンピュータ・グラフィックスでは三次元画像の二次元スクリーンへの投影や realistic-seeming motion を作るのに行列が用いられる。は、古典的な解析学における微分や指数関数の概念を高次元へ一般化するものである。 主要な数値解析の分野は、行列計算の効果的なアルゴリズムの開発を扱っており、主題は何百年にもわたって今日では研究領域も広がっている。行列の分解は、理論的にも実用的にも計算を単純化するもので、アルゴリズムは正方行列や対角行列などといった行列の特定の構造に合わせて仕立てられており、有限要素法やそのほかの計が効率的に処理される。惑星運動論や原子論では無限次行列が現れる。関数のテイラー級数に対して作用する微分の表現行列は、無限次行列の簡単な例である。.
新しい！!: ワーシャル–フロイド法と行列 · 続きを見る »
論理和
''P'' ∨ ''Q'' のベン図による表現 数理論理学において論理和（ろんりわ、Logical disjunction）とは、与えられた複数の命題のいずれか少なくとも一つが真であることを示す論理演算である。離接（りせつ）、選言（せんげん）とも呼び、ORとよく表す。 二つの命題 P, Q に対する論理和を P ∨ Q と書き、「P または Q」と読む。後述のように、日常会話における「または」とは意味が異なる。.
新しい！!: ワーシャル–フロイド法と論理和 · 続きを見る »
論理積
数理論理学において論理積（ろんりせき、logical conjunction）とは、与えられた複数の命題のいずれもが例外なく真であることを示す論理演算である。合接（ごうせつ）、連言（れんげん、れんごん）とも呼び、ANDとよく表す。 二つの命題 P, Q に対する論理積を P ∧ Q と書き、「P かつ Q」や「P そして Q」などと読む。 ベン図による論理積P \wedge Q の表.
新しい！!: ワーシャル–フロイド法と論理積 · 続きを見る »
Javaアプレット
Javaアプレット（Java Applet）は、ネットワークを通してWebブラウザに読み込まれ実行されるJavaのアプリケーションの一形態。.
新しい！!: ワーシャル–フロイド法とJavaアプレット · 続きを見る »
Python
Python（パイソン）は、汎用のプログラミング言語である。コードがシンプルで扱いやすく設計されており、C言語などに比べて、さまざまなプログラムを分かりやすく、少ないコード行数で書けるといった特徴がある。.
新しい！!: ワーシャル–フロイド法とPython · 続きを見る »
推移閉包
推移閉包（すいいへいほう、transitive closure）は、集合 X における二項関係 R に対して、R を含む X 上の最小の推移関係 R を意味する。 たとえば X を人間（生死は問わない）の集合とし、「x は y の親である」という関係 xRy を考えると、その推移閉包は「x は y の先祖である」という関係 xRy である。あるいは X を空港の集合とし、「x から y への直通便が存在する」という関係 xRy を考えると、その推移閉包は「x から y まで一回または複数の航空便で行くことができる」という関係 xRy である。.
新しい！!: ワーシャル–フロイド法と推移閉包 · 続きを見る »
正則行列
正則行列（せいそくぎょうれつ、regular matrix）、非特異行列（ひとくいぎょうれつ、non-singular matrix）あるいは可逆行列（かぎゃくぎょうれつ、invertible matrix）とは行列の通常の積に関する逆元を持つ正方行列のこと、言い換えると逆行列が存在する行列のことである。 ある体上の同じサイズの正則行列の全体は一般線型群と呼ばれる群を成す。多項式の根として定められる部分群はあるいは行列群と呼ばれる代数群の一種で、その表現論が代数的整数論などに広い応用を持つ幾何学的対象である。.
新しい！!: ワーシャル–フロイド法と正則行列 · 続きを見る »
正規表現
正規表現（せいきひょうげん、regular expression）とは、文字列の集合を一つの文字列で表現する方法の一つである。正則表現（せいそくひょうげん）とも呼ばれ、形式言語理論の分野では比較的こちらの訳語の方が使われる。まれに正規式と呼ばれることもある。 もともと正規表現は形式言語理論において正規言語を表すための手段として導入された。形式言語理論では、形式言語が正規言語であることと正規表現によって表せることは同値である。 その後正規表現はテキストエディタ、ワードプロセッサなどのアプリケーションで（ないし、そもそもそれ以前に単機能の文字列探索ツールの）、マッチさせるべき対象を表すために使用されるようになり、表せるパターンの種類を増やすために本来の正規表現にはないさまざまな記法が新たに付け加えられた。このような拡張された正規表現には正規言語ではない文字列も表せるものも多く、ゆえに正規表現という名前は実態に即していない面もあるが、伝統的に正規表現と呼ばれ続けている。 この記事では主にこのような正規表現を用いたパターンマッチングについて説明している。以下、誤解のない限り、アプリケーションやプログラミングにおいて正規表現を用いた文字列のパターンマッチングを行う機能のことを、単に正規表現という。 ほとんどのプログラミング言語では、ライブラリによって正規表現を使うことができる他、一部の言語では正規表現のリテラルもある。「正規表現によるマッチ」を意味する（専用の）演算子がある言語なども一部ある。具体例として、grep、AWK、sed、Perl、Tcl、lexなどがある。 それぞれの言語やアプリケーションで細部の仕様が異なっている、といったように思われることも多いが（また、古い実装では実際にそういうことも多いが）、近年は同じライブラリを使っていれば同じということも多い。またPOSIXなど標準もある。.
新しい！!: ワーシャル–フロイド法と正規表現 · 続きを見る »
正規言語
正規言語（せいきげんご）または正則言語（せいそくげんご）は、以下に示す性質（いずれも等価）を満たす形式言語である。.
新しい！!: ワーシャル–フロイド法と正規言語 · 続きを見る »
木 (数学)
数学、特にグラフ理論の分野における木（き、tree）とは、連結で閉路を持たない(無向)グラフである。有向グラフについての木（有向木）についても論じられるが、当記事では専ら無向木を扱う。 閉路を持たない（連結であるとは限らない）無向グラフを森（もり、forest）という。木は明らかに森である。 なお、閉路を持たない有向グラフは有向非巡回グラフである。有向木は有向非巡回グラフでもあるが、有向非巡回グラフは必ずしも有向木とは限らない。 コンピュータ上での木の扱いについては、木構造 (データ構造) を参照。 画像:Tree-sample1.png.
新しい！!: ワーシャル–フロイド法と木 (数学) · 続きを見る »
有限オートマトン
有限オートマトン（finite automaton)または有限状態機械（finite state machine, FSM）とは、有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」である。デジタル回路やプログラムの設計で使われることがあり、ある一連の状態をとったときどのように論理が流れるかを調べることができる。有限個の「状態」のうち1つの状態をとる。ある時点では1つの状態しかとらず、それをその時点の「現在状態」と呼ぶ。何らかのイベントや条件によってある状態から別の状態へと移行し、それを「遷移」と呼ぶ。それぞれの現在状態から遷移しうる状態と、遷移のきっかけとなる条件を列挙することで定義される。 有限オートマトンは様々な問題に応用でき、半導体設計の自動化、通信プロトコル設計、構文解析などの工学面での応用がある。生物学や人工知能研究では状態機械（群）を使って神経系をモデル化し、言語学では自然言語の文法をモデル化したりする。.
新しい！!: ワーシャル–フロイド法と有限オートマトン · 続きを見る »
最短経路問題
ラフ理論における最短経路問題（さいたんけいろもんだい、shortest path problem）とは、重み付きグラフの与えられた2つのノード間を結ぶ経路の中で、重みが最小の経路を求める最適化問題である。.
新しい！!: ワーシャル–フロイド法と最短経路問題 · 続きを見る »
擬似コード
擬似コード （ぎじコード、pseudocode）とは、アルゴリズムなどを、架空の非常に高水準なプログラミング言語（擬似言語）で記述したものである。Pascal、Fortran、C言語などの既存のプログラミング言語の構文と、自然言語に近い表現を組み合わせて記述することが多い。.
新しい！!: ワーシャル–フロイド法と擬似コード · 続きを見る »
2部グラフ
循環の無い2部グラフの例 完全2部グラフ 数学、とくにグラフ理論における2部グラフ（にぶぐらふ、bipartite graph）は、頂点集合を二つの部分集合に分割して各集合内の頂点同士の間には辺が無いようにできるグラフのことである。このような頂点の集合を独立集合といい、より一般にn個の独立頂点集合に分割可能なグラフのことをn部グラフ (n-partite graph) という。 完全2部グラフは、二つの頂点集合V1, V2に分割したとき、V1同士・V2同士の頂点間には辺が存在しないが、V1とV2間の任意の2点間に辺が存在するグラフのことである。m頂点の頂点集合とn頂点の頂点集合に分割されるような完全2部グラフのことをKm, nとかく。 隣り合った頂点同士を異なる色で塗ることを（頂点）彩色という。よって、n部グラフはn点彩色可能なグラフである。同様に、隣り合った辺同士を異なる色で塗ることを辺彩色という。 二部グラフの辺集合Mがマッチングであるとは、Mに属するどの2辺も隣接していないと言うことである。グラフGの最大マッチングとは、GのマッチングMのうち、辺の数が最大のものである。また、全ての頂点を含むマッチングのことを完全マッチングという。.
新しい！!: ワーシャル–フロイド法と2部グラフ · 続きを見る »
ここにリダイレクトされます：
ワーシャル-フロイド法、ワーシャル・フロイド法、ワーシャルフロイド法、フロイドのアルゴリズム、フロイド・ワーシャル法。
