東京工科大学 コンピュータサイエンス学部 担当：亀田弘之 コンピュータサイエンス概論２０１６第７日目 東京工科大学 コンピュータサイエンス学部 担当：亀田弘之

平成28年 東京工科大学コンピュータサイエンス学部 確認 授業計画 第１回:プログラミングの楽しさ 　　　　（21世紀の忍法使いアイテム＝プログラミング言語を知る） 第２回：コンピュータサイエンスと法・倫理（知的財産権，さまざまな事例紹介） 第３回：コンピュータサイエンスと知能研究・ゲーム研究 　　　　（人工知能・機械学習・脳科学・認知科学などの魅力を知る） 第４回：コンピュータと情報ネットワークの仕組み 　　　　（コンピュータとネットワークの仕組み・原理の基礎を知る） 第５回：クラウドコンピューティング 　　　　（ビッグデータ（オープンデータ）やデータベースの基礎など） 第６回：ソフトウェア工学（ソフトウェアはどのようにして作られるのか？ 　　　　　開発の現場を覗いてみる。開発プロセス，プロジェクトマネジメントなど） 第７回:コンピュータサイエンスにおける計算の理論 　　　　(チューリングマシン,コンピュータサイエンス小史など) 第８回：コンピュータサイエンスの全容と将来を議論 　　　　（e-healthCare, e-learning, e-government等， 　　　　　君は何を学ぶのか？　なぜ学ぶのか？　どうやって学ぶのか？） 　　　　　授業評価アンケート実施日（PC持参のこと） 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 質問　“計算”とは何ですか？ みなさんは、例えば ３ ＋ ５ の計算できますよね。 では一般に、「計算の原理・仕組み」はどのようになっているのか、 説明できますか？ これを説明するためには、そもそも「計算とは何か？」を 明らかにする必要があります。「数とは何か？」、「数をどう表現する か？」も重要なテーマです。 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 質問　次の内、計算ではないものはどれか 123 + 456 A×B + C 家計簿処理 自動車の運転 画像データの保存 IPアドレス確認のためのコマンド実行 平成28年　東京工科大学コンピュータサイエンス学部

問 次の計算における基本的な操作(ソフトウェア) は何か？ また、必要なハードウェアは何か？ 問　次の計算における基本的な操作(ソフトウェア) 　　 は何か？　また、必要なハードウェアは何か？ １２３ +) ４５６ 579 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 計算の歴史 アバカス（商業計算） 数字の表現方法 計算の方法 アバカスでの計算法 算盤（中国）での計算法 そろばん（日本）での計算法 計算尺（科学技術計算） 天文学，航海術 三角法の発達（計算の工夫） （参考） データ構造 と アルゴリズム 　　　|| || 数の表現方法　計算手順 （注）本ページの写真はWikipedia（アバカスの項目）より借用 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 人類最初の計算器（アバカス） ローマ数字 1=I, 5=V, 10=X, 50=L, 100=C, 500=D, 1000=M 計算方法 (参考動画1) (出典) http://blog.goo.ne.jp/aoniyoshinara/e/626f94db0fd3131b8fa6be74b818cd9b 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 参考動画 Meilensteine der Naturwissenschaft und Technik - Adam Ries und das Rechnen Part 1 von 2 (自然科学と技術のマイルストーン 　–Adam Riesと計算 　２の１) （ https://www.youtube.com/watch?v=ssBf6N2Qi5I ） 2分19秒～6分59秒(ローマ数字、アバカス、足し算の方法)および 8分0秒～9分36秒（掛け算の方法） Charles Babbage, Konrad Zuse und der Computer （ https://www.youtube.com/watch?v=-ReL9JnWA1A ） A Brief History of Computers (https://www.youtube.com/watch?v=9EURZF3C9iI) 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 アバカス（続き） 計算方法（装置の構成）と数字の表現方法との関係（密接な関係にある） アバカスは中東→ギリシア→ヨーロッパ→中国→日本と伝わり、次第に発展。 日本では「そろばん」として発展・定着 江戸時代は金・銀・銭の３つの通貨流通体系があったため、 今日のそろばんとは少し異なっていたが、合理的なものであった。 明治政府の方針により、日本は10進数を使うことになり、 そろばんも現在の５つ珠の形式となった。 現在のそろばんは、10進数での計算に特化した最も優れたアバカス。 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 大航海時代と計算 初期の冒険的大航海時代（１５世紀） 商業活動としての大航海時代（１６世紀） 大海原における、船（自分自身の）位置・移動方向・移動速度などを 知る必要あり。 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 大航海時代と計算（２） 丸太（log）を使い船の速さを測定 丸太を舳先から海に投げ入れ、船尾まで丸太が移動する時間を測定。 　　　　（船の長さ）/（計測時間）＝（船の速さ） ちなみに、現在でも航海日誌をつけることを“ログをとる”という。 位置は夜間の星（北極星）を利用 1/60度の測定誤差が、到着目標位置に約２kmの誤差を生じる。 北極星自体は、真の点の北極から約3.5度ずれていたため、 到着目標位置が約400kmずれることもあり。 正確な測定、つまり、正確な計算が求められた。 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 大航海時代と計算（３） 天文学の発展とも相まって、複数の星の位置を利用する方法（三角法）が発展。 三角測量法は、サインやコサインの掛け算といった所謂“科学技術計算”が求 められた。（それまでは、商人や税理官吏たちによるお金等の計算が主であっ た。新時代の到来。） 船の航行では、前述の理由から精度の高い計算が必要であったが、天文学で も精度の高い計算が必要であった。 当時の天文学では、小数点以下７桁の値が記された数表を用い、 sineやcosineの掛け算等を行っていた。 例えば、sin(A) = 0.1234567, cos(B) = 0.7654321 に対して、 sin(A)×cos(B)、つまり、0.1234567×0.7654321 のような計算 を盛んに行っていた。 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 大航海時代と計算（４） 天文学者たちの計算工夫： sin(A)×cos(B) = { sin(A+B) + sin(A-B) } / 2 　　　　　（三角関数の加法の定理、積和公式） 　掛け算を足し算で求める（２で割る手間はあるが）。 人類が必要とする計算は、事務計算とともに科学技術計算にまで拡 大された。 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 科学技術計算の発展 ネピアのアイデア（対数計算法）の着想 ある方法を思いついた（等差数列と等比数列を組み合わせる方法 ネピアの方法： 　　　　等差数列（初項０、等差１）、等比数列（初項１、等比２）を利用 　　　--------------------------------------------------------------------------------- 　　 等差数列 ｜ 0 1 2 3 4 5 6 7 8 9 10 　　--------------------------------------------------------------------------------- 　　 等比数列 ｜ 1 2 4 8 16 32 64 128 256 512 1024 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 　　 --------------------------------------------------------------------------------- 　　 等差数列 ｜ 0 1 2 3 4 5 6 7 8 9 10 　　--------------------------------------------------------------------------------- 　　 等比数列 ｜ 1 2 4 8 16 32 64 128 256 512 1024 例：４×１６を計算する。 手順１） まず、数“４”を等比数列の列の中に見つけ、 それに対応する等差数列の数を求める。４に対応している数は２。 （注）等比数列中の数を“真数（しんすう）”、それに対応する 等差数列の数を“対数（たいすう）”と呼ぶことにする。 手順２） 次に、真数１６に対する対数を求めると、４。 手順３） 求めた２つの対数の和を計算する。２＋４＝６。 手順４） 得られた対数の和６を等差数列の中に見つけ、 それに対応している真数を表から読み取る。 対数６に対する真数は６４。 手順５） 得られた数６４が、掛け算４×１６の答え。 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 　　 --------------------------------------------------------------------------------- 　　 等差数列 ｜ 0 1 2 3 4 5 6 7 8 9 10 　　--------------------------------------------------------------------------------- 　　 等比数列 ｜ 1 2 4 8 16 32 64 128 256 512 1024 例：４×１６を計算する。 手順１） まず、数“４”を等比数列の列の中に見つけ、 それに対応する等差数列の数を求める。４に対応している数は２。 （注）等比数列中の数を“真数（しんすう）”、それに対応する 等差数列の数を“対数（たいすう）”と呼ぶことにする。 手順２） 次に、真数１６に対する対数を求めると、４。 手順３） 求めた２つの対数の和を計算する。２＋４＝６。 手順４） 得られた対数の和６を等差数列の中に見つけ、 それに対応している真数を表から読み取る。 対数６に対する真数は６４。 手順５） 得られた数６４が、掛け算４×１６の答え。 問題　８×３２ ＝ ？ 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 この計算方法の欠点 ＊表にない数をどうやって計算するか？ （例：３×５はどうする？） ＊表のサイズはどの程度まで必要なのか？など 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 次のアイデア（常用対数） ネピアはブリッグスとともに、対数計算方法の改善をめざした。 ネピアの死後、ブリック数は14桁の対数計算用の数表を一生かけ完成させた。 ネピアのアイデアは、常用対数により一般の人たちにも広く使われるようになった。 常用対数とは、真数１に対して対数０を、真数１０に対して対数１を、真数１００に対して対 数２を対応させる、というもの。 この方法であれば、表のサイズが確定する。 　例えば、真数５０に対する対数を計算したければ、 ５０＝５×１０に注意して、 　　まず、５の対数を数表から読み取ると0.699、１０の対数は定義より１だから、 　　５０の対数は1.699 と求まる。このことを利用して、２５１の対数は、2.51×10^2であることより、 　　2.51の対数に2を足せば求まる。つまり、1～１0 までの対数表を作成しておけば 　　様々な掛け算が計算できる。 このため、一般の人たちに対数計算が広まった。それ故に“常用”対数と呼ばれる。 対数計算の発明により、「天文学者の人生が2倍になった」とも言われている。 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 ありがたさを知る例 1.41×1.73=? (自習問題： 普通のやり方と 常用対数計算とで、手間を比 較してみよう！) 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 その他の工夫 sin α ・cos β= 1 2 {sin (𝛼+β) + sin (α−𝛽)} 平成28年　東京工科大学コンピュータサイエンス学部

さて、「計算とはそもそも何？」に戻りましょう 平成28年　東京工科大学コンピュータサイエンス学部

次の計算における基本的な操作(ソフトウェア)は何か？ また、必要なハードウェアは何か？ 次の計算における基本的な操作(ソフトウェア)は何か？　また、必要なハードウェアは何か？ １２３ +) ４５６ 579 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 以下、「オートマトン理論」より抜粋 計算を行うことができる装置を実際に構成することができる。 それを見て行こう！ そのためには、まず、「有限オートマトン」から紹介します。 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 ①有限オートマトンの表現(1) 入力記号 セル 有限オートマトンの概観 a1 a2 ai-1 ai an ・・・ ・・・ ・・・ qk 入力テープ ヘッド 内部状態 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 ②有限オートマトンの表現(2) 有限オートマトン = ( K, Σ, δ, q0, F ) ただし、 K ：　状態の集合( Kは有限集合) Σ ：　入力アルファベット（Σは有限集合） δ ：　状態遷移関数 δ： K×Σ∋( a, qi ) → qj ∈ K q0 ：　初期状態 F ：　最終状態の集合 ( F ⊆ K ) 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 ②有限オートマトンの表現(2’) K = { r, s, t} , Σ= { a, b }, q0 = r, F ={ t }, δ ：　 状態 入力 次の状態 r a s b t 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 ③有限オートマトンの表現(3) s a a b r b t a b 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 ③有限オートマトンの表現(3) 入力の例： a aaa babaa s a a b r b t a b 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 今日の真打登場！ チューリングマシン (Turing Machine) 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 通常この形式のものを扱います 図．チューリングマシンの概要 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 チューリングマシンの定義 TM M ＝ < Q, Γ, Σ, δ, q0, B, F > (7つ組) Q:内部状態の集合 Γ：テープ記号の集合 Σ：入力記号の集合 ( Σ⊂ Γ ) δ：状態遷移関数 Q×Γ → Q×Γ×{ L, R } q0 ：初期状態 ( q0 ∈ Q) B:ブランク記号 ( B ∈ Γ – Σ) F:最終状態の集合 ( F ⊂ Q ) 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 TMのイメージ図 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 チューリングマシンの例 入力文字列 aa aabb bbaa aaaabbbb 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 言語 { anbnan | n>=1 } を受理するTM 　　　　図. 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 ｛ ww | w ∈ { a, b }+ ｝ を受理するTM 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 2進数の和を計算するTM 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 最後に、アルゴリズムについて 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 アルゴリズムとは何か？ “アルゴリズム(algorithm)”という用語はもともと数学 の分野で“手続き(procedure or recipe)”とも呼ばれて いたもの。 素数を発見するためのアルゴリズム(例：エラストテネ スの篩法)や最大公約数を計算するアルゴリズム (ユークリッド互除法)などが有名である。 しかしながら、“何らかの仕事を処理するための指示 群”といった程度の概念でとらえられていた。（それで も昔は十分だった…） 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 Hilbertの２３の問題 1900年に数学者David Hilbertが、パリで開催された 国際数学者会議の講演で、23の問題を提案した。 その第10問題がアルゴリズムに関するものであった。 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 Hilbertの第10問題 多項式(polynomial)pが与えられたとき、その多項式p は整数解のみを持つ多項式であるか否かを判定す る手順（アルゴリズム）を考えよ。 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 例： 次の多項式pはx=5,y=3,z=0のときゼロになる。つまり、 pは整数解を持つ。与えられた任意の多項式がこの ように整数解のみを持つかどうかを判定する処理手 続きを考案したい。 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 考えてみてください！ ある種の数学者たちはこのような問題に取り組んで います！ 皆さんも数学者に挑戦してみては？ 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 事実 そんなアルゴリズムは存在しない！ でも、存在しないことを証明することは困難であった。 「存在する」という証明は、例を１つみつければOK . 「存在しない」というのはどうやって証明すればいいの か？ そのような背景からアルゴリズムの理解は深まって 行った。 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 歴史的な話 1936年、Alonzo ChurchとAlan Turingの二人が、それ ぞれ“アルゴリズムの定義”を示した。 ラムダ計算(λ-clculus)による定義　（Church） Turing machineによる定義　（Turing） この２つの定義は同等であることが示された！ （これをChurch-Turing Thesisという） 平成28年　東京工科大学コンピュータサイエンス学部

Hilbertの第10問題 次のDは決定可能(decidable)か？ D = { p | p は整数解のみを持つ多項式} この問題に対する答えは否定的であった。 しかしながら、この問題はチューリング認識可能であることを示すこ とができる。 このことをもっと単純な問題で見てみよう！ 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 簡単化された問題 D1={ p | pはｘに関する多項式で、整数のみを解とし て持つ} チューリングマシン M1はD1を認識する。 M1： ｘに関する多項式pを入力とする。 多項式pの値を、以下のxについて順次計算し、 どこかでp=0となったらそのpを受理する。 　x=0, 1, -1, 2, -2, 3, -3, 4, -4, … 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 これは認識可能であるが決定可能ではない。また、多変数への拡張 は可能である。 しかしながら、これらは決定可能ではないという問題点がある。 だが、… 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 定理 多項式 　がx=aでp=0とする。このとき、 　とするとき以下の不等式が成り立つ。 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 この定理により、先の「簡単化された問題」は決定的であることが分 かる。 しかしながら、一般的な問題つまりHilbertの第10問題は決定可能な のだろうか？ 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 結論 1970年、Yuri MatijasevicによりHilbertの第10問題に対するアルゴリ ズムは存在しないことが証明された。 （ Matijasevic の定理） 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 お知らせ 来週は最終回です。 授業評価アンケートを行いますので、PCを忘れないように！ また、次回最終レポート課題に提示をします。 平成28年　東京工科大学コンピュータサイエンス学部

平成28年 東京工科大学コンピュータサイエンス学部 著作権に関して 本資料中のオートマトンの状態遷移図の一部は、下記の文献から 引用したものである。 [1] オートマトン・言語理論の基礎, 米田(監修), 米田・広瀬・大里・大川, 　　近代科学社(2003). 平成28年　東京工科大学コンピュータサイエンス学部