Microsoft PowerPoint - tm ppt [互換モード]
|
|
- ひでか かつもと
- 5 years ago
- Views:
Transcription
1 1 計算理論 I( チューリング機械と決定不能性 ) 平成 21 年度第 I 期 ソフトウェア基礎学講座安本慶一 スケジュール 2 講義日程 (6 回 ) 5 月 11,14,18,21,25,28 日 ( 月曜 1 限, 木曜 2 限 ) テスト :6 月 1 日 ( 月 )1 限 ( 資料, 参考書持込可 ) 講義資料 以下の URL で配布 毎回の授業前に各自でダウンロード 印刷すること 参考書 参考書 1. Michael Sipser: Introduction to the Theory of Computation, Second Edition, Course Technology, 2006 (Chapter 3-5) 2. 野崎, 高橋, 町田, 山崎訳 : オートマトン言語理論計算論 II [ 第 2 版 ], サイエンス社,2003 ( 第 8 章 ~9 章 ) 3. 丸岡章 : 計算理論とオートマトン言語理論, サイエンス社,2005( 第 6 章 ~7 章 ) 4. 岩間一雄 : アルゴリズム理論入門, 昭晃堂,2001 1
2 3 その他 成績判定 オートマトン ( 伊藤先生担当分 50 点 )+ チューリング機械 ( 安本担当分 50 点 ) の合計 60 点以上を合格 質問など 在室時オフィスまで直接, または, にて随時 担当教員 ( オフィス :A613 ) 安本 (yasumoto@is) TA ( オフィス :A616) D2 勝間 (ryo-k@is),m2 清川 (kota-k@is),m2 神山 (naoya-k@is) 4 本講義の目的 計算機とは何か? 何ができて何ができないのか? 究極に簡素化した数学的計算モデル ( チューリング機械 ) を使って 計算可能性 を学ぶ 計算可能 : 問題に対し解を答える / 解がない と答える計算手順 ( アルゴリズム ) が存在 チューリング機械 (TM): 現代の計算機にいくらでもメモリ, 時間を使えるとしたもの 計算可能性の定義 :TMで計算できる 一般的に計算できる ( 他の定義とも一致 ) 計算できない問題がある ( プログラムの停止性問題, ヒルベルト第 10 問題など ) 計算量理論を学ぶための準備 計算量理論 ( アルゴリズムの実行時間や必要な記憶容量を数学的に扱う理論 ) は本講 計算量理論 ( アルゴリズムの実行時間や必要な記憶容量を数学的に扱う理論 ) は本講義では扱わないが, 学ぶためにはチューリング機械の知識が必須 多項式問題 : 問題サイズ n に対し, 計算量は多項式オーダ (O(n 2 ) など ) 実行可能 NP 完全問題 : 問題サイズ n に対し, 計算量は指数オーダ (O(2 n ) など ) 実行不能 与えられた問題が NP 完全であるかどうかの証明 ( 計算理論 III で学ぶ ) 2
3 5 講義概要 チューリング機械 ( 第 1 回 ~3 回 ) チューリング機械 (TM) の定義 :TM=FA+ 無限長の書換可能なテープ TM と FA( 有限オートマトン ) との能力 ( 解ける問題のクラス ) の違い TM の能力 現代の計算機の能力 処理速度は無視 TM への機能拡張 ( 拡張しても能力は変わらない ) 標準 TM は十分強力 複数テープ, 非決定性, ランダムアクセスなどを拡張 ( アルゴリズムの記述は容易に ) TMによるアルゴリズムの記述法 計算機で解けない ( 決定不能 ) 問題とその証明法 ( 第 4 回 ~6 回 ) TMで解けない問題 (= 計算機で解けない問題 ) 万能チューリング機械 : 任意のTMのプログラムを読み込んで実行するTM ある問題 ( プログラムの停止性判定問題など ) が決定不能なことを証明 対角線論法によりその問題を解くアルゴリズム (TM) が存在しないことを示す 帰着を用いた証明法 : 既知の決定不能問題の対象問題への変換により証明 6 1. チューリング機械 3
4 7 チューリング機械登場の背景 19 世紀末 ~20 世紀初頭ヒルベルト プログラム (D. Hilbert) 始動 数学の全てを形式化し, 数学全体の完全性と無矛盾性を示そうとする試み ヒルベルトの 23 の問題 (1900 年 ) 第 10 問題 :n 個の未知数を含む整数係数の多項式 P(x 1,,x n ) が与えられたとき, 方程式 P(x 1,,x n )=0 が整数解を持つかどうか を判定するアルゴリズムを考案せよ例 )6x 3 yz 2 +3xy 2 x 3 10=0 のとき, 解 (x,y,z)=(5,3,0) が存在する答え : そのようなアルゴリズムは, 存在しない! 当時, アルゴリズム が何を意味するかは数学的に厳密に定義されておらず, 直感的なイメージ ( 意図した計算結果を得るための計算手順, 等 ) が用いられていた. アルゴリズムを数学的に扱う枠組み 1936 年チューリング (A. Turing) がチューリング機械発表 あらゆる計算 ( すなわち, アルゴリズム ) の形式化, 数学的議論が可能に 年頃最初のプログラム可能な計算機登場 1945 年プログラム内蔵方式 (J. von Neumann) ( 万能チューリング機械はその概念を先取り ) 1946 年米ペンシルバニア大が ENIAC 開発 8 チューリング賞 コンピュータサイエンス分野のノーベル賞にあたる権威ある賞 優れた功績を残した人に年に1 度, 米国学会 ACM (Association for Computing Machinery) が贈る 賞金は10 万ドル以上 (Intel, Googleが後援 ) 近年の受賞者 2003 年 Alan Kay オブジェクト指向技術 2004 年 Robert E. Kahn,Vinton G. Cerf TCP/IP 2005 年 Peter Naur プログラミング言語 ALGOL60 の定義 2006 年 F E All コンパイラ最適化技術 2006 年 Frances E. Allen コンパイラ最適化技術 2007 年 Edmund M. Clarke,E. Allen Emerson,Joseph Sifakis モデル検査技術 2008 年 Barbara Liskov プログラミング言語設計技術 4
5 チューリング機械 ( 以下 TM と略記 ) でできること 9 有限オートマトン (FA) で受理できない言語の取り扱い L={0 n 1 n } これらの言語を受理するプログラムを L={w w=w R } C 言語などで作成するのは簡単,TMでももちろん可能 チューリング機械では, 計算機で実行可能な任意のプログラムを, シンプルなモデルで表現できる TM= 有限オートマトン + 無限容量メモリ ( 無限長テープへの読み書き ) 計算機で扱うあらゆる問題に対する計算可能性を数学的に議論 与えられた問題が決定不能 ( 計算機で解けない / アルゴリズムが存在しない ) であることを数学的に証明 与えられた問題がどれくらい難しい ( 解くのに時間を要する ) のかを解析 TM の入出力 10 有限オートマトンと同じく,TM は与えられた入力記号列 w を受理するかどうかを判定 入力 :w TM M 動作 : 受理状態, 拒否状態で停止または停止しない ( 無限ループ ) 出力 : 受理で停止時のテープの内容 M(w) と表記 TM M が受理する入力の集合 受理言語と言い,L(M) と表記 L(M) は, ( どの入力も受理しない ), 有限集合, 無限集合のいずれか どんな ΤΜ Μ に対しても, その受理言語 L(M) が存在し, 一意に定まる 5
6 TM が扱う問題 11 TM M は入力文字列 w が,M の受理言語 L(M) に属しているかどうかを判定 言語とは何か? ある性質を持つ文字列集合 ( 文字列に含まれる0の数と1の数が同じ, など ) すなわち, 入力が, ある特定の性質をもつかどうかを判定する問題をTMは扱う. 本講義では, 以降, 言語への所属判定 = 判定問題, として扱う例 ) 言語 L={ 素数の集合 } を受理する TM は, 問題 入力が素数かどうか を判定する. 例えば以下の判定問題は全て言語として定式化でき,TM で扱うことができる プログラムの停止性判定問題 グラフがオイラー閉路 ( 全ての辺が一筆書きできる ) を持つか 論理関数 f(x 1, x 2,..., x n ) に対し,f(x 1,..., x n )=1 となる各変数への割当て方は存在するか? TM の定義 12 有限オートマトンに無限容量メモリ ( 読み書き可能なテープ ) を拡張した計算モデル 有限制御部 : 有限個の状態を持ち, 現在どの状態にいるのか記憶 テープ : セルに分割されており, 各セルは一つの記号を保持 最初, 有限長の入力記号列 wがテープ上に左詰で置かれる (wは空白を含まない!) ヘッド : 現在指しているセルの内容の読み取り, 書き込み, 左右への移動が可能 TM 始動時のヘッドの位置は, 入力記号列 wの左端 終端マーカ ( これより左には移動しない ) テープ q $ 入力列 w( 空白含まない ) ヘッド 有限制御部 空白記号 a a b a a... r テープの右側は空白のセルが無限にある 6
7 定義 1.1: TM の形式的定義 13 7 項組 M = (Q,, Γ, δ, q 0, q accept, q reject ) で定義 ( 定義は参考書ごとに異なる ) 記号 説明 TMへの入力 wにはσ の元のみ現れる Q 状態の有限集合 Γ-Σ の元 ( 空白記号 入力記号の集合 を含まない など ) は現れない Γ テープ記号の集合 (Σ {$,,...}) δ 遷移関数 ( Q Q Γ {L, R}) ) q 0 初期状態 (q 0 Q) q accept 受理状態 (qq accept Q) 到達すると直ちに停止拒否状態 (q reject Q) 到達すると直ちに停止 q reject L, R はヘッドの移動方向 q r a/b, R δ の各遷移は δ(q,a) = (r,b,r) と表記 状態 q で記号 a を読んだら, 現セルをb に書き換え, ヘッドを右に1つ移動し, 状態 r に移る 例 1.1: Σ={0,1}, Γ=Σ {$,,X,Y} TM の状態遷移図 Y/Y, R /, R q accept Y/Y, R q 0 q 3 0/X, R /, R 1/1, R Y/Y, R q 4 1/1, L 0/0, L 遷移は x/y, D の形式 D は L( 左 ) または R ( 右 ) のどちらか 0, Y を読み飛ばす q 1 X/X, R 14 遷移元と先が同じなら複数の遷移をまとめて書いても良い Y/Y, R Y/Y, L 0/0, R 0/0, L q 1/Y, L 2 0, Yの間巻き戻す /, R q reject 受理状態, または, 拒否状態に到達すると, 直ちに停止 q 0 初期状態 q accept q reject 受理状態拒否状態 遷移の形式には色々バリエーションがあり, 参考書ごとに異なるが, モデルとしては等価 ( 証明は略 ) D として,S( ヘッドを移動させない ) を持つモデルもある 7
8 TM と有限オートマトンとの違い 15 TM M は読み書き可能な無限テープを持つ テープへの読み書き, および, 読み書き位置の変更が可能 a/, R q accept /, R TM M は入力の末尾に達しても停止しない 空白記号を読みながら動作を継続 いつまでも停まらないかも知れない 永遠に止まらない TM を記述するのは簡単 q 0 q 1 /, L 無限ループを含む TM の例 TM M は受理状態または拒否状態に到達すると即座に停止 テープの内容やヘッドの位置に関係なく,q accept または q reject に到達すると停止 入力の読み込み途中で, それより後ろの文字列を読み込んでいなくても, 見てないところも含めて受理する TM M が入力 w に対して動作開始した時の結果は次の 3 通り 受理状態で停止 : M は w を受理する 拒否状態で停止 : M は w を受理しない 停止しない ( 無限ループ ): M は w を受理しない 様相 (configuration):tm のある時点での様子 16 様相の書き方 $ 現在の状態 x 1 x 2...x i-1 q x i x i+1...x n 現在の状態 :q 3 1q 3 10 ヘッドの左側の記号列 ($ からヘッド手前まで.$ は書かない ) ヘッドの右側の記号列 ( ヘッドから最も右の非空白記号まで ) ヘッド上の記号 空白を一つ書く! 特例 : ヘッドの左側に何もないとき,q x 1 x 2...x n ヘッド上から右側が全て空白のとき,x 1...x i-1 q 様相による TM の動作の表現 様相 C 1 にδ の遷移を適用し様相 C 2 が得られるとき, C 1 はC 2 を導出する という C 1 C 2 と表記 C 0 C 1... C n のとき (0 回以上の導出 ), C 0 * C n と書く TM の動作は, 初期様相 C 0 =q 0 w から q accept または q reject を含む様相への列として表現可能 様相の列が q accept または q reject に到達せず無限ループすることもある 8
9 17 TM の動作例 例 1.1 の TM M に文字列 01 を入力したときの動作 X/X, R Y/Y, R 0/0, R Y/Y, L 0/0, L q 0 0/X, R q 1 1/Y, L q 2 Y/Y, R /, R q accept q 3 Y/Y, R /, R 1/1, R Y/Y, R 1/1, L 0/0, L q 4 /, R q reject TM M q 0 01 Xq 1 1 q 2 XY Xq 0 Y XYq 3 XY q accept 0 1 X 1 X Y X Y X Y X Y q 0 q 1 q 2 q 0 q 3 q accept 18 練習問題 問 1.1: 例 1.1 の TM M について以下の問いに答えよ. a) 0011 を入力するとどうなるか. b) 011 を入力するとどうなるか. 9
10 TM の停止性 19 TM Mは入力 wに対して, 以下のいずれかの動作を行う (1) q accept に到達して停止 (2) q reject に到達して停止 (3) 永遠に停まらない ( 無限ループ ) M が w を受理するのは (1) の場合のみ (2) と (3) の場合は w を受理しないが,(3) かどうかを見極めるのは困難 Decider と Recognizer 20 計算できる の定義 問題に対し, 解を答える, または, 解がないと答えるアルゴリズムが存在する 語 w の言語 L への所属判定問題の場合 w が L に属する時は w を受理し, そうでない時は w を拒否して停止する TM が存在 TMの能力に応じて以下の呼称を用いる Decider ある言語 Lが存在し, 任意の入力 wに対し,w Lの時はq accept に到達し停止し, w L の時はq reject に到達し停止するTM Recognizer ある言語 L が存在し, 任意の入力 w に対し,w L の時は q accept に到達し停止する TM w L の時は停止しないかも知れない 問題が計算できる decider が存在 decider が存在しないが recognizer なら存在する問題もある ( 両方存在しない問題もある ) 10
11 半決定可能 / 決定可能な言語の定義 21 定義 1.2: ある言語 L の recognizer が存在するとき,L は半決定可能 (semi-decidable or Turing-recognizable) 1 と言う. 定義 1.3: ある言語 L の decider が存在するとき, L は決定可能 (decidable) 2 であると言う. Lが決定可能であるとき,Lは半決定可能でもある L の decider M は, 任意の文字列 w L を受理するため... 参考書によっては, 以下のように呼ぶことも... 1 帰納的可算 (RE: recursively enumerable) 2 帰納的 (recursive) 言語 L が半決定可能 / 決定可能であることの証明法 与えられた言語 L が半決定可能であることを証明したい L の recognizer または decider を一つ構成する 22 L が決定可能であることを証明したい L の decider を一つ構成する 他の証明方法 既知の ( 半 ) 決定可能な言語に帰着する ( 帰着は, 後に学ぶ ) 11
12 23 決定可能な言語の例 問 1.2: a) 有限長文字列の有限集合はどれも決定可能か? b) 正則言語はどれも決定可能か? 24 TM の簡略記述 TMの形式的記述( 形式レベル記述と呼ぶ ) は煩雑 全状態, 状態遷移関数を含む7 項組 M = (Q,, Γ, δ, q 0, q accept, q reject ) 全てを記述する, もしくは, 相当する状態遷移図を与える必要がある 労力軽減のため TM を簡略記述する ( 抽象レベル記述と呼ぶ ) ヘッドの移動, テープに書き込む記号の種類, 手順を自然語で記述 ( 状態, 状態遷移などは与えなくて良い ) 言語 L が半決定可能 ( または決定可能 ) であることを証明するには L 言語 L が半決定可能 ( または決定可能 ) であることを証明するには,L の recognizer( または decider) を抽象レベルで構成する 注意 抽象レベルで記述した TM から, 等価な形式レベルの TM が構成できることが必要 Decider の場合は, どんな入力に対しても停止することが必要 12
13 TM の抽象レベル記述例 n 例 1.2: L = { 0 2 n 0} を受理するTM Mを構成せよ. ( 抽象レベル記述 ) Mは入力 wを入力すると以下のように動作する. 基本アイデア 1 回のループで0の個数を半分にする. 最後に一つだけ0が残れば受理. アルゴリズムはこれ以外に色々考えられる! ( ステップ 1) テープの左端から入力 w の右端に向かってヘッドを移動させながら一つおきに 0 をテープ記号 X に書き換える (0 の個数を半分にする ) ( ステップ 2) ステップ 1 で 0 の数が 1 つだったら, 停止して受理 (accept) ( ステップ 3) ステップ 1 で 0 の数が (1 以外の ) 奇数だったら, 停止して拒否 (reject) ( ステップ 4) ヘッドをテープの左端に戻す ( ステップ 5) ステップ 1 から繰り返す ( 注 )TM を構成する際には, テープ記号として, 入力アルファベット Σ 以外の ( 有限個の ) 記号 (X, Y, Z など ) を使用して良いことに留意せよ. 25 よくある間違い (TM にない機能を使うのは ) 変数を使う, 算術演算を使う, など 練習問題 26 問 1.3: 例 1.2 の TM を形式レベル ( 状態遷移図 ) で記述せよ. ヒント :1 の個数が 1 の場合, 偶数個の場合, 奇数個 (3 つ以上 ) の場合を異なる状態で区別する. 問 1.4: 以下の言語を決定する TM を構成せよ ( 抽象レベル でよい ). a) 同数の 0 と 1 を含む列の集合 ( ただし,Σ={0,1}) b) {ww R w は 0,1 の任意の列 } (2005 年テスト問題 ) c) {0 n 10 n n 0 } (2006 年テスト問題 ) 13
14 一般の判定問題を TM で扱う方法 27 扱いたい問題を表す言語を定義 言語への所属判定として TM で扱うことができる. (1) 入力が文字列であるような問題 素数判定問題 :L={ 全ての素数の集合 } 文法チェック問題 :L={ 正しい文法で書かれたJavaプログラムの集合 } (2) 入力が任意のオブジェクトであるような問題 オブジェクトを2 進列に符号化 プログラムの停止性判定問題 任意のプログラムコードは2 進数の列で符号化できる. L={ 任意の入力で停止するようなプログラムの2 進列の集合 } とすれば, 言語になる. グラフがオイラー閉路 ( 全ての辺が一筆書きできる ) を持つか 行列やグラフを2 進文字列として符号化する. L={ オイラー閉路を持つグラフの符号の集合 } とすれば, 言語の認識問題になる. 論理関数 f(x 1, x 2,..., x n ) に対し,f(x 1,..., x n )=1となる各変数への割当て方は存在するか? 例えば,x 1 x 2 x 1 x 3 =1を満たす割り当て方は,x 1 =1, x 2 =0, x 3 =1である. 全ての論理関数を2 進符号化し, 真になる割当て方が存在するものの集合を受理言語とする. TM で解ける ( 決定可能な ) 判定問題の例 28 例 1.3: 判定問題 与えられた無向グラフGが連結であるかどうか は決定可能か? 証明 G=(V,E) で与えられ, 頂点の集合はV={v 1,v 2,...,v n }, 辺の集合はE={e 1,...,e m } 無向グラフGの符号を G と表記する. 図のグラフは例えば G =(1#2#3#4)((1#2)(1#3)(2#3)(3#4)) のように符号化できる. V E 次のTMを構成する. ただし,Σ={(, ), #, 1, 2, 3, 4}, Γ=Σ {1, 2, 3, 4, $, } 1. Gの最初の頂点をマークする ( 頂点 1 を 1 に書き換える ). 2. マークされた頂点がこれ以上増えなくなるまで3. を繰り返す 3. Gの各頂点に対し, マークされた頂点からの辺があるとき, その頂点をマークする 4. 全ての頂点をスキャンし, 全てマークされていたらaccept, そうでなければreject 上記のTMはこの問題のdeciderになっていることは明らか. 決定可能 14
15 練習問題 29 問 1.5: 例 1.3 の判定問題を表す言語を定義せよ. 記号の用法 30 文字 ( 記号 ) 0, 1, a, b, X, Yなどで表記 文字変数は,x, yなどで表記 アルファベット ( 文字の有限集合 ) Σ と表記. 例 ) Σ={0,1}, Σ={a, b, c} など 文字列 ( 語 ) 例 )0010, aabc, 0 k 1 k, vv R 入力文字列は慣用的にw と表記 空列 ε と表記. 例 ) 任意の文字列 wに対して,w 0 =ε 空集合 と表記(εとは異なるので間違えないように!) 言語 ( 文字列の集合 ) L と表記. 例 ) L={0 n 1 n n 0}={ε, 01, 0011, ,...} オブジェクト ( グラフなど )Oを符号化した文字列( 符号化法は固定 ) O と表記. 慣例的な用法 a,b,... 文字 q,r,... 状態 x,y,... 文字変数 w... ( 入力 ) 文字列 i,j,k,l,m,n... 整数 A,B,... 集合 M... 機械 L... 言語 M... 機械 M の符号 (=プログラムコード) 15
16 まとめ 31 チューリング機械 (TM) とは 形式的な定義 状態遷移図 様相 (configuration) TM の記述法 ( 形式レベル記述と抽象レベル記述 ) 半決定可能な言語と, 決定可能な言語 TM が扱う問題は判定問題 言語への所属判定 一般の判定問題 Homework( 次回講義時に提出 ) 問 1.1~1.5 16
オートマトン 形式言語及び演習 1. 有限オートマトンとは 酒井正彦 形式言語 言語とは : 文字列の集合例 : 偶数個の 1 の後に 0 を持つ列からなる集合 {0, 110, 11110,
オートマトン 形式言語及び演習 1 有限オートマトンとは 酒井正彦 wwwtrscssinagoya-uacjp/~sakai/lecture/automata/ 形式言語 言語とは : 文字列の集合例 : 偶数個の 1 の後に 0 を持つ列からなる集合 {0, 110, 11110, } 形式言語 : 数学モデルに基づいて定義された言語 認識機械 : 文字列が該当言語に属するか? 文字列 機械 受理
More informationMicrosoft PowerPoint - 5.ppt [互換モード]
5. チューリングマシンと計算 1 5-1. チューリングマシンとその計算 これまでのモデルでは テープに直接書き込むことができなかった また 入力テープヘッドの操作は右方向だけしか移動できなかった これらの制限を取り除いた機械を考える このような機械をチューリングマシン (Turing Machine,TM) と呼ぶ ( 実は TMは 現実のコンピュータの能力を持つ ) TM の特徴 (DFA との比較
More informationMicrosoft PowerPoint - tm ppt [互換モード]
1 2. チューリング機械の拡張 2 チューリング機械の拡張 標準 TM (1テープ1ヘッドTM) の拡張 標準 TMに段階的に機能を拡張する. 拡張したTMは標準 TMより高い能力を持つか? 結論 : 機能を拡張したTMの言語受理能力は標準のTMと同じ 標準 TMと拡張したTMが言語受理能力において等価であることを示す. ある言語 ( 問題 ) が決定可能 / 半決定可能かどうかを証明する際に,
More information情報数理学
2007 年度 情報数理学 履修にあたって 2007 年度大学院奇数セメスター ( 前期 ) 開講 教室 : K336 大学院棟 D46( 次回から ) 時限 : 火曜日 3 時限 (2:50-4:20) 担当 草苅良至 2 講義予定 計算機のいろいろな理論モデル 言語理論 計算の限界 問題の難しさ 現実問題と計算 計算量理論 アルゴリズム論 3 参考書 M. Sipser 著 計算理論の基礎 共立出版
More informationMicrosoft PowerPoint - 1.ppt [互換モード]
第 回オートマトンと正規表現 8//5( 火 ) 履修にあたって 8 年度情報数理学 8 年度大学院奇数セメスター ( 前期 ) 開講教室 : K6 大学院棟 D6( 次回から ) 担当 時限 : 火曜日 時限 (:5-:) 草苅良至 講義予定 計算機のいろいろな理論モデル言語理論 計算の限界計算量理論 問題の難しさ 現実問題と計算アルゴリズム論 参考書. Sipser 著 計算理論の基礎 共立出版
More informationMicrosoft PowerPoint - 3.ppt [互換モード]
3. プッシュダウンオートマトンと文脈自由文法 1 3-1. プッシュダウンオートマトン オートマトンはメモリがほとんど無かった この制限を除いた機械を考える 理想的なスタックを利用できるようなオートマトンをプッシュダウンオートマトン (Push Down Automaton,PDA) という 0 1 入力テープ 1 a 1 1 0 1 スタッb 入力テープを一度走査したあと ク2 入力テプを度走査したあと
More informationPowerPoint プレゼンテーション
コンパイラとプログラミング言語 第 3 4 週 プログラミング言語の形式的な記述 2014 年 4 月 23 日 金岡晃 授業計画 第 1 週 (4/9) コンパイラの概要 第 8 週 (5/28) 下向き構文解析 / 構文解析プログラム 第 2 週 (4/16) コンパイラの構成 第 9 週 (6/4) 中間表現と意味解析 第 3 週 (4/23) プログラミング言語の形式的な記述 第 10 週
More informationPowerPoint プレゼンテーション
解けない問題 を知ろう 保坂和宏 ( 東京大学 B2) 第 11 回 JOI 春合宿 2012/03/19 概要 計算量に関して P と NP NP 完全 決定不能 いろいろな問題 コンテストにおいて Turing 機械 コンピュータの計算のモデル 計算 を数学的に厳密に扱うためのもの メモリのテープ (0/1 の列 ), ポインタ, 機械の内部状態を持ち, 規則に従って状態遷移をする 本講義では
More informationオートマトン 形式言語及び演習 3. 正規表現 酒井正彦 正規表現とは 正規表現 ( 正則表現, Regular Expression) オートマトン : 言語を定義する機械正規表現 : 言語
オートマトン 形式言語及び演習 3. 酒井正彦 www.trs.css.i.nagoya-u.ac.jp/~sakai/lecture/automata/ とは ( 正則表現, Regular Expression) オートマトン : 言語を定義する機械 : 言語を記号列で定義 - 記述しやすい ( ユーザフレンドリ ) 例 :01 + 10 - UNIX の grep コマンド - UNIX の
More informationオートマトンと言語
オートマトンと言語 回目 4 月 8 日 ( 水 ) 章 ( 数式の記法, スタック,BNF 記法 ) 授業資料 http://ir.cs.yamanashi.ac.jp/~ysuzuki/public/automaton/ 授業の予定 ( 中間試験まで ) 回数月日 内容 4 月 日オートマトンとは, オリエンテーション 4 月 8 日 章 ( 数式の記法, スタック,BNF) 3 4 月 5 日
More informationオートマトン 形式言語及び演習 4. 正規言語の性質 酒井正彦 正規言語の性質 反復補題正規言語が満たす性質 ある与えられた言語が正規言語でないことを証明するために その言語が正規言語であると
オートマトン 形式言語及び演習 4. 正規言語の性質 酒井正彦 www.trs.css.i.nagoya-u.ac.jp/~sakai/lecture/automata/ 正規言語の性質 正規言語が満たす性質 ある与えられた言語が正規言語でないことを証明するために その言語が正規言語であると仮定してを使い 矛盾を導く 閉包性正規言語を演算により組み合わせて得られる言語が正規言語となる演算について調べる
More informationMicrosoft PowerPoint - mp11-06.pptx
数理計画法第 6 回 塩浦昭義情報科学研究科准教授 shioura@dais.is.tohoku.ac.jp http://www.dais.is.tohoku.ac.jp/~shioura/teaching 第 5 章組合せ計画 5.2 分枝限定法 組合せ計画問題 組合せ計画問題とは : 有限個の もの の組合せの中から, 目的関数を最小または最大にする組合せを見つける問題 例 1: 整数計画問題全般
More information4 月 東京都立蔵前工業高等学校平成 30 年度教科 ( 工業 ) 科目 ( プログラミング技術 ) 年間授業計画 教科 :( 工業 ) 科目 :( プログラミング技術 ) 単位数 : 2 単位 対象学年組 :( 第 3 学年電気科 ) 教科担当者 :( 高橋寛 三枝明夫 ) 使用教科書 :( プロ
4 東京都立蔵前工業高等学校平成 30 年度教科 ( 工業 ) 科目 ( プログラミング技術 ) 年間授業計画 教科 :( 工業 ) 科目 :( プログラミング技術 ) 単位数 : 2 単位 対象学年組 :( 第 3 学年電気科 ) 教科担当者 :( 高橋寛 三枝明夫 ) 使用教科書 :( プログラミング技術 工業 333 実教出版 ) 共通 : 科目 プログラミング技術 のオリエンテーション プログラミング技術は
More information論理と計算(2)
情報科学概論 Ⅰ アルゴリズムと計算 亀山幸義 http://logic.cs.tsukuba.ac.jp/~kam 計算とは? コンピュータが計算できることは? 1 2 関数 = 計算? NO 部分関数と計算 入力 1 入力 2 関数 出力 入力 1 入力 2 部分関数 出力 停止しない 入力 1 入力 2 コンピュータ 止まらないことがある出力 3 入力 1 入力 2 コンピュータ 出力 停止しない
More informationMicrosoft PowerPoint - 09re.ppt [互換モード]
3.1. 正則表現 3. 正則表現 : 正則表現 ( または正規表現 ) とは 文字列の集合 (= 言語 ) を有限個の記号列で表現する方法の 1 つ 例 : (01)* 01 を繰り返す文字列 つまり 0(0+1)* 0 の後に 0 か 1 が繰り返す文字列 (01)* = {,01,0101,010101,01010101, } 0(0+1)*={0,00,01,000,001,010,011,0000,
More informationMicrosoft PowerPoint - qcomp.ppt [互換モード]
量子計算基礎 東京工業大学 河内亮周 概要 計算って何? 数理科学的に 計算 を扱うには 量子力学を計算に使おう! 量子情報とは? 量子情報に対する演算 = 量子計算 一般的な量子回路の構成方法 計算って何? 計算とは? 計算 = 入力情報から出力情報への変換 入力 計算機構 ( デジタルコンピュータ,etc ) 出力 計算とは? 計算 = 入力情報から出力情報への変換 この関数はどれくらい計算が大変か??
More informationMicrosoft PowerPoint - 10.pptx
m u. 固有値とその応用 8/7/( 水 ). 固有値とその応用 固有値と固有ベクトル 行列による写像から固有ベクトルへ m m 行列 によって線形写像 f : R R が表せることを見てきた ここでは 次元平面の行列による写像を調べる とし 写像 f : を考える R R まず 単位ベクトルの像 u y y f : R R u u, u この事から 線形写像の性質を用いると 次の格子上の点全ての写像先が求まる
More informationJava Scriptプログラミング入門 3.6~ 茨城大学工学部情報工学科 08T4018Y 小幡智裕
Java Script プログラミング入門 3-6~3-7 茨城大学工学部情報工学科 08T4018Y 小幡智裕 3-6 組み込み関数 組み込み関数とは JavaScript の内部にあらかじめ用意されている関数のこと ユーザ定義の関数と同様に 関数名のみで呼び出すことができる 3-6-1 文字列を式として評価する関数 eval() 関数 引数 : string 式として評価する文字列 戻り値 :
More information論理と計算(2)
情報科学概論 Ⅰ アルゴリズムと計算量 亀山幸義 http://logic.cs.tsukuba.ac.jp/~kam 亀山担当分の話題 アルゴリズムと計算量 Fibonacci 数列の計算を例にとり アルゴリズムと計算量とは何か 具体的に学ぶ 良いアルゴリズムの設計例として 整列 ( ソーティング ) のアルゴリズムを学ぶ 2 Fibonacci 数 () Fibonacci 数 (2) = if
More informationMicrosoft PowerPoint - mp13-07.pptx
数理計画法 ( 数理最適化 ) 第 7 回 ネットワーク最適化 最大流問題と増加路アルゴリズム 担当 : 塩浦昭義 ( 情報科学研究科准教授 ) hiour@di.i.ohoku.c.jp ネットワーク最適化問題 ( 無向, 有向 ) グラフ 頂点 (verex, 接点, 点 ) が枝 (edge, 辺, 線 ) で結ばれたもの ネットワーク 頂点や枝に数値データ ( 距離, コストなど ) が付加されたもの
More information書式に示すように表示したい文字列をダブルクォーテーション (") の間に書けば良い ダブルクォーテーションで囲まれた文字列は 文字列リテラル と呼ばれる プログラム中では以下のように用いる プログラム例 1 printf(" 情報処理基礎 "); printf("c 言語の練習 "); printf
情報処理基礎 C 言語についてプログラミング言語は 1950 年以前の機械語 アセンブリ言語 ( アセンブラ ) の開発を始めとして 現在までに非常に多くの言語が開発 発表された 情報処理基礎で習う C 言語は 1972 年にアメリカの AT&T ベル研究所でオペレーションシステムである UNIX を作成するために開発された C 言語は現在使われている多数のプログラミング言語に大きな影響を与えている
More informationプログラミング実習I
プログラミング実習 I 05 関数 (1) 人間システム工学科井村誠孝 m.imura@kwansei.ac.jp 関数とは p.162 数学的には入力に対して出力が決まるもの C 言語では入出力が定まったひとまとまりの処理 入力や出力はあるときもないときもある main() も関数の一種 何かの仕事をこなしてくれる魔法のブラックボックス 例 : printf() 関数中で行われている処理の詳細を使う側は知らないが,
More information例 e 指数関数的に減衰する信号を h( a < + a a すると, それらのラプラス変換は, H ( ) { e } e インパルス応答が h( a < ( ただし a >, U( ) { } となるシステムにステップ信号 ( y( のラプラス変換 Y () は, Y ( ) H ( ) X (
第 週ラプラス変換 教科書 p.34~ 目標ラプラス変換の定義と意味を理解する フーリエ変換や Z 変換と並ぶ 信号解析やシステム設計における重要なツール ラプラス変換は波動現象や電気回路など様々な分野で 微分方程式を解くために利用されてきた ラプラス変換を用いることで微分方程式は代数方程式に変換される また 工学上使われる主要な関数のラプラス変換は簡単な形の関数で表されるので これを ラプラス変換表
More information計算機アーキテクチャ
計算機アーキテクチャ 第 11 回命令実行の流れ 2014 年 6 月 20 日 電気情報工学科 田島孝治 1 授業スケジュール ( 前期 ) 2 回日付タイトル 1 4/7 コンピュータ技術の歴史と コンピュータアーキテクチャ 2 4/14 ノイマン型コンピュータ 3 4/21 コンピュータのハードウェア 4 4/28 数と文字の表現 5 5/12 固定小数点数と浮動小数点表現 6 5/19 計算アーキテクチャ
More informationC プログラミング演習 1( 再 ) 2 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ
C プログラミング演習 1( 再 ) 2 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ 今回のプログラミングの課題 次のステップによって 徐々に難易度の高いプログラムを作成する ( 参照用の番号は よくわかる C 言語 のページ番号 ) 1. キーボード入力された整数 10 個の中から最大のものを答える 2. 整数を要素とする配列 (p.57-59) に初期値を与えておき
More informationPowerPoint Presentation
工学部 6 7 8 9 10 組 ( 奇数学籍番号 ) 担当 : 長谷川英之 情報処理演習 第 7 回 2010 年 11 月 18 日 1 今回のテーマ 1: ポインタ 変数に値を代入 = 記憶プログラムの記憶領域として使用されるものがメモリ ( パソコンの仕様書における 512 MB RAM などの記述はこのメモリの量 ) RAM は多数のコンデンサの集合体 : 電荷がたまっている (1)/ いない
More informationMicrosoft PowerPoint - ad11-09.pptx
無向グラフと有向グラフ 無向グラフ G=(V, E) 頂点集合 V 頂点の対を表す枝の集合 E e=(u,v) 頂点 u, v は枝 e の端点 f c 0 a 1 e b d 有向グラフ G=(V, E) 頂点集合 V 頂点の順序対を表す枝の集合 E e=(u,v) 頂点 uは枝 eの始点頂点 vは枝 eの終点 f c 0 a 1 e b d グラフのデータ構造 グラフ G=(V, E) を表現するデータ構造
More informationプログラミング実習I
プログラミング実習 I 03 変数と式 人間システム工学科井村誠孝 m.imura@kwansei.ac.jp 3.1 変数と型 変数とは p.60 C 言語のプログラム中で, 入力あるいは計算された数や文字を保持するには, 変数を使用する. 名前がついていて値を入れられる箱, というイメージ. 変数定義 : 変数は変数定義 ( 宣言 ) してからでないと使うことはできない. 代入 : 変数には値を代入できる.
More information文法と言語 ー文脈自由文法とLR構文解析2ー
文法と言語ー文脈自由文法とLR 構文解析 2 ー 和田俊和資料保存場所 http://vrl.sys.wakayama-u.ac.jp/~twada/syspro/ 前回までの復習 最右導出と上昇型構文解析 最右導出を前提とした場合, 上昇型の構文解析がしばしば用いられる. 上昇型構文解析では生成規則の右辺にマッチする部分を見つけ, それを左辺の非終端記号に置き換える 還元 (reduction)
More informationプログラミングA
プログラミング A 第 5 回 場合に応じた処理 繰り返し 2019 年 5 月 13 日 東邦大学金岡晃 場合に応じた処理 1 こういうプログラムを作りたい 5 教科のテスト 100 点以上各科目の点数の合計が 100 点未満 おめでとう! これで 100 点越えのプレゼントを獲得! というメッセージを出力 残念!100 点越えのプレゼントまであと ** 点! というメッセージを出力 5 教科の点数の合計が
More informationMicrosoft PowerPoint - ca ppt [互換モード]
大阪電気通信大学情報通信工学部光システム工学科 2 年次配当科目 コンピュータアルゴリズム 良いアルゴリズムとは 第 2 講 : 平成 20 年 10 月 10 日 ( 金 ) 4 限 E252 教室 中村嘉隆 ( なかむらよしたか ) 奈良先端科学技術大学院大学助教 y-nakamr@is.naist.jp http://narayama.naist.jp/~y-nakamr/ 第 1 講の復習
More informationMicrosoft PowerPoint - prog03.ppt
プログラミング言語 3 第 03 回 (2007 年 10 月 08 日 ) 1 今日の配布物 片面の用紙 1 枚 今日の課題が書かれています 本日の出欠を兼ねています 2/33 今日やること http://www.tnlab.ice.uec.ac.jp/~s-okubo/class/java06/ にアクセスすると 教材があります 2007 年 10 月 08 日分と書いてある部分が 本日の教材です
More informationMicrosoft PowerPoint - H22制御工学I-10回.ppt
制御工学 I 第 回 安定性 ラウス, フルビッツの安定判別 平成 年 6 月 日 /6/ 授業の予定 制御工学概論 ( 回 ) 制御技術は現在様々な工学分野において重要な基本技術となっている 工学における制御工学の位置づけと歴史について説明する さらに 制御システムの基本構成と種類を紹介する ラプラス変換 ( 回 ) 制御工学 特に古典制御ではラプラス変換が重要な役割を果たしている ラプラス変換と逆ラプラス変換の定義を紹介し
More informationプログラミングA
プログラミング A 第 5 回 場合に応じた処理 繰り返し 2017 年 5 月 15 日 東邦大学金岡晃 前回の復習 (1) このプログラムを作成し実行してください 1 前回の復習 (2) このプログラムを作成し実行してください 2 前回の復習 (3) 3 前回の復習 演算子 代入演算子 インクリメント シフト演算子 型変換 4 場合に応じた処理 5 こういうプログラムを作りたい 5 教科のテスト
More informationスライド 1
ブール代数 ブール代数 集合 { 0, 1 } の上で演算 AND, OR, NOT からなる数学的体系 何のため? ある演算をどのような回路で実現すればよいのか? どうすれば回路が小さくなるのか? どうすれば回路が速く動くのか? 3 復習 : 真理値表とゲート記号 真理値表 A B A B 0 0 0 0 1 0 1 0 0 1 1 1 A B A+B 0 0 0 0 1 1 1 0 1 1 1
More informationMicrosoft Word - thesis.doc
剛体の基礎理論 -. 剛体の基礎理論初めに本論文で大域的に使用する記号を定義する. 使用する記号トルク撃力力角運動量角速度姿勢対角化された慣性テンソル慣性テンソル運動量速度位置質量時間 J W f F P p .. 質点の並進運動 質点は位置 と速度 P を用いる. ニュートンの運動方程式 という状態を持つ. 但し ここでは速度ではなく運動量 F P F.... より質点の運動は既に明らかであり 質点の状態ベクトル
More informationMicrosoft PowerPoint - 13.ppt [互換モード]
13. 近似アルゴリズム 1 13.1 近似アルゴリズムの種類 NP 困難な問題に対しては多項式時間で最適解を求めることは困難であるので 最適解に近い近似解を求めるアルゴリズムが用いられることがある このように 必ずしも厳密解を求めないアルゴリズムは 大きく分けて 2 つの範疇に分けられる 2 ヒューリスティックと近似アルゴリズム ヒュ- リスティクス ( 発見的解法 経験的解法 ) 遺伝的アルゴリズム
More informationMicrosoft PowerPoint - 13approx.pptx
I482F 実践的アルゴリズム特論 13,14 回目 : 近似アルゴリズム 上原隆平 (uehara@jaist.ac.jp) ソートの下界の話 比較に基づく任意のソートアルゴリズムはΩ(n log n) 時間の計算時間が必要である 証明 ( 概略 ) k 回の比較で区別できる場合の数は高々 2 k 種類しかない n 個の要素の異なる並べ方は n! 通りある したがって少なくとも k n 2 n!
More information(1) プログラムの開始場所はいつでも main( ) メソッドから始まる 順番に実行され add( a,b) が実行される これは メソッドを呼び出す ともいう (2)add( ) メソッドに実行が移る この際 add( ) メソッド呼び出し時の a と b の値がそれぞれ add( ) メソッド
メソッド ( 教科書第 7 章 p.221~p.239) ここまでには文字列を表示する System.out.print() やキーボードから整数を入力する stdin.nextint() などを用いてプログラムを作成してきた これらはメソッドと呼ばれるプログラムを構成する部品である メソッドとは Java や C++ などのオブジェクト指向プログラミング言語で利用されている概念であり 他の言語での関数やサブルーチンに相当するが
More informationC8
システムソフトウェア講義の概要. 計算機システムの復習 : 中央演算処理装置 (CPU), プログラムの実行, 主記憶装置, 補助記憶装置 2. 時分割処理 : プロセス, スレッド, スケジューリング. スレッド間の排他制御 : フラグ, セマフォ, モニタ, デッドロック 4. デバイス管理,HDD へのアクセス制御 5. 記憶管理 : メモリ割り当て, ページング, セグメンテーション 6.
More informationMicrosoft PowerPoint - Compiler03note.pptx
コンパイラ 第 3 回字句解析 決定性有限オートマトンの導出 http://www.no.knd.c.jp/compler 38 号館 4 階 N4 内線 5459 tks@no.knd.c.jp コンパイラの構造 字句解析系 構文解析系 制約検査系 中間コード生成系 最適化系 目的コード生成系 処理の流れ情報システムプロジェクト I の場合 output (); 字句解析系 output ( 変数名
More informationMicrosoft PowerPoint - 2.ppt [互換モード]
0 章数学基礎 1 大学では 高校より厳密に議論を行う そのために 議論の議論の対象を明確にする必要がある 集合 ( 定義 ) 集合 物の集まりである集合 X に対して X を構成している物を X の要素または元という 集合については 3 セメスタ開講の 離散数学 で詳しく扱う 2 集合の表現 1. 要素を明示する表現 ( 外延的表現 ) 中括弧で 囲う X = {0,1, 2,3} 慣用的に 英大文字を用いる
More informationMicrosoft PowerPoint - Prog05.ppt
本日の内容 プログラミング言語第五回 担当 : 篠沢佳久櫻井彰人 平成 20 年 5 月 19 日 制御構造 条件式 論理式 ( 復習 ) if 式 繰り返し (1) 無限の繰り返し 1 2 Ruby vs. Excel 浮動小数点数の計算能力は同じ 整数の計算能力は Ruby が上 Ruby なら何桁でも計算できる Excel には 整数計算だけやって! ということができない欠点がある 使いやすさは
More informationプログラミング基礎
C プログラミング Ⅰ 授業ガイダンス C 言語の概要プログラム作成 実行方法 授業内容について 授業目的 C 言語によるプログラミングの基礎を学ぶこと 学習内容 C 言語の基礎的な文法 入出力, 変数, 演算, 条件分岐, 繰り返し, 配列,( 関数 ) C 言語による簡単な計算処理プログラムの開発 到達目標 C 言語の基礎的な文法を理解する 簡単な計算処理プログラムを作成できるようにする 授業ガイダンス
More information2-1 / 語問題 項書換え系 4.0. 準備 (3.1. 項 代入 等価性 ) 定義 3.1.1: - シグネチャ (signature): 関数記号の集合 (Σ と書く ) - それぞれの関数記号は アリティ (arity) と呼ばれる自然数が定められている - Σ (n) : アリ
2-1 / 32 4. 語問題 項書換え系 4.0. 準備 (3.1. 項 代入 等価性 ) 定義 3.1.1: - シグネチャ (signature): 関数記号の集合 (Σ と書く ) - それぞれの関数記号は アリティ (arity) と呼ばれる自然数が定められている - Σ (n) : アリティ n を持つ関数記号からなる Σ の部分集合 例 : 群 Σ G = {e, i, } (e Σ
More informationMicrosoft PowerPoint - H21生物計算化学2.ppt
演算子の行列表現 > L いま 次元ベクトル空間の基底をケットと書くことにする この基底は完全系を成すとすると 空間内の任意のケットベクトルは > > > これより 一度基底を与えてしまえば 任意のベクトルはその基底についての成分で完全に記述することができる これらの成分を列行列の形に書くと M これをベクトル の基底 { >} による行列表現という ところで 行列 A の共役 dont 行列は A
More information情報システム評価学 ー整数計画法ー
情報システム評価学 ー整数計画法ー 第 1 回目 : 整数計画法とは? 塩浦昭義東北大学大学院情報科学研究科准教授 この講義について 授業の HP: http://www.dais.is.tohoku.ac.jp/~shioura/teaching/dais08/ 授業に関する連絡, および講義資料等はこちらを参照 教員への連絡先 : shioura (AT) dais.is.tohoku.ac.jp
More informationAn Automated Proof of Equivalence on Quantum Cryptographic Protocols
量子暗号のための プロトコル等価性検証ツール 久保田貴大 *, 角谷良彦 *, 加藤豪, 河野泰人, 櫻田英樹 * 東京大学情報理工学系研究科, NTT コミュニケーション科学基礎研究所 背景 暗号安全性証明の検証は難しい 量子暗号でもそうである 検証のための形式体系が提案されているが, 実際には, 形式体系の適用は手作業では非常に煩雑である 形式検証のためには, 検証ツールが開発されることが望ましい
More informationPowerPoint Presentation
付録 2 2 次元アフィン変換 直交変換 たたみ込み 1.2 次元のアフィン変換 座標 (x,y ) を (x,y) に移すことを 2 次元での変換. 特に, 変換が と書けるとき, アフィン変換, アフィン変換は, その 1 次の項による変換 と 0 次の項による変換 アフィン変換 0 次の項は平行移動 1 次の項は座標 (x, y ) をベクトルと考えて とすれば このようなもの 2 次元ベクトルの線形写像
More informationデータベースS
データベース S 第 4 回データベース言語 SQL(1) システム創成情報工学科尾下真樹 2018 年度 Q2 今日の内容 前回の復習 SQLの概要 SQLによる問い合わせの記述方法 SQLの基本的な書き方 条件 (WHERE) の書き方 出力 (SELECT) の書き方 順序付け (ORDER BY) グループ表 (GROUP BY) 教科書 リレーショナルデータベース入門 [ 第 3 版 ]
More information02: 変数と標準入出力
C プログラミング入門 基幹 7 ( 水 5) 12: コマンドライン引数 Linux にログインし 以下の講義ページを開いておくこと http://www-it.sci.waseda.ac.jp/ teachers/w483692/cpr1/ 2016-06-29 1 まとめ : ポインタを使った処理 内容呼び出し元の変数を書き換える文字列を渡す 配列を渡すファイルポインタ複数の値を返す大きな領域を確保する
More informationMicrosoft PowerPoint - 9.pptx
9. 線形写像 ここでは 行列の積によって 写像を定義できることをみていく また 行列の積によって定義される写像の性質を調べていく 行列演算と写像 ( 次変換 3 拡大とスカラー倍 p ' = ( ', ' = ( k, kk p = (, k 倍 k 倍 拡大後 k 倍拡大の関係は スカラー倍を用いて次のように表現できる ' = k ' 拡大前 拡大 4 拡大と行列の積 p ' = ( ', '
More informationMicrosoft PowerPoint - 9.pptx
9/7/8( 水 9. 線形写像 ここでは 行列の積によって 写像を定義できることをみていく また 行列の積によって定義される写像の性質を調べていく 拡大とスカラー倍 行列演算と写像 ( 次変換 拡大後 k 倍 k 倍 k 倍拡大の関係は スカラー倍を用いて次のように表現できる p = (, ' = k ' 拡大前 p ' = ( ', ' = ( k, k 拡大 4 拡大と行列の積 拡大後 k 倍
More informationMicrosoft PowerPoint - prog04.ppt
プログラミング言語 2 第 04 回 (2007 年 05 月 14 日 ) 今日の配布物 片面の用紙 1 枚 今日の課題が書かれています 本日の出欠を兼ねています 1 今日やること http://www.tnlab.ice.uec.ac.jp/~s-okubo/class/language/ にアクセスすると 教材があります 2007 年 05 月 14 日分と書いてある部分が 本日の教材です 本日の内容
More informationDVIOUT
第 3 章 フーリエ変換 3.1 フーリエ積分とフーリエ変換 第 章では 周期を持つ関数のフーリエ級数について学びました この章では 最初に 周期を持つ関数のフーリエ級数を拡張し 周期を持たない ( 一般的な ) 関数のフーリエ級数を導きましょう 具体的には 関数 f(x) を区間 L x L で考え この L を限りなく大きくするというアプローチを取ります (L ) なお ここで扱う関数 f(x)
More informationスライド 1
順序回路 (2) 1 順序回路の設計 組合せ論理回路の設計法 構造や規則性に着目した手設計 ( 先人の知恵を使う ) 入力 出力の関係に基づく自動合成 ( カルノー図など ) 順序回路の設計法 構造や規則性に着目した手設計 ( 前回の各例 ) 入力 出力 状態の関係に基づく自動合成 2 同期式順序回路の入力 出力 状態の関係 x 1 x 2 組合せ回路 y 1 y 2 x n q 2 q p q 1
More informationオートマトンと言語理論 テキスト 成蹊大学理工学部情報科学科 山本真基 ii iii 1 1 1.1.................................. 1 1.2................................ 5 1.3............................. 5 2 7 2.1..................................
More informationコンピュータ工学講義プリント (7 月 17 日 ) 今回の講義では フローチャートについて学ぶ フローチャートとはフローチャートは コンピュータプログラムの処理の流れを視覚的に表し 処理の全体像を把握しやすくするために書く図である 日本語では流れ図という 図 1 は ユーザーに 0 以上の整数 n
コンピュータ工学講義プリント (7 月 17 日 ) 今回の講義では フローチャートについて学ぶ フローチャートとはフローチャートは コンピュータプログラムの処理の流れを視覚的に表し 処理の全体像を把握しやすくするために書く図である 日本語では流れ図という 図 1 は ユーザーに 0 以上の整数 n を入力してもらい その後 1 から n までの全ての整数の合計 sum を計算し 最後にその sum
More information<4D F736F F D208CF68BA48C6F8DCF8A C30342C CFA90B68C6F8DCF8A7782CC8AEE967B92E8979D32288F4390B394C529332E646F63>
2. 厚生経済学の ( 第 ) 基本定理 2 203 年 4 月 7 日 ( 水曜 3 限 )/8 本章では 純粋交換経済において厚生経済学の ( 第 ) 基本定理 が成立することを示す なお より一般的な生産技術のケースについては 4.5 補論 2 で議論する 2. 予算集合と最適消費点 ( 完全 ) 競争市場で達成される資源配分がパレート効率的であることを示すための準備として 個人の最適化行動を検討する
More informationcp-7. 配列
cp-7. 配列 (C プログラムの書き方を, パソコン演習で学ぶシリーズ ) https://www.kkaneko.jp/cc/adp/index.html 金子邦彦 1 本日の内容 例題 1. 月の日数配列とは. 配列の宣言. 配列の添え字. 例題 2. ベクトルの内積例題 3. 合計点と平均点例題 4. 棒グラフを描く配列と繰り返し計算の関係例題 5. 行列の和 2 次元配列 2 今日の到達目標
More information構造化プログラミングと データ抽象
計算の理論 後半第 3 回 λ 計算と型システム 本日の内容 λ 計算の表現力 ( 前回の復習 ) データの表現 不動点演算子と再帰 λ 計算の重要な性質 チャーチ ロッサー性 簡約戦略 型付き λ 計算 ブール値 組 ブール値と組の表現 true, false を受け取り 対応する要素を返す関数 として表現 T = λt.λf.t F = λt.λf.f if e 1 then e 2 else
More information講習No.1
プログラムはどこに保存され, どこで実行されるのか? 復習 ハードディスク キーボード Central Processing Unit 例えば i7, ARM, Cortex-A17 ディスプレイ 例えば 4G バイト メモリ プログラムは, ワープロ文章などと同様, ハードディスクなどにファイルとして保存されている. プログラムは, メモリ上に呼び出されて ( ロード ) 実行される. プログラムの作成
More informationプログラミング入門1
プログラミング入門 1 第 5 回 繰り返し (while ループ ) 授業開始前に ログオン後 不要なファイルを削除し て待機してください Java 1 第 5 回 2 参考書について 参考書は自分にあったものをぜひ手元において自習してください 授業の WEB 教材は勉強の入り口へみなさんを案内するのが目的でつくられている これで十分という訳ではない 第 1 回に紹介した本以外にも良書がたくさんある
More informationMicrosoft PowerPoint - prog03.ppt
プログラミング言語 2 第 03 回 (2007 年 05 月 07 日 ) 今日の配布物 片面の用紙 1 枚 今日の課題が書かれています 本日の出欠を兼ねています 1 今日やること hp://www.nlab.ice.uec.ac.jp/~s-okubo/class/language/ にアクセスすると 教材があります 2007 年 05 月 07 日分と書いてある部分が 本日の教材です 本日の内容
More informationMicrosoft PowerPoint Java基本技術PrintOut.ppt [互換モード]
第 3 回 Java 基本技術講義 クラス構造と生成 33 クラスの概念 前回の基本文法でも少し出てきたが, オブジェクト指向プログラミングは という概念をうまく活用した手法である. C 言語で言う関数に似ている オブジェクト指向プログラミングはこれら状態と振る舞いを持つオブジェクトの概念をソフトウェア開発の中に適用し 様々な機能を実現する クラス= = いろんなプログラムで使いまわせる 34 クラスの概念
More informationmemo
数理情報工学特論第一 機械学習とデータマイニング 4 章 : 教師なし学習 3 かしまひさし 鹿島久嗣 ( 数理 6 研 ) kashima@mist.i.~ DEPARTMENT OF MATHEMATICAL INFORMATICS 1 グラフィカルモデルについて学びます グラフィカルモデル グラフィカルラッソ グラフィカルラッソの推定アルゴリズム 2 グラフィカルモデル 3 教師なし学習の主要タスクは
More informationMicrosoft PowerPoint - Compiler03.pptx
コンパイラ 第 3 回字句解析 決定性有限オートマトンの導出 http://www.info.kindi.c.jp/compiler 38 号館 4 階 N-411 内線 5459 tksi-i@info.kindi.c.jp コンパイラの構造 字句解析系 構文解析系 制約検査系 中間コード生成系 最適化系 目的コード生成系 処理の流れ 情報システムプロジェクト I の場合 write (); 字句解析系
More informationMicrosoft PowerPoint - mp11-02.pptx
数理計画法第 2 回 塩浦昭義情報科学研究科准教授 shioura@dais.is.tohoku.ac.jp http://www.dais.is.tohoku.ac.jp/~shioura/teaching 前回の復習 数理計画とは? 数理計画 ( 復習 ) 数理計画問題とは? 狭義には : 数理 ( 数学 ) を使って計画を立てるための問題 広義には : 与えられた評価尺度に関して最も良い解を求める問題
More informationMicrosoft Word ã‡»ã…«ã‡ªã…¼ã…‹ã…žã…‹ã…³ã†¨åłºæœ›å•¤(佒芤喋çfl�)
Cellulr uo nd heir eigenlues 東洋大学総合情報学部 佐藤忠一 Tdzu So Depren o Inorion Siene nd rs Toyo Uniersiy. まえがき 一次元セルオ-トマトンは数学的には記号列上の行列の固有値問題である 固有値問題の行列はふつう複素数体上の行列である 量子力学における固有値問題も無限次元ではあるが関数環上の行列でその成分は可換環である
More informationnlp1-04a.key
自然言語処理論 I. 文法 ( 構文解析 ) その 構文解析 sytctic lysis, prsig 文の構文的な構造を決定すること句構造文法が使われることが多い文法による構文木は一般に複数ある 構文木の違い = 解釈の違い 構文解析の目的 句構造文法の規則を使って, 文を生成できる構文木を全て見つけだすこと 文法が入力文を生成できるかどうかを調べるだけではない pro I 構文解析とは 構文木の違い
More informationオートマトンと言語
オートマトンと言語 4 回目 5 月 2 日 ( 水 ) 3 章 ( グラフ ) の続き 授業資料 http://ir.cs.yamanashi.ac.jp/~ysuzuki/public/automaton/ 授業の予定 ( 中間試験まで ) 回数月日 内容 4 月 日オートマトンとは, オリエンテーション 2 4 月 8 日 2 章 ( 数式の記法, スタック,BNF) 3 4 月 25 日 2
More informationJavaプログラミングⅠ
Java プログラミング Ⅰ 2 回目 ようこそ Java へ 今日の講義で学ぶ内容 画面へのメッセージの表示 文字や文字列 数値を表現するリテラル 制御コードを表すエスケープシーケンス 画面出力の基本形 ソースファイル名 : クラス名.java class クラス名 System.out.println(" ここに出力したい文字列 1 行目 "); System.out.println(" ここに出力したい文字列
More informationInformation Theory
前回の復習 情報をコンパクトに表現するための符号化方式を考える 情報源符号化における基礎的な性質 一意復号可能性 瞬時復号可能性 クラフトの不等式 2 l 1 + + 2 l M 1 ハフマン符号の構成法 (2 元符号の場合 ) D. Huffman 1 前回の練習問題 : ハフマン符号 符号木を再帰的に構成し, 符号を作る A B C D E F 確率 0.3 0.2 0.2 0.1 0.1 0.1
More informationJavaScriptで プログラミング
JavaScript でプログラミング JavaScript とは プログラミング言語の 1 つ Web ページ上でプログラムを動かすことが主目的 Web ブラウザで動かすことができる 動作部分の書き方が C や Java などに似ている 2 JavaScript プログラムを動かすには の範囲を 1. テキストエディタで入力 2..html というファイル名で保存
More informationアルゴリズムとデータ構造
講義 アルゴリズムとデータ構造 第 2 回アルゴリズムと計算量 大学院情報科学研究科情報理工学専攻情報知識ネットワーク研究室喜田拓也 講義資料 2018/5/23 今日の内容 アルゴリズムの計算量とは? 漸近的計算量オーダーの計算の方法最悪計算量と平均計算量 ポイント オーダー記法 ビッグオー (O), ビッグオメガ (Ω), ビッグシータ (Θ) 2 お風呂スケジューリング問題 お風呂に入る順番を決めよう!
More information2006年10月5日(木)実施
2010 年 7 月 2 日 ( 金 ) 実施 ファイル処理ファイルとはファイル (file) は日常用語では紙などを綴じたものを表すが, コンピュータ用語ではデータの集合体を指す言葉である ファイルは例えば, 文書ファイルやプログラムファイルのように, 用途によって分類されることもあれば, また, テキストファイルやバイナリファイルのように, ファイルの作り方によって分類されることもある なお,
More information040402.ユニットテスト
2. ユニットテスト ユニットテスト ( 単体テスト ) ユニットテストとはユニットテストはプログラムの最小単位であるモジュールの品質をテストすることであり その目的は結合テスト前にモジュール内のエラーを発見することである テストは機能テストと構造テストの2つの観点から行う モジュールはプログラムを構成する要素であるから 単体では動作しない ドライバとスタブというテスト支援ツールを使用してテストを行う
More informationMicrosoft Word 基_シラバス.doc
4-5- 基 Web アプリケーション開発に関する知識 1 4-5- 基 Web アプリケーション開発に関する知識 スクリプト言語や Java 言語を利用して Ruby on Rails やその他 Web フレームワークを活用して HTML(4, 5) XHTML JavaScript DOM CSS といったマークアップ言語およびスクリプト言語を活用しながら Ⅰ. 概要ダイナミックなWebサービスを提供するアプリケーションを開発する際に
More information構造化プログラミングと データ抽象
計算の理論 後半第 3 回 λ 計算と型システム 本日の内容 λ 計算の表現力 ( 前回のつづき ) 前回の復習 不動点演算子と再帰 λ 計算の重要な性質 チャーチ ロッサー性 簡約戦略 型付き λ 計算 ブール値 組 ブール値と組の表現 ( 復習 ) true, false を受け取り 対応する要素を返す関数 として表現 T = λt.λf.t F = λt.λf.f if e 1 then e
More informationPowerPoint プレゼンテーション
プログラミング初級 第 7 回 2017 年 5 月 29 日 配列 ( 復習 )~ 文字列 1 配列とは 2 配列 : 複数の変数をグループとしてまとめて扱うもの 配列 変数 int data[10]; 整数型の配列 同種のデータ型を連続して確保したものを配列とよぶ = 整数がそれぞれにひとつずつ入る箱を 10 個用意したようなもの int data; 整数型の変数 = 整数がひとつ入る dataという名前の箱を用意したようなもの
More information講義の進め方 第 1 回イントロダクション ( 第 1 章 ) 第 2 ~ 7 回第 2 章 ~ 第 5 章 第 8 回中間ミニテスト (11 月 15 日 ) 第 9 回第 6 章 ~ 第 回ローム記念館 2Fの実習室で UML によるロボット制御実習 定期試験 2
ソフトウェア工学 第 7 回 木曜 5 限 F205 神原弘之 京都高度技術研究所 (ASTEM RI) http://www.metsa.astem.or.jp/se/ 1 講義の進め方 第 1 回イントロダクション ( 第 1 章 ) 第 2 ~ 7 回第 2 章 ~ 第 5 章 第 8 回中間ミニテスト (11 月 15 日 ) 第 9 回第 6 章 ~ 第 12 14 回ローム記念館 2Fの実習室で
More informationモデリングとは
コンピュータグラフィックス基礎 第 5 回曲線 曲面の表現 ベジェ曲線 金森由博 学習の目標 滑らかな曲線を扱う方法を学習する パラメトリック曲線について理解する 広く一般的に使われているベジェ曲線を理解する 制御点を入力することで ベジェ曲線を描画するアプリケーションの開発を行えるようになる C++ 言語の便利な機能を使えるようになる 要素数が可変な配列としての std::vector の活用 計算機による曲線の表現
More informationDVIOUT-SS_Ma
第 章 微分方程式 ニュートンはリンゴが落ちるのを見て万有引力を発見した という有名な逸話があります 無重力の宇宙船の中ではリンゴは落ちないで静止していることを考えると 重力が働くと始め静止しているものが動き出して そのスピードはどんどん大きくなる つまり速度の変化が現れることがわかります 速度は一般に時間と共に変化します 速度の瞬間的変化の割合を加速度といい で定義しましょう 速度が変化する, つまり加速度がでなくなるためにはその原因があり
More informationファイル入出力
C プログラミング Ⅱ の基礎 とは ファイルへデータを書き込んだり ( 出力 ), ファイルからデータを読み込んだり ( 入力 ) する C 言語では キーボードからの入力 画面への出力と同じようなコードで 処理を実現できる プログラム 入力 出力 ファイル 出力 入力 2 入出力の基本 ストリーム プログラム上で様々な装置への入出力を行う機構様々な入出力装置を統一的な方法で扱うことができる ハードディスクなどではファイルデータによって入出力が行われる
More information第 3 回講義の項目と概要 統計的手法入門 : 品質のばらつきを解析する 平均と標準偏差 (P30) a) データは平均を見ただけではわからない 平均が同じだからといって 同一視してはいけない b) データのばらつきを示す 標準偏差 にも注目しよう c) 平均
第 3 回講義の項目と概要 016.8.9 1.3 統計的手法入門 : 品質のばらつきを解析する 1.3.1 平均と標準偏差 (P30) a) データは平均を見ただけではわからない 平均が同じだからといって 同一視してはいけない b) データのばらつきを示す 標準偏差 にも注目しよう c) 平均 :AVERAGE 関数, 標準偏差 :STDEVP 関数とSTDEVという関数 1 取得したデータそのものの標準偏差
More informationオートマトンと言語
授業のねらい アルゴリズムとデータ構造 III 木曜日 2 時限鈴木良弥 アルゴリズムとデータ構造 I,II で学んだ事柄の復習 事例を通じて, 今まで学んだアルゴリズムとデータ構造を組み合わせたアプリケーションのアルゴリズムとデータ構造を学ぶ 授業資料 http://ir.cs.yamanashi.ac.jp/~ysuzuki/pulic/algorithm3/index.html 他の授業との関連科目間関係科目名キーワード関連度教科書,
More informationポインタ変数
プログラミング及び実習 5 馬青 1 文字処理 数値処理 : 整数 浮動小数点数 単一の文字は と ( シングルクォーテーション ) で囲んで表現される 文字のデータ型は char または int である int を用いたほうが ライブラリの関数の引数の型と一致する 以下は全部 int の使用に統一する 従って int ch; で文字変数を宣言しておくと ch= A ; のように ch に文字 A
More informationMicrosoft PowerPoint - 2-LispProgramming-full
2013 年 5 月 31 日 Lisp プログラミング入門 西田豊明 Copyright 2013 Toyoaki Nishida All Rights Reserved. 今回あらすじ 1. Lisp の実践的な使い方を学習する. 2. Lisp インタープリタの動かし方, 電卓的使い方, 関数定義, 条件分岐,S 式の基本操作, プログラミング手法, プロトタイピング法などを中心に解説する.
More informationはじめてのPFD
はじめての PFD 派生開発 WG アンリツエンジニアリング株式会社文書番号 :AE-RAEB00000063 初版 Copyright 2016 Anritsu Engineering Co.,Ltd. Publicly available 演習概要 PFDの書き方 : 15 分 演習 : 30 分 + 発表 ( 講評 ) 20 分 まとめ 2 参考文献 PFD(Process Flow Diagram)
More informationMicrosoft PowerPoint - prog04.ppt
プログラミング言語 3 第 04 回 (2007 年 10 月 15 日 ) 1 今日の配布物 片面の用紙 1 枚 今日の課題が書かれています 本日の出欠を兼ねています 2/33 1 今日やること http://www.tnlab.ice.uec.ac.jp/~s-okubo/class/java06/ にアクセスすると 教材があります 2007 年 10 月 15 日分と書いてある部分が 本日の教材です
More informationメソッドのまとめ
メソッド (4) 擬似コードテスト技法 http://java.cis.k.hosei.ac.jp/ 授業の前に自己点検以下のことがらを友達に説明できますか? メソッドの宣言とは 起動とは何ですか メソッドの宣言はどのように書きますか メソッドの宣言はどこに置きますか メソッドの起動はどのようにしますか メソッドの仮引数 実引数 戻り値とは何ですか メソッドの起動にあたって実引数はどのようにして仮引数に渡されますか
More informationJavaプログラミングⅠ
Java プログラミング Ⅰ 5 回目演算子の優先順位と変数の型変換 今日の講義で学ぶ内容 演算子の優先順位 優先順位の変更の方法 キャスト演算子と型変換 演算子の優先順位 演算子の優先順位 式を計算するときの演算の順序です例えば a=b*c+d; では乗算を先に計算するというルールです ( 主な演算子の優先順位 ) 演算子 名前 結合規則 ++ 後置インクリメント 左 -- 後置デクリメント 左!
More informationMicrosoft Word - 19-d代 試é¨fi 解ç�fl.docx
2019 年度ディジタル代数期末試験解答例 再評価試験は期末試験と同程度の難しさである. しっかり準備して受けるように. 1. アドレスが 4 バイトで表わされた画像処理専用プロセッサが幾つかのデータを吐き出して停まってしまった. そのデータの 1 つはレジスタ R0 の中身で,16 進表示すると (BD80) 16 であった. このデータに関して, 以下の問に対する回答を対応する箱内に書け. (1)
More informationFunctional Programming
PROGRAMMING IN HASKELL プログラミング Haskell Chapter 7 - Higher-Order Functions 高階関数 愛知県立大学情報科学部計算機言語論 ( 山本晋一郎 大久保弘崇 2013 年 ) 講義資料オリジナルは http://www.cs.nott.ac.uk/~gmh/book.html を参照のこと 0 Introduction カリー化により
More informationV-CUBE One
V-CUBE One コンテンツ配信機能システム管理マニュアル ブイキューブ 2016/12/22 この文書は V-CUBE One コンテンツ配信機能のシステム管理マニュアルです 更新履歴 更新日 内容 2015/04/28 新規作成 2015/07/24 グループ管理のユーザーインタフェース変更に伴う修正 ユーザー管理のユーザーインタフェース変更に伴う修正 2015/09/30 連携サービス追加に伴う
More informationMicrosoft PowerPoint - 11Syntax.ppt
言語理論 : 知的情報処理 (11) 構文論 慶應義塾大学理工学部櫻井彰人 言語を定義する方法 ( いくつかある ): 文法 ( 生成規則 ) オートマトン 既知の言語間の演算 これらの間には対応関係がある 自然言語の記述だけでなく 例えば コンパイラの設計に使用 言語の定義方法 プログラム言語の構文を簡単に どうやって定義するか 定義方法は使いやすくあるべし, i..: 定義は有限の長さ 与えられた文字列がその言語に属するか否かを調べるアルゴリズムが存在する必要がある
More informationMicrosoft PowerPoint ppt
仮想マシン (2), コード生成 http://cis.k.hosei.ac.jp/~asasaki /lect/compiler/2007-1204.pdf ( 訂正版 ) 1 概要 仮想マシン 概要 ( 復習 ) 制御命令 出力命令 コード生成 式のコード生成 文 文の列のコード生成 記号表 2 演習で作るコンパイラの例 test.hcc Int main() { int i j; i = 3;
More informationMicrosoft PowerPoint - algo ppt [互換モード]
( 復習 ) アルゴリズムとは アルゴリズム概論 - 探索 () - アルゴリズム 問題を解くための曖昧さのない手順 与えられた問題を解くための機械的操作からなる有限の手続き 機械的操作 : 単純な演算, 代入, 比較など 安本慶一 yasumoto[at]is.naist.jp プログラムとの違い プログラムはアルゴリズムをプログラミング言語で表現したもの アルゴリズムは自然言語でも, プログラミング言語でも表現できる
More informationテキストファイルの入出力1
テキストファイルの入出力 1 0. 今回の目的前回までは 2 回にわたって繰り返しについて学んできました 今回からテキストファイルの入出力について学ぶことにします 1. テキストファイルへの出力 1.1 テキストファイルについてテキストファイルとは コンピュータで扱うことが出来るファイルの中で最も基本的なファイルであり どの様な OS でもサポートされているファイル形式です Windows においては
More informationメソッドのまとめ
配列 (2) 2 次元配列, String http://jv2005.cis.k.hosei.c.jp/ 授業の前に自己点検 配列変数に格納される配列の ID と配列の実体の区別ができていますか 配列変数の宣言と配列の実体の生成の区別ができていますか メソッドの引数に配列が渡されるとき 実際に渡されるものは何ですか このことの重要な帰結は何ですか 引数の値渡しと参照渡しということばを例を挙げて説明できますか
More information