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

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

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

Perish or Perish

私のtwitterアカウントを見ていた方はご存知かと思いますが、SC2016秋の新刊を落としました。まず、「帰宅演習・補遺」に関しては、事前に計画上の無理が生じていたのが分かっていたので、そもそも出さないという結論になりました。これは今回は出さなかった…

文化の日だから文化的なことを書こう

といっても大したことを思いつかないので、新しく作ったサイトからネタを引っ張ってきます。おっと、もう gillirb です。いい加減寝ないと、という冗談はさておき、brillig は午後4時を指します、というのもまぁ本当か嘘かは分からない、「鏡の国のアリス(T…

お鰭持ち表明

金曜にお会いした方もそうでない方もこんにちは。あざペンです。前回の更新以後、何の告知もせずに頒布翌日まで来てしまってすみません。もっとも、筆者の怠惰によりこのブログは半年更新しないこともあるので珍しいことではありませんが。コミックマーケッ…

桁落ちを簡単に検出&表示

桁落ちは数値計算において精度を下げる重要な原因となります。 自分のテスト用ですが、C++ で桁落ちを検出して表示するプログラムを書きました。 小数に double 型を使用したC++ プログラムにおいて、次の mydouble.h をインクルードすると、桁落ちが生じる…

帰宅演習

ミッドウェイ島からこんばんは。お久しぶりです。一部のヒトからは死んだと思われていた azapen6 です。C89の告知(帰宅第一)以来の更新ですが、今度はC90の告知です。この度筆者 azapen6 はちょうど1ヶ月先に開催されるコミックマーケット90にサークル参加…

帰宅第一

世はクソアヌス一色ですが告知です。前にも書きましたが、来週開催されるコミックマーケット89にて「帰宅部活動記録」合同誌『帰宅第一』が頒布されます。日および場所は1日目西れ09a「78Hz」、価格は1000円/部です。あざペンは「OTCの謎」という漫画を寄稿…

アクセルほど微分精度は加速していくよ!

今回のテーマは微分の計算です。やりたいことは、実数の範囲で定義されたなめらかな関数 と実数値 が与えられたとき、 の での微分係数 を求めることです。もし が初等関数の式として与えられているならば話は簡単です。 に微分公式を適用していけば必ず導関…

gnuplot で brainfuck のインタープリタを作った話

gnuplot とは関数のグラフや実験データをプロットするためのフリーソフトウェアの一つです。例えば、次のようなグラフを描くことができます。さて、gnuplot には作業を自動化するためにバッチファイルを読み込んで実行する機能があります。例えば、上のグラ…

ブログのデザイン

またまた今更ですが、ブログのデザインを変えてみました。最初は今まで使っていた公式デザインにちょろっと書き足せば済むと思ったのですが、それだけではどうにもうまく行きませんでした。筆者の要求は 背景を白に、リンクを青にしたい 見出しの下線を実線…

無料の帰宅部・後半

今更ですが、ニコニコ動画にて帰宅部活動記録が無料配信されています。前半の無料期間は既に終わっていて、23日からは後半の7〜12話(記録の二十一〜五十七)が無料になっています。57は素数。前半を観ていない、あるいは、前半で脱落したという人にこそ後半…

ありがとうくろは先生

この度、コミックマーケット89に向けて漫画・アニメ「帰宅部活動記録」(作:くろは)の合同同人誌を制作するプロジェクト(project968)が動き出しました。それに筆者 azapen6 も寄稿させて頂けることになりました。ジャンルは漫画です。ネタは今考えている…

割り算を使わずに割り算をする

妙なタイトルですが、今回は次のような問題を考えます。割り算を計算をするために電卓を使いたい。しかし、電卓を持ってきたところ、割り算のボタンが故障していて使えないことが判った。他のボタンは問題なく機能しているが、割り算だけは使えない。なんと…

割り算の計算量

足し算、引き算、掛け算と来たら、残る四則演算は割り算です。割り算においてこれまでと違うことは、何と言っても「割り切れない」場合が存在することでしょう。他の四則演算はすべて整数の範囲で閉じている*1のですが、整数同士の割り算では結果が整数とな…

Toom-Cook法:掛け算の数が減るカラクリ

今回は、Karatsuba法をダシにして、「高みの見物で構造が見えてくる」というお話をします。最初の高速乗算アルゴリズムであるKaratsuba法は、それだけ見ると天下り的に上手いことやって式を作ったように思えます。あるいは実際そうだったのかもしれません。…

掛け算の計算量

前回の足し算の計算量に続いて、今回は掛け算の計算量について見ることにします。掛け算(および割り算)において一つ重要なことは、筆算よりもオーダーの意味で(定数倍を超えて)速い計算方法が存在することです。一方で、足し算(および引き算)の場合は…

計算量とは

間に挟む形で「計算量」というものを扱う上での心構えなどについて書いておきます。 計算量とは 「計算量」とはその名の通り計算の難しさを測る何らかの数値のことです。あるいは計算にかかるコスト=資源の消費量と言ってもいいでしょう。つまり、ある問題…

オーダーのすゝめ

前回の計算量の議論の問題点として、数字の見方(基数)を自由に変えられるとした場合、計算量が一定しないことを最後に述べました。それは例えば計算量がCPUに依存するということであり、計算量を理論的に抽象化して議論する場合の妨げとなります。そこで、…

算術演算の計算量

気がつけば大晦日。明日はもう2014年です。このブログを始めて1年も過ぎました。記事が充実しないのは筆者の怠慢の致すところであります。久々の更新で一体何を書くのかといえば、大分放置していた計算量の定義です。誕生日のパラドックスを素因数分解に応用…

フカシギの数え方

先日、北海道大学に行く機会があったのですが、そこの博物館で標題の「フカシギの数え方」という展示が行われていました。これは、北大の湊真一教授率いるプロジェクトの概要と成果を一般向けに紹介するもので、元々は今年始めまで東京でやっていたのを撤収…

何て読むんだこの人?の等式

この人名、何て読むんだ…?と途方に暮れることが時々あります。読み方に困る名前というのは様々あるのですが、日本人の場合はやはり漢字の読みが問題となるでしょう。例えば、「中田」は「なかた」か「なかだ」かというように読み方にバリエーションがある場…

括弧をカッコよく数えよう!

前回の話を踏まえて、今回は場合の数の数え上げを扱います。この種の問題の基本形は、ある条件が与えられたとき、それを満たす対象が全部でいくつあるかを数えよ、というものです。最初に用語を紹介しておくと、今回紹介する数え上げの手法は、「母関数(gen…

二項係数がゲシュタルト崩壊する〜

遅ればせながら赤座あかりちゃん誕生日おめでとう。定義が面倒な計算量の話を先延ばしにして小ネタで穴埋めしようとしたら、そこで使う予定だった二項係数が出なかったので焦りました。幸い別の方法で出せたので良かったです。今回は小ネタの準備ということ…

誕生日のパラドックスと素因数分解・その1

皆さんは「誕生日のパラドックス」と呼ばれるものを耳にしたことがあるでしょうか?それは具体的には次のようなものです。人が23人集まれば、その中には50%の確率で同じ誕生日を持つ人の組が存在する。もっと言えば、人が57人集まれば、その中には99%の確率…

当たり前?

突然ですが、次の式を見て下さい。あるいは、として何?こんなの当たり前じゃないかって?残念!それが通るのは高校までです。上の関係式は「微分積分学の基本定理」と呼ばれています。その名が示す通り、微分積分を議論する上で最も基本的かつ重要な定理で…

オーダー記法・その4

今回は新しいオーダー記法を導入します。それらは主に計算量理論において用いられ、他の分野ではあまり見かけることがない(マニアックな)ものです。とはいえ、使うところでは普通に使うので、今後のためにも定義をちゃんと述べておく必要があるでしょう。…

オーダー記法・その3

今回の目標は、より複雑なオーダー記法をきちんと定義することです。例えば、あるいは、もっと複雑なのような記法です。 オーダー記法の拡張 右辺の式にオーダーが入る場合 最初の例を解釈して適切な意味付けを与えましょう。 に関して に続く項を誤差項とし…

オーダー記法・その2:基本的な定義

それでは、前回の話を踏まえて、オーダー記法を厳密に定義しましょう。今回は、最も基本的な場合として、 のとき のように、右辺に一つのオーダーだけがある場合を扱います。これは、今後出てくるすべての派生的な記法の大元です。そのために、(筆者ができ…

オーダー記法・その1:使用例からの導入

今回は情報科学においてよく用いられる「オーダー記法」について説明します。オーダー記法は、諸量の評価式から重要な部分を抜き出すのに便利な記法であり、情報系分野では基本的な記法として多く用いられます。ただ、見かけによらずその厳密な意味は少々複…

ちょっと複雑な論理表現・その2

前回は数学で用いられる論理の基礎を説明しただけで終わってしまいました。今回こそは本題に入ります。 条件付き量化子 最初に言ったように、この話で問題にするのは、ある実数 が存在して、すべての について が成り立つ。のような表現です。量化子に範囲指…

仮定が偽なら結論は何でもあり

前回の補遺として、演算子「ならば」のところで述べた、 は が偽のときには の真偽に拘らず真となる、という真理値割り当てを検証します。これは二値(古典)論理において重要なポイントなのですが、どうにも直感では理解が難しい部分でもあると思われます。…

ちょっと複雑な論理表現・その1

今回は、数学の書き方についての話です。主にターゲットとするのは、数学でよく用いられるある実数 が存在して、すべての に対して、○○が成り立つのような表現です。この「ある『実数』 が存在して」や「すべての 『』 に対して」 のような変数に範囲指定や…

全問外すことは全問当てることと同じくらい凄い?

前の記事: http://azapen6.hatenablog.com/entry/2013/01/13/192612これまで話してきたエントロピーの応用として、こんな問題を考えてみることにします。太郎くんは選択問題だけからなるテストで0点を取ってしまいました。しかし、彼はそれを受けて、自慢げ…

情報がない

前回の話で、エントロピーの大小が当たりのつけにくさを表していることを述べました。この見方によれば、エントロピーが最大となる確率分布のもとでは、出てくる要素の予測が全くできない、言い換えれば何の情報も与えられていないと言うことができます。前…

エントロピーとは何か??

今年最後*1のエッセイとして、物理学と情報科学および数学のある分野において重要な概念である「エントロピー」*2というものについて少々話をさせて頂きます。いきなりネタをばらしてしまいますが、この話はタイトルの疑問に答えるものではありません。むし…

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

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

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

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

アリスとボブは妥協する

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