ゲームプログラミング - ゲーム創作場
[2013.10.05] 点と平面の距離 平面上の最近点 [2013.09.29] 点と三角形の内外判定 点と三角形の当たり判定をします。 [2013.09.28] ポリゴンの表裏判定 OPenGLとDirectXで混乱した。結局一緒なのかー。 [2013.09.27] 十字キーと８方向キーの方向判定 スマホで仮想十字キー作ったりドラッグ方向の判定にどうぞ。 [2013.09.26] ２線の交点を求める方法 ３次元でも２次元でも大丈夫な２線の交点を求める方法です。 [2013.02.16] お詫びと訂正。 斜方投射で説明していた式に誤りがありました。ご指摘いただいた方ありがとうございます。 http://www.sousakuba.com/Programming/algo_dandoukeisan2.html 旧 新 ルートの中のプラスマイナスが逆でした。 [2012.11.30] 平面と
ymuto109の日記 - AdaBoostに関する調査
AdaBoost は Freund と Schapier によって提案された． 学習データが外れ値などのノイズをあまり含まなければ，高い判別能力を示す． 変種として Discrite AdaBoost, Gentle AdaBoost, Real AdaBoost, Logit AdaBoost, Modest adaBoost などがある． 損失関数 上記の AdaBoost, Logit Boost, MadaBoost は損失関数によって異なるのみ（？） (http://www.msi.co.jp/vmstudio/materials/files/misc/boosting.ppt を見よ） ブースティングの案内ページ http://ibisforest.org/index.php?%E3%83%96%E3%83%BC%E3%82%B9%E3%83%86%E3%82%A3%E3%83
ROC曲線
試験の点数から○○大学に合格（T）か不合格（F）かを予測したいときや，検査値から病気（T）か健康（F）かを判断したいときなどがあります。要するに，与えられた値から，真（TRUE）か偽（FALSE）かを判断したいわけです。 例として右の表のような場合を考えましょう。 与えられた値をどこで切っても，TとFは完全には分離できません。例えば11で切って，11以上を陽性（positive），11未満を陰性（negative）とした場合，10個のTのうち5個がpositiveに入りますので，true positive（真陽性）の割合は0.5です。また，5個のFのうち1個がpositiveに入りますので，false positive（偽陽性）の割合は0.2です。そこで，(0.2, 0.5) をプロットします。このように，区切る値（閾値，カットオフポイント）をいろいろ変えて，横軸にfalse positi
第2回 DES暗号化
今回は長らく暗号化技術の標準規格として利用されていたDESについて解説する。DESはすでに利用は非推奨となっているが、DESの制定を契機にさまざまな暗号技術や解読技術が進化するなど、その存在意義は大きい。 前回は暗号化技術の基礎について見てきた。今回は代表的な共通鍵暗号方式であるDESについて取り上げる。 DESは安全性に対する懸念から、すでに現在では非推奨の暗号化アルゴリズムとなっている。しかし、標準規格化された暗号化アルゴリズムであることから広く普及し、その後の暗号化アルゴリズムの研究・開発などにも大きく貢献した。そのため、最新の暗号化アルゴリズムを知る上でもDESを理解しておくべきだ。 DESとは 「DES（Data Encryption Standard）」は、1977年に米国商務省標準局（NBS：National Bureau of Standard。現NIST：National
無題ドキュメント
3.1 DES暗号（共通鍵暗号） 3.1.1 DES暗号とは DES暗号は1977年にアメリカのANSIが応募したデータ暗号化規格公募の際,IBMから提出されたものに修正を加えたものです． DESは56bit長の暗号化鍵を使い 64bitの平文ブロックごとに暗号化するブロック暗号です．また暗号化,復号化に使用する鍵が同じため,共通鍵（秘密鍵）暗号方式と呼ばれる暗号方式です． 3.1.2 アルゴリズム DESの暗号化アルゴリズムはラウンドという単位で行われます．一つのラウンドでは転置 シフト演算 換字／選択排他的論理和という作業が行われます．ラウンドは全部で16回あります．それぞれの処理について順次説明しています． 3.1.3 転置 転置とはビット並び順を転置表を用いて入れ替えることです．例えば下の図,初期転置表の左上の58とは転置前58bit目のbitが転置後1bit目になることを示します
パワー法 - Google 検索
• 大規模問題：逆反復法，同時反復法（べき乗法の拡張）. Page 8. Eigen. 8. • 行列の固有値問題. • べき乗法. Page 9. べき乗法（Power Method）. 9. Eigen. 絶対値最大の ...
ハル研究所プログラミングコンテスト2015 - hirokazu1020の日記
応募最終日では1位と同スコア同実行時間で2位でした。 ・方針 ある時間帯に配達する荷物を決めたときの最小コストは明らかに巡回セールスマン問題(TSP)の応用で解ける。 それぞれの荷物をどの時間帯に割り当てるかは愚直に探索するとO(4^n)で間に合わないが(時間帯,残りの荷物集合)を状態として持つDPでbit演算で部分集合を列挙するテクを使うとO(3^n)で解ける。 最適解を求めることは出来たので以降はずっと高速化。 ・探索パターンの削減 自明な事実として時間帯0と時間帯1の荷物集合を入れ替えてもコストは変わらないのでこのような重複パターンの探索を避ける。 例として最大ケースである時間帯指定のない荷物が16個ある場合を考える。 未割り当ての荷物が16個の場合、4つの時間帯はどれも荷物が割り当てられていない。荷物集合はどの時間帯に配達してもコストは変わらないので、1つ目の荷物についてはどの時間
最短経路問題 - Wikipedia
グラフ理論における最短経路問題（さいたんけいろもんだい、英: shortest path problem）とは、重み付きグラフの与えられた2つのノード間を結ぶ経路の中で、重みが最小の経路を求める最適化問題である。 2頂点対最短経路問題 特定の2つのノード間の最短経路問題。一般的に単一始点最短経路問題のアルゴリズムを使用する。 単一始点最短経路問題 (SSSP：Single Source Shortest Path) 特定の1つのノードから他の全ノードとの間の最短経路問題。この問題を解くアルゴリズムとしては、ダイクストラ法やベルマン-フォード法がよく知られている。 全点対最短経路問題 (APSP : All Pair Shortest Path) グラフ内のあらゆる2ノードの組み合わせについての最短経路問題。この問題を解くアルゴリズムとしては、ワーシャル-フロイド法が知られている。 このよう
ActionScript入門Wiki@rsakane - 塗りつぶしアルゴリズム(スキャンライン - シードフィル編)
おすすめリンク | 価格比較@price | オークション相場@price | デジカメプリント | 年賀状 | ましかくプリント | @wiki - 無料レンタルウィキサービス | プライバシーポリシー| 関連ページ| 関連ホットワード
バケツ プログラム - Google 検索
2022/05/14 · さて、プログラミング言語には、バケツにいれるデータを厳しく取り決めているものがある。つまり、このバケツにはコレ、あのバケツにはアレというぐあいで ...
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意していま
領域内高速塗りつぶし法 / High-speed Region Fill Method – WAISJP
図１のような閉じた領域の内部を高速に塗りつぶすアルゴリズムと、プログラム例を示す Why? かつて作っていた『お絵描き掲示板』に、「塗りつぶし」コマンド（＝お絵描きソフトで、ペンキ缶のアイコンのやつ） をつけようかなと思い、そのやり方を考えてみました。そしたら、とてもいいロジックが出来たので紹介することにしました。このロジックは、私が今まで調べたもののうち、どんなものよりも高速で、 かつ単純なものになっています。 （ただし、これは2000年ごろに作ったものですし、もっと速いやり方があるかもしれません！）。 ではさっそくそのロジック（アルゴリズム）を説明します。 原理 一般的な塗りつぶしのアルゴリズムは以下のようなもの。 これは、走査線一本ごとに境界を探して行く方法なので、 「スキャンラインアルゴリズム」とか「走査線アルゴリズム」とか呼ばれている。 処理ステップ 前提として、図２のような、閉
ロベールのＣ＋＋教室 - 第３１章 出鱈目？ 規則的？ -
今回はちょっと趣向を変え、疑似乱数の作り方について話します。乱数については第１部第７５章でやりました。この時、「疑似乱数はある初期値を元に計算を行って生成されます」といいました。今回はその方法の１つ「線形合同法」について話します。 疑似乱数生成ルーチンを自作すると、いろいろ面白いこともできるでしょう。 では、今回の要点です。 ｘ ｉ＋１＝（ａｘ ｉ＋ｃ） ＭＯＤ Ｍという数列は乱数っぽく見える。 合同法乱数は周期性を持っている。 合同法乱数は１個ずつ使えばランダムだが、組にして使うとランダム性が低い。 合同法乱数は上位ビットを取り出してから使うとよい。 では、いってみましょう。 一見でたらめな数を計算で出すにはどうすればいいでしょうか？ 普通の四則演算などを行っていると、何か規則性の見える結果がでてきます。かといって、ややこしい計算をしてでたらめな数がでてきても、速度が欲しいときには実用的
xorshift 周期 - Google 検索
周期の特定. 編集. シード値を128bitの二元横ベクトル β {\displaystyle \beta }. {\displaystyle \beta }. 、現在の状態から次状態への二元遷移行列を T {\displaystyle T}.
メルセンヌ・ツイスタ - Wikipedia
メルセンヌ・ツイスタ (Mersenne twister、通称MT) は擬似乱数列生成器 (PRNG) の1つである。1996年に国際会議で発表されたもので（1998年1月に論文掲載）松本眞と西村拓士による。既存の疑似乱数列生成手法にある多くの欠点がなく、高品質の疑似乱数列を高速に生成できる。考案者らによる実装が修正BSDライセンスで公開されている。 「メルセンヌ・ツイスタ」は厳密にはある手法に基づいた乱数列生成式（あるいは生成法）の族を指し、内部状態の大きさや周期は設定可能である。以下の長所と短所では、メルセンヌ・ツイスタ自体、よく使われている生成法のMT19937、さらにその実装について、区別することなく述べている。 219937-1 (≒4.315×106001) という長い周期が証明されている。 この周期は、名前の由来にもなっているように（24番目の）メルセンヌ素数であり、保証され
メルセンヌ数 - Wikipedia
メルセンヌ数（メルセンヌすう、英: Mersenne number）とは、2の冪よりも 1 小さい自然数、すなわち 2n − 1（n は自然数）の形の自然数のことである。これを Mn で表すことが多い。メルセンヌ数を小さい順に列挙すると となる。メルセンヌ数は2進法表記で n 桁の 11⋯11、すなわちレピュニットとなる。 Mn = 2n − 1 が素数ならば n もまた素数であるが、逆は成立しない (M11 = 2047 = 23 × 89)。素数であるメルセンヌ数をメルセンヌ素数（メルセンヌそすう、英: Mersenne prime）という。なお、「メルセンヌ数」という語で、n が素数であるもののみを指したり[1]、さらに狭義の意味でメルセンヌ素数を指す場合もある[注釈 1]。 Mn が素数ならば n もまた素数であることは、次の式から分かる[2][3]： 2ab − 1 = (2a
すごい乱数生成アルゴリズム「xorshift」 - Pashango’s Blog
みなさん、こんにちは、今回は乱数の話です。 特に複数機種でのコンシューマ機でゲームを開発をしていると、機種間で乱数値を統一するために乱数生成アルゴリズムを自作しますよね。 そこでよく使われるアルゴリズムが「線形合同法」です、内容は至って簡単で、以下の漸化式を使います。 A,B,Mは定数で、どの値が入るかは処理系依存です。 例えばUnixなどの処理系ではA=1103515245,B=12345,M=2147483647などが入ります。 C言語ですと以下のようになります。 static unsigned int x=1; void srand(unsigned int s) { x=s; } unsigned int rand() { x=x*1103515245UL+12345UL; return x&2147483647UL; } この「線形合同法」は計算が簡単で高速ですから、いろいろな環
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
数理勢の知らないグラフ理論1:オイラー回路 - okunoin’s blog
http://www.arch.cs.kumamoto-u.ac.jp/~kuga/cad/crypt/des/
ActionScript入門Wiki@rsakane - アルゴリズム