Download presentation
Presentation is loading. Please wait.
1
アルゴリズムとチューリングマシン 「もの」(商品)としてのコンピュータ 「こと」(思想)としてのコンピュータ アルゴリズム
Turing Machine 現実のコンピュータ
2
アルゴリズム 一般的なアルゴリズム概念の成立は今世紀(コンピュータ誕生以降) Algorithm (アルゴリズム)
Alkwarizmi(アルフワリズミ、アラブ)の創始 様々なアルゴリズム ユークリッドの互除法(最大公約数、最小公倍数) エラストテレスのふるい(素数) 探索 ソート(整列) バブルソート クイックソート、ヒープソート etc. 一般的なアルゴリズム概念の成立は今世紀(コンピュータ誕生以降)
3
Turing Machine Alan Turing (1912－1954) 「決定問題」 機械概念の定式化 「内部状態」の遷移
数学の全ての問題を1つずつ解決できる一般的な機械的手続きは存在するか(Hilbelt) 機械概念の定式化 「内部状態」の遷移
4
現実のコンピュータの仕組み 論理回路 順序回路
もしわれわれが、おそらく天使たちが持ち、人間の創造主なら確実に持つような知識を人間について持っているとしたら､人間の本質についていまその定義にふくまれるものとは全く違う概念を持つはずである。あたかもストラスブールの時計の内部にあるぜんまいや歯車やその他の巧緻な品々すべて知っているものが持つ知識は、単に針の動きを見、時計の時の打つのを聴き、概観の若干にのみ瞠目してしまうような田舎者が抱くものとは異なっているように…。ジョン ロック
5
命題論理とブール代数 「命題」と、その「変数」のとり得る「値」 命題Aに関しての真理値表 ２つの命題A,Bに関する演算（和、積）
命題：「・・・は×××である」 とり得る値：「真」か「偽」か（２値）。 命題Aに関しての真理値表 A 」A Ｔ Ｆ Ｆ Ｔ ２つの命題A,Bに関する演算（和、積） A ＋ B, A ・ B
6
２つの命題A,Bに関する演算の真理値表 A B A・B T F A B A+B T F
7
基本論理ゲート NOTゲート、 ORゲート、 ANDゲート
8
ブール代数の応用（回路の簡素化） ブール代数 」x+」y = 」( x・y) , 」x・」y = 」(x+y) (ド・モルガンの定理)
回路の等価性
9
実際の回路 ダイオード回路 TTL（Transistor transit logic）,ECL(emitter coupled logic)
NAND回路
10
デコーダとエンコーダ エンコーダ：番号付けされたn個の入力のうちの1個が1､残りが0の状態にあるとき、１の状態は何番目かを２進数で与える。
11
加算器 一桁の２進数の加算 sum:排他論理和 carry:論理積 a b carry sum 0 0 0 0 0 1 0 1
sum:排他論理和 carry:論理積
12
半加算器と全加算器 半加算器：下の桁からの繰り上がりを勘定に入れない 全加算器：桁上がりも勘定に入れる
13
順序回路 1.フリップフロップ 2.有限状態機械 3.Turing 機械
14
記憶する回路 A 現在のC 次のC もっともらしい記憶装置 (うまくいかない) C A
15
SRフリップフロップ S入力:1、R入力:0 Q出力:1、」Q出力:0 (Rが0である限り、変わらない)
16
同期式SRフリップフロップ C入力が０のときRまたはS入力が１になっても出力には変化が無い。C入力はクロックというものでパルス列が入る。
出力はこのパルスに同期する。
17
各種フリップフロップ
18
カウンタ(Tフリップフロップ) 入力されたパルスの数を2進化して出力 初段のフリップフロップの出力が2段目のクロック入力…。
19
状態遷移図 SRフリップフロップの状態遷移
20
有限状態機械(オートマトン) 自動販売機の「状態遷移」モデル 「記憶」のないチューリングマシン
21
Turingマシン
22
Turingマシンのテープ
23
一元数に１を加えるチューリング機械 00→00R 01 →11R 10 →01STOP 11 →11R
動作確認はシミュレータソフトウェア(圧縮ファイルを解凍し、`Readme.txt’ をお読みの上、使ってください)で行なえます。
24
万能チューリングマシン テープに書かれたチューリングマシンの「命令列」を読み取って、チューリングマシンの代わりを行う。
後世のコンピュータの基本モデル。 「コンピュータ」：プログラムがメモリに内在され、自分でそれを買えることができるもの。
25
一元数を2倍にするチューリング機械 00→00R 01 →10R 10 →101L 11 →11R 100 →110R 101 →1000R
110 →01STOP 111 →111R 1000 →1011L 1001 →1001R 1010 →101L 1011 →1011L
26
2つの一元数の最大公約数 00R → 00R 01 → 11L 10 → 101R 11 → 11L 100 → 10100R
10100 → 00STOP 10101 → R
Similar presentations
