- 情報コース
- テレビ科目
- 辰己丈夫先生（放送大学教授）
- 高岡詠子先生（上智大学教授）
- 西田知博先生（大阪学院大学教授）
- 村上祐子先生（立教大学特任教授）
- 難易度 ★★★★☆
- おすすめ度 ★★★★☆
4人の先生が交代で、計算機科学の基礎となる理論をかなり突っ込んで解説する、導入科目とは思えないほど高レベルの講義が展開される。15回で数、暗号、プログラミング、アルゴリズム、確率、符号化、論理演算、記号論理学、などなど幅広いテーマを詰め込みまくりで高密度な講義が目白押し、理解できれば達成度も高いが難しすぎるという学生も大勢いるだろう。特に村上先生のパートは難解で理解に時間がかかる。個人的には、高岡先生パートがおすすめ。聞き手の雨宮さんは京大卒のイケメンで、理解力が高すぎて学生が置いていかれることもしばしば。
第1回
コンピュータにおける数の表し方から。聞き手は雨宮さん（男性、珍しい）
数と数字の違い。数字は数を表す文字のことで、表し方が多様である。数は文字で表さなくても概念として存在している。例えば個数。碁石でもテキストでもなんでも表せるし、文字で表さなくても表現できる。
個数を数える時は「同じ」かどうかで判別する。同じかどうかは相対的なものである。赤と青のコップがあったら、コップ自体は別のもので1つずつだが、「コップ」でくくれば2つとなる。
数の定義。自然数はここでは0を含むらしい。太文字のN。整数はマイナスを含んで太字のZ(Zahl：独)で表す。有理数は太字のQ(quotient：英)。実数はR。無理数は実数の行き着く極限という考え方らしい。例えばπは3→31/10→314/100→3141/1000→…と極限に進んでいくから。無理数＝比で表せない数のこと。
記数法とは。数字を使って数を表す方法で、文化によって違う。アラビア数字とか漢数字とか。私たちが使っている記数法を、位取り記数法という。アラビア数字を桁が上がるごとに左に追加していく記数法のこと。n進法は、n個の数字を使った位取り記数法と定義できる。十六進法は0x2C、十進法は0d44、八進法は0o134、二進法は0b101100などと書く。
いろんな記数法について。古代バビロニアの数字は10進法で0がない。ローマ数字はI(1), V(5), X(10), L(50), C(100), D(500), M(1000)を使う。444はCDXLIV。実例として昔の看板がでてきた。MDCCXLVIII(1000+500+200+40+8 = 1748年)。
そろばん。位取り記数法で10進法。十干十二支は位取り記数法ではない。十干と十二支を組み合わせて数字を表す（しらんかった！）なんと両方とも同時に動く。10と12だから組み合わせは10*6=60通りで、奇数ずれは存在しないから半分の組み合わせは使われてない。
命数法。大きな数を表すときに使う。万とか億とか。10の4乗ずつ進む。万進法ともいう。英語は千進法。なお、2進法で大きい数を使うときは、KiB(2の10乗＝1,024)が単位となる。ギガはGiB=1,073,741,824、2の30乗なので一般的なギガより少し多い。
桁区切り。ドイツは千九百を1.900みたいに書くらしい。フランスだとスペース区切りで、1 900。
辰己先生は文字通り、数字に強い先生だな！
第2回
二進法やビットについて。宇宙人の指が14本だったら？14進数になるのではないか、という話から始まった。
固定長表記と可変長表記。固定長と言えば電話番号と郵便番号、ロッカーとか。0が付く固定長と、つかないもの（ナンバープレートとか）がある。なぜ固定するか。範囲を決めておくと便利なことが多いから。固定長でオーバーフローすると、桁あふれが発生する。桁あふれが発生すると、右側だけ見て計算したのと同じになる。昔のゲームのバグはだいたいこれを利用したものが多いですよね。アイテム無限増殖バグとか。あれは桁あふれもあるけど、メモリ破壊を使ってる気もする。
二進法を十進法に直すやりかた。ちょっと変わったやり方をしてる。2倍して1を加えたり加えなかったり、を繰り返してる。たしかにそれでもあり。十進法→二進法は、高校でもおなじみの2で割っていくやり方。2倍して1を加える…のやりかただと、なぜ2で割っていって余りを並べていけば2進法になるのか、がわかりやすい。なるほどなー。これ授業で使ってみよ。
百進法。[00] [24]みたいに2桁で1桁というように扱う。[99] + 1 = [01][00]。見た目は十進法っぽい。なんで先に百進法が出てきた？いうと二進法と十六進法の関係がまさにこれだから。
2C9(16)→[0010](2) [1100](2) [1001](2)→1011001001(2)
110100100(2)→[0001] [1010] [0100] → 1A4(16)
というわけ。
小数とは。10進法なら1桁動けば10倍だけど、2進法なら2倍。小数点以下3桁なら8で割ればいい。2進法を2倍していけば10進法に直せる。が、2倍していっても一生終わらない場合があって、これは循環小数になる。二進法の循環小数も有理数になる。これは証明も可能。ちょっと速いのでここはテキストでしっかり復習したい。
椿の目付字。江戸時代に2進法があったという話。これいったいどういう仕組みなの。。？すげー不思議。
指数対数の話。対数の例としてデシベルの話を、放送大学の音声担当さんに取材してる。
デシベルは絶対ではなく相対的な話。音声業界では、最高に出せる音を0dBFSと呼んでる。放送大の音声は、-20dBFS（0dBFSの10分の1）を基準にしている。騒音レベルは、可聴範囲の最小限を0dBとしてそこから上げていく。100dBが地下鉄、120dBがジェット機くらい。なぜデシベルか。対数にすると刻みがちょうどいい感じになるから。100倍とか1000倍とか言ってもよくわからんし。
デシベルは20上がると10倍、つまり10の0.05x乗倍だけど、マグニチュードは1上がると31のx乗倍。1上がって31倍。2上がれば31の二乗で1000倍。でかいですね。
第3回
今日から高岡先生。計算とは何か、という話。
四則演算の仕組みの話。13*18の計算を筆算するときは、13*8と13*10を足す。
68*62を暗算するときはどうする？十の位が等しい、一の位を足すと10になる場合は、まず60*70 = 4200を計算する。さらに、8*2=16を計算する。足して4216が答え。なんで？
→(x+a)(x+10-a) = x^2 + 10x + a(10-a) = x(x+10) + a(10-a) で、x=60, a=8とおいたものと等しいから。xの1乗の項の係数がちょうど10になるところがポイントだと思う。
47*67はどうするか。十の位が足して10、一の位が同じ。
→(10a+b){10(10-a) + b} = 100a(10-a) + 100b + b^2 = 100{a(10-a) + b} + b^2 で、a=4, b=7とすればいい。(4*6+7)*100 + 49 = 3149となる。今度は、前半が100でくくれるところがポイントかな。
次に一般的な問題。13*18。ちょっと複雑なので文字で表すのは無理だけど、長方形を切り取って貼り付けて・・・を繰り返すと、(10+8+3)*10 + 3*8 = 234 と計算できる（らしい）。
32*26。32 = 20 + 12、26 = 20 + 6と考える。すると32 * 26 = (20+12+6) * 20 + 12 * 6 = 760 + 72 = 832となる。工夫の問題。
次は割り算。621 / 45はいきなり計算したくないが、ここで公約数3を考える。207*3 / 15*3 = (207/15) * 3 = (13あまり12) * 3 → 13あまり36(=12*3) と考えればいい。
合同式。5≡8≡11(mod 3)とか。5≡8→5倍してもいい。25≡40となる。
(17*19*23) / 13の余りは、17, 19, 23を13で割って、余りを掛け算すればよい。4*6*10≡4*6*(-3) = -72 ≡ -72 + 13*6 = 6となる。13*6を足すとこが、勘が必要になりそうな気がする。
で、ここまでの話はどうコンピュータに関係してるのか。東大の喜連川（きつれがわ）教授の研究室を訪ねた。ビッグデータがメインの研究で、ナンバーワン（＝競争が激しい）よりオンリーワン（＝誰もやったことのない）の研究をすることをモットーとしてるらしい。具体的にはでかすぎるデータ。サイバー空間内のソシオシステムというのが対象らしい。サイバー空間が現実の射影と考え、現実がわかるかも？という信念に基づく。日本語のページを全部集めたりしているらしい。
日本の一級河川のデータをリアルタイムで集めたものを研究したりもしている。25ペタバイト（！！）のデータがある。豪雨のときのデータなども集めている。あと、データベースの非同期による命令（！？）の研究もしているらしい。順序実行原理というものを開発して、プロセッサの数を増やさないでも100倍～1000倍の実行速度になったらしい。本当に珍しい研究が多い。発想で勝負できる。
非順序型データベースエンジンの解説。従来型データベースは処理順序がプログラムで決定されている。これを非決定的にする。ストレージが返せる順番で順番にデータを返していく。すると単位時間あたりの処理量がとても多くできる。実際のデモも見せてもらった。HDD24台分の10億件のデータを抽出する。従来型だとハードディスクが暇な時間が多い。20分かかる。非順序型にすると、ハードディスクのランプがよく点滅する。10秒で終わった。すげーー－。
仮想機械の話。チューリングマシン。現在のコンピュータと全く同じらしい。マシン、ヘッド、テープから成る。ある状態→テープから記号を読み取る→書き込む→ヘッドを動かす→状態が変わる、ということを繰り返す。これがコンピュータの基礎になる。トレースしないとよくわからん。要復習
第4回
誤り訂正、暗号化法など。
まずはパリティビットの考え方。最終列、最終行に偶数or奇数を決めておいてチェック用のビットを置く。するとエラーが発生しているかどうかわかるし、1ビットの誤りなら訂正できる。そういえばPCが「パリティエラー」ってエラー出してビープ音が鳴って起動できなくなったことがあったなあ。あれはメモリかHDDのデータが壊れてたんだな。
チェックサムも同じ仕組み。これはISBNコードでの例。
①チェックサム以外の奇数桁の和をとる。
②偶数桁は3倍して足す。
③①②の和の下一桁をとる。
④10-③とチェックサムが等しいかチェックする
ISBNコード以外のチェックサムは多分違う仕組みだろう。放送大のIDの最終桁チェックサムなんじゃない？商品のバーコードもそうだよね。
暗号。まずはシーザーの暗号から。アルファベットをずらす。ずらす文字数が暗号鍵といえる。共通鍵暗号方式である。鍵を第三者に知らせずに送信するのが難しいのが問題。
これを解決したのが公開鍵暗号方式。暗号化を公開鍵で行い、秘密鍵で復号する。秘密鍵を送らなくていいので安全だが計算量が多い。また、電子署名はこの逆で、秘密鍵で暗号化し、公開鍵で復号する。実は今までここら辺の関係を散々聞いてたのに全然わかってなかったのだけど、意味わかったので助かりました。
クレカの暗号化の仕組み(SSL)。SSLはハイブリット方式といい、共通鍵と公開鍵を両方使う。通信データの暗号化には共通鍵を用い、共通鍵を暗号化するのに公開鍵を使う。
具体的には、
①クライアントからSSLを要求
②サーバ→クライアントに公開鍵を送信
③クライアントは共通鍵を生成し、サーバの公開鍵で暗号化
④サーバはクライアントにもらった暗号化された共通鍵を、サーバーの秘密鍵で復号（鍵はデータ量少ないから復号が速い）
⑤これで共通鍵が両者に渡ったので、安心してクライアント⇔サーバ間で共通鍵で暗号化したデータを受け渡しする
ってわけか！よくわかった！
電子署名。本人証明と非改竄証明の両方の機能がある。本人証明には、なりすまし防止のため、PKIという仕組みがある。鍵の有効性を第三者に認証してもらうことで信頼性を高めている。非改竄証明については、平文→一定の手法で要約→秘密鍵で暗号化→受け手側が公開鍵で不幸語か→受け手が行った平文の要約と一致しているか確かめる、というやり方。ここでは要約って言ってるけど、たぶんハッシュ関数のことだろうな。説明しづらいから要約って言ってるだけで。
RSA暗号について。素因数分解を使うということまでは知ってたけどちゃんと解説してもらえるらしい。短時間でできるのか？
まず素数の説明。2と自分以外では割れない数。次に余りの話。合同とはnで割った余りが等しいこと。a≡b(mod n)のように書く。
RSA本体の説明。まず暗号化プロセスでは、平文をe回掛け算する。そしてnで割る。これを暗号化鍵(e, n)と呼ぶ。
復号プロセスでは、暗号文をd回掛け算して、nで割る。すると平文に戻る（！？）。これを秘密鍵dと呼ぶ。
このようなことが可能である正の整数e,d,nの組み合わせを作るのが難しいところが、RSA暗号のキモということになる。
前提として、平文をe乗して、さらにd乗すると、元の平文に戻るという仮定があるらしい。なんでed乗すると元に戻るのかは謎で、よくわからんかった。(→余りの話をしているから大丈夫と後でわかった)
さらに、割り算に使うnは、素数pとq（どっちも大きめ）の積ということにしておくと、edは(p-1)(q-1)で割った余りが1になるように選べばいいらしい（なんでじゃ！？→直観的には、余りを1にすれば、何度も掛け算していった後に最後の1乗が効いて、元の文が復元するからだと思う。要数学的証明→やりました https://t.co/v7J1KjcyG7 こっちも参照→RSA暗号の正しさを徹底的に証明する – Qiita）。
実例。
平文M=4とする。鍵に使う素数p=3, q=7とすればn=21、(p-1)(q-1)=2*6=12と互いに素になるように（なぜ！？→互いに素にしないと、edを12で割った余りが1にならないから）eを選ぶ。とりあえずe=5にする。
暗号化。M=4の5乗で、4*4*4*4*4 = 16*16*4 ≡ (-5) * (-5) * 4 = 100 ≡ 16(mod 21)。暗号文C=16になった。
次は、β=edの候補。 (p-1)(q-1) = 12で割った余りが1になる数は、13,25,37,…だけど、e=5にしたから、d=5(β=25)か17(β=85)にしないといけない。とりあえずd=5にする。
では復号化する。d=5にしたから、また5回かけてn=21で割る。16*16*16*16*16 = 32*32*32*32 ≡ 11*11*11*11 = 121*121 ≡ 16*16 ≡ (-5)*(-5) = 25 ≡ 4 (!!!) と、元に戻った。
公開鍵のnは公開しておいてもよいが、pとqが分からなければ破れない。つまり、素因数分解しづらいnを選んでおけばいいというわけ。nが100桁でも現代コンピュータでは結構難しいらしい。実際は300～1000桁のものが使用されているらしい。1桁上がるだけでめっちゃ破りにくいらしい。
やっとRSA暗号の仕組みがわかった！しかもほんの30分くらいで！先生ありがとう！
村上先生にチューリングのエニグマについて聞く。2014年イミテーションゲームという映画の暗号解読の話。ナチスドイツの暗号はエニグマというしくみで計算されていた。チューリングが作った自販機くらいの大きさの機械が出てきた。なんでこれで暗号復号ができるんだ！？こいつをつかってイギリスがナチスドイツの暗号を破って勝利したらしい。もっと暗号の度合いが高いローレンツ暗号器もイギリスがコロッサスという解読器で破ったらしい。でっかいテープを読み取る装置が出てきた。0.6秒に1クロックという速さだったらしい。当時、コンピュータは人間コンピュータを意味し、女性の仕事だったらしい。そういえばこの科目の教授、2人も女性がいる。中谷先生もいるし情報系は女性に相性がいいように見える。でも日本だと情報科学は男性ばっかに見える。何かおかしいのではないか。私も以前は情報科学は男性向きだと思っていたが、どうもそうではないらしい。
第5回
画像と音声のデジタル化の話。今日も高岡先生。
まず音の話。振幅と周波数、周期の説明から。雨宮さんよくわかってる人っぽいけど、調べたら京大院卒、日本科学未来館のコミュニケーターさんだったよ。
雨宮 崇 TAKASHI AMEMIYA | ブルーバックス (ismedia.jp)
さて音の波が0-1に変わるまではどうするのか。標本化→量子化→符号化をする。標本化とはデータを一定間隔で区切ること。よく言われるサンプリング周波数(44.1kHzとか)ってのは1秒間の標本化の数のこと。可聴周波数の2倍のサンプリング周波数が必要なのはなぜか。ナイキスト、クロードシャノン、等が「標本化定理」として証明したらしいから難しい話っぽい。要調査。それにしても予想を超えていつも一気に難しい話になるなあ。楽しいけど。
ハイレゾにはどんな意味があるか。聞こえない高周波、100kHzとかは脳によいと言われている。ハイパーソニックエフェクトやん。ここでも紹介されてる。
量子化は標本化した波形を離散的な整数の値に変換すること。ビット数が多ければ元の波形に近づく。音楽CDは16ビット=65536段階。ハイレゾは24ビット=1670万段階。ビットが変わると臨場感も変わるんだって。
最後に符号化。標本化と量子化で得られた数値を2進数で表すこと。2進数はビットの窪みで表せる。CDの量子化の掛け算を実際に行う。10分は16ビット=2バイト*44100Hz*10分(600秒) = 50MB。70分で350MB。ステレオなら2倍で700MBになる）。たしかにこんなくらいだね。
次は画像。標本化は画像データを区切ることになる。解像度とは画像をどのくらい細かく区切るかということになる。量子化は1つのピクセルをどのように表現するかという問題になり、量子化ビット数は色の数に対応する。モノクロなら2色、RGBならまあ24ビット640*480(古いな！)の生データは24*640*480=1MBになる。いわゆるフルカラーは24ビット1677万色だが、48ビットにすると281兆色（！）になるらしい。
次は社会の情報の可視化。喜連川研究室の取材が出てきた。ソーシャルメディアの可視化の話。ってtwitterじゃん。震災の際の情報の広がりを見た。阪神大震災に関連付けたある1つの避難情報（ガスの元栓を閉めろ！みたいな）をRTしていく様子が、まるで蜘蛛の巣っていうか花火みたいに広がっていく様子が可視化されている。もう少し縮小すると、微生物の繁殖みたいにコロニーがいくつかできている。コロニーはだいたい有名な人がリツイートすることでできるみたい。こういうノードのつながりみたいな可視化ツールってどうやって作るんだろうな。やったら楽しいじゃん。twitterはAPIも公開されてるし、作るの楽なのかもなー。リアルタイムで見ることができるとめっちゃ面白い。社会全体の動きを知ることができる。教授やマーケティングで実際にもう利用されてるらしい。
プリンタの話。モニタとプリンタと色の表現方法が違う。モニタは加法混色という。混ぜると明るくなる。RGB方式。印刷は減法混色。混ぜると黒くなる。CMYK方式。変換については印刷教材について書いてあるらしい。楽しみ。
ビットマップとベクタの差異について。ベクタは図形の点、線、面を数値で表したものなので拡大縮小には強いが、複雑な色情報を持つのが難しい。ビットマップ→ベクタの変換はまず無理らしい。
アナ→デジ変換について。実際に変換する（！？）。紙を縦に四等分して切ってる。2人ともA～Dと名前を付けて、Eiko, 雨宮と書いた(洗練されたYouTube動画なら、ここは5倍速再生してるところだ！)。先生がAに点を打って、雨宮さんが目視でBに同じ場所に点を打った。雨宮さんがAに点を打ち、先生がBに目視で点を打った。
次はAの紙を半分に折って、点が左にあれば0、右にあれば1と書く。以後繰り返して01を書いていき、線の上に点が乗ったら1と書いて終わり。実はこれで、紙の左側からどのくらいに点を打ったかが分かる。先生のAでこれを行うと、011となった。これは0.011 = 3/8ということになる。これは、点の位置のデジタル化に相当する。雨宮さんのAは0.111→7/8になった。
次にCにAで計算した値を書いて相手に渡す（デジタル信号の伝送）。さらにCを書かれた01に従って折っていき、点を書く（デジアナ変換）。次にAを交換するとA、B、Cを比較できる。AとCはデジタル変換なのでほぼあってるが、Bは目視（アナログ→アナログ伝送）なのでだいたいずれてる。という面白い実験でした。紙を使ってもデジタル伝送ってできるんだね！！
第6回
題名が「おはなしコンピュータ」！？今回から西田先生が4回担当する。関西弁だ。コンピュータがどうやって計算していくのかという話らしい。
まず温度計のようなPCを用意した（超ミニwinPC？）。温度センサーというinputをコンピュータが処理して、液晶outputに最高気温を出力する装置。
変数の説明から。変数委は名前と値が必要。アドレスと名前が紐づけられている。次は情報処理技術者試験でおなじみの疑似コードでif文、代入の説明。まずmaxにセンサーの気温を代入（ちゃんと初期化してた。）次はtempにセンサーからの気温を代入し、temp > maxならmaxを更新する。これを1分ごとに行えばOK。一日分なら1440回ループすればよし。
さっきのミニPCを図解してる。入力装置、出力装置に加えて、記憶装置、制御装置、演算装置で構成される。CPUにちゃんとヒートシンクついてる。記憶装置は主記憶装置（メモリ）と補助記憶装置（HDD、SSD、USBメモリ等）に分類できる。そういえばCD-ROMやDVD-ROMってもう下火だよね。みんなダウンロードになっちゃった。出現したときは革命だったのにもう割に合わなくなってしまった。
CPUとメモリの関係。CPUはレジスタ、ALU(算術論理演算装置)、特殊なレジスタ（プログラムカウンタ、命令カウンタ、メモリアドレスレジスタ）で構成される。レジスタはCPU内のメモリみたいなもん。プログラムカウンタコンピュータが次に実行する命令のメモリのアドレスを示すレジスタのこと。命令レジスタ、メモリアドレスレジスタは命令の保存、データの位置を保存するレジスタ。
アセンブリの疑似言語を使ってCPUの動きを見る。アドレスにloopやらloopendのようなラベルを付けて、番地と紐づけておいて命令で使う。命令は例えば「count(0016番地)の値が0以下ならばloopend(0013番地)に行く」のように書かれる。昔のBASICみたいだね。「1分待機」みたいな命令もあるけどこれ実際はアセンブリでどうやって実装されてるんだろうな。
実際のプログラム言語の説明。プログラムはあいまいさがなく実行できるような形式で記述する必要がある。雨宮さんも触ったことあるって（すごいレベルだと思う）。聞き手として優秀だなあ。
アセンブリ言語は低水準言語、CとかPythonとかは高水準言語。今回はPythonを使うらしい。Pythonはインタプリタ言語。実行するまでエラーがあるかどうかわからないからちょっと恐怖だよね。
Pythonはオランダ人グイド・ヴァンロッサムって人が作ったらしい。オランダ発なんだ。簡単（大事）、インタプリタ、動的型付け、ライブラリが多い（大事）ってことが特徴。
macのPython3.7.0 Shellを使ってる。5 + 4 – 2と書くと7と返ってきた。print(5*4/2)と書くと10.0となった。/2があるから小数になるらしい。print(10/3)は3.33333333333335になる。print(int(10/3))は3、print(10%3)は1になる(余り)。
m = "おはよう"
a= "こんにちは"
import datetime
datetime.datetime.now().hour →12 (12時なのか)
if datetime.datetime.now() hour < 12:
print m
else
print a
→"こんにちは"
こんなの作ってた。
第7回
本格的にプログラムを作るらしい。制御構造と計算の手順の話。
制御構造は順次構造、分岐構造と反復構造がある。順次構造はA→B→Cみたいなやつ。当たり前だけどこれがないと確かに進まないね。あとはifとfor。構造化定理：すべての計算手順は全部3つの構造で記述できる（そうなんだ！？）。たしかにこれ以外の構造ないかも。
計算の順序について。3 + 5 * 8は、3+5からか、5*8からか。私たちは5*8からやる。四則演算には優先順位があるから。優先順位が同じなら左から計算する。プログラム言語内でもいろいろ優先順位がある。
分岐構造。pythonなら
t = int(input("最高気温を入力してください:"))
if t >= 25:
print("夏日です")
else
print("暑くありません")
みたいな書き方をする。先生pythonのShellつかうのはやい。
反復。whileが例。
a=0
i=1
while i<=10:
print(str(i) + "を加算")
a=a+i
i=i+1
print("計算結果:" + str(a))
のように書く。forなら
a=0
for i in range(1, 11):
print(str(i) + "を加算")
a = a + i
print("計算結果:" + str(a))
のように書く。pythonの仕様上、range(1, 11)は1~10の配列を作るといった意味になる。zero based indexなのだろう。range(2, 11, 2) にすると、2,4,6,8,10の配列ができる。3つめの数字がstepを表すということだろう。応用すれば、nまでの和（rangeを1,n-1にする）とか階乗（rangeをn,0,-1にする）を求めることができる。
三角形の面積を求めるプログラム。底辺*高さ/2にすればよくない？input使って入力させてる（コードは略）。float使えば実数になるのね。pythonのfloat型って何バイト型なんだろ？
ヘロンの公式つかう場合。import mathとmath.sqrt関数を使う必要がある。で、三角不等式を満たさないといけないので、if a<b+c and b<c+a and c<a+b で括ってあげてる。まじめだなあ。でも三角不等式満たさないと面積が虚数になったりするから仕方ないか。
FizzBuzzゲーム。3の倍数ならFizzと言う。5の倍数ならBuzzという。15の倍数ならFizzBuzzという。これがプログラム志願者の適性を見分ける問題として知られるらしい。
あ、アレクサ出てきた！アレクサでもできるのか！！！
アレクサと雨宮さんが対決している！！負けた
コード的にはこんな感じ
for i in range(1,101):
if i%3 == 0:
print("Fizz")
elif i%5 == 0:
print("Buzz")
elif i%15 == 0:
print("FizzBuzz")
else:
print(i)
これは間違い。15の倍数の時にFizzになってしまう。正しくは15の倍数かどうかを先に判定する。
for i in range(1,101):
if i%15 == 0:
print("FizzBuzz")
elif i%3 == 0:
print("Fizz")
elif i%5 == 0:
print("Buzz")
else:
print(i)
私なら上のように書いちゃうけど、面白い別解もある
for i in range(1,101):
if i%3 == 0:
print("Fizz", end="") #改行しない
if i%5 == 0:
print("Buzz", end="") #改行しない
if i%3 != 0 and i%5 != 0:
print("FizzBuzz")
else:
print(””) #いらないんじゃね？と思ったけどここは改行のため入れてる
あー言われてみればなるほどだわ。さらに、割り算を使わない別解
n3 = 3
n5 = 5
for i in range(1,101):
fizz = ""
buzz = ""
if i == n3:
fizz = "Fizz"
n3 = n3 + 3 #次の3の倍数を指す
if i == n5:
buzz = "Buzz"
n5 = n5 + 5 #次の5の倍数を指す
if fizz == buzz:
print(i) #3の倍数でも5の倍数でもないから数字を出力
else:
print(fizz + buzz)
これは思いつかないわ！！
第8回
アルゴリズムについて。
いきなりプログラムを書くと失敗するので、まずアルゴリズムを書くのがよいという話。そーだよね。
アルゴリズムの定義。問題の解き方の手順を明確に示したもの。フローチャートみたいなやつでもいいし、表現方法は何でもいいが、あいまいさがないようにすること。
アルゴリズムが充たすべき性質。健全性：正しい答えが出ること。停止性：有限回で終わること。両方を満たすと完全性があるという。絶対これが充たされるとは限らないので、近似的にこれを満たすような近似アルゴリズムという考え方もある。特に統計的な話だと健全性を満たすのは難しいよね。
ユークリッドのアルゴリズム（最古のアルゴリズム）。
aとbが等しくない間、以下を繰り返す
aがbより大きければ、
a = a - b
そうでなければ
b = b - a
最大公約数としてaの値を表示
36と24の最大公約数なら、a=36, b=24→a=12, b=24→a=12, b=12で12
11と30の最大公約数なら、a=11, b=30→a=11, b=19→a=11, b=8→a=3, b=8→…→a=1, b=1で互いに素
なるほどねー。で、これはなぜ正しいのか！！？？
引き算を割り算で置き換えられる。引き算しているのを割り算の余りにすれば次のようになる。
a≧bを仮定する
bが0でない間、以下を繰り返す
aをbで割った余りを新しいbとする
元のbを新しいaとする
最大公約数としてaの値を表示する
これでユークリッドの互除法になった。計算は同じ。引き算って割り算の余りなんだな！
アルゴリズムの手間の話。ユークリッドの互除法は数回で済む。n^2とかの話かな？と思ったけど途中で終わった
おかあさんといっしょのアニメが出てきた。正方形の迷路の数え方。1*1なら2通り、2*2で12通り。3*3で182通り。4*4で8512通り（！）。ではどういうアルゴリズムを使えばいいか。二分木を作るとよい。道にA, B, C…と名前を付けて、二分木を作っていく。ところが真面目に二分木を作ると2*2でも8190本の二分木ができてしまうので、いろんな工夫によって37本まで減らすことができる（具体的にどうやるんだ！？）4*4でも2兆。16*16で不可思議とか使っても全然表せない天文学的どころでもない数字になる。これがAIのとこでよく言ってた計算爆発ってやつか。グラフ処理はpythonだとGraphillionというツールでできるらしい。
大根のいちょう切りのアルゴリズム。40片のいちょう型が欲しい。使える操作は輪切り＋十字切りのみ。
①輪切り*9＋十字*20 →29カット
②十字*2→半円柱の輪切り*9 *2→20カット（①より早い）
②で円柱のままやれば11回だが無理。なので②が妥当。アルゴリズムは、現実的実施可能性も大事になる。
次は金種計算の話。お釣りをどういう紙幣・硬貨で払うか。なるべく硬貨が少なくなるようにしたい。
高額の硬貨から順に支払えるだけの枚数を支払う→枚数最小、過不足もない。これを貪欲法という。問題を分割し、それぞれ最も好ましい解を選ぶ方法。今回は大丈夫だけど、毎回妥当とは限らない。
500で割って余りをとる、100で割って余りをとる、50で割って余りをとる→同じ処理じゃない？そこでpythonではリストを使って、処理をひとまとめにする。[500,100,50,10,5,1]で割って余りをとっていけばいい。
Kinshu = [500,100,50,10,5,1]
kingaku = int(input("金額を入力してください："))
for k in Kinshu:
n = int(kingaku/k)
if n > 0:
print(str(k) + "円玉×" + str(n))
kingaku = kingaku - k*n
7行でできた！
逆に財布から小銭を支払う場合は、自分の持っている硬貨の枚数を最大値として保持していないといけない。枚数を配列に保持し、入れ子型の配列にすればいい。KTabke = [[500,1], [100, 2], [50, 3], [10,12], [5,4], [1,10]]みたいに財布の中身を表現すればよし。コードはちょっと長いので略します。要は枚数の最大値まで払うっていうif文を入れるだけでいいんだけれども。
こういう形でアルゴリズムを紹介するってことは、プログラムってのは数学的にはアルゴリズムの写像って考えていいのかな？
第9回
アルゴリズムと能率について。問題を解くときにかかる時間の話をしてくれるらしい。計算量とその評価がメイン。
計算は使う資源が少ないほど効率が良い。資源には時間、空間（メモリ）がある。最大公約数を求めるプログラムをforループで総当たり（2～最小値まで公約数かどうか判定）で実現すると、例えば10179と24360の最大公約数を求めると20356回も割り算をすることになる。ユークリッドの互除法なら6回。ここには大きな差がある。つまりアルゴリズムには良し悪しがある。
どうやって評価するか。時間だけで評価してもいいが環境に左右されてしまう。なので主要な処理が何回行われるかを調べればいい。さっきの話なら前者は2(n-1)回（常に）、後者なら5log10n以下（ラメの定理？より）になる。logが出てくると一気に強くなるね。しかも以下なのでもっと少ないかも。計算量は2のn乗が一番大変で、logが出てくるとすごく小さくなる。
漸近的評価。nが非常に大きい時だけを考えればいいから、主要な項だけ考えればいいし、2もいらない。2(n-1)はnと考えてしまえばいい。2nの2だってコンピュータが発展すればすぐ覆いつくされるので。。と先生は言ったが確かにそのとおりだ。で、これをオーダといってO(n)などと表す。オーダの定義は、カッコの中の値で割ってnを無限大に飛ばせば定数になる、ということ。
さてnの10000000万乗と2のn乗は、2のn乗の方が速い。ここでまた前回のおかあさんといっしょのVTRに飛んだ。高校数学でよくある迷路の問題って、最短経路だから場合の数はたいしたことないけど、最短ではない経路も含めると本当にやばい数が出てくる。数えるのも大変。例えば5*5の迷路は126万通り。6*6は5.7億通り。7*7は7893億通り。8*8。3266兆通り。2のn乗のオーダで増えるとこんなに大変なことになる。
京大の湊先生。アルゴリズムは目に見えないので、目に見えるようにいろんな展示を作る努力をしていらっしゃる。さっきのおかあさんといっしょのビデオも京大のグループで作ったらしい！
年月日から曜日を計算するアルゴリズムについて。西暦1年1月1日以降の任意の年月日を計算する。
普通は1年で1つ曜日がずれるが、閏年は2つずれる。曜日を数字で表し（0が日曜とか）、1年1月1日の曜日に毎年ずれる日数を加えて7で割ればOKじゃない？これを基準日から計算するアルゴリズムという。
これを実現すると、forループが2個できる。1個目は年ごとのずれの判定、2個目が今日を表す月の日数を足していくループ。1個目のループは年nの繰り返し。2個目は最大11回なので定数。計算量はO(n)となる。
ツェラーの公式で計算する。年＋閏年のずれ（切り捨て）＋月のずれ（切り捨て）＋日数を7で割る。月のずれの所がこの公式のすごいとこで、(13m+8)/5で計算すればいいらしい。7で割ると、前の月までの日数を7で割った値と同じになる。上手に調整した感じの数。こういうのを見つけるのが数学マニアってやつですよね。これはオーダがO(1)で計算できてしまう。はやい。
探索処理。ランダムに並んだ15枚のカードから指定した数を選ぶ。普通は前から総当たりで攻めていくしかない。これを線形探索という。最悪n回で平均はn/2回。オーダはO(n)になる。
順番に並んでいるデータを探索する方法。2分探索法が有名。真ん中のデータを調べ、大小を比較してから次に探索する範囲を半分にする。私も、どのソースコードの変更で不具合が起きたか、履歴を総当たりで調べなければならない時によく使う。オーダーはO(log2n)となる。n=100000でも最悪17回で探せる。はやい。雨宮さんは2分探索知ってるみたいだった。
第10回
いろんなアルゴリズム、特にソートについて。辰己先生に戻ってきた。
探索の計算量について。2分探索の計算量はなぜlognになるのか。これは漸化式で求められる。つまりk回の操作でak個の数が判断できるなら、a1=1, ak+1 = 2ak + 1を解けばいいってわけ。これを解くと（中略）ak = 2k-1なので、n = 2k-1とすると、逆算してk = log2(n+1)となる。なるほど！！
先生、放送大学図書館に来た（行ってみたい！）。本の探し方、並べ方について聞きに来た。The art of computer programmingを調べたい。司書の人異様にタイピングとPC操作速い。番号が出たのですぐ見つかった。もし本がばらばらに並んでいたら、全探索するしかない（詰む）。
ソートとは。ある関係に従ってデータを並べる作業のこと。「ある関係」は任意のものである。整列されているデータ、されていないデータで大きく使い勝手が異なる。コンピュータは大小関係しか判断できない（これがコンピュータの頭悪い所だと思う）ので、大小関係を何度も判定して全体を並べるアルゴリズムが必要になる。
まずバブルソートから。隣り合う2枚を総当たりで全部比較する方法。一度全部比較したら最大値だけ取り除いてやり直し。計算量はO(n2)で、まあまあでかいオーダ。実務でもC++だとコード書くのが面倒なときに使ったことがある。
選択ソート。まず左端の値を決めたいから、最小値を選んで一番左に置く。次に最小から2番目の値を選ぶ。。。と繰り返すが実質バブルソートと同じで、オーダもO(n2)。
挿入ソート。整列済みの配列に挿入していく。まず1枚の場合は何もしなくていい。2枚目は前か後ろにつける。3枚目は適切な位置に挿入する。。。を繰り返す。手間がかかる場合（降順に並んでたら大変）とかからない場合（最初から整列済みならなにもしない）がある。オーダは最小O(n)～最大O(n2)。
マージソート。整列されてないリストを2つに分割してから、整列して、マージ。これどういうメリットがあるんだ？分割は再帰的にできるので、まず全体を全部2つずつに分割。それぞれ大小比較して整列する。次にマージして4つにする。8つにする。以下繰り返し。人間がやると大変だが、計算量はnlognになるのでだいぶ小さい。なぜnlognになるかというと、やはり漸化式（証明はちょっと長いので略）。
最後にクイックソート。リストにおいてある値を軸として分割を繰り返して整列させる（！？？）。なんのこっちゃ。
とりあえず1つ軸を選ぶ。1～15のカードで8を軸とする。次に8より小さいシリーズ、大きいシリーズに分ける。小さいシリーズの中でまた軸を決め、大小に振り分ける。振り分けたとこのサイズが1~2だったらそこで大小比較して、軸の左と右に置く。これで軸を含む要素がソートされた。で、しかもソート済みの要素はこれ以上マージする必要もなく結合するだけでいいから、結構はやい。計算量は印刷教材を見よだって。いったいいくつなんだ。
n2とnlognの計算量はどのくらい違うか。n=10で後者は1/3の計算量で済む。n=100だとどのくらいなの？
組み合わせ爆発の話。正方形の迷路の道順を真面目にスパコンで計算すると9*9は6年半、11*11は290億年かかるらしい。雨宮さんによるとこの間の話が面白いらしい。で、動画に戻る。なかなか強烈な動画なので皆さんにも見てほしい。っていうかこの動画、科学技術館のやつだし雨宮さんのチームが作ったんじゃ、、
オチが。。。悲しいです。。。
最後に無限の猿定理の話。サルが適当にキーボードをたたくと偶然シェークスピアの小説が出てくるかもしれない？か？実際計算した人もいるらしい。これも組み合わせ爆発の話で、2-3文字なら簡単に出てくるが、数十文字になると無理になってきて、結局、シェークスピアの小説のごく一部分が出てくるだけでも数百億年以上かかるらしい。公開鍵暗号もいっしょ。適当な数字を並べていけばいつかは当たるが、まず当たらない。
第11回
集合と確率の話。
外延的な記法と内包的な記法について。列挙するのが外延的 {1,3,5}とか、定義を書くのが内包的 {x|x≧1}とか。
集合が同じとは、ある要素がすべて別の集合の要素である、逆も成り立つ、ということをいう。大学受験でたまに使う論証だ。なお、この定義だと同じ要素が複数入ってることは考慮されない。
命題の真偽で定義する積集合と和集合の話。ベン図で書ける奴やつ。補集合と全体集合も出てきた。補集合を考えるためには、必ず全体集合が何なのかを考えなければいけない。
中国人剰余定理。「aとbの最大公約数が1のとき、ax+by=1を満たす整数x,yが必ず存在する」
例えば11x – 7y = 1→x=2, y=3。21x-7y=1→解なし。じゃあこれを一般的にどうやって説明するか。
a=11, b=7とすると、11k-1を7で割った余りは、k=0,1,2,3,4,5,6に対して6,3,0,4,1,5,2となる（重ならない）。これはどのような互いに素なaとbについても成り立つ（余りが等しいと仮定すると、引き算した時bで割り切れてしまうから、矛盾を導ける）。つまり全体として集合が一致している。で、必ず余りが0になるところがあるから解があるという論理の流れになるらしい。
フェルマーの小定理。「pを素数とする。aがpで割り切れないとき、ap-1はpで割り切れる」
実例。a=2, p=13として、2の12乗は4096で、(4096-1) / 13 = 315余り0となる。適当な数字が素数かどうか判定できるテストの第1段階として使える。
証明の概略。途中までは中国人剰余定理と同じで、pで割った余りの集合が1~pになるねって話。そのあとが難しい（略、印刷教材見よ）。二人ともほ～そうなんだ～って感じでスイスイ進んでいくけど私全然わかんないです。大事なのは集合が使われているって話です。
この定理、どこで役に立つか。公開鍵暗号でこの定理がないと先に進めない。ので暗号で役に立つ（以前私も証明に使いました）。
確率の定義。「その自称がまだ起こっていない状態で、起こりえる可能性があるかを数値的に表現したもの」。確かに起こってない！！打率みたいにすでに起きたことは「記述統計」という。確率とは違う。
事象→起こっているか起こっていないかをはっきりと判定できること（確かにはっきり判定できないとダメだ！）
確率変数→とりうる値の集合（確かに！？）
5回に1回傘を忘れるAさんがA, B, Cの教室で授業を受け、傘を忘れた。それぞれの教室に忘れた確率を求めよ。
考え方の例：125本傘を持ってきたと仮定→Aに25本忘れる、Bに20本忘れる、Cに16本忘れる。忘れた本数は61本だから25/61, 20/61, 16/61。これは思いつかないっす。。いきなり難しい例です。
さらに難しい例。モンティ・ホール問題。宝物を当てるゲーム。3つの箱から宝物を選ぶ確率で、どういう戦略をとるのが賢いか考える話。ちょっと言葉で説明するのが難しいのでこれも印刷教材見よう。
モンテカルロ法。あーこれ昨日アルゴリズムとプログラミングの講義でやったやつや。この授業では視覚的にやってる。米を円を書いた紙の上に均等にばらけさせてから、円周の中と外の米粒の数を数えることで円周率を計算するってわけ。143個と491個になった。合計634個で、理論的には全体と円の面積の比が1 : π/4だから、π = 4 * 491 / 634となるはず。3.0977なのでまあまあいい値になった！！
単純な計算方法が見つかってない場合はいまでもモンテカルロ法を使ってる。囲碁のAIとか（そうなの！！？？）。ランダムに試合をすると勝つ・負けるが確定するから、勝つように学習を重ねていけばいい。1秒で1局できれば1日で何十万局もできるじゃんってわけ。なんかわくわくしてきたぞ。音楽とか絵とかはどうすればいいんだ？→人間が評価していくしかないって話になった。でも、一定の評価方法が確立していれば音楽でもできるのでは。。？これは研究に使えそうな気がするぞ。論文いっぱいできてるだろうし調べてみよう！
第12回
高岡先生だ！データと計算量について。特に量についての話になるらしい。
情報とは何か。シャノンの情報理論だ。はい-いいえの質問に答えると1ビット使う。8個の選択をするためには3ビット。2のn乗をの選択肢の中から1つの情報を伝えるにはnビット必要。ただし、全部等確率という仮定が必要。じゃあ等確率でない場合も考えないといけない。
ある事象が起こる確率をP(X)、情報量をH(X)とすれば、H(X) = log21/p(X) = -log2P(X)と定義できる。例えば確率1/8ならH(X) = 3ビットになる。つまり確率が低ければ情報量が大きくなる。確率が低ければ受け取った価値が大きいということになる。例えば宝くじが当たることを誰かが教えてくれれば、その情報は価値が高い。
情報源の話。なんか歯ブラシいっぱい出てきた。4つ+4つの歯ブラシと、8本異なる歯ブラシ。平均情報量は、個々の情報量*確率を足したものと定義できる。前者は確率1/2で4本ずつなので、1ビット*1/2 が2種類、足して1ビット。後者は3ビット*1/8 * 8 = 3ビット。まあ確率が全部同じだからそうか。平均情報量（≒情報エントロピー？）は、ネットワークの通信速度などで使われるらしい。エントロピーが高い→知らないことが多い、エントロピーが低い→知っていることが多い、ということ。情報の圧縮（エントロピーが低いと圧縮しやすいのかな）とかAIとかでも使うらしい。
東大の豊田先生の研究室へ。ドラレコのデータをビックデータにして研究してる。事故が起きた場所と運転状況を掛け合わせる（かける！？）といろんなことが見えてくるらしい。事故が起きる場所はパターンがあり、まだ起こっていないとしても、事故が起きやすい場所もわかってくる。すると事故の起きにくい場所をナビするということができる。
次の話。道の凸凹をスキャンするシステムを作った。業務用車両にセンサーを付けてもらって情報をとってきたらしい。地図で可視化すると道の状態が悪いところがよくわかるので、自治体がどこを優先に直していいかがわかる。経時的情報もあるから、道の補修履歴もわかる。ズームするだけで詳細な情報が出てくるからめっちゃわかりやすい。すげ。
次も東大の生駒先生の気象データについての話。いろんな気象データを統合するためのシステムを開発してるらしい。理系らしい、めっちゃ見づらいスライドや。しかも速い。とりあえず気象データが発展して詳細になったことがわかった。DIASというシステムで基本的なデータベースやネットワークを提供し、使いたい人がアプリを作ってDIASにアクセスしてデータを持ってくる基盤を作った、ということもわかった。基盤作るのって大変だよね。だれでも使えるような仕様策定がめっちゃ大変そうだし障害も頻繁に起きそう。
雨宮さんが突然01100011みたいな暗号を出した。それから暗号解読表も出してきた。ところが解放が一意に安定しないという欠点が見つかった。これを一意復号ではないというそうだ。また、順次に復号できていって、最初からやり直しにならないことが保障されていることを瞬時復号というらしい。しかし高岡先生って感情表現が極端に苦手な感じがする。本当は気持ちが大きく動いていると思うのだけれども。瞬時復号を満たすための必要十分条件ってなんだろね。二分木が完璧に作れることなんだろうけど、数学的にはどうなんだろ？
平均符号長とエントロピーについて。平均符号長はエントロピー以下になることはない（情報源符号化定理）。例えばA B C D を 11 10 01 00 で表すとすると符号長は2ビット、確率1/4で等確率。平均符号長は2ビット。エントロピーは2ビット * 1/4 * = 2ビット。直感的には、確率がばらけると平均符号長はかわらないがエントロピーが増える気がする。講義でも確率がばらける場合を計算してるけど平均符号長＝エントロピーになった。エントロピーに平均符号長を近づけていくと効率が良くなる→エントロピーまでは圧縮できる！ってことらしい。
17歳男子の身長分布。きれいな正規分布になってる。最頻値、平均値、中央値が大体同じ。標準偏差をsとすると、-s～sの間にだいたい68%が来る。2sなら95%。17歳男子のデータを見る-s～sの間に73%、2sの間に96%。やはりほぼ正規分布である。体重は正規分布に従ってない。左に山が偏っていて、最頻値60、中央値61、平均値62.6kg。3つの値がずれていない＝ほぼ正規分布であるということになるらしい。
第13回
今日から最後まで立教の村上先生。一階述語論理について。日常言語を論理言語に翻訳する所がメインらしい。
文と命題の違いについて。命題とは真偽が一義に決まる文のこと。文はそうでもない。「この問題は難しい」、とか、「それをとってください」とか。
で、科学的命題とは、真偽が実験・観察等の統計的な確かさにより決まる文のことを言う（えっ、100％じゃないのを命題って言っていいんだ！？）。例えばカラスは黒いということは、白いカラスは無視する。統計的に高い確率で成立すればいいや、ということ。これに対して演繹的命題は、真偽が100%はっきりしている命題のこと。例えば、一次方程式ax+b=0には解がある、という命題について。
「この一次方程式ax+b=0には解がある」→aとbが不明だから命題ではない
「一次方程式ax+b=0（a=0、b≠0）には解がある」→偽→命題である
「一次方程式ax+b=0には解がある」→偽→命題である ※最初に「すべてに」を補わないといけない。暗黙の量化という。あっこれ慶應の論理学でやったやつや。
全称量化→∀のこと。「すべての」と表現する。
存在量化→∃のこと。「ある」と表現する。
この授業では記号を使ってないのでわかりづらい。
量化の例。Everybody loves somebody. は①「誰もに好きな人がいる（全員が誰でもいい誰かのことが好き）」②「誰もが好きな人がいる（特定の1人のことを全員が好き、本人含む）」の2通りに取れる。①は∀∃、②は∃∀と表現すればよい。
じゃあこれを否定するには？「誰もに好きな人がいるわけではない（ある人が存在して誰も好きでない人がいる）」￢∀∃「誰もが好きな人がいるというわけではない（すべての人に好かれている人は存在しない）」￢∃∀
「すべてAだ」「Aでないものがない」は同じ意味。
「あるものはAではない」と「Aでないものがある」は同じ意味。
雨宮さん、ついていけてるけど正直ぜんぜんいみわからん。記号で表現してください。たのんます。
空虚な真について。そもそも対象がない場合は反例を作れないから絶対に真になる。否定が不可能＝真である命題を空虚な真という。これってあれか？反出生じゃん。「まだ存在していないわが子がかわいそう」みたいなやつ。これぞ空虚な真。真だけど意味がない。つまり論理的真であることは真実を意味しないかもしれない。
「ならば」について。Aが偽か、Bが真なとき。前者は直感に反する。前者は反例を作ることができないからって理屈。前提が間違っているときは必ず「ならば」が成り立ってしまうというのは、皮肉な感じがする（慶應の論理学でも思った）。それにしてもこの授業は早すぎていみわからん。駆け足すぎる。AならばB、の場合は包含関係が成り立たないといけない（B⊂A）。ベン図のよくある重なってる奴だと絶対成り立たない（反例があるから）。
ってか記号使ってくれよ！意地でも使ってないけど印刷教材では使ってるんだろうか？
カードゲームで論理の話をしている。ちょっとわかんないです。どうも対偶の話をしているような気がする。対偶を調べれば勝てるみたいな感じ？あっやっぱそうか。
条件文と同値文の違い。日常言語だと「ならば」を同値文の意味として扱うことがある（ここはスライド作ってください！）例えば「雨が降っていたから動物園に行かなかった」は同値の例。逆が真だから。あれそうか？雨が降ってなくても動物園に行かないかもしれないじゃない？
演繹的推論について。0個以上の推論を使って結論を導くこと。妥当な推論とは、すべての前提が（内容にかかわらず）真なら結論が真になる推論のこと。まともな推論（？）とは、前提が実際にすべて真であるような妥当な推論のこと。
結論だけの妥当な推論はあり得るか？例えば1=1かな？
妥当な推論は空虚な真も含まれてしまうので、中途半端な感じだそうだ。
妥当な推論の例。三段論法。クジラは哺乳類である、哺乳類は温血動物である→だからクジラは温血動物である。集合の包含関係が成り立つから必ず成り立つ。
妥当でない例。たまたま前提も結論も真のケース。例えば、クジラはサメではない、クジラは哺乳類である→だから、サメは哺乳類ではない（サメをイルカに変えるとおかしさが分かると考えた）
前提がすべて真だが結論は偽のケース。ハトはスズメではない、ハトは鳥である→だから、スズメは鳥ではない（上のイルカの例と同じ）。だからこの推論はおかしい、妥当ではない。
妥当であるかどうか調べる方法。同じパターンの推論で、前提が真なのに結論が偽になるシナリオ（＝反例）が存在するかどうかを調べる。とにかく反例を考えなければいけない。たいへんや。なので、これを自動化したい気持ちがある。すると一階述語論理が出てくるらしい。で、それを実装したのがコンピュータってわけ。と考えると面白くなってくるね。
第14回
タブローによる計算の話。タブローって慶應通信の論理学でもちょっと出てたあれだ。
妥当性の検証を自動的に行うのがタブロー法らしい。
言語とは何か。共通している文法があるものが言語？シグナルの部分と意味の部分を分けるのが言語学らしい。記号列→文法に従って構成されている単位→統語論の世界。記号列を解釈して結びつけること→意味論の世界。例えば（シグナル）赤信号が青になった→（意味）前進してもよい。（シグナル）イルカが音を出す→（意味）意味あるかもしれんけどわからない。などなど。
人工言語の話。人工言語は意味はもとより統語論は得意。意味は私たちが決めればいい（？）。これから語彙と文法と操作規則を定義する。
述語記号P, Q, R、関数記号f, g, h、変数記号x,y,z, 定数記号a, b, c、等号=、論理演算記号∧、∨、￢、⇒、⇔、量化記号∃、∀を使う。いわゆる記号論理学のやつだ。
項。変数や定数、これらを関数に入れたやつは項。例えばf(x), f(g(x,f(z)))など。（≧∀≦）は項ではない。gzもだめ（関数の定義にあってないから！？）。
文。項を統合でつないだやつ t=s は原子文である。Pが述語記号ならP(t1, t2, …)も原子文。これを演算子でつないだやつが文。つまり∧、∨、￢、⇒、⇔でつないだり、前に∃、∀を付けたやつが文。もう文は無限個あるね。
等号＝→項と項を結ぶ。同値記号⇔は文と文を結ぶ。f(x) = g(w, y)は文だが、f(x)⇔g(w, y)は文ではない（文法的ではない）。
量化記号の復習。だれもに好きな人がいる→∀x∃yAxy、だれもが好きな人がいる→∃x∀yAxyと書ける（x, yは人を表す変数として、Aはなんだろう？→好き、というかんけいのことだとわかった）
代入すること。同じ変更が「自由に」表れているとき、同じ記号で置き換えられる。先の例なら、∀x∃yAxy→∃yAay、Aabって感じ（！？いみわかりません）。
「自由に」ってなんだよ？→複雑なのででテキストをお読みくださいだって。あんまり詰め込まないでほしいぜ！
意味論の話。一つの個体に対して牛若丸＝義経（原子文）みたいに複数の名前がついていることがある。これは統語論の話。あれ？この話どう関連してるかわからない。とりあえず対象の集合を領域にするってくらいの意味らしい。次は、付置関数。約束の話。弟はだれ、妹は誰、みたいなこと。
例。兄弟の定義を記号でやる。R→兄弟である。f→父、g→母なら Rxy⇔∃z(f(x)=z∧f(y)=z) となる。真面目に言葉で解釈すると「xとyが兄弟であるとは、xの父がzでかつyの父がzであるようなzが存在することと同値」ということになる。まあ確かにそうだ。
頼朝と義経の関係を記号で表している。雨宮さん、歴史の教科書これで表してくださいよって言ってる（やめてほしい）。実際やってる奴がいるらしい。
タブロー法。これは反例があるかどうか自動的に検証する方法らしい。偽であると仮定して文を分解→矛盾が発生したシナリオを却下→以下繰り返し→却下されないシナリオがあれば判例になる、ということらしい。
スズメ、ハト、鳥の例でタブロー法を実演してる。ちょっとwordpressでは書けないので、テキストを参照するしかない。雨宮さん、よくついてけるなこれ！
全体的にいえば、間違った三段論法を機械的に判定できるということ。中身を全く考えなくていいのがすごいけど、案外、直感的にわかるかもしれん。反例を構造的に頭の中で考えられたら最高だけどそれは、タブロー法を全部頭の中でこなした上で、直感レベルまで訓練を続けないと無理だね。将来的にはそういう教材を作成してもいいかもしれん。
ここまでやったら論理的な話、数学的な話は全部コンピュータができるんじゃね？と思われたが、無理らしい。なぜ無理か。それを次回やるそうです。
第15回
証明と計算について。まず自然数と帰納法の話。
文通クラブのパズルについて。4つの条件からメンバーが何人かを推理する。
- ①どのメンバーも少なくとも1人に手紙を送っている
- ②自分宛てに手紙を送らない
- ③どのメンバーも多くても1人からしか手紙をもらっていない
- ④誰からも手紙をもらっていないメンバーが1人だけいる
④から始めるとわかるが、これは無限になる。
①→一人にだけ手紙を送った、に変更するとどうなるか。やっぱり④から始めると無限になってしまう。一人から次の人次の人…と手紙が受け渡されるので、直線的な関係になる。→自然数の公理と同じらしい（！？）
というわけで自然数は関数S（次の数に進む）を使って表すことができる。
- ①0が存在する
- ②Sx=SyならX=y
- ③xが0でなければ、x=Syとなるyが存在する
- ④すべてのxについて、Sx=xでない
- ⑤Sx=0となるxは存在しない
どれも手紙ゲームのルールと同じ（言われてみれば）。
さて、前述の手紙ゲームで、命題A「どの手紙についても手紙を書いた人の髪が青ければ、受け取った人の髪も青い」という条件を追加すると、全員の髪は青くなるか？これは、青くなる。最初の人④に当たる人が青ければ全員青いのだけど、最初の人は青いかどうかわからない。でも青い。なぜかというと、命題Aを否定するには、前半が真かつ後半が偽にならないといけないが、そのような場合はない（全員青いから）。というわけで反例が作れず、全員青い。ここ理解するのめっちゃ時間かかったんだけど雨宮さん2秒でわかってる。すげーなー。
これは数学的帰納法という手法でした。わかりやすいですね。高校との違いは、一直線の論証だけじゃなくて、分岐しても大丈夫ってこと。
帰納法の誤りを指摘する問題。どんな馬の集合でもの馬が1色であることを証明するために、次の帰納法を使おうとした。
- ①1頭なら1色（自明）
- ②どんなn頭の集合をとってきても1色と仮定
- ③n+1頭にしても、任意のn頭は1色なのだから、n+1頭でも1色
- ①～③より、どんな馬の集合でも馬は1色
一見すると正しそうだが、結論がどう考えてもおかしい。ということはどこかに穴があり、これは③がおかしい。n+1頭目が別の色なら1色にならない（反例）。よってこの帰納法は間違っている。一々難しいな。こういう論証の誤りを一瞬でつけるようになりたいよ。
集合の濃度について。無限集合は部分集合と全体集合の濃度が同じになることがあり、これを「濃度が等しい」という。例えば自然数には濃度がある。自然数は元を数えることができるという特徴があり、これを可算、ℵ0という。ℵはヘブライ文字でアレフと読む。
濃度が変わらないというのは、1対1対応があること（？）。自然数に何か有限個のものを加えても、tanという関数を区間[-π/2, π/2]の間で考えても、1対1関係があるから、幅を大きくしたり小さくしても実数と濃度は同じ。
有理数の濃度は？有理数は分数で表せる、すなわち自然数と自然数の組だから数えられる（可算）。また、有利集の集合は自然数の集合を部分集合としている一方で、この集合の部分集合とみなされるから加算（「この」が何を指しているかわからず意味わからんかった）。
実数Rはどうか？これは加算でないことが証明できる。まず実数の濃度は有限区間[0, 1]実数の濃度と同じである。次は背理法。[0,1]の実数が全部数え上げらえると仮定する。すると、0.a1a2a3a4…というすべてを網羅するリストができることになるはず。ところが、リストに入ってない数を作ることができてしまう。例えば、数え上げたリストを斜めに取っていって各桁を+1した無限小数を考える。するとこの小数はリストにない。なぜかというと、これはi番目に入っているはずだが、i番目にある無限小数のi桁目は+1されていて、リストのi番目のと違う。だから矛盾する。よって実数は可算ではない。以上。対角線論法というらしい。
正直全然わからん論証なので、おとなしく印刷教材を真面目に読みます。
同様の理由で無理数も可算ではない。そして無限も無限にあるらしい（！？）。集合論をまともに勉強しないと意味わからんです。
なぜこんな七めんどくさい表現をするのかというと、みんな同じ数を使っているんだ！っていう前提をはっきりさせておかないと、議論ができないからなんだね。数学、機械のためのルールを一意にしないと、すべてが曖昧でめちゃめちゃになってしまう。数学はこういうことをはっきりさせているからとても好きです。