タグ

algorithmとwikipediaに関するHashのブックマーク (18)

  • Lamport timestamp - Wikipedia

    The Lamport timestamp algorithm is a simple logical clock algorithm used to determine the order of events in a distributed computer system. As different nodes or processes will typically not be perfectly synchronized, this algorithm is used to provide a partial ordering of events with minimal overhead, and conceptually provide a starting point for the more advanced vector clock method. The algorit

    Hash
    Hash 2016/01/11
    "a simple algorithm used to determine the order of events in a distributed computer system." minimal overhead で半順序(partial order)を提供するアルゴリズム. この先に vector clock メソッドへ応用可能
  • 巡回冗長検査 - Wikipedia

    巡回冗長検査(じゅんかいじょうちょうけんさ、英: Cyclic Redundancy Check, CRC)は、誤り検出符号の一種で、主にデータ転送などに伴う偶発的な誤りの検出によく使われている。送信側は定められた生成多項式で除算した余りを検査データとして付加して送信し、受信側で同じ生成多項式を使用してデータを除算し、その余りを比較照合することによって受信データの誤り・破損を検出する。 デジタル回路で簡単に実装でき、数学的にも分析が容易であり、また、ビットのランダム誤りやバースト誤りを検出できるので、HDLC手順やCSMA/CD方式などにおいて誤りチェック・伝送路ノイズチェックによく使われている。パリティや単純な加算によるチェックサムに比べ検出精度が高く、その点では高級なチェックサムと言える。単純なチェックサムと同じく、データの改竄に対する耐性はない。 W・ウェスレイ・ピーターソンが発明し

  • Heuristic (computer science) - Wikipedia

    In mathematical optimization and computer science, heuristic (from Greek εὑρίσκω "I find, discover"[1]) is a technique designed for problem solving more quickly when classic methods are too slow for finding an exact or approximate solution, or when classic methods fail to find any exact solution in a search space. This is achieved by trading optimality, completeness, accuracy, or precision for spe

  • Big O notation - Wikipedia

    Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by German mathematicians Paul Bachmann,[1] Edmund Landau,[2] and others, collectively called Bachmann–Landau notation or asymptotic notation. The letter O was chosen by Bachmann to stand for

    Big O notation - Wikipedia
    Hash
    Hash 2015/01/28
    O記法の"="用法について詳しく書かれてる
  • Longest common subsequence - Wikipedia

    Comparison of two revisions of an example file, based on their longest common subsequence (black) A longest common subsequence (LCS) is the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from the longest common substring: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. The prob

    Longest common subsequence - Wikipedia
    Hash
    Hash 2015/01/17
  • Shortest common supersequence - Wikipedia

    In computer science, the shortest common supersequence of two sequences X and Y is the shortest sequence which has X and Y as subsequences. This is a problem closely related to the longest common subsequence problem. Given two sequences X = < x1,...,xm > and Y = < y1,...,yn >, a sequence U = < u1,...,uk > is a common supersequence of X and Y if items can be removed from U to produce X and Y. A sho

  • Spanning tree - Wikipedia

    For the network protocol, see Spanning Tree Protocol. For other uses, see Spanning tree (disambiguation). A spanning tree (blue heavy edges) of a grid graph In the mathematical field of graph theory, a spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G.[1] In general, a graph may have several spanning trees, but a graph that is not connect

    Spanning tree - Wikipedia
  • ニュートン法 - Wikipedia

    数値解析の分野において、ニュートン法(ニュートンほう、英: Newton's method)またはニュートン・ラフソン法(英: Newton–Raphson method[1])は、方程式系を数値計算によって解くための反復法による求根アルゴリズムの1つである。対象とする方程式系に対する条件は、領域における微分可能性と2次微分に関する符号だけであり、線型性などは特に要求しない。収束の速さも2次収束なので古くから数値計算で使用されていた。名称はアイザック・ニュートンとジョゼフ・ラフソンに由来する。ニュートン法を複素平面に適用し、初期値がどの解に収束するかについて色分けした結果としてニュートン・フラクタルを描くことができる(初期値の境界における挙動の予測が難しいことを示している)[2]。 ニュートン法の一手順の概念図 (青い線が関数 f のグラフで、その接線を赤で示した). xn よりも xn+

    ニュートン法 - Wikipedia
  • Suffix tree - Wikipedia

    Suffix tree for the text BANANA. Each substring is terminated with special character $. The six paths from the root to the leaves (shown as boxes) correspond to the six suffixes A$, NA$, ANA$, NANA$, ANANA$ and BANANA$. The numbers in the leaves give the start position of the corresponding suffix. Suffix links, drawn dashed, are used during construction. In computer science, a suffix tree (also ca

    Suffix tree - Wikipedia
  • Blowfish (cipher) - Wikipedia

    Four rounds of Blowfish are susceptible to a second-order differential attack (Rijmen, 1997);[2] for a class of weak keys, 14 rounds of Blowfish can be distinguished from a pseudorandom permutation (Vaudenay, 1996). Blowfish is a symmetric-key block cipher, designed in 1993 by Bruce Schneier and included in many cipher suites and encryption products. Blowfish provides a good encryption rate in sof

  • Key size - Wikipedia

    In cryptography, key size or key length refers to the number of bits in a key used by a cryptographic algorithm (such as a cipher). Key length defines the upper-bound on an algorithm's security (i.e. a logarithmic measure of the fastest known attack against an algorithm), because the security of all algorithms can be violated by brute-force attacks. Ideally, the lower-bound on an algorithm's secur

    Hash
    Hash 2013/01/21
    RSA暗号鍵を1024文字以上とする的なところのお話あとで読む
  • 有限オートマトン - Wikipedia

    オートマトン理論 有限オートマトン(ゆうげんオートマトン、英: finite automaton)または有限状態機械(ゆうげんじょうたいきかい、()英: finite state machine, FSM)とは、有限個の状態と遷移規則からなる状態機械。 チューリングマシンとは異なり計算状態を記憶するテープを持たず、チューリング完全ではないが、様々な応用がある。 状態[注 1]は、システムの振る舞いのノードであり、システム内で遷移[注 2]を実行するトリガーを待っている。一般に状態は、同じトリガーに対してシステムの反応が常に同じではない場合に導入される。例えば、カーラジオのシステムでは、特定のラジオ局の放送を聴いている状態で「次へ」というトリガーは次のラジオ局(の放送受信)への移行を意味する。しかし、CDプレーヤーのシステムでは、「次へ」は次のトラックへの移行を意味する。これらは、同じトリガ

    有限オートマトン - Wikipedia
    Hash
    Hash 2012/11/30
    fsm ってこれか...
  • Knight's tour - Wikipedia

    An open knight's tour of a chessboard An animation of an open knight's tour on a 5 × 5 board A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once. If the knight ends on a square that is one knight's move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is "closed", or

    Knight's tour - Wikipedia
    Hash
    Hash 2012/10/13
    ちょっとした問題
  • Two-phase commit protocol - Wikipedia

    "2PC" redirects here. For the play in American and Canadian football, see Two-point conversion. For the cryptographic protocol, see Commitment scheme. For the concurrency control, see Two-phase locking. A typical sequence of a Two-phase commit. In transaction processing, databases, and computer networking, the two-phase commit protocol (2PC, tupac) is a type of atomic commitment protocol (ACP). It

    Two-phase commit protocol - Wikipedia
  • 乱択アルゴリズム - Wikipedia

    乱択アルゴリズム(らんたくアルゴリズム)、ランダム・アルゴリズム(英: randomized algorithm)または確率的アルゴリズム(かくりつてきアルゴリズム、(英: probabilistic algorithm)は、その論理の一部に無作為性を導入したアルゴリズムである。通常のアルゴリズムでは自然数を順番にあてはめるような決定的な部分で、乱数による非決定的な選択を入れることで、「平均的に」よい性能を実現することを目的とすることがある。形式的には、乱択アルゴリズムの性能はランダムビット列で決定される確率変数となる。その期待値を期待実行時間[1]と呼ぶ。最悪の場合に関して「無視できる」ほどに低い確率であることが、一般に、この類のアルゴリズムが効果的である要件となる。 n 個の要素からなる配列から「a」という要素を探す問題を考える。この配列の各要素は半分が「a」で残りが「b」である。単純

  • ハッシュ関数 - Wikipedia

    この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方) 出典検索?: "ハッシュ関数" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2018年6月) ハッシュ関数で名前と0から15までの整数をマッピングしている。"John Smith" と "Sandra Dee" のハッシュ値が衝突している。 ハッシュ関数 (ハッシュかんすう、英語: hash function) あるいは要約関数[1]とは、任意のデータから、別の(多くの場合は短い固定長の)値を得るための操作、または、その様な値を得るための関数のこと。ハッシュ関数から得られた値のことを要約値やハッシュ値または単にハッシュという。 ハッシュ関数は、主に

    ハッシュ関数 - Wikipedia
  • Constraint (computational chemistry) - Wikipedia

    Hash
    Hash 2009/05/14
    SHAKE法、LINCS法の分子制限アルゴリズム。77年あたりに開発さる。
  • Category:アルゴリズム - Wikipedia

    このカテゴリ下にあるページは、該当する適切なサブカテゴリに移動してください。 このカテゴリは大きくなり過ぎないように継続的なメンテナンスが求められています。このカテゴリの下位にある適切なカテゴリに項目を移動してください。

    Hash
    Hash 2006/09/28
    おいしそう
  • 1