ダイクストラ法 - Wikipedia
ダイクストラ法の動作のアニメーション ダイクストラ法（だいくすとらほう、英: Dijkstra's algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。 ダイクストラ法は、1959年エドガー・ダイクストラによって考案された。 応用範囲は広くOSPFなどのインターネットルーティングプロトコルや、カーナビの経路探索や鉄道の経路案内においても利用されている。 ほかのアルゴリズムとして、 最短経路長の推定値を事前に知っているときは、ダイクストラ法の改良版であるA*アルゴリズムを用いて、より効率的に最短経路を求めることができる。 辺の重みが全て同一の非負数の場合は幅優先探索がより速く、線形時間で最短路を計算可能である。 無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズム[1]によって線形時間での計算が可能
最良優先探索 - Wikipedia
最良優先探索（さいりょうゆうせんたんさく、英: best-first search）は、幅優先探索（英: breadth-first search）を何らかの規則（評価関数）に従って次に探索する最も望ましいノードを選択するように拡張した探索アルゴリズムである。 探索ノードを効率的に選択するには優先度付きキュー（英: priority queue）を用いて実装するのが一般的である。キューに貯めずに最良のノードだけを扱うと山登り法になる。キューを評価関数でソートしないと幅優先探索になる。 最良優先探索の例としてはダイクストラ法（英: Dijkstra's algorithm）やA*アルゴリズム（英: A* search algorithm）や均一コスト探索を挙げることができる。最良優先探索は経路探索においてしばしば使われるアルゴリズムである。コンピュータ将棋・コンピュータチェスなどでも最良優先
A* - Wikipedia
A*探索アルゴリズム A*（A-star、エースター）探索アルゴリズム（エースターたんさくアルゴリズム）は、グラフ探索アルゴリズムの一つ。 最良優先探索を拡張したZ*に、さらにf値として「現時点までの距離」g と「ゴールまでの推定値」h の和を採用したもの[1]。h は ヒューリスティック関数と呼ばれる。 A* アルゴリズムは、「グラフ上でスタートからゴールまでの道を見つける」というグラフ探索問題において、 ヒューリスティック関数 h(n) という探索の道標となる関数を用いて探索を行うアルゴリズムである。h は各頂点 n からゴールまでの距離のある妥当な推定値を返す関数で、解くグラフ探索問題の種類に応じてさまざまな h を設計することが出来る。 例えば、カーナビなどで用いられる単純な二次元の地図での探索では、h としてユークリッド距離 を使うことができ、この値は道に沿った実際の距離のおおま
ベルマン–フォード法 - Wikipedia
ベルマン–フォード法 (英: Bellman–Ford algorithm) は、重み付き有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズム[1]の一種である。各辺の重みは負数でもよい。辺の重みが非負数ならば優先度付きキューを併用したダイクストラ法の方が速いので、ベルマン–フォード法は辺の重みに負数が存在する場合に主に使われる。名称は開発者であるリチャード・E・ベルマンと Lester Ford, Jr. にちなむ。 グラフに「負閉路」(negative cycle) が含まれるとき、すなわち辺の重みの総和が負になるような閉路が存在するとき、好きなだけ小さな重みを持つ歩道を取れるので、「最短」経路は定まらない。このためベルマン-フォード法も負閉路が始点から到達可能である場合は正しい答を出せないが、負閉路を検出してその存在を報告することはできる。 ロバート・セジウィックによ
イェンセンの不等式 - Wikipedia
イェンセンの不等式（いぇんせんのふとうしき、英語: Jensen's inequality）は、凸関数を使った不等式である。 f(x) を実数上の凸関数とする。 離散の場合： を、 を満たす正の実数の列とする。また、 を、実数の列とする。そのとき、次が成り立つ。 連続値の場合： を、 を満たす実数上の可積分関数とする。また、 を実数上の可積分関数とする。そのとき、次が成り立つ。 ルベーグ積分論の観点では、 離散の場合も連続の場合も同一に見倣せる。 証明は、f のにおける接線を g とおいて、常に g(x) が f(x) よりも小さいことを使えばよい。 統計学において、式の下限を評価する際に、一定の役割を担っている。例えば、カルバック・ライブラー・ダイバージェンスが常に 0 より大きいことを証明するときに用いられる。p(x) が確率密度関数の場合を考えると、イェンセンの不等式は次のように書け
Visual Studio Code - Wikipedia
Visual Studio Codeの機能の多くはメニューやユーザーインタフェースを通して公開されていない。代わりに、コマンドパレット（例: スニペットの挿入）あるいは.json設定ファイル（例: ショートカットキーの設定）を経由してアクセスする。コマンドパレットはキャラクタユーザインタフェースの一種である。 ディレクトリを開くことで、そのディレクトリに含まれる複数のファイルがツリー状に表示される。開いたファイルはタブにも表示され、タブを切り替えながら複数のファイルを並行して編集できる。ただしWeb版の場合、Google ChromeやMicrosoft Edgeなど一部のChromium系ブラウザでしかディレクトリを開くことはできない。これは、Visual Studio CodeがFile System Access APIというAPIを使用してディレクトリを操作するためである[13]
分岐予測 - Wikipedia
コンピュータ・アーキテクチャにおける分岐予測（ぶんきよそく、Branch Prediction、ブランチプレディクション）とは、プログラム実行の流れの中で条件分岐命令が分岐するかしないかを予測することにより、命令パイプラインの効果を可能な限り維持し、性能を高めるためのCPU内の機能である。 2方向分岐は一般に条件分岐命令で実装されている。条件分岐は、分岐せず (not taken) に分岐命令直後に続く命令の流れをそのまま実行し続ける場合と、分岐して (taken) プログラム内の異なる位置に分岐してそこから命令実行を続行する場合がある。 図 1: 4段パイプラインの例。色つきの四角形が命令を表している。 条件分岐命令が分岐するかしないかは、分岐条件を計算し、条件分岐命令が実行ステージ（図1の Stage: 3）を過ぎるまでわからない。 分岐予測を行わない場合、条件分岐命令が実行ステージを
ほとんど整数 - Wikipedia
ある数がほとんど整数（ほとんどせいすう、英: almost integer）であるとは、整数ではないが、整数に非常に近いことを意味する。どれほど近ければ十分であるのか明確な決まりはないが、一見して整数に近いとは分からないのに、近似値を計算すると驚くほど整数に近い数で、小数点以下の部分が「.000…」または「.999…」のように、0か9が数個連続する場合、このように表現される。例えば、「インドの魔術師」の異名をもつシュリニヴァーサ・ラマヌジャンは など、整数に近い数の例をいくつか与えた[1]。また、黄金比 φ = 1.618… の累乗、例えば は整数に近い。整数に近い数を与えることは、単なる趣味の範疇であることが多いが、意義深い数学的な理論が背景にあることも少なくはない。 整数に近い値となることについては、理由を説明すれば自明なもの、単純な説明が与えられるもの、あるいは（現在のところ）数学的
マクスウェルの悪魔 - Wikipedia
マクスウェルの悪魔（マクスウェルのあくま、Maxwell's demon）とは、1867年ごろ、スコットランドの物理学者ジェームズ・クラーク・マクスウェルが提唱した思考実験、ないしその実験で想定される架空の、働く存在である。マクスウェルの魔、マクスウェルの魔物、マクスウェルのデーモンなどともいう。 分子の動きを観察できる架空の悪魔を想定することによって、熱力学第二法則で禁じられたエントロピーの減少が可能であるとした。 熱力学の根幹に突き付けられたこの難問は1980年代に入ってようやく一応の解決を見た。 マクスウェルが考えた仮想的な実験内容とは以下のようである（Theory of Heat、1872年）。 マクスウェルの悪魔。分子を観察できる悪魔は仕事をすることなしに温度差を作り出せるようにみえる。 均一な温度の気体で満たされた容器を用意する。 このとき温度は均一でも個々の分子の速度は決して
歪エルミート行列 - Wikipedia
歪エルミート行列（わいえるみーとぎょうれつ、英語: Skew-Hermitian matrix）あるいは反エルミート行列（はんえるみーとぎょうれつ、英語: Anti-Hermitian matrix）とは、自身のエルミート共役（＝随伴）が自身に負号をつけたものに等しいような複素正方行列のことである。つまり、n 次正方行列 A に対し、そのエルミート共役を A* で表すとき、A が歪エルミートならば、以下の条件を満たす。 行列 A の成分をあらわに書けば、これは次のようにも表せる。 n 次歪エルミート行列の集合はリー代数をなし、 と表される。 歪エルミート行列と似た定義を持つ行列として、エルミート行列がある。エルミート行列は自身と自身のエルミート共役が等しい。 歪エルミート行列はエルミート行列と同じく、正規行列の特別な場合であり、−1 をユニタリ行列 U と見なせば、以下の正規行列の定義を満
九後汰一郎 - Wikipedia
九後 汰一郎（くご たいちろう、1949年3月 - ）は、日本の理論物理学者。京都大学名誉教授。京都大学基礎物理学研究所第8代・10代所長。専門は素粒子論。理学博士（京都大学・1976年）。京都市出身。本名は九後太一（くご たいち）。研究者としては汰一郎を使用。 研究[編集] 九後・小嶋形式の定式化[編集] 小嶋泉との共同研究により、非可換ゲージ理論（ヤン＝ミルズ場の理論）の共変正準量子論において物理的状態を選び出す条件（九後・小嶋の補助条件）を見出し、物理的S行列のユニタリー性に対する明快な証明を与えた。その際、非物理的状態の寄与がゲージ場の縦波・スカラー状態、およびゴースト・反ゴースト状態の四つで互いに相殺すること（九後・小嶋のカルテット機構）を発見した。さらに、カルテット機構に基づいて、QCDにおけるカラー閉じ込めの十分条件（九後・小嶋の閉じ込め条件）を提唱した。 その他、畑浩之と共
論点先取 - Wikipedia
アリストテレスの胸像。彼は『分析論前書』の中で論点先取について論じた。 論点先取（ろんてんせんしゅ、英: Begging the question、羅: Petitio Principii）とは、証明すべき命題が暗黙または明示的に前提の1つとして使われるという誤謬の一種[1][2][3][4][5]。論点先取の虚偽（ろんてんせんしゅのきょぎ）とも言われる[6]。論点先取は、循環論法の誤謬と関連している。西洋での最初の定義としては、古代ギリシアの哲学者アリストテレスが紀元前350年ごろに行ったものが知られており、その著書『分析論前書』[7][8]や『詭弁論駁論』にある。 ラテン語では「assumptio non probata」（「論点窃取」とも訳された[9]）であり、その一種に「hysteron proteron」（不当仮定、倒逆法）や「circulus in probando」（循環論証
情報理論 - Wikipedia
情報理論（じょうほうりろん、英: Information theory）は、情報・通信を数学的に論じる学問である。応用数学の中でもデータの定量化に関する分野であり、可能な限り多くのデータを媒体に格納したり通信路で送ったりすることを目的としている。情報エントロピーとして知られるデータの尺度は、データの格納や通信に必要とされる平均ビット数で表現される。例えば、日々の天気が3ビットのエントロピーで表されるなら、十分な日数の観測を経て、日々の天気を表現するには「平均で」約3ビット/日（各ビットの値は 0 か 1）と言うことができる。 情報理論の基本的な応用としては、ZIP形式（可逆圧縮）、MP3（非可逆圧縮）、DSL（伝送路符号化）などがある。この分野は、数学、統計学、計算機科学、物理学、神経科学、電子工学などの交差する学際領域でもある。その影響は、ボイジャー計画の深宇宙探査の成功、CDの発明、携
負の確率 - Wikipedia
他にも例として、1932年にユージン・ウィグナーが量子誤り訂正の研究[7]で提案した位相空間上の擬確率分布であるウィグナー関数が挙げられる。1945年バートレットはウィグナー分布が負の値をもつことに数理論理的な矛盾がないことを見出した[8]。ウィグナー関数は量子光学分野でよく利用され、位相空間量子化の基礎となっている。また、量子干渉のある場合に負値となることから、量子干渉があることをわかりやすく示すことができる。ウィグナー関数が負値をとる領域は、量子論の不確定性原理により直接観測することが困難なほど小さいが、可観測量の期待値を求めるときに利用されている。 ファイナンス[編集] 最近になって負の確率は数理ファイナンスに応用されるようになった。計量ファイナンスにおいてはほとんどの確率はリスクニュートラル確率として知られる正の確率や擬確率である。確率論上の一連の仮定の下で、正の確率だけでなく負の
アインシュタイン方程式 - Wikipedia
一般相対性理論におけるアインシュタイン方程式（アインシュタインほうていしき、英: Einstein's equations, Einstein Field Equations）[注 1]は、万有引力・重力場を記述する場の方程式である。アルベルト・アインシュタインによって導入された。 アイザック・ニュートンが導いた万有引力の法則を、強い重力場に対して適用できるように拡張した方程式であり、中性子星やブラックホールなどの高密度・大質量天体や、宇宙全体の幾何学などを扱える。 一般相対性理論によれば、大質量の物体は周囲の時空を歪ませる。すなわち、重力とは時空の歪みであるとして説明される。その理論的な帰結・骨子となるのが、次のように表されるアインシュタイン方程式である。 左辺は時空がどのように曲がっているのか（時空の曲率）を表す幾何学量であり、右辺は物質の分布を表す量である。 おおざっぱに言えば、星の
)
モナド (プログラミング) - Wikipedia
関数型プログラミングにおいて、モナドはプログラムを構造化するための汎用的な抽象概念である。対応したプログラム言語では、ボイラープレート的なコードでもモナドを使って除去することが可能となる。これはモナドが、特定の形をした計算を表すデータ型と、それに関する生成と合成の2つの手続きを提供することによって実現されている。生成は任意の基本型の値をモナドに包んでモナド値を生成する手続きであり、合成はモナド値を返す関数(モナド関数)たちを合成する手続きである。[1] 広い範囲の問題をモナドを使うことで単純化できる。例えば、Maybeモナドを使えば未定義値への対処が簡単になり、Listモナドを使えばリストに入った値を柔軟に扱うことができる。複雑に組み合わさった関数は、モナドを使えば、補助データの管理や制御構造や副作用を除去した簡単なパイプライン構造に置き換えることができる[1][2]。 モナドの概念や用語
信用照会端末 - Wikipedia
INFOXで使用されている東芝テックの信用照会端末 CT4100 信用照会端末（しんようしょうかいたんまつ、英語: Credit Authorization Terminal）は、クレジットカード加盟店で、カードの有効性を確認するため、カードの情報を信用照会（オーソリゼーション）センターなどへ問い合わせ、次いで決済する装置である。 日本でCATと土台となるネットワーク網CAFISが登場する1980年代前半まで、クレジットカードを用いて加盟店で買い物する際は、インプリンタにクレジットカードと複写式売上伝票を挟み、カードの凸凹状に刻印された番号や会員名義など（エンボス）を店員が転写し[1]、金額・署名の記入後に、売上を取り纏めるカード会社（アクワイアラ）へ郵送しなければならなかった。 しかしながら、この手法では偽造クレジットカードなど不正なカードか否かは、高額取引による電話承認を行わなければ見
エントロピー符号 - Wikipedia
エントロピー符号（エントロピーふごう）とは、情報源アルファベットのシンボルに対し符号語を割り当てるコンパクト符号の概念の一つで、シンボル毎の出現確率に基づき異なる長さの符号語長を用いることで、情報源を効率的に符号化することを目的としたもの。具体的な例としてハフマン符号や算術符号などがあり、データ圧縮に広く用いられている。 符号アルファベットの要素数を、任意のシンボルの出現確率をとすると、の長さの符号語を割り当てた時に最短の符号が得られることが知られている。当然、任意の情報源に対してこれらの最適な符号語長は整数にはならない。ハフマン符号では、ハフマン木を用いて各符号語長が整数になるように近似しているため、簡便な手法ではあるが最短の符号は得られない。算術符号は半開区間の分割を繰り返すことで、この問題を克服している。 エントロピー符号を復号するには、情報源アルファベットの各出現確率を事前に通知す
)
カルノーの定理 (熱力学) - Wikipedia
熱力学におけるカルノーの定理とは、熱機関の最大効率に関する定理である。ニコラ・レオナール・サディ・カルノーの名にちなむ。カルノーの原理とも呼ばれる。 熱エネルギーを力学的な仕事へと変換するには、高温の熱源の他に低温の熱源を必要とする（熱力学第二法則を参照）。熱機関では、ある作業物質（空気など）が高温熱源から熱 を得て、そのエネルギーの一部を仕事 として使う。その際、残りのエネルギーは熱 として低温熱源へと移動する。 この場合、熱効率は、 と定義できる。高温熱源から得た熱のうち仕事として使われる量が多いほど、効率のよい熱機関であるといえる。 このとき、以下の定理が成り立つ。 これがカルノーの定理である。 たとえば、一般的に蒸気機関は水蒸気を圧縮・膨張させて動力を得ているため、作業物質は水蒸気となる。カルノーの定理は、この水蒸気の代わりに他の気体（あるいは液体、固体）を使用しても最大効率は変わ
熱力学ポテンシャル - Wikipedia
熱力学ポテンシャル（ねつりきがくポテンシャル、英語: thermodynamic potential）とは、熱力学において、系の平衡状態における熱力学的性質の情報を全て持つ示量性状態量である。完全な熱力学関数とも呼ばれる[1]。 ウィラード・ギブズは基本的な方程式 (fundamental equations)と呼んでいた[2]。 概要[編集] 「熱力学的性質の情報を全て持つ」とは全ての状態量がこの関数から（偏微分等の組み合わせにより）与えられるという意味である。言い換えれば、完全な熱力学関数が与えられればそこから状態方程式や熱容量などの系の性質が決まる[3]。熱力学からは関数形に制約（凸性など）を与えるが、具体的な関数形は実験的に決められるか、統計力学から導出するなど、熱力学以外から与えられる[4]。 熱力学ポテンシャルの一つである内部エネルギー U は、エントロピー S、体積 V、各成
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
