読者です 読者をやめる 読者になる 読者になる

あざらしとペンギンの問題

主に漫画、数値計算、幾何計算、TCS、一鰭旅、水族館、鰭脚類のことを書きます。

切り分けても切り分けても長方形

前の記事: http://azapen6.hatenablog.com/entry/2012/12/29/053705今回は引き続いて、乱数を使わないで完全なチェックを求める限りは、どうやっても対象のデータをそのまま送信するのと通信量の意味で差をつけられないことの証明に入ります。前回の最後に…

できないことを言うときは用意周到に

前の記事: http://azapen6.hatenablog.com/entry/2012/12/22/031000今回と次回の話では、前回掲げた「妥協するのも悪くない」という主張の裏をとって、「妥協しないとお手上げ」という場合が実際にあることを示します。問題は前回に引き続き、アリスとボブ…

アリスとボブは妥協する

手始めに、ちょっと妥協すると大きな効果が得られるという例をお見せして、全体の入門と致しましょう。何を妥協するのかというと、アルゴリズムがいつでも正しい答えを出すということを、稀に間違った答えを出しても構わないとする、もしくは、稀にアルゴリ…