チューリング完全 - Wikipedia
チューリング完全（チューリングかんぜん、英語: Turing-complete）とは、計算理論において、ある計算のメカニズムが万能チューリングマシンと同じ計算能力をもつとき、その計算モデルはチューリング完全あるいは計算完備であるという。 チャーチ＝チューリングのテーゼによれば「計算可能関数」は、それを計算しようとする計算モデルがチューリング完全であれば計算できる。 一般的なプログラミング言語の背景にある計算モデルの多くはチューリング完全である。一見単純な機能しか持たない言語がチューリング完全な例としては、Lazy K、Brainfuckなどがある。究極的に単純な計算モデルとしては「ウルフラムの2状態3記号チューリングマシン（英語版）がチューリング完全であると証明されている。 チューリング完全かどうかという事は、計算可能性理論の問題である。計算複雑性の分野の問題である時間や記憶容量の消費量に
バイトニックソート - 高速化プログラミング
高速化プログラミング トップページページ一覧メンバー掲示板編集 バイトニックソート 最終更新： highcalc 2010年07月25日(日) 14:43:05履歴 Tweet 以下の手順で要素交換を行うことで、ソートが完了する。 「昇順＋降順のバイトニック列」にする。 2^n･･･2^0間を昇順（降順）で比較する。 メリット それぞれの交換は独立に行うことができるので並列化が容易 交換回数が要素数で決まるので終了判定が不要 デメリット 要素数が2^nでない場合にはダミーデータの追加が必要 Bitonic sort http://www.t-pot.com/program/90_BitonicSort/index.... ソートの比較 http://jyoken.net/2005/kenpatsu/enari_oraf/ 分岐しないソート http://www.emit.jp/prog/p
やねうらお将棋講座 その1 - やねうらおブログ(移転しました)
アマ初段ぐらいの知り合いに将棋を教えようと思って資料作ってたのだけど、こういうの興味のある人が居るかも知れないので、体裁を整えて一部を公開する。続きははてブが10個以上ついたら公開しようとも思うが、たぶんつかない。 ■ 遠方駒 遠方への利きのある駒(飛・角・香)をここでは遠方駒と呼ぶ。 ■ ピン(pin)について 次図のように遠方駒で玉が間接的に狙われているとき、その中間にある駒(次図の３ニの金)は移動させられないので、この状態を「(３ニの金が)ピンされている」と表現する。 ピンされている場合でもその遠方駒の利きの方向には移動できる。(上図の３ニの金を４ニに移動させるのはすぐに飛車で取り返されるが、手としては合法手だと言う意味で。) ■ ピンされている駒は取られる ピンされているとその駒を動かせないので、上図で４一銀や４三銀、４四桂などとピンされている駒に利きを足されると、ピンされている駒
GPU(オクルージョンクエリ)による衝突判定はやっぱすごい - 日記名思いつかない
おいこれマジで凄いぞ。 これが全然一般的に広まってないのはおかしいんじゃないのか。 本当に万能な衝突判定ライブラリができちゃうと思うんだが。 描画関数そのものがパラメータとなって判定できるってこれ以上無いほど理想的ではないのか。 まあ欠点もあるにはあるが、横スクロールアクションや横or縦STGを作る分には万能だ。 http://marupeke296.com/COL_main.html このURL先の内容が全然わからなくても正確な3Dの衝突判定ができてしまうのだ。 信じられん。 まあ、OpenGLなりDirectXのグラフィクシステムを良くわかってないとだめだけどね。 どんな形状のモデルを作ろうが衝突判定してくれるとか ゲーム作るの楽になりすぎだろ。 ゲームプログラミングのためのリアルタイム衝突判定 作者: Christer Ericson,中村達也出版社/メーカー: ボーンデジタル発売日
昔のドット絵がくっきり、なめらかに蘇る「魔法の技術」とは
将来的にはゲームへの応用も？ まずはこちらの2枚の画像をご覧下さい。片方は昔懐かしいドット絵のキャラクター。もう片方は、その元になったイメージイラスト……に見えますが、そうではありません。 実は右側のイラストは、左のドット絵をもとに、特殊なスムージング処理を行い、生成したもの。元のドット絵ではカクカクだった輪郭線がくっきり、なめらかになり、まるでIllustratorで描いたかのような、自然なイラストに仕上がっています。 海外ニュースサイト「Extreme Tech」が伝えるところによれば、この技術は、Microsoft Researchとヘブライ大学が共同で開発したもの。ビクセルデータのスムージングという点だけを見れば、Illustratorなどにも同様の機能はありましたが、こちらはよりドット絵に適したアルゴリズムとなっているのが特徴。従来のスムージング処理が、すべてのドットを「等しく重
4chan BBS - Genius sorting algorithm: Sleep sort
1 Name: Anonymous : 2011-01-20 12:22 Man, am I a genius. Check out this sorting algorithm I just invented. #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait example usage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7 2 Name: Anonymous : 2011-01-20 12:27 >>1 Oh god, it works. But I don't like to wait 218382 seconds to sort '(0 218382)
乱択アルゴリズム - Wikipedia
乱択アルゴリズム（らんたくアルゴリズム）、ランダム・アルゴリズム（英: randomized algorithm）または確率的アルゴリズム（かくりつてきアルゴリズム、（英: probabilistic algorithm）は、その論理の一部に無作為性を導入したアルゴリズムである。通常のアルゴリズムでは自然数を順番にあてはめるような決定的な部分で、乱数による非決定的な選択を入れることで、「平均的に」よい性能を実現することを目的とすることがある。形式的には、乱択アルゴリズムの性能はランダムビット列で決定される確率変数となる。その期待値を期待実行時間[1]と呼ぶ。最悪の場合に関して「無視できる」ほどに低い確率であることが、一般に、この類のアルゴリズムが効果的である要件となる。 n 個の要素からなる配列から「a」という要素を探す問題を考える。この配列の各要素は半分が「a」で残りが「b」である。単純
たった3パターン覚えるだけ！ルービックキューブ六面解法のコツ | nanapi [ナナピ]
2020年8月31日(月)をもちまして、nanapiに関わるすべてのサービスは終了いたしました。 nanapiは、2009年のサービス開始より「みんなで作る暮らしのレシピ」という考えのもと、ユーザーの皆さまに生活に関する様々な「ハウツー」を投稿していただく投稿型ハウツーサービスとして運営してまいりました。 約11年間にわたって皆さまからご支援をいただきサービスを継続できたこと、nanapi編集部一同、心より御礼申し上げます。 掲載されていたコンテンツなどのnanapiについてのお問い合わせは、nanapi@supership.jp までお願いいたします。 長きに渡りnanapiを応援してくださり、本当にありがとうございました。
![たった3パターン覚えるだけ！ルービックキューブ六面解法のコツ | nanapi [ナナピ]](https://cdn-ak-scissors.b.st-hatena.com/image/square/5993849edc8012df3c55024258207de74e7902dd/height=288;version=1;width=512/https%3A%2F%2Fp1-dd40651e.imageflux.jp%2Fr%2F2017%2F12%2F13%2F18%2Fd780d8d5-20c5-41a8-9b7c-2c46a94d571b.jpg)
Chromeがバイナリ差分で新アルゴリズム実装 － ＠IT
2009/07/17 グーグルのChromeチームは7月16日、Chromeの自動アップデートで使われるバイナリアップデートに新たなアルゴリズムを実装したことを明らかにした。実際の例として、実行形式のフルアップデートで10MBの容量が必要だったものが、従来の差分方式で704KB、今回発表した新方式では78KBにまで縮小したという。 Chromeには自動アップデートの仕組みが組み込まれており、脆弱性の報告などがあると、これに対応するパッチを当てたバージョンをChromeユーザーにプッシュすることができる。これにより攻撃者が脆弱性を利用する時間が短くなるため、安全性が高まる。 セキュリティパッチなどは、ソースコードレベルで数行の変更であることも多いため、新バージョンの実行バイナリを丸ごとユーザーに送りつける代わりに、差分だけ送ることで転送量を抑えることができる。これまでChromeチームではb
レインボーテーブル - Wikipedia
レインボーテーブル (rainbow table) は、ハッシュから平文を得るために使われるテクニックの一つである。特殊なテーブルを使用して表引きを行うことで、時間と空間のトレードオフを実現している。 以降では、このテクニックの元となっているアイディアについて説明する。 3 種類の還元関数を使った簡単なレインボーテーブルの例 レインボーテーブルは「あるハッシュ値に対して総当たり攻撃を行った際の計算結果を、別のハッシュ値を攻撃する際に使用する」というアイデアに端を発する。例えば、平文 Pi (i = 1, 2, ...) と、それらをハッシュ化した値 Ci をテーブルに格納しておき、このテーブルを逆引きすればハッシュ値から対応する平文が得られる。 ただし、この方法では、得られた平文とハッシュ値とのペアを全て記録しておく必要があり、実現には莫大な記憶領域を必要とする。 使用する記憶域の量を削減
知ってる？ クレジットカード番号の意味と暗算認証術
知ってる？ クレジットカード番号の意味と暗算認証術2011.01.24 12:0029,477 satomi 暗算で偽造カード見分けられるなんて...知らなかった！ 毎日のように使うクレジットカード。丸暗記して時間セーブしてる人も、あの数字16桁の意味までは知らないんじゃ？ 16個の数字にはそれぞれ意味があるんですよ。米国で人気のオンライン資産管理サービス｢Mint｣がズバリ図解してくれました！ （図の訳） 1）最初の1桁：主要産業識別子 （MII:Major industry identifier）。カード発行者の業界を表します。 0 予備 1、2 航空 3 旅行・娯楽 4、5 銀行・金融 6 商品輸送・銀行 7 石油 8 通信 9 国ごとの割り当て分 2）MIIを含む最初6桁：発行者識別番号（IIN:Issuer Identifier Number）。カード発行者の身元を表します。 [
GameInternals - Understanding Pac-Man Ghost Behavior
GameInternals aims to spread knowledge of interesting game mechanics beyond the game-specific enthusiast communities. Each post focuses on a specific game mechanic that would normally only be known to high-level players of a particular game, and attempts to explain it in a manner that would be understandable even by readers unfamiliar with that game. GameInternals articles were researched and writ
【レポート】GNU grepが高速な理由 | エンタープライズ | マイコミジャーナル
FreeBSD - The Power To Serve why GNU grep is fast (なぜGNU grepは高速なのか)といったタイトルの興味深いメールがFreeBSD開発者メーリングリストに投函された。メールを出したのはGNU grepのオリジナル開発者であるMike Haertel氏。Mike Haertel氏はFreeBSDユーザでもあり、FreeBSD開発者メーリングリストで興味深いやりとりがあったため、このメールを流したとしている。Mike Haertel氏の紹介する内容はgrep(1)の実装のみならず、高速な文字列処理を実現するひとつの方法として参考になる。紹介されているGNU grep高速さの秘訣は次のとおり。 GNU grepは入力バイトのすべてをチェックするようなことは避けている。 GNU grepはバイトごとに適用する操作を極力最小限に減らしている。 G
チェインハッシュ法
チェインハッシュ法について解説します。 ハッシュについての基本的な事柄については、こちらに載せてあります。 チェインハッシュ法は、ハッシュで問題となっていた、 計算したキーのハッシュ値が同じになる要素については、格納できないという問題を、 同じハッシュ値のものを格納するとき、チェインのようにつないで格納する ことで解決することから、チェインという名前になっています。 まず例として、ハッシュで格納したハッシュの状態を見てください。 key value +--------+-------------+ (0) | Albert | 855-69-7889 | +--------+-------------+ (1) | empty | empty | +--------+-------------+ (2) | Ciel | 854-37-4645 | +--------+----------
yebo blog: クヌース教授は間違っていた
2010/06/15 クヌース教授は間違っていた Slashdotによれば、この数十年間、クヌース教授をはじめとするコンピュータ科学者が最適としてきたアルゴリズムを10倍高速にする方法をPoul-Henning Kamp (PHK) というハッカーが見付けたという。その論文タイトルは「You're Doing It Wrong (あなた達のやっている事は間違っている)」で、ACM Queueに掲載されている。別にクヌース教授の考えが間違っているわけではなく、アルゴリズム的には正しいが、実用レベルでは、OSには仮想メモリがあり、VMと干渉しないようにすれば簡単に高性能なシステムが作れる。従来の考え方はモダンな計算機を考慮に入れていないので、現実的には不適合を起こしている。具体的にはヒープにBツリーの要素を取り込んだBヒープというデータ構造を使うことで、バイナリヒープの10倍のパフォーマンスを
PS3とMD5ハッシュ値衝突の脆弱性との"危険な"関係 - SHA-2を代替関数に | エンタープライズ | マイコミジャーナル
米SymantecのSecurity Response Blogによると、最近、full-disclosureメーリングリストに興味深い投稿があったという。これはMarc Stevens氏、Arjen K. Lenstra氏、Benne de Weger氏らによって共同で発表された"Predicting the winner of the 2008 US Presidential Elections using a Sony PlayStation 3"であり、そのタイトルが意味するがごとく、ソニーのPS3を計算に使用した2008年米国大統領選挙の結果予測であるかに見えた。しかしながら、その実情は異なり、特定のファイルにMD5アルゴリズムを使用してハッシュ値を算出し、それを使用した一意性の保証はもはや意味がないことを示すことにあったという。すなわち、もはやMD5アルゴリズムを使用したハッシ
第20回世界コンピュータ将棋選手権に鬼将会登場 - 三軒茶屋 別館
ハチワンダイバー 9 (ヤングジャンプコミックス) 作者: 柴田ヨクサル出版社/メーカー: 集英社発売日: 2008/11/19メディア: コミック購入: 3人 クリック: 21回この商品を含むブログ (92件) を見る まともな将棋なんて一局もないっ！これはっ… 鬼将会は”切れ負け”に追い込んで勝ってる… お互いたった２分という持ち時間… 三沢九段は…時間が切れて負けている 持ち時間が切れたら秒読みナシで即負けというルールでは真剣師ならではの別の将棋が出現する 将棋が強いのは三沢九段 常に優勢なのは三沢九段 ところが真剣師はギリギリで受ける ただ受ける ムダに受ける もっさりした筋悪な受け 攻める方が攻め疲れて１秒でも２秒でも多く時間を使って考えればそれで十分 将棋は優勢なのに”２分切れ負け”という括りの中で プロが負ける （『ハチワンダイバー』９巻ｐ120〜122より） 2010年5月
コンピュータに画像はどう見えるのか？ その4 傾き補正編 - 電子化
本日のお題画像： *1 非常に分かりにくいのですが、お題画像の左側、 この画像、左に0.8度くらい傾いています。ウソだとお思いなら、分度器で測ってみてください。 大量のスキャン画像を処理する場合、その都度、分度器で測定するわけには行きません。 そこで登場するのが、今までに何度か登場しているHough変換（ハフへんかん）です。 すでに、http://d.hatena.ne.jp/denshikA/20100420で確認したとおり、「赤枠内の交差点の位置だけで、緑枠内に線が、どのあたりに、どんな傾きであるのか、分かってしまう」わけです。 今日は、傾きに注目してみましょう。とりあえず、以下の4つを見てください。 うすうすお分かりのように、緑枠の縦っぽい線が左に45度づつ傾くと、赤枠内の交差点が右に1/4づつ進みます。 つまり、赤枠内の横軸は、ゼロから180までをあらわしていて、交差点の位置から、
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
How to Implement World Fastest Grep.
wonderfl build flash online | 面白法人カヤック