情報科学屋さんを目指す人のメモ(FC2ブログ版)

何かのやり方や、問題の解決方法をどんどんメモするブログ。そんな大学院生の活動「キャッシュ」に誰かがヒットしてくれることを祈って。

ブログ内検索

スポンサーサイト このエントリーを含むはてなブックマーク

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
スポンサー広告 | 編集

人工衛星が自分に当たる確率と140人の誕生日が異なる確率が同じくらいと聞いて このエントリーを含むはてなブックマーク

140人の誕生日が相異なる確率。 #人工衛星が自分に当たる確率の22兆分の1を一番わかりやすく何かに喩えた奴が優勝

このツイートを見かけて、「n人の誕生日がおたがいに異なる確率」の早見表をExcelで計算してみた。閏年ごめんなさい。

スポンサーサイト
数学・情報科学 | コメント:0 | トラックバック:0 | 編集

「言語哲学大全III 意味と様相(下)」の感想・書評・概要 このエントリーを含むはてなブックマーク

言語哲学大全 3 意味と様相 (下) 並列アルゴリズムの動作を検証する方法を学びたいというきっかけから時相論理と様相論理に興味を持ち、ひとまず様相論理に関する名著らしい「言語哲学大全 3 意味と様相 (下)」を読んでみました。感想などを書いておきます。以下、論説文モードで。

感想+書評

本書を読む以前は、「神は存在するのか」のような問題について考える学問が哲学であるとイメージしていた。しかし、それはあくまで古典的な哲学であり、現代の哲学には、はるかに広大な分野が存在することが分かった。哲学に対して同様に感じているのならば、その感じ方は本書を通じて大きく変わると思われる。

あらかじめ断っておくが、本書は様相論理や時相論理の使い方やそれを用いた証明を扱うことが目的ではないし、そもそも数理論理学に分類されさえしないだろう。本書が扱うのは現代の言語哲学である。様相論理はそもそも言語を分析するために生まれた論理であるので、まさに様相論理の源流にあたる学問である。また「現代の」とは主に1900年代後半であり、哲学に対する私のイメージからすれば驚くほど最近のことを対象とする。本書を読み進めることで、そのごくごく最近に様相論理を含めた言語哲学が大きく進歩したことが理解できたと共に、哲学に対するイメージは大きく変化することとなった。

言語哲学の大きな進歩とは、可能世界意味論の登場である。可能世界意味論は、可能性や必然性を表す言葉に意味を与える。そしてこれにより、可能性や必然性を扱う論理である様相論理は大きく発展した。そして現在、様相論理およびその応用である時相論理は、今では計算機科学分野でも応用され、システムの形式的検証に利用されている。本書では、様相論理の誕生から可能世界意味論の登場以前までにわたって、どのように扱われてきたかに触れ、様相論理の抱えていた問題を説明する。そして、可能世界意味論の登場によって、どう問題が解決されたかを詳細に述べ、これが言語哲学においていかに重要な出来事であったかを明らかにする。

また、この可能世界意味論が様相論理に限らず、様々な哲学分野で役に立つ道具であることを述べ、古典的な哲学の解釈にさえ影響を与えたことが明らかになり、この発明の影響の大きさに興奮させられた。その一方で本書では、可能世界意味論の登場により新たに生まれた問題について議論を深めていき、哲学の発展が現在へ続いていることを実感させてくれる。

書籍全体を通じて、後に否定される主張も含めた多くの主張と、それを扱った議論が紹介される。このおかげで、可能世界意味論誕生前後の哲学者たちが何を考え、そこにどのような背景が存在したかを読み取ることが出来る。これにより、表面的には難しい内容を、深いところから時間をかけて読み解くことが出来、結果、非常に得ることの大きい書籍になっている。また、その主張と反論の数々とその解説は、対象を哲学に限らない、理論の見方のようなものを示しているように感じる

"新しい理論が支持者に事欠かないのは、何が中心的な問題であり、何が周辺的な問題であるかの判断自体が変わりえたという理由によると考えられる。" (p.291)

Wikipediaには、本書が哲学(分析哲学)を専攻する日本の学生および研究者の必読書として不動の地位を占めているとされているが、必読書と呼ばれて当然と思える内容である。

数学・情報科学 | コメント:0 | トラックバック:0 | 編集

群論のおすすめ入門書 このエントリーを含むはてなブックマーク

情報科学という分野には、さまざまな分野が混在していますが、その中に群論という分野があります。

群論を勉強しよう

群論を勉強したからといって、プログラミングするのに突如役に立つと言うことは多くないと思いますが、暗号化や、圧縮の分野の基礎を学習する前提になっていたりします

ということで、群論を勉強するのにちょうどいい入門書を発見したので紹介します

数学・情報科学 | コメント:0 | トラックバック:0 | 編集

中国の剰余定理の使い方 このエントリーを含むはてなブックマーク

中国の剰余定理(中国人の剰余定理)って、よく聞くし、印象にも残るんですが、それを使った問題の解き方を忘れがち。ということで、中国の剰余定理の定番問題を解いてみます。とりあえず、例題はこちら。

以下の連立合同式を解け
x≡1 mod 3
x≡2 mod 5
x≡3 mod 7

なんだか定番らしいと言うか、問題自体はシンプルで、ありがちです。

さて、ここで中国の剰余定理を使うと、答えが以下のような形になることが分かります。

x≡??? mod 105

105は、3,5,7の積です。ようするに、具体的にxが一つ定まるのではなく、105で割ったあまりが???なら何でも解になるということです。

つまり、中国の剰余定理は、連立合同式のそれぞれの式「x≡a mod m」のmどうしが互いに素のときに、解が存在して、「x≡??? mod m_1*m_2*…m_n」の形になることを教えてくれます。

つまるところ、実際の解の求め方を教えてくれるわけではないんですね。

さて、解いてみましょう。

まず、解はたくさんあるのですが、そのうちの一つを求めます。

その一つである「x」はどういう形になるかというと、こんな形になります。

x=a*5*7 + 3*b*7 + 3*5*c
ただし、以下を満たす
a*5*7 ≡ 1 mod 3
3*b*7 ≡ 2 mod 5
3*5*c ≡ 3 mod 7

実は、このa*5*7 + 3*b*7 + 3*5*cという数には秘密があって、a*5*7+3*(b*7 + 7*c)なので、3で割ると、a*5*7が余ります。同様にして、5で割ると3*b*7が、7で割ると3*5*cが余ります。

つまり、もし3つの条件を満たすのならば、xは確かに問題の連立合同式を満たすことになります。3で割ったら、a*5*7があまって、実はa*5*7自体を3で割ったら1あまるので、結果xを3で割ると1余るので。2つめ、3つめの式も同様です。

こんな説明で伝わるか気になるんですが、ここが一番重要だと思います。ちょっと考えてみてください。

さて、ここまできたら、解のうちの一つxを求めることは、a,b,cを求めることなのですが、 たとえば、aは次のようにして求めることができます。

a*5*7 ≡ 1 mod 3 より、
35a ≡ 1 mod 3
右辺に3をいくら足しても、3で割ったときのあまりは変わらないので、69を足して
35a ≡ 70 mod 3
両辺35で割ると、
a ≡ 2 mod 3

なんでここで69を足したのかというと、次のところで35で両辺を割って、左辺をaだけにしたかったからです。

同様に、

3*b*7 ≡ 2 mod 5
21b ≡ 2 mod 5
21b ≡ 2 + 5*8 mod 5
21b ≡ 42 mod 5
b ≡ 2 mod 5

3*5*c ≡ 3 mod 7
15c ≡ 3 mod 7
ここは3で割れるので
5c ≡ 1 mod 7にしてから
5c ≡ 1 + 7*2 mod 7
5c ≡ 15 mod 7
c ≡ 3 mod 7

ということで、以下のようになりました

a ≡ 2 mod 3
b ≡ 2 mod 5
c ≡ 3 mod 7

これを満たすa,b,cならなんでもいいので、a=2、b=2、c=3にしてみると、

2*5*7 ≡ 1 mod 3
3*2*7 ≡ 2 mod 5
3*5*3 ≡ 3 mod 7

なので、これを使うと、

x = 2*5*7 + 3*2*7 + 3*5*3(= 157)

これは、連立合同式を満たす解のうちの一つになっています。

連立合同式を満たす一つの解が分かったので、他の解を考慮した解は

x ≡ 2*5*7 + 3*2*7 + 3*5*3 ≡ 157 mod 105
x ≡ 52 mod 105

と、なります。これで問題が解けました!

仕組みを冷静に考えると、そんなに奇抜なことをやっているわけではありません。ただ、解の一つをa*5*7 + 3*b*7 + 3*5*cと置けばいいなんて思いつかないかもしれないですけどね。

数学・情報科学 | コメント:0 | トラックバック:0 | 編集

OSの基本を俯瞰できる良書「オペレーティングシステムの仕組み」 このエントリーを含むはてなブックマーク

数日前に、「オペレーティングシステムの仕組み 」(朝倉書店)を購入しました。そして、3日くらいで読み、これは良書だと思いました。

オペレーティングシステムの仕組み (情報科学こんせぷつ)
オペレーティングシステムの仕組み (情報科学こんせぷつ)河野 健二

朝倉書店 2007-10
売り上げランキング : 232262

おすすめ平均 star
starかゆいところに手が届いている(と思います)
starOSの入門教科書

Amazonで詳しく見る

OS(オペレーティングシステム)の本ですが、これを知ることで、普段のOSの挙動が想像しやすくなるだけでなく、マルチスレッドプログラミングや、メモリ管理プログラムなどへの基本的な理解が深まります。

この本の重要なところは、本自体が分厚くないこと。だいたい、厚みにして1cmくらいです。

これがどうよいかというと、それぞれのトピックに深入りしすぎず、OSの基本的な内容を素早く知ることができるからです。

この本の内容は、OSの基本的な内容を網羅しており、以下のようなキーワードについて記述されています。(注意:目次ではありません)

  • 割り込み
  • ポーリング
  • メモリマップドI/O
  • システムコール
  • 特権モード
  • ユーザモード
  • プロセス
  • ヒープ領域・スタック領域
  • スレッド
  • コンテキストスイッチ
  • スケジューリング
  • CPU-bound・I/O-bound
  • FCFS
  • ラウンドロビンスケジューリング
  • 相互排除(mutex)・同期
  • マルチスレッドプログラミング
  • 競合状態(race condition)
  • 飢餓状態(starvation)
  • デッドロック(deadlock)
  • ライブロック(livelock)
  • ロック・セマフォ
  • メモリ管理
  • 仮想アドレス・物理アドレス
  • ページテーブル
  • TLB
  • 仮想記憶
  • デマンドページング
  • LRU
  • ファイルシステム
  • ネットワーク
  • セキュリティ

上記において太字になっている部分は、特に詳細に分かりやすく解説されています。

いずれの項目も、OSを理解し、プログラミングする上で非常に重要な内容なので、これだけ薄い本によくまとまっていると思います。

この本を読む前提として必要だと思ったことは、コンピュータアーキテクチャの基本的な仕組みです。プログラムが命令の列であるアセンブラとして実行されること、レジスタというものが何であるか、コンピュータにはメモリ(メインメモリ)とハードディスクに代表される二次記憶があることなどが前提知識となっています。詳しく知っている必要はないと思いますが、概要を知っていた方が読みやすいと思います。

特に、一度はOSについて勉強したことがある。講義を受けたことがあるという人にとっては、それらを確認し、内容を深めるのに非常に役に立つと思います。集中すれば十分1日で読めるので、明後日テストだという人のテスト対策にもなると思います。

この本がどれだけ有名なのかは知りませんが、情報科学に携わる、コンピュータ系の仕事・趣味をするのなら、読んでおきたい本だと思います。

数学・情報科学 | コメント:0 | トラックバック:0 | 編集
 | HOME |  OLD >>
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。