トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター
トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター：最強最速アルゴリズマー養成講座（1/4 ページ） プログラミングにおける重要な概念である「探索」を最速でマスターするために、今回は少し応用となる探索手法などを紹介しながら、その実践力を育成します。問題をグラフとして表現し、効率よく探索する方法をぜひ日常に生かしてみましょう。 まだまだ活用可能な探索 前回の「知れば天国、知らねば地獄――『探索』虎の巻」で、「探索」という概念の基礎について紹介しました。すでに探索についてよく理解している方には物足りなかったかと思いますが、「問題をグラフとしてうまく表現し、そのグラフを効率よく探索する」というアルゴリズマー的な思考法がまだ身についていなかった方には、得るものもあったのではないでしょうか。 前回は、「幅優先探索」と「深さ優先探索」という、比較的単純なものを紹介しましたが
GNU grep 2.18リリース: 10倍速くなったと思ったら今度は200倍遅くなっていた | はむかず！
先日の記事 いまさらgrepが10倍高速化したのはなぜか が思わぬ閲覧数を稼いでしまい、トルコ語の知識を日本に広めるのに大きな貢献をしたような気がしますが、みなさんいかがお過ごしでしょうか。 実は先日の記事を書いた時にはすでに2.18がリリースされてたのだが、今回は2.17のときと違って日本の大手メディアが取り上げてなかったので、ついつい見落としていた。しかし実は2.18でも大きな変更が！！ リリースノート抜粋： grep -i in a multibyte, non-UTF8 locale could be up to 200 times slower than in 2.16. [bug introduced in grep-2.17] なんということでしょう。-iオプションでUTF8のときは2.17で10倍速くなっていたのだが、それ以外のマルチバイトロケールのときは200倍遅くなって
コンピュータを進化させてきた偉大なるアルゴリズムまとめ
By Kai Schreiber IT技術の進化のスピードには目を見張るものがありますが、それを支えているのはアルゴリズムと呼ばれる処理方法(技術的アイデア)です。さまざまなアルゴリズムの中でも、コンピュータの進化に革命的な影響をもたらしたとされる偉大なアルゴリズムは以下の通りです。 Great Algorithms that Revolutionized Computing http://en.docsity.com/news/interesting-facts/great-algorithms-revolutionized-computing/ ◆ハフマン符号(圧縮アルゴリズム) Huffman coding(ハフマン符号)は、1951年にデービッド・ハフマン氏によって開発されたアルゴリズム。頻出頻度の大小によって対戦するトーナメントツリーを考えて、ブロックごとに0と1の符号をもたせる
ウソつきっ娘論理プログラミング - 小人さんの妄想
全ての問題にかわいい女の子が出てくる、「登場する人物の発言を手がかりに問題を解くタイプ」の論理パズル集。 萌え萌えウソつきッ娘論理パズルI 作者: 小野田博一出版社/メーカー: イーグルパブリシング発売日: 2009/09/25メディア: 単行本（ソフトカバー）購入: 5人 クリック: 172回この商品を含むブログ (7件) を見る * 出版社での紹介 >> http://www.tp-ep.co.jp/ep-hp/top.html 第１問目は、こんな感じです。 * 第１問目の画像イメージ >> http://www.tp-ep.co.jp/ep-hp/images/top/ronripazuru_01.jpg 【Q1】水泳大会 水泳大会で、この４人が１位から４位を獲得しました（同順位はありません）。 スタート前の予想は下のとおりで、３人が当たり、１人が外れました。 誰が何位だったのでしょ
スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す（C ） | 配電盤
魔方陣の解の列挙は並列化しやすそうな問題ですが、ここでの方針では、探索効率を上げるためには条件分岐が不可欠なので、（「数」を求めるだけだとしても）GPGPUでうまくやる方法がわかりません。そこで、CPUに載っているコアのみで並列化します（Xeon Phiなら簡単なのでしょうか→追記参照）。 一番外側の、0から(1<<25)-1まで変化する変数iのループをOpenMPで並列化します（schedule(guided)では遅くなります。schedule(auto)はVisual C++でサポートされたら試します）。変数iは上の図の緑の部分（カンで5個にしました）を各数5ビットで表現し、つなげたものです。マスに入りうる数は1から25までなので、5ビットというのはちょっと冗長ですが、とりあえずはよしとしましょう。 出力はバイナリ形式で、1つの解に25バイト使います（1つのマスに入る数を1バイトで表現
ＲＳＡのひ・み・つ - 小人さんの妄想
ＲＳＡとは、今日最も広く普及している公開鍵暗号です。 公開鍵暗号というのは、暗号をかける鍵と、暗号を解く鍵が異なっている暗号のことです。 普通に考えれば、かける鍵と解く鍵は同じでなければならないような気がします。 （かける鍵と解く鍵が普通に同じである暗号は「共通鍵暗号」と言います） ところが公開鍵暗号は、 ・暗号をかける鍵は暗号化専用で、解くことはできない。 ・暗号を解く鍵は復号化専用で、かけることはできない。 といった、なんとも不思議な仕組みなのなです。 なぜこんなことができるのか、秘密を探ってみましょう。 ■ 一巡する計算 普通の（物理的な）錠前は、同じ１本の鍵で開閉を行います。 なぜかというと、開ける動作を全く逆にしたものが、閉める動作になっているからです。 つまり普通の錠前は「一直線の往復」なのです。 もし、開ける鍵と閉じる鍵を別々にしたかったなら「一直線の往復」ではダメで、 「行
高校生がスーパーコンピュータを使って5×5魔方陣の全解を求めることに成功 | 筑波大学 計算科学研究センター
概要 筑波大学計算科学研究センターは、全国共同利用施設として、一般公募による「学際共同利用プログラム」※1を実施しています。平成25年度に、茨城県立並木中等教育学校4年次（高校1年）の杉﨑行優（すぎざき・ゆきまさ）君の申請が採択されました。杉﨑君は筑波大学計算科学研究センターの朴泰祐教授と共同研究を進めた結果、スーパーコンピュータ「T2K-Tsukuba」※2を使った並列計算により、5×5の魔方陣の全ての解を求めることに成功しました。 魔方陣とは、正方形のマス目に、縦・横・斜めの合計が同じになるよう数字を置いたものです。5×5の魔方陣の全解は2億7530万5224通りあることがすでにわかっています。杉﨑君は「枝刈り法」を改良した求解アルゴリズムを考案し、スパコンに並列計算させるためのプログラムを開発しました。朴教授は、並列データの収集や並列化に関する詳細なアドバイスを行いました。並列計算
いまさらgrepが10倍高速化したのはなぜか – はむかず！
最近GNU grepコマンドの最新バージョンがリリースされ、速度が10倍になったとのアナウンスがあった。それを聞いて、なんであんな枯れた技術に10倍もの高速化の余地があったのだろうと不思議に思った人も多いだろう。 ニュース記事：grepコマンド最新版、”-i”で10倍の高速化 本家のリリースノート：grep – News: grep-2.17 released [stable] 今回のリリースでは正確には、マルチバイトロケールで、-iオプション（–ignore-case、つまり大文字小文字を区別しないオプション）をオンにした時の速度が10倍くらいになったそうだ。 なぜそんなに速くなったのか？逆を言えば今までなぜそんなに遅かったのか？ そもそも、多くの日本人にとって「大文字小文字の区別」というと英語のアルファベットか、せいぜいフランス語とかドイツ語とかのアクサン記号・ウムラウトがついたものく
海辺の美女の問題を遺伝的アルゴリズムで解く - 小人さんの妄想
急いては事を仕損じる。 あわてて物事を取り決めてしまうと、後からもっと良いものが出てくることがある。 かといって、いつまでも慎重に見送っていたのでは、みすみすチャンスを逃してしまうこともある。 いったいどのタイミングで決断を下せば、最大の期待値を引き当てられるのか？ この問題は、秘書問題、あるいは、最良選択問題、海辺の美女の問題などと呼ばれていて、 幾つかのケースでは数学的に最適な答が知られています。 >> wikipedia:秘書問題 たとえば、海辺に２０人の美女がいたとして、順番に出会ってゆくものとします。 これぞと思った美女をデートに誘いたいのですが、 あまり早いうちに誘ってしまうと、後からもっといい女が出現するかもしれません。 かといって誘いを出さずに見送っていると、いい女を逃してしまいます。 誘いを出すのは１回だけで、もちろん後戻りはできません。 美女は必ず誘いに乗ってくれるもの
ディフィー・ヘルマン鍵共有の仕組み - 小人さんの妄想
２人の間で秘密の暗号通信を行うには、まず最初に２人だけが知っている共通のキーワード〜鍵を取り交わす必要がある。 しかし、２人が遠く離れていて、盗聴の危険性のあるインターネットでしか通信できないとしたら、 どうやって最初の鍵を取り交わすことができるか？ この難問を解決するアルゴリズムとして「ディフィー・ヘルマン鍵共有」が知られています。 >> wikipedia:ディフィー・ヘルマン鍵共有 あからさまに盗聴されている通信路だけを使って、２人だけの秘密を共有する・・・ そんな一見不可能に思える離れ業を、どのようにして実現するのでしょうか？ ディフィー・ヘルマン鍵共有（以下、ＤＨ法と略）の基本となる考え方は、以下の図から出発します。 いま、アリスとボブの２人が、２人だけの秘密の数字を共有したかったとしましょう。 まず、アリスが数字Ａを、ボブが数字Ｂを決めて、お互いに交換します。 そして、お互いに
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意していま
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
「群れ」の科学