(n=2)
(n=3)
(n=4)
(n=5)
(n=6)
(n=7)
(n=8)n=12,15 のものは少し小さくしてあります。画像をクリックすると 大きい画像が見られます。
(n=10)
(n=12)
(n=15)
集合自身を要素として持つ集合を考えることは可能です。 例えば A={1,2,3} に対して、A の部分集合全体の集合
P = {B | B は A の部分集合} = {{},{1},{2},{3},{1,2},{1,3},{2,3},A}のような集合を扱うことができます (この P を A の巾集合といいます)。
しかし、有名な哲学者でもあったラッセル (B.A.W.Russell 1872-1970 英) は、 考え得る集合全体の集まりのような巨大な集まりをも「集合」と見なすのは 危険である、ということを次のような反例として指摘しました。
すべての集合の集まりを X とすると、それが集合ならば X 自身が X を含むことになる。 つまり、自分自身を元として含むような集合が存在することになる。よって、この X や Y のように大きな集まりは集合とはみなせない、 と指摘したのです。さて、ラッセルのいう矛盾がわかりますか ?
今、Y = {Z | Z は自分自身を元として含まないような集合}とすると、もし Y も集合だとすると Y 自身は Y に含まれるのか、 Y に含まれないのかを考えると矛盾が起こる。
なお、数学はその当時、集合論を基礎として厳密に構成されると 信じられていましたので、これらの矛盾は数学に対する危機として受け止められ、 集合論、証明論、論理学などをさらに厳密に矛盾なく構成する必要があることが 再認識されるようになり、そこから「数学基礎論」という学問が生まれました。 そして「数学基礎論」は、ヒルベルト、フォン・ノイマン、ゲーデルらの 天才的数学者がたずさわったにも関わらず未だ完成されてはおらず、 数学には様々な限界があることを示し続け、社会的に影響を与えた時期もあり、 20 世紀の数学の極めて大きな特色となっています。
(04/14 2001)0 がインドで発見される前の記数法は、漢数字による記数法のような、 計算には不便なものしかありませんでした。 0 の発見と位取り記数法の発明は、世界の歴史を動かす程の 非常に偉大なものだったのです。
古代の記数法がどのようなものだったかについては、 次の数学史のサイト
MacTutor Histroy of Mathematics (英セントアンドリュース大学のサイト)の下の 「古代の記数法、数の歴史」の項目に、以下のものがありました (全部英語ですが (^^;)。
エジプト, バビロニア, ギリシャ, インド, アラビア, マヤ, インカ他にも以下のようなサイトを見つけました。 ただ、どの位まともに書いてあるのかまではちゃんとはチェックしていません。 また、点字ではどうやって数字を書き表すか知っていますか。興味のある方は こちらへどうぞ。
参考文献:
講義では、C のデータ型を
short int = 16bit, long int = 32bitと紹介しましたが、これは「現在の多くの C コンパイラでは」ということで、 C 言語の仕様としてこう決まっているわけではありませんので、 実際はそのサイズはコンパイラに依存します。 C の仕様書ともいえる K&R 2nd. (「プログラミング言語 C 第 2 版」 B.W.カーニハン、D.M.リッチー) によれば
short int = int = 16bit, long int = 32bit32bit CPU 用の多くの C コンパイラは
short int = 16bit, int = long int = 32bitを採用していますし、64bit CPU の C コンパイラで
short int = 16bit, int = 32bit, long int = 64bitというものがあるようです。 64bit 整数は、最近は LONGLONG, __int64 (MS-Windows のコンパイラに多い), long long (UNIX のコンパイラに多い) のような型名として定義されていることも 多いようです。
自分の使っているコンパイラでは、short int, int, long int のサイズが 何であるか、調べてみてください。どうすればそれがわかるでしょうか。
なお、処理系によるデータ型のサイズの違いは、他の処理系へのソースの 移植を妨げる要因の一つです。 他にも、アラインメント、ビットフィールド、エンディアンなど、 ソースの移植、あるいは原因の分かりにくいバグが入り込みやすい余地は たくさんあります。
(05/24 2001)講義中に紹介したドラゴン曲線ですが、これの絵をいくつか紹介します。 有名な曲線ですから、どこかで見たことがある人も多いのではないかと 思います。
(n=2)
(n=3)
(n=4)
(n=5)
(n=6)
(n=7)
(n=8)
n=12,15 のものは少し小さくしてあります。画像をクリックすると
大きい画像が見られます。
(n=10)
(n=12)
(n=15)
わざと角を少し丸めてあるのですが、良く見ると、一度も交差していない ことが分かるでしょうか。 講義でも紹介したように、紙を n 回同じ方向に折って、その折り目を 90 度に広げてできる曲線なのですが、交差しないということは なんとなく納得できるでしょうか。
ただ、実際に紙を折って作れるドラゴン曲線は n=5,6 位 ?
(06/07 2001)教科書の p53 に、「このことは定義として受け取る方がよい」と書いてありますが、 それではあまりに何なので、多少説明してみましょう。
なお、教科書には "〜"(否定) と "または" の 優先順位について何も書かれていませんが、優先順位は "〜" の 方が上です。よって、「〜P または Q」は「(〜P) または Q」であって 「〜 (P または Q)」ではありません。
今、A=「P==>Q」、B=「〜P または Q」とし、(A が真) ならば (B は真) と、(B が真) ならば (A は真) を説明します。 そうすれば、A と B が等しいことになります。
そして、この事実によると、P が真でなければ 〜P は真になり、 「〜P または Q」は常に真になりますので、
前提 P が偽ならば 結論 Q が真か偽かに関わらず、 命題「P==>Q」は真となるということが言えます。間違った前提からはどんな結論も導けてしまうのです。 日頃の自分や他人の言動にも注意してみましょう。 (06/07 2001)
教科書 第 2 章の「論理」はこの講義の範囲ではありませんので、 勉強したい人は自分で勉強してください。 ただその場合、26 ページ 定理 2.6 はやや証明が不親切で、 また省略されているものもありますので、その証明を LaTeX で書いてみました。
下のいずれかをどうぞ。
PDF ファイルを追加し、HTML 版にそれへのリンクを追加しました。
(01/13 2009)
教科書 p96 例 3.6 に K(5) が平面グラフでないことの証明が載っていますが、 説明が不親切な点があります (|E|≧7×3/2)。 その説明と、ついでに K(3,3) (完全 2 部グラフ) が平面グラフでないことの 証明を書いてみました。
下のいずれかをどうぞ。
PDF ファイルを追加し、HTML 版にそれへのリンクを追加しました。
(01/13 2009)
教科書 p97-98 に、全ての頂点が偶数次ならオイラーグラフであることの 証明が載っていますが、その証明はやや難しく、 講義では、帰納法による構成的な証明を紹介したつもりだったのですが、 その証明にはいくつかの穴がありました。 それを厳密にしたものを書きましたのでここにあげておきます。
下のいずれかをどうぞ。
PDF ファイルを追加し、HTML 版にそれへのリンクを追加しました。
(01/13 2009)
ある単語の文字を並び変えて、別な単語を作ることをアナグラムと言うそうです。 ひらがなのアナグラムよりもアルファベットのアナグラムの方がバリエーションが 広いわけですが、 試験では私の名字で、そのアルファベットのアナグラムの総数を出題しました。
数え上げる方法、または読めないものを捨てる方法の 2 種類の数え方が あると思いますが、いずれもそう簡単ではありません。 色んな誤答がありましたが、多かったのは 'n' を 'ん' と読ませるのを 忘れている 36 通りという解答でした。 正解は、実はやや問題に曖昧なところがあり、2 つあるのですが、
アルファベットとして読めるものを作るには
"'t'+母音", "'k'+母音", 'n', "母音"の 4 つを並び変えればいい、ということになります。よって、2. の解は 4!×3! (3! は母音の入れ替えの数) として得られます。
1. の解も同様で、'n' 以外が先頭の場合 (=3×3!×3!) と、 'n' が先頭の場合 (この場合は "'n'+母音" である必要があるので 2!×3!) の和で 120 通りとなります。
読めないものを捨てるという考え方だと、重複して数えないようにする処理が 結構面倒です。 読めないための条件を集合を使って書き表し ('t' の次に 'k' がくるとか、 't' が最後にくるだとか)、 それらの共通部分などを丁寧に数えていけばできなくはありません。
ところで、このアナグラムですが、1. の解をひらがなに直したものを 最後につけておきます。 意味のある単語はほとんどありませんね。 推理小説ではこのようなアナグラムが使われることもあるようです。
ところで、以下の一覧はもちろん手で一つ一つ書いたわけではなく、 プログラムを組んで (AWK と sed と csh script で) それに吐かせたのですが、 皆さんもこのようなプログラムを自分で作ってみて (難しい ?)、 自分の名字や名前のアナグラムを作ってみたらどうでしょうか。 適当なアルゴリズムの実習になると思いますし、 自分の姓名に意外なアナグラムが見つかるかも知れません。
あけとん, あけんと, あこてん, あこんて, あてこん, あてんこ,なお、私の名前の方だと、 "shigeharu" ならば 432 通り ("sigeharu" ならば 578 通り)、 姓と名を合わせると、'ん' で始まるものを認めなければ、 "takenoshigeharu" で 69903360 通り (約 7 千万通り) もあるようです (試算ですので見落としもあると思いますが)。 この中には意外な文字列もあるのでしょうか。
あとけん, あとんけ, あんけと, あんこて, あんてこ, あんとけ,
えかとん, えかんと, えこたん, えこんた, えたこん, えたんこ,
えとかん, えとんか, えんかと, えんこた, えんたこ, えんとか,
おかてん, おかんて, おけたん, おけんた, おたけん, おたんけ,
おてかん, おてんか, おんかて, おんけた, おんたけ, おんてか,
かえとん, かえんと, かおてん, かおんて, かておん, かての,
かとえん, かとね, かねと, かのて, かんてお, かんとえ,
けあとん, けあんと, けおたん, けおんた, けたおん, けたの,
けとあん, けとな, けなと, けのた, けんたお, けんとあ,
こあてん, こあんて, こえたん, こえんた, こたえん, こたね,
こてあん, こてな, こなて, こねた, こんたえ, こんてあ,
たえこん, たえんこ, たおけん, たおんけ, たけおん, たけの,
たこえん, たこね, たねこ, たのけ, たんけお, たんこえ,
てあこん, てあんこ, ておかん, ておんか, てかおん, てかの,
てこあん, てこな, てなこ, てのか, てんかお, てんこあ,
とあけん, とあんけ, とえかん, とえんか, とかえん, とかね,
とけあん, とけな, となけ, とねか, とんかえ, とんけあ,
なけと, なこて, なてこ, なとけ, ねかと, ねこた,
ねたこ, ねとか, のかて, のけた, のたけ, のてか
