タグ

関連タグで絞り込む (0)

  • 関連タグはありません

タグの絞り込みを解除

algorithmとAlgorithmとwikipediaに関するItisangoのブックマーク (9)

  • Parsing expression grammar - Wikipedia

    Parsing Expression Grammar(PEG)は、分析的形式文法の一種であり、形式言語をその言語に含まれる文字列を認識するための一連の規則を使って表したものである。PEGは再帰下降構文解析を文法を示すためだけに純粋に図式的に表現したものと見ることもでき、具体的な構文解析器の実装やその用途とは独立している。 PEGにおける構文(文法)の定義は文脈自由文法のバッカス・ナウア記法によるそれに似ているが、文脈自由文法では一般に「|」(縦棒、バーティカルバー)で表される「これらのうちどれか」ではなく、「最初の解析がうまくいったらそれを、失敗なら次を順に試してゆき、成功したものを採用」(「/」であらわす)という意味を使う。 このため、文脈自由文法とは異なり、PEGには曖昧さは存在しない。文字列を構文解析する場合、正しい構文木は常に1つしかない。このためPEGはコンピュータ言語の構文解析

    Itisango
    Itisango 2021/11/14
    “PEGには曖昧さは存在しない。文字列を構文解析する場合、正しい構文木は常に1つしかない。このためPEGはコンピュータ言語の構文解析に向いており、一方、自然言語の”形式化には向かない。
  • 巡回冗長検査 - Wikipedia

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

  • 動的計画法 - Wikipedia

    動的計画法(どうてきけいかくほう、英: Dynamic Programming, DP)は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果の記録を利用して全体の問題を解く手法を総称してこう呼ぶ。 細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。 帰納的な関係の利用:より小さな問題例の解や計算結果を帰納的な関係を利用してより大きな問題例を解くのに使用する。 計算結果の記録:小さな問題例、計算結果から記録し、同じ計算を何度も行うことを避ける。帰納的な関係での参照を効率よく行うために、計算結果は整数、文字やその組みなどを見出しにして管理される。 「動的計画法 (dynamic programming)」という言葉は1940年代にリチャード・E・ベルマンが最初に使いはじめ、1953年に

    動的計画法 - Wikipedia
    Itisango
    Itisango 2020/03/15
    “近年は色々なプログラミング言語がメモ化を言語レベルでサポートしている。その機能を利用した場合、より簡単に書ける場合がある。例えば Groovy の場合、@Memoized を付けることでメモ化する”
  • ファジィ論理 - Wikipedia

    ファジィ論理(ファジィろんり、英: Fuzzy logic)は、1965年、カリフォルニア大学バークレー校のロトフィ・ザデーが生み出したファジィ集合から派生した[1][2]多値論理の一種で、真理値が0から1までの範囲の値をとり、古典論理のように「真」と「偽」という2つの値に限定されない[3]ことが特徴である。ファジィ論理は制御理論(ファジィ制御)から人工知能まで様々な分野に応用されている。 ファジィ論理と確率論理は数学的に似ており、どちらも0から1までの値を真理値とするが、概念的には解釈の面で異なる。ファジィ論理の真理値が「真の度合い」に対応しているのに対し、確率論理では「確からしさ」や「尤もらしさ」に対応している。このような違いがあるため、ファジィ論理と確率論理では同じ実世界の状況に異なるモデルを提供する。 真理値と確率が0から1の範囲の値をとるため、表面的には似ているように思われる。例

    ファジィ論理 - Wikipedia
  • エラトステネスの篩 - Wikipedia

    この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方) 出典検索?: "エラトステネスの篩" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2019年6月) エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がついている。

    エラトステネスの篩 - Wikipedia
  • メルセンヌ・ツイスタ - Wikipedia

    メルセンヌ・ツイスタ (Mersenne twister、通称MT) は擬似乱数列生成器 (PRNG) の1つである。従来の疑似乱数列生成手法にある多くの欠点を克服し、高品質の疑似乱数列を高速に生成できるものとして、1996年に松眞と西村拓士によって国際会議で発表された(1998年1月に論文掲載)。考案者らによる実装が修正BSDライセンスで公開されている。 「メルセンヌ・ツイスタ」は厳密にはある手法に基づいた乱数列生成式(あるいは生成法)の族を指し、内部状態の大きさや周期は設定可能である。以下の長所と短所では、メルセンヌ・ツイスタ自体、よく使われている生成法のMT19937、さらにその実装について、区別することなく述べている。 219937-1 (≒4.315×106001) という長い周期が証明されている。 この周期は、名前の由来にもなっているように(24番目の)メルセンヌ素数であり、

  • ガウス=ルジャンドルのアルゴリズム - Wikipedia

    この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方) 出典検索?: "ガウス=ルジャンドルのアルゴリズム" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2016年3月) ガウス=ルジャンドルのアルゴリズム(英語: Gauss–Legendre algorithm)は、円周率を計算する際に用いられる数学の反復計算アルゴリズムである。円周率を計算するものの中では非常に収束が速く、2009年にこの式を用いて2,576,980,370,000桁(約2兆6000億桁)の計算がなされた[1]。 このアルゴリズムはカール・フリードリヒ・ガウスとアドリアン=マリ・ルジャンドルがそれぞれ別個に研究したものである。これは

    Itisango
    Itisango 2010/09/11
    "2009年にこの式を用いて2,576,980,370,000桁(約2兆6000億桁)の計算がされた。"
  • 竹内関数 - Wikipedia

    再帰的に定義される、3個の引数 x, y, z をとる次のような関数である。 特に変わる所は無いがLisp版[1]も参照のこと。定義からわかるように処理を次々にたらい回しにしていくことから、たらいまわし関数[2]、たらい関数 (Tarai function) とも呼ばれる(後述のマッカーシー版との混同を避けるためこの名で呼ばれることのほうが多いが、こちらの定義のほうがオリジナルである。マッカーシー版を特にTak関数として区別する場合もある)。電電公社研究員(当時)の竹内郁雄が、1974年の夏前の頃、後述するような特性のある関数をあれこれ考えていた、ある日の午前に思いついたものである[3]。竹内関数と命名したのは野崎昭弘である[4]。 特性として、よくベンチマークに使われる関数であるフィボナッチ数を何の工夫もなく計算するいわゆるダム(dumb)フィボナッチと比較して、大きな数の計算が必要ない

  • マルコフ連鎖 - Wikipedia

    この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方) 出典検索?: "マルコフ連鎖" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2018年1月) マルコフ連鎖(マルコフれんさ、英: Markov chain)とは、確率過程の一種であるマルコフ過程のうち、とりうる状態が離散的(有限または可算)なもの(離散状態マルコフ過程)をいう。また特に、時間が離散的なもの(時刻は添え字で表される)を指すことが多い[注釈 1]。マルコフ連鎖は、未来の挙動が現在の値だけで決定され、過去の挙動と無関係である(マルコフ性)。各時刻において起こる状態変化(遷移または推移)に関して、マルコフ連鎖は遷移確率が過去の状態によらず、

  • 1