コンピュータサイエンス概論2015第5日目

コンピュータサイエンス概論
２０１５第６日目
東京工科大学
コンピュータサイエンス学部
担当：亀田弘之
平成27年東京工科大学コンピュータサイエンス学部
1
授業計画
第１回:プログラミングの楽しさ
（21世紀の魔法使いの道具プログラミング言語を知る）
第２回：コンピュータサイエンスと知能研究・ゲーム研究
（人工知能・機械学習・脳科学・認知科学などの魅力を知る）
第３回：コンピュータと情報ネットワークの仕組み
（コンピュータの基本構成、ネットワークの基本構成などの
基本的仕組み・原理を知る）
第４回：クラウドコンピューティング
（ビッグデータ（オープンデータ）が世界を変える。データベースの基礎な
ど）
第５回：ソフトウェア工学
（ソフトウェアはどのようにして作られるのか,開発の現場を覗いてみる。
開発プロセス，プロジェクトマネジメントなど）
第６回:コンピュータサイエンスにおける計算の理論
(チューリングマシン,コンピュータサイエンス小史など)
第７回：コンピュータサイエンスと法・倫理
（知的財産権，さまざまな事例紹介）
第８回：コンピュータサイエンスの全容と将来を議論する
（e-healthCare, e-learning, e-government等，
君は何を学ぶのか？なぜ学ぶのか？どうやって学ぶのか？）
平成27年東京工科大学コンピュータサイエンス学部
2
授業計画
第１回:プログラミングの楽しさ
（21世紀の魔法使いの道具プログラミング言語を知る）
第２回：コンピュータサイエンスと知能研究・ゲーム研究
（人工知能・機械学習・脳科学・認知科学などの魅力を知る）
第３回：コンピュータと情報ネットワークの仕組み
（コンピュータの基本構成、ネットワークの基本構成などの
基本的仕組み・原理を知る）
第４回：クラウドコンピューティング
（ビッグデータ（オープンデータ）が世界を変える。データベースの基礎な
ど）
第５回：ソフトウェア工学＋システムエンジニアリング
（ソフトウェアはどのようにして作られるのか,開発の現場を覗いてみる。
開発プロセス，プロジェクトマネジメントなど）
第６回:コンピュータサイエンスにおける計算の理論
(チューリングマシン,コンピュータサイエンス小史など)
第７回：コンピュータサイエンスと法・倫理
（知的財産権，さまざまな事例紹介）
第８回：コンピュータサイエンスの全容と将来を議論する
（e-healthCare, e-learning, e-government等，
君は何を学ぶのか？なぜ学ぶのか？どうやって学ぶのか？）
平成27年東京工科大学コンピュータサイエンス学部
3
到達目標
コンピュータサイエンスに関して以下のことが到達目標である。
１．コンピュータサイエンスの
社会的役割・意義を理解し説明できる。
２．コンピュータサイエンスを学ぶ上での
重要な能力・資質を理解する。
３．コンピュータサイエンスの概要を説明できる。
４．将来のコース選択（案）を自力で作成し、
人にわかりやすく説明できる。
平成27年東京工科大学コンピュータサイエンス学部
4
質問 “計算”とは何ですか？
平成27年東京工科大学コンピュータサイエンス学部
5
質問次の内、計算ではないものはどれか
a.
b.
c.
d.
e.
f.
１２３ + 456
A×B + C
家計簿処理
自動車の運転
画像の保存
MACアドレスのコマンドによる確認
平成27年東京工科大学コンピュータサイエンス学部
6
次の計算における基本的な操作(ソフトウェア)は
何か？また、必要なハードウェアは何か？
１２３
+) ４５６
579
平成27年東京工科大学コンピュータサイエンス学部
7
計算の歴史
• アバカス（商業計算）
• 数字の表現方法
• 計算の方法
• アバカスでの計算法
• 算盤（中国）での計算法
• そろばん（日本）での計算法
• 計算尺（科学技術計算）
• 天文学，航海術
• 三角法の発達（計算の工夫）
（注）本ページの写真はWikipedia（アバカスの項目）より借用
平成27年東京工科大学コンピュータサイエンス学部
8
参考動画
1. Adam Ries und das Rechnen
（https://www.youtube.com/watch?v=IVfVQYbO6H8）
2. Charles Babbage, Konrad Zuse und der Computer
（https://www.youtube.com/watch?v=fpwqqu24_bQ）
3. History of computers - “Past to Present & Beyond”
( https://www.youtube.com/watch?v=iEgLwKTsgEo )
平成27年東京工科大学コンピュータサイエンス学部
9
ネピアのアイデア（対数計算法）の着想
• ある方法を思いついた（等差数列と等比数列を組み合わせる方法
• ネピアの方法：
等差数列（初項０、等差１）、等比数列（初項１、等比２）を利用
--------------------------------------------------------------------------------等差数列｜ 0 1 2 3 4 5 6
7
8
9
10
--------------------------------------------------------------------------------等比数列｜ 1 2 4 8 16 32 64 128 256 512 1024
--------------------------------------------------------------------------------平成27年東京工科大学コンピュータサイエンス学部
10
例：４×１６を計算する。
手順１）まず、数“４”を等比数列の列の中に見つけ、
それに対応する等差数列の数を求める。４に対応している数は２。
（注）等比数列中の数を“真数（しんすう）”、それに対応する
等差数列の数を“対数（対数）”と呼ぶことにする。
手順２）次に、真数１６に対する対数を求めると、４。
手順３）求めた２つの対数の和を計算する。２＋４＝６。
手順４）得られた対数の和６を等差数列の中に見つけ、
それに対応している真数を表から読み取る。対数６に対する真数は６４。
手順５）得られた数６４が、掛け算４×１６の答え。
平成27年東京工科大学コンピュータサイエンス学部
11
この計算方法の欠点
＊表にない数をどうやって計算するか？
（例：３×５はどうする？）
＊表のサイズはどの程度まで必要なのか？など
平成27年東京工科大学コンピュータサイエンス学部
12
次のアイデア（常用対数）
• ネピアはブリッグスとともに、対数計算方法の改善をめざした。
• ネピアの死後、ブリック数は14桁の対数計算用の数表を一生かけ完成させた。
• ネピアのアイデアは、常用対数により一般の人たちにも広く使われるようになった。
• 常用対数とは、真数１に対して対数０を、真数１０に対して対数１を、真数１００に対
して対数２を対応させる、というもの。
• この方法であれば、表のサイズが確定する。
例えば、まず、５の対数を数表から読み取ると0.699１０の対数は定義より１だから、５０の対数
は1.699 と求まる。この真数５０に対する対数を計算したければ、５０＝５×１０に注意して、
ことを利用して、２５１の対数は、2.51×10^2だから、2.51の対数に2を足せば求まる。つまり、1
～１0 までの対数表を作成しておけば様々な掛け算が計算できる。
• このため、一般の人たちに対数計算が広まった。それ故に“常用”対数と呼ばれる。
• 対数計算の発明により、「天文学者の人生が2倍になった」とも言われている。
平成27年東京工科大学コンピュータサイエンス学部
13
ありがたさを知る例
1.41421356×1.41421356=?
(自習問題：普通のやり方と
常用対数計算とで、手間を比
較してみよう！)
＝＞来週説明します。
平成27年東京工科大学コンピュータサイエンス学部
14
その他の工夫
1
sin α ・cos β = sin(𝛼 + β) + sin(α − 𝛽)
2
平成27年東京工科大学コンピュータサイエンス学部
15
さて、「計算とはそもそも何？」に戻りましょう
平成27年東京工科大学コンピュータサイエンス学部
16
次の計算における基本的な操作(ソフトウェア)は
何か？また、必要なハードウェアは何か？
１２３
+) ４５６
579
平成27年東京工科大学コンピュータサイエンス学部
17
以下、「オートマトン理論」より抜粋
• 計算を行うことができる装置を実際に構成することができる。
• それを見て行こう！
• そのためには、まず、「有限オートマトン」から紹介します。
平成27年東京工科大学コンピュータサイエンス学部
18
①有限オートマトンの表現(1)
• 有限オートマトンの概観
a1 a2
・・・
セル
入力記号
ai-1 ai
・・・
・・・
an
qk
入力テープ
内部状態
ヘッド
19
②有限オートマトンの表現(2)
有限オートマトン = ( K, Σ, δ, q0, F )
ただし、
K ：状態の集合( Kは有限集合)
Σ ：入力アルファベット（Σは有限集合）
δ ：状態遷移関数
δ： K×Σ∋( a, qi ) → qj ∈ K
q0 ：初期状態
F ：最終状態の集合 ( F ⊆ K )
20
②有限オートマトンの表現(2’)
K = { r, s, t} ,
q0 = r,
δ ：
状態
r
r
s
s
t
t
Σ= { a, b },
F
={ t },
入力次の状態
a
s
b
r
a
t
b
r
a
t
b
r
21
③有限オートマトンの表現(3)
a
r
b
a
s
b
b
t
a
22
③有限オートマトンの表現(3)
a
r
b
a
s
入力の例：
1. a
2. aaa
3. babaa
b
b
t
a
23
今日の真打登場！
• チューリングマシン (Turing Machine)
24
通常この形式のものを扱います
25
チューリングマシンの定義
• TM M ＝ < Q, Γ, Σ, δ, q0, B, F > (7つ組)
•
•
•
•
Q:内部状態の集合
Γ：テープ記号の集合
Σ：入力記号の集合 ( Σ⊂ Γ )
δ：状態遷移関数
Q×Γ → Q×Γ×{ L, R }
• q0 ：初期状態 ( q0 ∈ Q)
• B:ブランク記号 ( B ∈ Γ – Σ)
• F:最終状態の集合 ( F ⊂ Q )
26
TMのイメージ図
27
チューリングマシンの例
入力文字列
1. aa
2. aabb
3. bbaa
4. aaaabbbb
28
言語 { anbnan | n>=1 } を受理するTM
29
｛ ww | w ∈ { a, b }+ ｝を受理するTM
30
2進数の和を計算するTM
31
最後に、アルゴリズムについて
©Tokyo University of Technology, School of
Computer Science, H.Kameda
32
アルゴリズムとは何か？
• “アルゴリズム(algorithm)”という用語はもともと数学
の分野で“手続き(procedure or recipe)”とも呼ばれて
いたもの。素数を発見するためのアルゴリズム(例：エ
ラストテネスの篩法)や最大公約数を計算するアルゴ
リズム(ユークリッド互除法)などが有名である。
しかしながら、“何らかの仕事を処理するための指
示群”といった程度の概念でとらえられていた。（それ
でも十分だった…）
©Tokyo University of Technology, School of
Computer Science, H.Kameda
33
Hilbertの２３の問題
• 1900年に数学者David Hilbertがパリで開催された国
際数学者会議の講演で、23の問題を提案した。
その第10問題がアルゴリズムに関するものであった。
©Tokyo University of Technology, School of
Computer Science, H.Kameda
34
Hilbertの第10問題
• 多項式(polynomial)pが与えられたとき、その多項式p
は整数解のみを持つ多項式であるのか否かを判定
する手順（アルゴリズム）を考えよ。
©Tokyo University of Technology, School of
Computer Science, H.Kameda
35
例：
• 次の多項式pはx=5,y=3,z=0のときゼロになる。つまり、
pは整数解を持つ。与えられた任意の多項式がこの
ように整数解のみを持つかどうかを判定する処理手
続きを考案したい。
6 x yz  3xy  x 10
3
2
2
©Tokyo University of Technology, School of
Computer Science, H.Kameda
3
36
考えてみてください！
• ある種の数学者たちはこのような問題に取り組んで
います！
皆さんも数学者に挑戦してみては？
©Tokyo University of Technology, School of
Computer Science, H.Kameda
37
事実
• そんなアルゴリズムは存在しない！
• でも、存在しないことを証明することは困難であった。
• 「存在する」という証明は、例を１つみつければOK .
• 「存在しない」というのはどうやって証明すればいいの
か？
• そのような背景からアルゴリズムの理解は深まって
行った。
©Tokyo University of Technology, School of
Computer Science, H.Kameda
38
歴史的な話
• 1936年、Alonzo ChurchとAlan Turingの二人の“アル
ゴリズムの定義”が得られた。
• ラムダ計算(λ-clculus)による定義（Church）
• Turing machineによる定義（Turing）
この２つの定義は同等であることが示された！
（これをChurch-Turing Thesisという）
©Tokyo University of Technology, School of
Computer Science, H.Kameda
39
Hilbertの第10問題
• 次のDは決定可能(decidable)か？
D = { p | p は整数解のみを持つ多項式}
この問題に対する答えは否定的であった。
しかしながら、この問題はチューリング認識可能であることを示すこ
とができる。
このことをもっと単純な問題で見てみよう！
©Tokyo University of Technology, School of
Computer Science, H.Kameda
40
簡単化された問題
• D1={ p | pはｘに関する多項式で、整数のみを解とし
て持つ}
• チューリングマシン M1はD1を認識する。
• M1：
ｘに関する多項式pを入力とする。
1. 多項式pの値を、以下のxについて順次計算し、
どこかでp=0となったらそのpを受理する。
x=0, 1, -1, 2, -2, 3, -3, 4, -4, …
©Tokyo University of Technology, School of
Computer Science, H.Kameda
41
• これは認識可能であるが決定可能ではない。また、多変数への拡張
は可能である。
• しかしながら、これらは決定可能ではないという問題点がある。
• だが、…
©Tokyo University of Technology, School of
Computer Science, H.Kameda
42
定理
• 多項式
p  c1 x  c2 x
n
n1
  cn x  cn1
がx=aでp=0とする。このとき、
cmax  {c1 , c2 ,, cn1}
とするとき以下の不等式が成り立つ。
cmax
| a | (n  1)
| c1 |
©Tokyo University of Technology, School of
Computer Science, H.Kameda
43
• この定理により、先の「簡単化された問題」は決定的であることが分
かる。
• しかしながら、一般的な問題つまりHilbertの第10問題は決定可能な
のだろうか？
©Tokyo University of Technology, School of
Computer Science, H.Kameda
44
• 1970年、Yuri MatijasevicによりHilbertの第10問題に対するアルゴリ
ズムは存在しないことが証明された。
（ Matijasevic の定理）
©Tokyo University of Technology, School of
Computer Science, H.Kameda
45
講演会のお知らせ（確認）
• ６月１５日（月）３限 Adroidとオープンデータに関する講演会を開催
します。これに参加してかつレポートを提出し他人には、成績に加点
します。科学技術館等の見学レポートに替えることも可能とします。
• この講演会は、東京工科大学ＣＳ学部１年生の皆さんにぜひ聞いて
欲しいものの１つです。ＣＳ学部での学びが、皆さん一人一人にとっ
てどのような広がりを持っているか知ってもらうことが目的です。
平成27年東京工科大学コンピュータサイエンス学部
46
見学の勧め（再）
• 科学技術に関する博物館や科学館の見学をし、その見学した内容
を紹介するとともに、それらとＣＳとのかかわりに関する私見をレ
ポートにまとめる。
• 成績に最大で＋１０点の加点を行う。（原則、＋１０点とするが、内容
が不十分であったり、レポートとしての体裁に問題がある場合は、若
干の減点を行う。）
• 書き方及び内容構成は、「レポートの構成」のページ（２ページ先）を
参照のこと。
見学の勧め（２）
• 科学技術館
• 郵政博物館
• 東芝未来科学館など
（技術全般に関する博物館見学であれば可）
レポートの構成
• 表紙
• レポートタイトル「〇〇の見学報告」
• レポート提出日・学生番号・氏名
（用紙のサイズはＡ４版とする。）
• 本文
1.
2.
•
見学場所（施設名と所在地）、見学日時
見学内容
①
②
③
④
⑤
施設の何を見学したのか？
何を学んだのか？
ＣＳとの関わり（自分の意見）
ＣＳを学ぶ者として、将来どのような社会貢献ができそうか？（自分の考え）
その他（何かあれば）
締切
•
平成２７年７月末日（提出先：研Ａ６階レポートボックス）
参考情報
1. わずか1000円の激安コンピュータ「CHIP」
http://gigazine.net/news/20150508-chip/
2. 人口130万人エストニアから税理士や会計士が消滅した理由
http://www.excite.co.jp/News/world_g/20141029/Postseven_28
3759.html
3. これからの20年で現在のアメリカの雇用の50％以上がコン
ピューターに代替される
http://social-design-net.com/archives/9672
4. others
著作権に関して
• 本資料中のオートマトンの状態遷移図の一部は、下記の文献から
引用したものである。
[1] オートマトン・言語理論の基礎, 米田(監修), 米田・広瀬・大里・大川,
近代科学社(2003).
平成27年東京工科大学コンピュータサイエンス学部
51

Download Report