データ構造と アルゴリズム 知能情報学部 新田直也.

Slides:



Advertisements
Similar presentations
コンピュータ概論 B ー ソフトウェアを中心に ー #13 アルゴリズム・計算可能性 京都産業大学 安田豊.
Advertisements

オブジェクト指向 言語 論 知能情報学部 新田直也. 講義概要  私の研究室: 13 号館 2 階 (13-206)  講義資料について :  参考図書 : 河西朝雄 : 「原理がわかる プログラムの法則」,
データ構造とアルゴリズム 平成20年度 前期 2年生必修  水曜日 3-4時限.
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
黒澤 馨 (茨城大学) 情報セキュリティ特論(4) 黒澤 馨 (茨城大学) 2017/3/4 confidential.
チューリングマシン 2011/6/6.
Q q 情報セキュリティ 第6回:2005年5月20日(金) q q.
データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也.
オブジェクト指向言語論 知能情報学部 新田直也.
5.チューリングマシンと計算.
5.チューリングマシンと計算.
計算の理論 I ー DFAとNFAの等価性 ー 月曜3校時 大月 美佳.
授業展開#11 コンピュータは 何ができるか、できないか.
1. アルゴリズムと計算量.
プログラミング言語論 第1回 導入 情報工学科 篠埜 功.
プログラミング言語論 理工学部 情報システム工学科 新田直也.
情報工学通論 プログラミング言語について 2015年 6月 16日 情報工学科 篠埜 功.
データ構造と アルゴリズム 第二回 知能情報学部 新田直也.
情報科学1(G1) 2016年度.
Semantics with Applications
動的ハフマン符号化の例 入力:ABCDEからなる文字列 出力:動的に作ったハフマン木.
計算の理論 I -講義について+αー 月曜3校時 大月美佳.
オブジェクト指向 プログラミング 第一回 知能情報学部 新田直也.
プログラミング言語論 第1回 導入 情報工学科 篠埜 功.
データ構造と アルゴリズム 第十一回 理工学部 情報システム工学科 新田直也.
7.時間限定チューリングマシンと   クラスP.
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
チューリング機械 状態の有限集合 ヘッドの方向を表す。 L:1コマ左へ R:1コマ右へ テープ記号の有限集合 入力記号の有限集合 動作関数
アルゴリズムとチューリングマシン 「もの」(商品)としてのコンピュータ 「こと」(思想)としてのコンピュータ アルゴリズム
形式言語の理論 5. 文脈依存言語.
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 II Turing機械の合成 月曜5校時 大月美佳 2004/11/15 佐賀大学理工学部知能情報システム学科.
オートマトンとチューリング機械.
5.RSA暗号 素因数分解の困難性を利用した暗号.
アドバンスドトピック 計算できるものと計算できないもの 2008年4月9日 神林 靖.
計算の理論 II 時間量と領域量 月曜5校時 大月美佳 2019/4/10 佐賀大学理工学部知能情報システム学科.
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
計算の理論 I ε-動作を含むNFA 月曜3校時 大月 美佳.
知能情報システム特論 Introduction
チューリングマシン 0n1nを受理するチューリングマシン 入力テープ b b b b 状態遷移機械.
形式言語とオートマトン 中間試験解答例 2016年11月15実施 中島毅.
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
第6章-2 計算のモデル オートマトン Turing 機械 計算可能性 1.
補講:アルゴリズムと漸近的評価.
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
計算の理論 I -数学的概念と記法- 火曜 12:50~14:20 大月 美佳 2004年4月20日.
情報基礎Ⅱ (第1回) 月曜4限 担当:北川 晃.
5.チューリングマシンと計算.
計算の理論 I -プッシュダウンオートマトン-
人工知能特論II 第8回 二宮 崇.
計算の理論 I プッシュダウンオートマトン 火曜3校時 大月 美佳 平成16年7月6日 佐賀大学知能情報システム学科.
コンピュータアーキテクチャ 第 5 回.
計算機プログラミングI 第4回 2002年10月31日(木) 問題解決とアルゴリズム クラスメソッドと手続きの抽象化 最大公約数
計算の理論 I -数学的概念と記法- 月曜3校時 大月 美佳.
計算の理論 I -講義について+αー 月曜3校時 大月美佳 平成31年5月18日 佐賀大学理工学部知能情報システム学科.
アルゴリズムとデータ構造 --- 理論編 --- 山本 真基
4.プッシュダウンオートマトンと 文脈自由文法の等価性
コンピュータアーキテクチャ 第 5 回.
計算の理論 I NFAとDFAの等価性 火曜3校時 大月 美佳 平成16年5月18日 佐賀大学理工学部知能情報システム学科.
オブジェクト指向言語論 第二回 知能情報学部 新田直也.
コンパイラ 2012年10月11日
Q q 情報セキュリティ 第8回:2004年5月28日(金) の補足 q q.
オブジェクト指向言語論 第一回 知能情報学部 新田直也.
情報数理Ⅱ 第10章 オートマトン 平成28年12月21日.
計算の理論 I -講義について+αー 火曜3校時 大月美佳 平成31年8月23日 佐賀大学理工学部知能情報システム学科.
計算の理論 I ー ε-動作を含むNFA ー 月曜3校時 大月 美佳.
オブジェクト指向言語論 第三回 知能情報学部 新田直也.
計算の理論 I プッシュダウンオートマトン 月曜3校時 大月 美佳 平成15年7月7日 佐賀大学知能情報システム学科.
計算の理論 II 多テープTuring機械 月曜4校時 大月美佳 平成16年11月29日 佐賀大学知能情報システム学科.
情報処理Ⅱ 第8回:2003年12月9日(火).
Presentation transcript:

データ構造と アルゴリズム 知能情報学部 新田直也

講義概要 私の研究室: 13号館2階(13-206) 講義資料について: http://silverbullet.is.konan-u.ac.jp/lectures/ 教科書: 近藤嘉雪:「Cプログラマのためのアルゴリズムとデータ構造」, ソフトバンクパブリッシング 成績評価: 主に試験(1回),演習(2回)で評価

講義計画 第1回 アルゴリズムとは 第2回 アルゴリズムと計算量 第3回 基本データ構造 第4回 連結リストとその操作(1) 第5回 連結リストとその操作(2) 第6回 演習 第7回 二分木とその操作(1) 第8回 二分木とその操作(2) 第9回 二分木とその操作(3) 第10回 演習 第11回 線形探索 第12回 二分探索 第13回 二分探索木(1) 第14回 二分探索木(2) 第15回 試験

アルゴリズムとは? 直感的には,与えられた問題を解くための処理手順のこと. プログラミング言語に依存しない. (コンピュータができる前からアルゴリズムの概念はあった.) 同一の問題に対して複数の解法が存在しうる. →優れた解法,劣った解法? 解法1 問題A 解法2 解法3

最大公約数を求めるアルゴリズム 問題: 与えられた2自然数 a, b の最大公約数を求めよ. 解法1: 総当り計算 c := min{a, b} とおく. c が a, b を共に割り切る場合, c を出力して停止. c := c – 1 とおき,2) へ. 解法2: ユークリッドの互除法 c := max{a, b}, d := min{a, b} とおく. c を d で割った余りを r とおく. r が 0 ならば,d を出力して停止. c := d, d := r とおき,2) へ.

計算の例 12と9の最大公約数を求めよ. [総当り計算] [ユークリッドの互除法] c := 9 割り切らない c := 8 2) 割り切らない 3) c : = 7 3) c : = 6 3) c : = 5 3) c : = 4 3) c : = 3 2) 割り切るので 3 を出力 [ユークリッドの互除法] c := 12, d:= 9 r := 3 r は 0 でない 4) c := 9, d := 3 2) r := 0 3) r が 0 なので 3 を出力 入力(a, b)の値が大きくなればなるほど, ユークリッドの互除法の方が総当り計算より 短いステップで答えを出す傾向が強くなる. →時間計算量の議論は次週に

アルゴリズムと数学 数学の問題を解く手続きは,アルゴリズムである. 割り算: 鶴亀算: 与えられた2整数 a, b について, ax = b を満たす x を求めよ. 解法: 割り算の筆算 鶴亀算: 与えられた2整数 a, b について, 2x + 4y = a, x + y = b を満たす x, y を求めよ. 解法: x := (4b – a) / 2 を計算,y := b – x とする.

アルゴリズムの数学的定義 数学的にアルゴリズムとは? チューリングマシン チャーチの提唱(1936年) 「チューリング計算可能関数,一般帰納的関数,λ定義可能関数のクラスはすべて一致する.チューリングマシンで記述可能な手続きをアルゴリズムと呼ぼう.」 チューリングマシン アラン・チューリング(1936年) 「計算」を数学的にモデル化したマシン. 現在のコンピュータも理論的にはチューリングマシン. チューリング賞はコンピュータ科学における最高権威. 暗号機械エニグマの解読に成功

チューリングマシン 有限状態制御部,半無限長のテープ,テープヘッドからなる機械で,その動作は遷移関数によって定義される. テープは加算無限個のセルの列で構成され,各セルには有限種類のテープ記号 (空白記号を含む)のうちのいずれか1つが記憶される. b d a a c b a c … テープヘッドは常にテープ上の1つのセルを指し, 1回の動作でセル1つ分右または左に移動する. 各動作によってテープヘッドの先のセルの内容が 読み書きされる. α 有限状態制御部には有限種類の状態記号のうちのいずれか1つが記憶され, 動作の度に読み書きされる.状態記号のうちのいくつかは終了状態を表し, 終了状態になったときマシンは yes を出力し終了.

チューリングマシンの動作 遷移関数δは各マシン毎に定義される. δ(α, a) = (β, c, L) であった場合: b d a a c … β α

チューリングマシンの例 チューリングマシンによる引き算 テープ記号: {1, -, =} 状態記号: {q0, q1, q2, q3} 遷移関数: 終了状態 遷移前のテープ記号 1 - = q0 (q0,1,R) (q1,-,R) (q3, ,L) (q0, ,R) q1 (q2, ,L) (q1, ,R) q2 (q2,-,L) 遷移前の状態記号 5 2 1 1 1 1 1 - 1 1 = … q0 q0 q1 q2 q3

チューリングマシンの能力 本質的に,チューリングマシンによってあらゆる算術計算を表現することができる(計算万能). チューリングマシン以外にも一般帰納関数,λ計算などの計算機構が考えられたが,いずれもチューリングマシンと表現能力が等しいことが証明された. 今のところチューリングマシンの能力を超える計算機構は見つかっていない. →チューリングマシンを計算手続き(アルゴリズム) の定義とみなそう!!(チャーチの提唱)

チューリングマシンの限界 有限時間内で解くアルゴリズム(チューリングマシン)が存在しない問題が存在する. 言い換えれば,その問題を解こうとすると無限時間かかってしまうような問題. 決定不能命題と呼ばれる. ゲーデルの不完全性定理の別表現. 情報科学分野には決定不能命題がたくさんある. 与えられたチューリングマシンが与えられた入力に対していずれ停止するか否か?(停止性判定問題) 与えられたプログラムが無限ループに入らないか否か? 与えられた2つのチューリングマシンが等価であるか否か? 解けないと証明されている問題に取り組んでも意味がない.

結局アルゴリズムとは? 理論的にはチューリングマシンで定義されるが,等価な計算機構なら何でもよい. チューリングマシンと等価な計算機構: λ計算 一般帰納関数 DNA計算機 量子計算機 ランダムアクセス機械 プログラミング言語(ただしメモリは無尽蔵) :