sumiiの日記 このページをアンテナに追加 RSSフィード

2012-10-04

再帰」の説明の一例(プログラミング初心者向け)

Twitterから参照するためのメモです)

まずそもそも「関数」は「同じ形の計算を何度も書かないための仕組み」であることを十分に理解する(させる)。その上で、

sum(0) = 0
sum(1) = 0+1
sum(2) = 0+1+2
sum(3) = 0+1+2+3
sum(4) = 0+1+2+3+4
...

も「同じ計算を何度も書いている」から、

sum(0) = 0
sum(1) = sum(0)+1
sum(2) = sum(1)+2
sum(3) = sum(2)+3
sum(4) = sum(3)+4
...

と書き換える。これを一般化すると

sum(0) = 0
sum(n) = sum(n-1)+n (n>0の場合)

つまり

sum(n) = if n=0 then 0 else sum(n-1)+n

となる

追記:n<0の場合は気にするな。

2011-08-30

帰納法と余帰納法の何がどう双対なのか(初等的に)

(高校で習うはずの)数学的帰納法をはじめとする帰納法(induction)と、(π計算など並行プロセス計算に出てくる)双模倣(bisimulation)をはじめとする帰納法(coinduction)は、双対(dual)であると言われます()。双対というのは、大雑把に言うと、論理式のド・モルガンの法則 ¬(A∨B) ⇔ ¬A∧¬B と ¬(A∧B) ⇔ ¬A∨¬B のように、何か一組のもの(ここでは∧と∨)をひっくり返しても同じ式が成り立つという関係です()。

しかし、自分は学部4年ぐらいのときに余帰納法(というか双模倣)を習って、「(数学的帰納法のような)帰納法と(双模倣のような)余帰納法が双対」と聞いても、何となく「余帰納法は結論を仮定する(?)から、仮定を仮定する(?)帰納法と反対なのかなあ」と思うぐらいで、恥ずかしながら何が双対なのかよくわかりませんでした。かといって、詳しい人に「何が双対なんですか」と下手に聞くと、高い確率で「始代数と終余代数が…」みたいなカテゴリー理論的(?)説明をされてしまい、それはそれで面白いし落ち着いて確かめれば形式的には(=字面上は)意外と簡単(?)なのですが、(当時の)自分にとっては「数学的帰納法と双模倣の何が双対なのか」という素朴な疑問に対してピンと来る答にはなりませんでした。

仕方がないので(当時の)自分なりに思案した説明が以下です。教科書的定義から繰り返すと長くなってしまうので、単調関数の最小不動点と最大不動点がどうとかいうは知っているとします(詳しく知りたい人はTAPLの21.1節がわかりやすいと思います。その章の元になった論文の2節も、短いですが証明以外の大まかな内容はほぼ同じです)。すると、例えば自然数の集合Nは

  • 0∈X
  • ∀n.n∈X⇒n+1∈X

(の両方)を満たす最小の集合X、すなわち

  • F(X) = {0}∪{n+1 | n∈X}

なるFの最小不動点と定義されます。高校で習う(はずの)いわゆる数学的帰納法(すなわち自然数に関する帰納法)は、自然数に関する命題(すなわち自然数の集合)Pが

  • 0∈P
  • ∀n.n∈P⇒n+1∈P

(の両方)を満たせば∀n∈N.n∈Pを満たす、という(自然数の集合Nの)性質を利用した証明法です。これは論理的に

  • 集合PがP⊇F(P)を満たせばN⊆Pを満たす … (1)

と言いかえられるので、「NはX⊇F(X)を満たす最小の集合X」という自然数(の集合)の定義にも合います。

これに対し、余帰納法は、単調関数Fの最大不動点S(すなわちX⊆F(X)なる最大のX)に対し、

  • 集合RがR⊆F(R)を満たせばS⊇Rを満たす … (2)

という性質を利用した証明法です。具体例としては、プロセスの組の集合(すなわちプロセス上の二項関係)Xに対し

  • F(X) = {(p,q) | ∀p'.p→p'⇒∃q'.q→q'∧(p',q')∈X}

とすると、Fの最大不動点Sはプロセスの模倣性(similarity)関係になります(ただし、→はプロセスの遷移を表す二項関係で、ここでは詳しく定義しません)。これを用いて、例えばあるプロセスp1が別のプロセスq1を模倣(simulate)することを示したかったら、(p1,q1)∈RかつR⊆F(R)なるRを一つ「発見」する(ないし「構成」する)ことができれば、(2)よりS⊇Rなので、めでたく(p1,q1)∈Sが言えます。

(1)と(2)は見た目から明らかに「双対っぽい」ですし、教科書的説明に出てくる式ですが、それらの「使い方」も

  • 帰納法は「集合Pに対し、Fの最小不動点Nに属する任意の要素nが、Pに属する」ことを示したいときに使う … (1')
  • 帰納法は「集合Rに対し、Rに属する任意の要素(p,q)が、Fの最大不動点Sに属する」ことを示したいときに使う … (2')

と言えば「双対っぽい」感じになります(もちろん、(p,q)とかはあくまで例で、一般に組である必要はありません)。

細かい用語や記法は「いいかげん」ですし、すぐにわかる人には当たり前すぎる話かもしれませんが、(昔の)自分はすぐにわからなかったので、ひょっとしたら他人の参考になるかもしれないと思い恥を忍んで(?)久しぶりにエントリを書いてみました。最近の老化により記憶(と認知)が怪しい(笑)ので、何か大ボケ(ないし小ボケ)があったら是非ともご指摘ください。(_ _)

2010-02-05

FLOPS 2010参加登録受付開始

遅くなりましたがFLOPS 2010の参加登録受付を開始しました。皆様よろしくお願いします。

http://www.kb.ecei.tohoku.ac.jp/flops2010/

ご質問や誤植などがありましたらコメント、Twitter、メールのいずれでも結構ですので是非ともお気軽にご連絡ください。

追記:FLOPS 2010は皆様(特にIFIP WG2.8関係者各位)のご厚意で、アイスランド火山噴火の影響によるプログラム変更はありますが開催できそうです。ヨーロッパからの招待講演者はむしろ増える(!)予定です。準備ができ次第、上述Webサイトと参加登録者各位へのBccメールでアナウンスします。

2010-01-20

医療保険

契約している医療保険が値下げ(!)されて更新(解約&再契約)が必要になったので、この機会に考察してみました。プロや詳しい方のツッコミをお待ちしております。

まず、そもそも保険の目的は、(正確な比喩ではないかもしれませんが)「大数の法則」のように、多くの人が集まることにより、確率的事象の影響を予測しやすくすることです。例えば「百万分の一の確率で、一年後に十億円が必要になります。払えなかったら破産です」と言われたら、(普通の)個人では対処のしようがなく、「百万分の一の確率で一年後に破産する」しかありません。そこで、「今のうちに1,100円を払ってくれれば、一年後に十億円が必要になっても肩代わりします」という仕組みがあると助かります。それが保険です。(期待値との差の100円は手数料です。加入者が100万人だったら、一人100円×100万人=1億円が保険会社の収入になります。)

では、「入院1日目から、最大60日目まで、一日5千円を支払います」という保険と、「入院61日目から、最大1,000日目まで、一日1万円を支払います」という保険はどちらが得でしょうか。無論、前者は比較的高確率、後者は低確率の事象ですが、当然ながら保険料も確率に応じて(かなり正確に)決まっているので、「確率の高い出来事だから保険に入る」というのはナンセンスです。例えば、もし確率100%の事象だったら、明らかに自分で貯金したほうが(保険会社の手数料分だけ)得です。同様に、よほどのお金持ちか貯金不足で限り、「入院1日目から60日目まで」などという保険に意味は無く、むしろ確率は低いけれども損害が大きい「入院61日目から1,000日目まで」のような保険のほうが有用です。残念ながら現在のところ、日本の保険会社で後者のような医療保険は存在しない(?)ようですが…

追記:もちろん、高額療養費制度は存在しますが、現在の公的医療保険制度がいつまで存続するかわかりませんし、(現役の場合は)長期入院により収入が減少するリスクのほうが問題です。所得補償保険もありますが、逆選別のため(?)か、一般に割高のようです。最も悩ましいのは「入院」ではなく「療養」により収入がなくなるリスクで、良い案があったら教えてください。(自分の場合、「療養」できる状態ならば、無理すれば「就業」も可能かもしれませんが…)

2009-11-12

税金の無駄」について我々国民が肝に銘じておくべきこと

私は政治や財政の専門家でも何でもありませんが、最近の(特に一部のマスメディアやネット上の)議論では、あまりにも当然のことが無視されているように思うので、(こんなところで私が言っても意味がないことは承知で)陽に述べさせていただきたいと思います。

  • 大前提1:日本は国民主権民主主義国家ですから、政治の最終責任はすべて国民にあります。政治家」や、ましてや「官僚」のせいにすることは許されません政治家は国民が選出した代表、官僚は国民が雇用している従業員に過ぎません。(「俺が儲からないのは従業員のせいだから従業員をクビにする。残ったやつはもっと働け。ただし給料は減らす。」なんて経営者は最悪ですよね?)
  • 大前提2:「税金」は「私たちがみんなで議論・合意して、お互いのために出し合うお金」です。

以上を踏まえ、常に意識すべきこと:

  • 私(あなた)はいくら税金を払っているか。普通のサラリーマンであれば、国の直接税(所得税)は、給与明細源泉徴収票にはっきりと書いてあります。国の間接税消費税)は、普通は4%です(1%は地方消費税)。(法人税なども何らかの意味で間接的には払っているはずですが、計算が難しそうです。良い計算方法があったら教えてください>詳しい方)
  • 私(あなた)はいくら税金を使っているか。これはさらに計算が難しいと思いますが(良い計算方法があったら教えてください)、意識することが重要です。例えば外を歩くだけでも道路や信号を使っているはずですし、息をするだけでも空気を浄化するために使用された税金を使っていることになります。ちなみに信号機は一基あたり数百万円〜一千万円ぐらいだそうです(もちろん機種や仕様によると思いますが)。
  • これらを考えた上で、「税金の無駄」があるとしたら、具体的にどれが無駄で、具体的にどうしたら削減できるのか(あるいはそもそも本当に無駄なのか)。大前提1・2で述べた通り、それを考えるのは我々国民であって、「政治家」や「官僚」に責任転嫁することは許されません。

繰り返しになりますが、私は専門家ではないので、専門家の方のご意見・ご指摘がありましたら是非とも宜しくお願い致します。(_ _)

追記:未成年者には選挙権がない、外国人は日本の総人口にカウントされているが日本国民ではない等々、多少の不正確さはご容赦ください。(指摘は歓迎します)

2009-11-04

Microsoft Academic Search

またTwitterから転載します。(「はてな」と統一できればよいのですが、文字数制限が一番のネックです…)

  • Microsoft Academic Search ( http://academic.research.microsoft.com/ ) という、Google ScholarやCiteseerのMS版があることを知った。
  • MS Academic Search、ちょっとデータが古い&論文のunificationが甘い? > http://academic.research.microsoft.com/Author/822441.aspx
  • 学会や論文誌についての統計(引用数など)は参考になる。> http://bit.ly/2VS5Z8
  • …というか研究「者」個人まで陽にランキングされてるのかー。これはきつい…(笑) > http://bit.ly/30GiSK
  • ふーむ、大学ランキング同様、多少の疑問はあるかもしれないが(全体を100として±5ぐらいの誤差?)、学会ランキングも人間ランキングもほぼ実感を反映している
  • 若輩としては、citations / publications ではなく citations / (publications * years) で計算してほしかったですが:-)
  • ちなみに人名からcitations / publicationsとかcit / (pub * years)とかcit / (pub * yrs * authors)とかを計算してくれるソフトウェアもあります。 > http://www.harzing.com/pop.htm
  • 多少の誤差はあっても大体は一致しているわけですから、人事(採用)では研究分野の好き嫌いとか知り合いとかではなく、こういう客観的指標をきちんと使用していただきたいものです。最近はやや減っているようですが、いまだに明らかに逆転しているケースが…
  • 文字数制限のせいで書き忘れましたが、MS Academic Searchの件は松岡さん(などと私がお呼びするのも失礼ですが)経由で知りました。> http://twilog.org/ProfMatsuoka#091102

2009-11-03

2009-10-19

2009年世界大学ランキング by Times Higher Education/QS

ちょっと遅いですが、

http://www.timeshighereducation.co.uk/WorldUniversityRankings.html (目次)

http://www.timeshighereducation.co.uk/Rankings2009-Top200.html (総合)

http://www.timeshighereducation.co.uk/Rankings2009-Top50-IT.html (工学 & IT)

(via いろいろなところ)

人間による評価なので(?)多少の疑問はあるかもしれませんが、ほぼ実感と一致しているように思います。(分類が大きすぎるので、可能であればもっと細かくわけてほしいところですが)

続・科研費について

元から申請締め切りの時期、かつ、若手(S)と新学術領域研究(研究課題提案型)が募集キャンセルされたこともあって、科研費の話題が(通常よりは)目立つようですので、以前にtwitterのほうに書いた(ごく素朴な)考えを転載します。(前回のエントリもご参照ください。)

きちんとしたエントリを「はてな」に書きたかったのですが、時間がないのでこちらで:前にも触れましたが、税金を使う立場から見て、「税金の無駄づかい」は確実に存在します。が、それは「年度会計」と「人間は未来を完璧には予測できない」という(非常に明白な)事実との矛盾が最大の原因です。

したがって、(単年度にせよ複数年度にせよ)予算に使用期限が存在する限り、「見直し」とか「組み直し」とかで解決できる見込みはまったくありません。どれぐらいの予算が必要になるか絶対的に予測不可能なので、常にworst caseを考えて最大の予算を確保・使用しなければならないからです。

もっとも身近な実例として、「旅費が必要になるかどうか」は「学会に論文がacceptされるかどうか」によって完全に左右されますが、それを予算申請時(数年以上前)に予測することは100%不可能です。

科研費は一年だけ繰り越しができるようになってやや改善されましたが、「論文がrejectされたから」という繰り越し理由は認められていません。

何千万円(何億円?)もするような大型実験装置などに比べれば旅費なんて誤差の範囲なのでまだ良いのですが、(私には縁がありませんが)高価な実験器具も同様でしょう。研究の成否や進捗が完全に予測・計画できるとしたら、それはすでに研究ではありません。

予算を返還することができるようになり、かつ、それが「positiveに」評価されるようになれば解決すると思いますが、現状は正反対です(予算の返還は大問題)。それを実現するというマニフェストがあれば大賛成なのですが、寡聞にしてまったく知りません。

もっとも、こんなことは税金を使ったことがある人間ならば誰でもわかっていて、そういう意見が伝わっていないはずはないので、何か実現できない理由があると思うのですが…(以前に「はてな」で言及した憲法第86条が本当に原因なのでしょうか。)

参考: http://bit.ly/388t8u

「その年度に割り当てられた予算を消化するのが官僚の義務となる」「血税の浪費をただ単に奨励するのでなく、義務付けている」

(日本語版Wikipedia全体のデフォルトのようなものですが)出典がほしいところです。専門家間では常識なのでしょうか。

2009-10-08

FLOPS 2010論文要旨締め切り10/16(金)、本文締め切り10/23(金)

が近づいています。日本で開かれている数少ない(唯一の?)関数型・論理型言語に関する国際会議の第10回で、場所は仙台です(来年4月)。よろしくお願いします。

http://www.kb.ecei.tohoku.ac.jp/flops2010/wiki/index.php?CallForPapers

[]夜のトイレからの声

昨日の夜、どこからともなく「くわっ  くわっ  くわっ  くわっ」という声がするので(数分以上)、寝室で寝ている次男かと思ったのですが、その寝室から妻が出てきて「何の音?」と言います。外に鳥でもいるのかと思ったのですが、家の中から聞こえてきます。すわ心霊現象か!と思って音源を探したら、トイレにおいてあった時計でした。アラーム音を録音できるのですが、長男が(次男も?)いたずらしたようです。

クレタ人のパラドックス

ある理由で「論理学」(野矢茂樹著)*1を(時間的余裕がなかったので極めて速く)読んだ/眺めたのですが、その161ページに

なお,流布した誤解に,「あるクレタ人曰く,『クレタ人はみんな嘘つきだ』,この発言は矛盾している」というものがある.しかし,これは別に矛盾ではない.(検討されたし.)

(強調筆者)とあり、なるほどと思いました。(有名事実なのかもしれませんが、私は恥ずかしながら考えたことがありませんでした。あるいは聞いたことがあるのかもしれませんが、覚えていませんでした。)

P.S. 同じ著者の「論理トレーニング」も良い本でした。

科研費

以前にも参照させていただきましたが、「私と科研費」第1回(小林 誠・日本学術振興会・理事)より:

明確な研究課題の設定に至る前の試行的な研究や、経常的なデータの蓄積を必要とする研究、あるいは上述のような理論研究など、比較的少額でもよいが安定的な研究費が手当てされることが望ましいケースが多くある。こうした基礎的な研究に対する経費は、国立大学の場合、以前は講座研究費という形で一定の研究費が手当てされていたが、法人化後、運営費交付金が毎年1%削減されており、基礎的な研究費の部分が縮小し続けているのではないかと推察される。その肩代わりを現在の競争的資金制度に求めるのは筋違いではなかろうか。

端的に言うと、研究資金(私の場合は主に学会発表のための旅費など)に関する手続きの負荷が大きいため、研究をする時間がありません(確率が低いので、「切れ目」のないように研究を続けるためには、ほぼ常に何らかの手続きをし続けていなければなりません)。かといって、資金がまったく得られなければ研究活動を行うことができないだけでなく、各種評価にも直接影響します。金額はもう少し小さくても良いので、期間をもっと長く(できれば有限の金額で期間は無限に)していただけると有難いのですが、やはり憲法第86条問題なのでしょうか。

P.S. 科研費の使途の制限は、文科省・学振レベルでは大幅に緩和されています。(説明会資料内「科学研究費補助金制度について」27〜28ページ等参照)

  • 「研究者使用ルール」に特に記載がないことを事務担当者に尋ねると、前例がないので購入を止めて下さいと言われる。
  • 「研究者使用ルール」に特に記載がないことを「学内ルール」として決めていて、それが大変厳しい。
  • 一部の研究機関の方におかれては、補助条件等を厳格に捉え過ぎて、結果、研究者が使いにくいと感じる例が見受けられる。
  • これらの点について無責任で良いと申し上げるのではなく、補助事業(研究課題)の研究のために必要な経費が使えないというのでは本末転倒。
  • 現在、研究のために必要であって支払えない経費はほとんどない。「これ以上何を改めることができるか」と言えるレベルまで柔軟にしてきている。
  • 科研費制度としては、ここまで柔軟に使用できるようにしているので、これを如何に上手に使うかは、各研究機関の腕の見せどころである。

*1:専門書ではなく(素晴らしい)入門書ということになっていますが、このように(私にとっては)自分自身の良い勉強にもなりました

2009-10-07

東京大学理学部情報科学科(IS)紹介パンフレット2009年度版

ができたそうです。部外者が見ても(むしろ部外者のほうが?)カリキュラムなどがわかって面白いかもしれません。

http://www.is.s.u-tokyo.ac.jp/pamph/

(一括ダウンロードはhttp://www.is.s.u-tokyo.ac.jp/pamph/pdf/utokyo_ISguide2009.pdf