ブラウザよりも高速アクセス！
14 関係: 二項ヒープ、ロバート・タージャン、プリム法、ヒープ、データ構造、フィボナッチ数、ダイクストラ法、グラフ理論、償却解析、全域木、計算機科学、最短経路問題、1984年、1987年。
二項ヒープ
二項ヒープ（にこうヒープ、binomial heap）とは、計算機科学におけるデータ構造（ヒープ）の1つである。特徴は以下の通り。.
新しい！!: フィボナッチヒープと二項ヒープ · 続きを見る »
ロバート・タージャン
バート・タージャン（Robert Endre Tarjan, 1948年4月30日 - ）は、アメリカ合衆国の計算機科学者。などのグラフアルゴリズムを発見し、スプレー木とフィボナッチヒープというデータ構造を共同で発明した。2012年現在はプリンストン大学で計算機科学の教授を務めており、ヒューレット・パッカードのシニアフェローでもある。.
新しい！!: フィボナッチヒープとロバート・タージャン · 続きを見る »
プリム法
プリム法とは、グラフ理論で重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。全域木（対象となるグラフの全頂点を含む辺の部分集合で構成される木）のうち、その辺群の重みの総和が最小となる木を求めるものである。このアルゴリズムは1930年に数学者 Vojtěch Jarník が発見し、1957年に計算機科学者ロバート・C・プリムが独自に発見、さらに1959年にはエドガー・ダイクストラが再発見しダイクストラ法の論文に記載している。そのため、DJP法、Jarník法、Prim-Jarník法などとも呼ばれることがある。アルゴリズムの発想や計算量は同時期に発表されたダイクストラ法に類似している。.
新しい！!: フィボナッチヒープとプリム法 · 続きを見る »
ヒープ
ヒープ（heap）とは、「子要素は親要素より常に大きいか等しい（または常に小さいか等しい）」という制約を持つ木構造の事。単に「ヒープ」という場合、二分木を使った二分ヒープを指すことが多いため、そちらを参照すること。 二分ヒープのインデックス付け.
新しい！!: フィボナッチヒープとヒープ · 続きを見る »
データ構造
データ構造（データこうぞう、data structure）は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。 ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム（アルゴリズム）の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。 多くのプログラムの設計において、データ構造の選択は主要な問題である。これは大規模システムの構築において、実装の困難さや質、最終的なパフォーマンスはベストのデータ構造を選択したかどうかに大きく依存してきたという経験の結果である。多くの場合、データ構造が決まれば、利用するアルゴリズムは比較的自明に決まる。しかし場合によっては、順番が逆になる。つまり、与えられた仕事をこなす最適なアルゴリズムを使うために、そのアルゴリズムが前提としている特定のデータ構造が選択される。いずれにしても適切なデータ構造の選択は極めて重要である。 この洞察は、多くの定式化された設計手法やプログラミング言語において、データ構造がアルゴリズムよりもキーとなる構成要素となっていることに現れている。大半の言語は異なるアプリケーションにおいてデータ構造を安全に再利用できるよう、実装の詳細をインターフェイスの背後に隠蔽するような、モジュール化のしくみを備えている。C++やJavaといったオブジェクト指向プログラミング言語はクラスをこの目的に用いている。 データ構造は専門的なプログラミングにとって非常に重要なので、C++におけるSTLや、Java API、および.NET Frameworkのようなプログラミング言語の標準ライブラリや環境において多くのデータ構造がサポートされている。 データ構造が実装を表すのかインターフェースを表すのかについてはいくらか議論がある。どのように見えるかは相対的な問題なのかもしれない。データ構造は2つの関数の間にあるインターフェイスとして見ることもできるし、データ型に基づいて構成されたストレージにアクセスする方法を実装したものとして見ることもできる。.
新しい！!: フィボナッチヒープとデータ構造 · 続きを見る »
フィボナッチ数
フィボナッチ数列の各項を一辺とする正方形 メインページ（2007年〜2012年）で使われていたイメージ画像もフィボナッチ数列を利用している フィボナッチ数（フィボナッチすう、Fibonacci number）は、イタリアの数学者レオナルド・フィボナッチ（ピサのレオナルド）にちなんで名付けられた数である。.
新しい！!: フィボナッチヒープとフィボナッチ数 · 続きを見る »
ダイクストラ法
ダイクストラ法の動作のアニメーション ダイクストラ法（だいくすとらほう、Dijkstra's algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。辺の重みに負数を含む場合はベルマン-フォード法などが使える。辺の重みが全て同一の非負数の場合は幅優先探索が速く、線形時間で最短路を計算可能である。また、無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズムによって線形時間での計算が可能であるが、実用性はあまり高くない。.
新しい！!: フィボナッチヒープとダイクストラ法 · 続きを見る »
グラフ理論
ラフ理論（グラフりろん、graph theory）は、ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフに関する数学の理論である。グラフ (データ構造) などの応用がある。.
新しい！!: フィボナッチヒープとグラフ理論 · 続きを見る »
償却解析
ンピュータサイエンスにおける 償却解析 (Amortized analysis, ならし解析ともよばれる)とは、与えられたアルゴリズムのまたは、コンピュータプログラムの文脈における資源、特に時間またはメモリをどれだけ必要とするかを分析する手法である。償却解析の動機は、一回の実行あたりの最悪実行時間を見ることがあまりにも悲観的であるということである。 与えられたアルゴリズムの一定の動作は著しく計算資源を消費するかもしれないし、他の動作はそれほど消費しないかもしれない。償却分析はアルゴリズムの一連の動作全体にわたってコストが高い、またはそうでもない動作の両方を考慮する。これは、そのパフォーマンスに影響を与える要素(入力の種類、入力の長さなど)の説明を含んでもよい。.
新しい！!: フィボナッチヒープと償却解析 · 続きを見る »
全域木
4×4のグリッドグラフにおける全域木の一例 全域木（ぜんいきぎ、Spanning tree）、極大木（きょくだいき）、スパニング木、スパニングツリーとは、グラフ理論において、以下のように定義される木のことである。 つまり、あるグラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木のことである。.
新しい！!: フィボナッチヒープと全域木 · 続きを見る »
計算機科学
計算機科学（けいさんきかがく、computer science、コンピュータ科学）とは、情報と計算の理論的基礎、及びそのコンピュータ上への実装と応用に関する研究分野である。計算機科学には様々な下位領域がある。コンピュータグラフィックスのように特定の処理に集中する領域もあれば、計算理論のように数学的な理論に関する領域もある。またある領域は計算の実装を試みることに集中している。例えば、プログラミング言語理論は計算を記述する手法に関する学問領域であり、プログラミングは特定のプログラミング言語を使って問題を解決する領域である。.
新しい！!: フィボナッチヒープと計算機科学 · 続きを見る »
最短経路問題
ラフ理論における最短経路問題（さいたんけいろもんだい、shortest path problem）とは、重み付きグラフの与えられた2つのノード間を結ぶ経路の中で、重みが最小の経路を求める最適化問題である。.
新しい！!: フィボナッチヒープと最短経路問題 · 続きを見る »
1984年
この項目では、国際的な視点に基づいた1984年について記載する。.
新しい！!: フィボナッチヒープと1984年 · 続きを見る »
1987年
この項目では、国際的な視点に基づいた1987年について記載する。.
新しい！!: フィボナッチヒープと1987年 · 続きを見る »
