yebo blog: ルービックキューブはどんなポジションでも20回動かせば解決
2010/08/10 ルービックキューブはどんなポジションでも20回動かせば解決 Googleからコンピュータの空き時間として35CPU年を提供してもらい、ルービックキューブの全てのポジションにおける解法を調べたところ、どんなポジションでも20回動かせば解決できる事が分かったそうだ。神のアルゴリズム(ルービックキューブを解くアルゴリズム)が年々短くなってきているのが分かる。キューブの全てのポジションは43,252,003,274,489,856,000との事で、どうやってそれが分かったかというと、19,508,428,800ポジション毎の2,217,093,120セットに分類対称と集合(set covering)を使って解決すべきセットを55,882,296に抑えるそれぞれのポジションの最適解を見つけれなかったが、代わりに20以下の解決法だけを見つける約20秒で1つのセットを解決するプログ
コンピュータサイエンス史上最大の課題「並列処理による性能向上」～情報処理学会創立50周年記念全国大会の招待講演
「いま、並列処理の壁というコンピュータサイエンス史上最大の課題に直面しています。しかしこれはチャンスでもあります。新しい時代を切り開いていきましょう」。IBM名誉フェローのFran Allen氏は、昨日3月10日に行われた日本の情報処理学会創立50周年記念全国大会の招待講演の演壇からこんなメッセージを聴衆に投げかけました。 Fran Allen氏は、コンパイラやプログラミング言語が専門で、女性で初めてチューリング賞を受賞した人。今回の招待講演のためにわざわざ来日したと紹介されました。 講演のタイトルは「The Challenge of the Multicores」。ここからは、Allen氏の講演の内容を紹介しましょう。 （この講演は英語で行われたものです。内容にはできるだけ正確を期したつもりですが、理解不足のところや聞き取れなかったところもありました。もし誤解や不正確なところがありました
就職活動インタビュー反省記録 with Yahoo
Yahoo とのインタビューは、明らかに失敗だったとインタビュー中に分かったケースです。というのも、電話インタビューの最中に私のプリペイドの携帯の残高がゼロになり、会話が 8 分も途切れてしまったからです。前回残高を追加したのが夏学期の途中だったので、残高をチェックするのを忘れて、電話インタビューをしてしまいました。これは問答無用でアウトです ;( だって、interviewer からしてみれば、「おいおい、こっちは貴重な勤務時間を割いてインタビューしてるのに、残高ゼロで会話できませんってどういうことだよ。スキル以前の問題じゃないか」て思いますもんね、普通。 このインタビューに関しては、反省すべき点は火を見るより明らかなので、以降は Yahoo にアプライした経緯やインタビューで聞かれた問題を紹介したいと思います。 私がアプライしたのは、Back End Engineer、Qualit
「ランキングアルゴリズムを1日当たり2回変更している」 Google Marissa Mayer ::SEM R (#SEMR)
「ランキングアルゴリズムを1日当たり2回変更している」 Google Marissa Mayer グーグル・マリッサ・メイヤーのインタビュー記事。1日2回と小さな改良をランキングアルゴリズムに加えていき、検索をユーザにとってより便利なものにしていく。 公開日時：2009年11月12日 13:27 米Google VP・Marissa Mayer氏のインタビュー記事。ユーザがわかる範囲で週あたり2～5の変更を加えているほか、ランキングアルゴリズムも1日2回ほどの割合で変更を加えていると答えている。日々小さな改良を加えて、検索をより便利なものにしている。 また、2007年5月から始まったユニバーサル検索は現在、全検索クエリの25%で表示されているとも説明。 We have two, three, five changes every week that are visible to the e
驚くべきテクニックで「スーパーマリオ」をクリアしていく人工知能
ゲームがゲームをクリアする時代に？ 「New スーパーマリオブラザーズ Wii」で、初心者向けに新しく搭載されるという噂の「スキップ機能」は、もしかしたらこんな感じなのかもしれません。 土管や砲台、敵キャラクターなど多くの障害物が設置されたコース上を、驚くべきスムーズさで、マリオがひたすら右へ右へと進んでいくこちらの動画。迫りくる敵の間を難なくすり抜けたり、パックンフラワーの間をギリギリでくぐり抜けていったりと、確かに上手いプレイであることは分かるのですが、何かがちょっと違うことに気付いたでしょうか。 実はこれ、すべてAI制御による自動プレイ。マリオの前方に表示されている赤い放物線は、この先進むルートの候補を表したもので、どうやらこの中から安全で、なおかつ最短でゴールにたどり着けるルートを自動で選択するようプログラムされているようです。途中、何度かはヒヤリとさせられる場面もあるのですが、き
きまぐれ日記: 「読めてしまう」コピペがなぜ読めてしまうのか
http://www.asks.jp/users/hiro/59059.html http://www.itmedia.co.jp/news/articles/0905/08/news021.html 最初読んだとき、違和感なく読めてしまったのですが、よくよく見てみると、そんなトリックがあったのですね。 さて、この「読めてしまう」がなぜよめてしまうのでしょうか？ 人間の言語モデルの単語パープレキシティは、約100ぐらいであると言われています。どういうことかというと、 人間が文章を読んでいるときに、次の単語を過去の文章から推測するのは 1/100 程度の 確率で正解するということです。 件のコピペですが、最初の文字は変わらないので、その正解率は平仮名の数(52)倍になります。 すなわち、52/100 =~ 0.5 実際には、最後の文字も変わらないし、 単語の長さが変わらないというもの、大きな
SSD がコモディティになっても状況はかわらない - kazuhoのメモ置き場
脊髄反射。 Oracle や MySQL など近年の RDBMS はインデックスのデータ構造にB木 (の変種) を採用していますが、その理由はここにあります。 SSD がコモディティになると状況は変わる (中略) 二次記憶上での検索用のインデックスにはこれまで B木のようなディスクに最適なデータ構造が必然的に選択されてきましたが、SSD に変わると、現実的に利用可能なデータ構造にも幅が出て、アプリケーションによっては劇的な改善が可能になるというわけです。 この先 SSD の普及によって、色々なソフトウェアで、驚くような改善が行われる機会を目にすることが多くなるのではないかと思います。その時、単に SSD に変わったから速くなったと捉えるのではなく、どのようなデータ構造が選択されて、そのデータ構造の特性が SSD とどのようにマッチしたのかという視点で見ていくことが大切ではないかと思います。
孤独なプログラマー : 新規保存で劣化していくJPEG形式の画像の様子をとらえ・・・てない気がする
2009年04月19日14:08 カテゴリ 新規保存で劣化していくJPEG形式の画像の様子をとらえ・・・てない気がする ソースコードを見ると、 ＞ float q = map(i,0,numberOfFrames,1,0);＞ p.setQuality(q,true); だから、多分0〜numberOfFramesまでの間にあるiを1〜0にマッピングして、それをJPEGの圧縮率に指定しているんだと思う。 記事内容見ると「JPEG形式で保存を繰り返すだけで画像がどんどん劣化していき、最後は見るも無残なことに」と解釈されているみたい。でも、それならsetQualityに設定されるべき値は一定であるべきだと思うんだけどなーー ということで実験実験。 --- A=0 while [ $A -lt 6000] do echo "$A" OLD=`expr $A` A=`expr $A + 1` co
新規保存で劣化していくJPEG形式の画像の様子をとらえたムービー
JPEG形式の画像は基本的に非可逆圧縮で、保存するたびに劣化してしまいます。1度や2度の保存では違いが分かりにくいのですが、保存を繰り返すことですぐに分かるほどに劣化していきます。そんな少しずつ圧縮されて劣化する画像の様子がムービーでまとめられていたのでご紹介します。 詳細は以下から。 新規保存を600回繰り返して劣化していく20秒のムービー。 GENERATION LOSS | HADTO.NET 4秒(約120回)付近で明らかな違いが出ています。 10秒(約300回)付近。粒状感たっぷり。 もう空には見えません。 最終的にはテレビの砂嵐のような画像になっています。 2009/04/19 22:04追記 これは単純に同じ圧縮率でJPEG保存を繰り返しているのではなく、少しずつ圧縮率を上昇させていって保存した画像をつなげたムービー。プログラムのコードの中身としては、MAPクラスとJPEGの
2の冪 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "2の冪" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2024年6月) 2の冪 2n の直方体による図示。 左上1 (=20) から右下 1024 (=210) まで。 2の冪（にのべき、（英: power of two）は、2 を底とし整数の指数を持つ冪である。2の冪は、指数を n として一般に、2n の形で表される（例えば n = 0, 1, 2, 3, … に対してそれぞれ 20 = 1, 21 = 2, 22 = 4, 23 = 8, …）。 1に2倍のみを繰り返すことによって得られる数であり、ごく基本的な数量操作で得られる
GIFライセンス問題についてわかるページ
【集中企画】 GIFライセンス問題についてわかるページ さきごろ、Webブラウザーやメールソフトなど、Internet Explorer（IE）コンポーネントを呼び出しているソフトがいくつか、公開中止や仕様変更となった。これは、GIFフォーマットで使われているLZW圧縮伸張アルゴリズムに関して米Unisysが特許を持っており、これを使ったソフトを開発するにはライセンスを受ける必要があることによるもの。Microsoftは自社のライセンスについて、Microsoft製品を部品として使う開発者には適用されないと声明しており、ソフト作者がライセンス違反を懸念して今回の動きとなった。 今回の集中企画では、このGIF（LZW）ライセンス問題についてWebで論じているページを見てみる。 注意：ここで紹介するのはあくまでも各サイトの論点であり、その見解そのものを保証するものではありません。
3 NOT problem - あどけない話
和田先生が紹介されていた3 NOT problemを解こうといろいろ考えましたが、結局できませんでした。orz 答えが分らないと、気になって次の仕事に進めないので、検索して答えを見つけました。 Haskell でアルゴリズムを書いておきます。 import Data.Bits input = map triple [0..7] where triple :: Int -> (Bool,Bool,Bool) triple n = (testBit n 2,testBit n 1,testBit n 0) output = map (\(x,y,z) -> (not x, not y, not z)) input threeNot (x,y,z) = let aa = y && z ab = x && z ac = x && y ad = y || z ba = x && aa bc = x
パラメトロン計算機
久野君たちの努力により, Beautiful Codeの翻訳がでた. 以前 三省堂の洋書の棚にあるのを見たことはあったが, その時はパスした. 翻訳をみると, なにしろ多くの人がそれぞれのプログラム言語で書いた自分のプログラムを(それもかなり大きい部分を)自讚しているから, 読むのが大変そうである. 短くて面白かったのは, 33章「『本』のためにプログラムを書く」であった. 要するに平面上の3点A, B, Cの座標が与えられた時, その3点が同一直線上にあるかを判定するプログラムを書くのだ. 私がやっても多分こういうアプローチになるであろうという風に話は展開していく. まずA,Bの2点を通る直線の式を決め, 点Cがそれに乗っているかを問うもの. これは最初の2点がy軸と平行な線上にあるときの始末が面倒. 次はABを通る直線の勾配と, ACを通る直線の勾配を計算し, それらが一致するかを見る
フランスの地でアルゴリズムの未来を切り開く男 高橋直大
Microsoftが主催する学生向けの技術コンテスト「Imagine Cup」。そのアルゴリズム部門で世界の頂点に挑むのは、プログラミング歴が2年にも満たない一人の数学好きだった。 Microsoftが主催し、全世界の学生を対象にする技術コンテスト「Imagine Cup」。今年は日本時間の7月4日からフランスのパリで開催される。幾つかの部門が用意されているが、その中の1つであるアルゴリズム部門の日本代表としてフランスの地を踏んだことで、この男の今後はどのように変化するのだろうか。 Imagine Cupのアルゴリズム部門で世界大会に進むのはわずか6名。高橋氏についてもアルゴリズム部門日本代表というよりは、ファイナリストと表記した方が正確だろう。このファイナリスト6名が24時間で10問の問題に挑み、世界の頂点を目指す。今回は、7月3日に20歳の誕生日を迎え、大きな変化の波のまっただ中にいる
プレイヤーが選べる難易度設定とゲームが自動調整するランク、どっちがいい？ - ABAの日誌
The Designer's Notebook: Difficulty Modes and Dynamic Difficulty Adjustment (http://www.gamasutra.com/view/feature/3660/the_designers_notebook_.php) この著者は難易度設定派っぽいが、それはそれとしてそれぞれの利点、欠点がまとまっていていい記事だ。 難易度設定の欠点としては、 ゲームの最初に難易度を決めなければならない 設定できる難易度の粒度が荒すぎる おおざっぱすぎてプレイヤーのスキルに適応できない。射撃がうまくて運転が下手な人はどうする？ が挙げられている。それに対して動的な自動調整のランク (DDA)の欠点は、 わざと下手なプレイをしてDDAの穴をつくことができる 数値を変更するタイプの調整以外には使えない いくら速く走っても追いつかれるレ
ユビキタスの街角: Knuth先生にアルゴリズムを教えたよ
Donald Knuth先生の 弟子の播口さんに誘われて、 Knuth先生と夕食を御一緒させていただいた。 185cm以上はある大きな人で、想像よりも若かった。 1938年生まれだからまだ70歳らしい。 とても頭が良さそうな顔をしている。当たり前か。 世間話の中で先生の執筆環境について聞いてみた。 M: 「文章書きとかどういう環境でやってるですか?」 K: 「大きなマシンも使ってるけど文章とかはLinuxノーパソでEmacsだね」 M: 「Emacsなんですか。仕様が変で困ったりしませんか?」 K: 「変な機能は使わないからね。自分で色々カスタマイズしてるし」 K: 「たとえば行に色をつけるElispを使ってる。参考文献リストとか書くときに、 大事なのとそうじゃないので色を変えるんだ」 K: 「CWEBを書くための仕組みも作ってる。まだ書いてないモジュールのリストは全部 木構造でダンプして
「解読不能は数学的に証明済み」、RSAを超える新暗号方式とは ― ＠IT
2008/04/11 すべての暗号はいずれ破られる。2000年前のシーザー暗号の時代から高度な暗号技術が一般化したデジタル通信の現代に至るまで、それが暗号通信の歴史が証明し続けた事実であると同時に、もっとも人口に膾炙したクリシェでもあった。例えば、鳴り物入りでリリースされたDVDのコンテンツ暗号技術「CSS」（Content Scramble System）が、リリースからわずか数年で10代のノルウェー人ハッカーに破られたことは記憶に新しい。 【追記】（2008年4月15日） この記事は取材に基づいて執筆したものですが、一部専門家らから「CAB方式暗号は解読不能」というのは誇大表現ではないかとの疑義が呈されています。アルゴリズムの公開や第三者による検証がない現在、この記事に登場するCAB方式が発案者・実装者の主張通り画期的な暗号方式で、本当に解読が不可能であるかどうか分かりません。現在、専
“解読不能”の新暗号の記事について、いつくかのお詫び ― ＠IT
先週末の金曜日に掲載した「『解読不能は数学的に証明済み』、RSAを超える新暗号方式とは」がアクセスランキングの2位に入っているが、はてなブックマークやブログで、たくさんのご指摘、ご批判をいただいた。取材、執筆したニュース担当記者である私（西村賢）はいくつかお詫びしなければならない。 1つは記事タイトルや冒頭の記述だけを見ると、まるで確定事項のように見えること。アルゴリズムの公開や検証が済んでいないので「原理的に解読不能と主張する研究者が現れた」と書かなければならないところだった。記事の末尾で「CAB方式は、まだ実績がなく事実上未公表の技術だ。情報が公になっていくにつれて、専門家たちがどう反応するかは未知数だ」と書いたときには、今後アルゴリズムが公表されてすぐに理論的な瑕疵が見つかる可能性があるという意味のつもりだったが、誤解を与える記事構成だった。 アルゴリズムを非公表にしたまま「解読不能
書評 - javaによるアルゴリズム事典 : 404 Blog Not Found
2006年11月05日21:15 カテゴリ書評/画評/品評 書評 - javaによるアルゴリズム事典 土と芋とユンボに戯れ、ご機嫌で過ごした三連休の最後をしめくくるかのように宅配ボックスに入っていたのがこちら。 javaによるアルゴリズム事典 奥村 晴彦他 404 Blog Not Found:Mastering Algorithms with Perl-siuyeさんのコメントjava版が数年前出てましたよ。＞アルゴリズム辞典 を見て注文のが本書「javaによるアルゴリズム事典」、なのだけど.... これは、ヨイショしづらい。 まず、コード。あまりに「C言語による最新アルゴリズム事典」からのコピペが多い。 int main (int argc, char **argv){ /* コードはこちら */ } を、 class Example{ public void main(String[
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
お手軽に強い将棋プログラムを作る10の方法 - aki.の日記 (2009-02-19)
