okamoto7の日記 天使と悪魔の問題
解かれたらしい．知らなかった． どういう問題かというと，2次元の無限正方格子のある1点に天使がいる．天使は1回にある決められた量だけ格子にそって動くことができる．しかし，その後，悪魔は格子の1点を(天使がいるところ以外は)どこでも壊すことができる．天使と悪魔が交互に自分の手を指していくが，最終的に天使がある有界の領域に閉じ込められてしまうかどうか，を考える．つまり，天使は悪魔に閉じ込められないようにしたいのである． 天使の1回の移動量が十分に大きいとき，天使は必ず逃げ切れる，というものがConwayによる予想だった．これが肯定的に解かれた，というのがニュース． もう少し詳しいことはwikipediaを参照． ちなみに，天使が1回に1歩しか動けない場合，天使はつかまってしまう． 原稿をようやく書き終えた．結局3ページぐらいになってしまった．端折りすぎたかも．
ミニ研究集会「組合せゲーム・パズル」
科学研究費補助金の特定領域研究「新世代の計算限界」の活動の一環として、 組合せゲーム・パズルに関するミニ研究集会が昨年の9月12日に京都大学で行なわれ ました。 世話役をして頂いたのは京都大学の伊藤大雄先生です。 中村義作先生の特別講演に加え、一般の講演が9件行なわれ、かなりの人数が 集まり盛況の研究集会となりました。 私がこの研究集会に参加した大きな理由のひとつは、 中村先生の特別講演が行なわれるというということでした。 LAには同じような人がかなり多いのではないかと思うのですが、昔からパズル、 ゲームの類が好きで高校、大学の頃（だったと思う）を中心にブルーバックス あたりから始まって、この手の本をかなり読んでいて、その中に 中村先生の本も何冊か含まれていました。他に主な名前をあげると、 藤村幸三郎、高木茂男、H.E.デュードニー、M.ガードナー、などなど。 （でも少し調べてみたら、当時
棒取りゲーム - 週1でも日記
小中学生の頃 ||| ||||| ||||||| のように並んだ縦棒を取っていき、最後に取った人が負けと言うゲームが流行っていた。 続けて横に並んでいる棒は何本でも取れるが、複数の段の棒を同時に取ったり、既に取られた棒をまたいで取ったりはできない。(google:棒取りゲーム で検索すると分かりやすい説明が読めるだろう。) 棒が 3,5,7 本でやる事が多かったのだけど、この場合先手必勝と後手必勝のどちらだろう。 (3,5,6) 本は後手必勝? だとしたら (3,5,7) 本は先手必勝になるんだが。 追記:手順を graphviz の dot 形式で書いてみる。 終盤カタマリ(リンク先ネタバレ注意)が 1 個になった時以外、N山崩しゲームの必勝手と同じっぽい。 はてなブックマークで smoking186 さんに 石とりゲームの数理 POD版 (数学ライブラリー 教養篇) という本がある事を
d.y.d.
16:48 06/10/31 無限ループ From このへん。 _=*"".."_" 0H10B、とかはありでしょうか。このRangeのmin辺りを呼べばメモリも食わず経済的です。 ゴミメール す 写 つ 男 当 ご 景 行 わ こ 先 秋 女 ぐ 真 ま 性 サ 希 気 き た の 日 も 性 に 付 り 会 ｜ 望 も 違 く 度 小 一 h の ご き 本 員 ク も 徐 い し ア 池 段 t 写 希 プ 当 様 ル 充 々 で 山 ド よ と (以下略) なんか縦書きのスパムが来ててちょっと面白かったです。フィルタ避けでしょうか。 でもURLまで縦書きだと、さすがに誰もたどろうとしないと思うんだ。 クリックは当然のこと、コピペもできない。 ゴルフ ネタバレはないですよ。 Switchboard: 109B (Ruby, とりあえず書いてスペース削っただけ版) → 88B～
[結] 2006年10月 - 結城浩の日記 - ルソー展と陣取りゲーム・クイズ
目次 2006年10月31日 - Tropy一周年 / 仕事 / 2006年10月30日 - 仕事 / 2006年10月29日 - 礼拝 / トドちゃん / 2006年10月28日 - lingr.com実験中 / 2006年10月27日 - 仕事 / 2006年10月26日 - 仕事 / 疑似乱数列を生成する計算方法の妥当性を調べるのにチューリングテスト的方法は使えるか / 2006年10月25日 - 仕事 / 仕事 / 仕事 / アナザ・タボウ / 2006年10月23日 - 多忙 / 2006年10月20日 - 仕事 / 2006年10月19日 - 仕事 / 仕事 / 『新版Perl言語プログラミングレッスン入門編』 / 2006年10月18日 - 仕事 / 仕事 / 仕事 / 2006年10月17日 - 仕事 / 2006年10月16日 - トドちゃん到着 / 今日の魔法の言葉 /
数列辞典
The page you're looking for has moved, been replaced, or is currently unavailable to view. If you previously bookmarked a page and have now reached this message, check to make sure the link was not shortened, or go to our home page to find the page from there. We've been upgrading this site. If you selected a link on our site and reached this message, use the Back button to return to the previous
Computational Complexity: A Modern Approach / Sanjeev Arora and Boaz Barak
Cambridge University Press This is a textbook on computational complexity theory. It is intended as a text for an advanced undergraduate course or introductory graduate course, or as a reference for researchers and students in computer science and allied fields such as mathematics and physics. See also Amazon page for the book. This page contains: Draft of the book with links to additional relevan
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Complexity Theory Theme Song options
Cryptology ePrint Archive 2007/169 - M. Backes, D. Unruh "On the Security of Protocols with Logarithmic Communication Complexity"
UCSD Security and Cryptography People
Conference on Computational Complexity: Accepted Papers
Page Not Found
CiteSeerX
https://dl.acm.org/citation.cfm?id=195129&coll=portal&dl=ACM
ニュースレター6
Whose Thesis is it Anyway?
ECCC Report TR06-131 - Konstantin Pervyshev "On Heuristic Time Hierarchies"
APPROX 2006 + RANDOM 2006: Program
Project: Complexity of lattice problems
The Hidden Subgroup Problem - Review and Open Problems