Ver.2 再掲:講義資料の所在 (URL) 後にレポートを回収した時に、提出者の学籍番号を、ここに掲載する予定です。

Slides:



Advertisements
Similar presentations
1 線形代数学. 2 履修にあたって 電子情報システム学科 必修 2005 年度1セメスタ開講 担当 草苅良至 (電子情報システム学科) 教官室: G I 511 内線: 2095 質問等は上記のいずれかに行なうこと。 注意計算用のノートを準備すること。
Advertisements

朝日大学大学院 経営学研究科 奥山 徹 データベース論 朝日大学大学院 経営学研究科 奥山 徹 2006/04/17 データベース論(1回目)
0章 数学基礎.
Probabilistic Method 7.7
初年次セミナー 第8回 データの入力.
離散数学入門 (集合論、ベン図) 情報システム学科 中田豊久.
情報・知能工学系 山本一公 プログラミング演習Ⅱ 第4回 配列(2) 情報・知能工学系 山本一公
コンパイラ 2011年10月17日
プログラミング言語としてのR 情報知能学科 白井 英俊.
情報科学概論I 【第5週】単位区間上のカオスとフラクタル ~実数の不思議~ 徳永隆治 (情報学類).
ファーストイヤー・セミナーⅡ 第8回 データの入力.
プログラミング演習Ⅱ 第12回 文字列とポインタ(1)
5.チューリングマシンと計算.
5.チューリングマシンと計算.
Extremal Combinatorics 14.1 ~ 14.2
計算の理論 I ー DFAとNFAの等価性 ー 月曜3校時 大月 美佳.
プログラミング演習(2組) 第12回
計算の理論 I -数学的概念と記法- 月曜3校時 大月 美佳.
論理式の表現を数学的に取り扱いやすくするために代数学の助けを借りる.
条件式 (Conditional Expressions)
情報教育論 第9回 仮定文の仕組み 政策・メディア研究科 岡田 健.
数理論理学 第1回 茨城大学工学部情報工学科 佐々木 稔.
Probabilistic Method 6-3,4
計算の理論 I -講義について+αー 月曜3校時 大月美佳.
A path to combinatorics 第6章前半(最初-Ex6.5)
Probabilistic method 輪講 第7回
コンパイラ 2012年10月15日
8.Intersecting Families
コンパイラ 2012年10月22日
Ver.2 再掲:講義資料の所在 (URL) 下のURLは「情報数学」シラバスの「履修上の注意」に掲載されています。
コンパイラ 2011年10月24日
寄せられた質問: 演習問題について この講義の範囲に含まれる適切な演習問題が載っている参考書がありますか? できれば解答や解説が付いているものがあると良いのですが… 第3回の授業の中で、演習問題に取り組む方法を説明します.
Googleのページランク 基本的な仕組は数学的 グラフの行列による表現 隣接行列(推移行列、遷移行列) 固有値と固有ベクトル W大学
計算の理論 I -Myhill-Nerodeの定理 と最小化-
Basic Tools B4  八田 直樹.
1. 集合 五島 正裕.
関係 (relation) 集合Aの要素aとBの要素bとが、ある条件Rを満たすとき「Rの関係にある」といい、aRb と書く。
補遺:質問への解答(1) 順序対と非順序対(1回目の授業)
非線形システム特論 (平成20年度版) 徳永隆治 筑波大学 システム情報工学研究科 CS専攻.
レポート提出者のリスト 次のURLに掲載 ~goto/infomath.html 学内のIPアドレスからのみ閲覧 ( )
計算の理論 I -Myhill-Nerodeの定理 と最小化-
レポート提出者のリスト 次のURLに掲載 ~goto/infomath.html 学内のIPアドレスからのみ閲覧 ( )
9.通信路符号化手法1 (誤り検出と誤り訂正の原理)
知能情報システム特論 Introduction
2007年 4 月~7 月( 合計12回予定) 講義資料: 上田 和紀 原著 後藤 滋樹 三訂
SUNFLOWER B4 岡田翔太.
2007年度 情報数理学.
A path to combinatorics 第3章後半(Ex3.8-最後)
プログラミング言語論 第9回 情報工学科 木村昌臣 篠埜 功.
計算の理論 I ー閉包性ー 月曜3校時 大月 美佳.
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
2007/6/12(通信コース)2007/6/13(情報コース) 住井
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
計算の理論 I 反復補題 月曜3校時 大月 美佳 平成15年7月14日 佐賀大学知能情報システム学科.
計算の理論 I -数学的概念と記法- 火曜 12:50~14:20 大月 美佳 2004年4月20日.
5.チューリングマシンと計算.
コレクション・フレームワーク データベース論 第7回.
プログラミング言語論 第10回 情報工学科 篠埜 功.
~sumii/class/proenb2010/ml2/
計算の理論 I -数学的概念と記法- 月曜3校時 大月 美佳.
矛盾した知識 デフォルト推論 仮説を用いた推論 準無矛盾推論 デフォルト規則 デフォルト理論の拡張 → デフォルト証明 シナリオ
2006/6/27(通信コース)2006/7/5(情報コース) 住井
4.プッシュダウンオートマトンと 文脈自由文法の等価性
~sumii/class/proenb2009/ml6/
計算の理論 I 反復補題 火曜3校時 大月 美佳 平成16年7月13日 佐賀大学知能情報システム学科.
PROGRAMMING IN HASKELL
プログラミング基礎a 第5回 C言語によるプログラミング入門 配列と文字列
第4回 配列.
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
Presentation transcript:

http://www.goto.info.waseda.ac.jp/ ~goto/infomath.html Ver.2 再掲:講義資料の所在 (URL) 後にレポートを回収した時に、提出者の学籍番号を、ここに掲載する予定です。 後藤研のWEBページ(日本語)の「後藤先生担当の講義」から辿ることもできます。 http://www.goto.info.waseda.ac.jp/ ~goto/infomath.html ここに ~ が必要

数学は、その場で考えれば解るのか? 解りません 基本的な記号の意味を覚える必要がある 数学は記号の羅列 記号の辞典がある 使うことにより、学習できる 普通に考えると解らないような箇所を出題 基本的な考え方を身に付けておく

参考書(金曜日・後藤担当分) 講義資料の多くの部分を作成した上田先生の参考文献 (1) J. マトウシェク, J. ネシェトリル著 根上生也, 中本敦浩訳「離散数学への招待 上」      シュプリンガー・フェアラーク東京 ISBN 4-431-70896-0 (2)M.A.アービブ, A.J.クフォーリ, R.N.モル 著 甘利俊一, 金谷健一, 嶋田晋 訳 「計算機科学入門」 (Information & Computing 1)      サイエンス社 ISBN4-7819-0375-4 後藤が教材を追加した際に参照した文献 (3)守屋悦朗「コンピュータサイエンスのための離散数学」      (Information & Computing 61)      サイエンス社 ISBN 4-07819-0643-5 (4)小野 寛晰「情報代数」情報数学講座 第2巻     共立出版 ISBN 4-320-02652-7 

演習問題の解答はスライドに掲載せず 例外として次を解説「ラッセルのパラドックス」 集合Xを次のような「もの」の集まりとする Xの要素は「自分自身を要素として含まない集合」である [説明]Xは集合である。XはX自身を含むか、含まないか、いずれかである。もし   とすると       となる。すなわちXはXを含むから定義によりXはXの要素ではありえない。これは矛盾。一方   とすると、XがX自身を含まないのであるから、定義によりXはXの要素となる筈である。これは矛盾。

写像 (map) または関数 (function) AとBを集合とする f がAからBへの写像 (map) または関数 (function) であるとは fがAの各要素に対して、Bのただ一つの要素を対応させる規則であること [例題]実数xにxの実数平方根を対応させる規則 上の対応規則は関数(写像)ではない。

関数と関数空間 集合Bの要素の中でfの像になっている要素の集合 をfの値域 (range) という。 を と書くことがある。説明は後述。 A の要素にB の一つの 要素を対応づける規則 f A から B への 写像(関数)全体の集合 集合Bの要素の中でfの像になっている要素の集合          をfの値域 (range) という。     を  と書くことがある。説明は後述。 定義域(始集合) domain 終集合 codomain (値域と区別)

関数のグラフ A B 関数の内包的定義: 外延的定義: これを関数のグラフという グラフは直積AXB の部分集合である       のグラフとは グラフは直積AXB の部分集合である グラフが同じ関数は等しい(外延的な等しさ) A B

単射と全射 写像 (関数) が任意の に対して、 という性質を満たす時に単射という。1対1写像ともいう。 上の性質は とも書ける。 論理記号 ならば implies 写像 (関数)      が任意の     に対して、           という性質を満たす時に単射という。1対1写像ともいう。 上の性質は           とも書ける。 写像 (関数)      が、任意の   に対して     なる    が存在する時に全射という。上への写像ともいう 全射かつ単射である写像を全単射という。 [例]     を     と定めると、全単射となる

関数と部分関数 論理記号 同値 条件②が成り立たない場合は部分関数(部分写像)

多変数の関数(多引数の関数) 2 引数関数 の考え方 直積の上の1 引数関数 と同一視 2 引数関数 の考え方 直積の上の1 引数関数 と同一視 x だけ指定すると y に関する 1 引数関数になる.つまり を満たすような関数 (= x を与えると「y に関する1引数関数」を返す関数)を考えることができる (currying) と  は対等 2次元配列 は1次元配列の配列 (プログラム) 0 引数関数 というのは定数のことである 数学ではあまり見ないがプログラムで使う

配列と関数 プログラムでは区別がある。 数学的には同一視できる。 n 要素の一次元配列: を 定義域 (domain) とし、   を終集合とする関数 上の二つは対等(同一視可能). 集合論では自然数を         と定義 上の見方は  という表記と合致する

部分集合と特性関数 (または )と とは同じ意味 集合 A の部分集合を一つ与えることは に属する関数を一つ決めることと同じ (または )と とは同じ意味 集合 A の部分集合を一つ与えることは に属する関数を一つ決めることと同じ つまり と とは対等 部分集合 S に対応する関数のことを S の特性関数 (characteristic function) という black magenta red 1 blue 1 cyan yellow 1 green white

集合族 (family of sets) プログラミングでは配列が便利である。 集合に添字をつけることがある。 と書く。 集合族は,実は添字 i を集合  に写像する関数に他ならない。

集合の 関数 とするとき、 引数の値に応じて,返す値の型が決まる関数 例: n を与えると配列      が返る 和集合

集合の 直和の個数を一般化したもの 例:Aがアルファベットの集合 有限長の文字列全体の集合は 例:Aがアルファベットの集合  有限長の文字列全体の集合は 演習:I  {0,1} , A0 { 2, 3, 4 }, A1={ 3, 5 } の場合に 上の定義による   の要素を具体的に記せ。 直和

cardinal number, cardinality 無限集合 無限集合の例: 集合Aの要素の数 |A| を基数、濃度という。 上の例では、要素の数は無限。 ただし、すべての要素にもれなく通し番号をつけることができる。 ここで、無限の要素に必ず通し番号がつけられるかどうかは自明でない。(後述) cardinal number, cardinality potency, power

有限集合と無限集合の要素の数に注目 有限集合 無限集合 Z と R

可算無限集合 「集合 S の全要素に通し番号がつけられる」 ⇔ 「S と 自然数の集合N とが対等」( ) N と対等な集合のことを可算無限集合または可算集合 (enumerable set, denumerable set, countable set) という。 や  は 可算無限集合である 例題:自然数の集合Nから0を除いた集合 Nー{0} とNとの間には    という全単射が存在する。よって       である。

集合の濃度 A や B が有限集合のとき, A と B とが対等であるための必要十分条件は である。 が全射ならば 単射ならば     が全射ならば    単射ならば 無限集合のときも,   のとき,そしてそのときに限って    と書く。  ,つまり一般化された個数のことを A の濃度 (cardinarity) という。 数学者は  のことをしばしば  と書く 例:          アレフ・ゼロ 無限集合では、自分自身の真部分集合と対等になる場合がある。例:

可算(無限)集合の例 素数全体の集合 一般に可算集合の無限部分集合は可算集合 自然数格子点の集合 有理数全体の集合 有限長の数列全体の集合 整数Z

自然数 N と整数 Z 全単射 0 1 2 3 4 5 6 7 8 9 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9

可算でない無限集合 対角線論法 実数全体の集合 R は可算集合ではない [証明の概略]R’ を 0 および正の実数の集合とする。N⊂R’⊂Rである。|N| ≦ |R’| ≦ |R| である。 NからR’への全単射 f が存在すると仮定する。 有限小数は 0 を付ける fは全射であるからr=f(s)となる自然数sが存在する筈。そのdssに注目する。

可算でない無限集合 [続]r=f(s)となるsが存在する。ところでf(s)の小数点以下第(s+1)桁目は定義によりdssである。一方で、rの小数点以下第(s+1)桁目は定義によりdssであり、この二つは一致しない。 Nの部分集合全体の集合  は可算集合でない 任意の集合Aに対して 自然数上の関数全体の集合  は可算集合でない ~

再履修の諸君に重要な連絡 再履修の諸君に大切な連絡があります できるだけ迅速に上田和紀先生にメールで連絡をすること メールアドレスが不明の場合には、学科事務所で尋ねるか、クラス担任の先生に質問する