コンピュータを進化させてきた偉大なるアルゴリズムまとめ
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通りあることがすでにわかっています。杉﨑君は「枝刈り法」を改良した求解アルゴリズムを考案し、スパコンに並列計算させるためのプログラムを開発しました。朴教授は、並列データの収集や並列化に関する詳細なアドバイスを行いました。並列計算
海辺の美女の問題を遺伝的アルゴリズムで解く - 小人さんの妄想
急いては事を仕損じる。 あわてて物事を取り決めてしまうと、後からもっと良いものが出てくることがある。 かといって、いつまでも慎重に見送っていたのでは、みすみすチャンスを逃してしまうこともある。 いったいどのタイミングで決断を下せば、最大の期待値を引き当てられるのか？ この問題は、秘書問題、あるいは、最良選択問題、海辺の美女の問題などと呼ばれていて、 幾つかのケースでは数学的に最適な答が知られています。 >> wikipedia:秘書問題 たとえば、海辺に２０人の美女がいたとして、順番に出会ってゆくものとします。 これぞと思った美女をデートに誘いたいのですが、 あまり早いうちに誘ってしまうと、後からもっといい女が出現するかもしれません。 かといって誘いを出さずに見送っていると、いい女を逃してしまいます。 誘いを出すのは１回だけで、もちろん後戻りはできません。 美女は必ず誘いに乗ってくれるもの
ディフィー・ヘルマン鍵共有の仕組み - 小人さんの妄想
２人の間で秘密の暗号通信を行うには、まず最初に２人だけが知っている共通のキーワード〜鍵を取り交わす必要がある。 しかし、２人が遠く離れていて、盗聴の危険性のあるインターネットでしか通信できないとしたら、 どうやって最初の鍵を取り交わすことができるか？ この難問を解決するアルゴリズムとして「ディフィー・ヘルマン鍵共有」が知られています。 >> wikipedia:ディフィー・ヘルマン鍵共有 あからさまに盗聴されている通信路だけを使って、２人だけの秘密を共有する・・・ そんな一見不可能に思える離れ業を、どのようにして実現するのでしょうか？ ディフィー・ヘルマン鍵共有（以下、ＤＨ法と略）の基本となる考え方は、以下の図から出発します。 いま、アリスとボブの２人が、２人だけの秘密の数字を共有したかったとしましょう。 まず、アリスが数字Ａを、ボブが数字Ｂを決めて、お互いに交換します。 そして、お互いに
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
「群れ」の科学