シラバス参照

講義概要/Course Information
2020/04/28 現在

科目基礎情報/General Information
授業科目名
/Course title (Japanese)
離散数理工学
英文授業科目名
/Course title (English)
Discrete Mathematical Engineering
科目番号
/Code
INS602c INS602d
開講年度
/Academic year
2020年度 開講年次
/Year offered
3
開講学期
/Semester(s) offered
後学期 開講コース・課程
/Faculty offering the course
情報理工学域
授業の方法
/Teaching method
講義 単位数
/Credits
2
科目区分
/Category
専門科目
開講学科・専攻
/Cluster/Department
Ⅰ類
担当教員名
/Lecturer(s)
岡本 吉央
居室
/Office
西4-206
公開E-Mail
/e-mail
okamotoy の後に @uec.ac.jp
授業関連Webページ
/Course website
http://dopal.cs.uec.ac.jp/okamotoy/lect/2020/dme/
更新日
/Last updated
2020/03/06 16:17:51 更新状況
/Update status
公開中
/now open to public
講義情報/Course Description
主題および
達成目標
/Topic and goals
主題:数え上げ組合せ論,代数系,離散確率論を道具として,離散システムの設計と解析,離散アルゴリズムの設計と解析に関する方法論を学習する.
キャッチフレーズは「離散数学を使う」.

達成目標:以下の3項目をすべて達成することを目標とする
(1) 数え上げ組合せ論,代数系,離散確率論における用語を正しく使うことができる.
(2) 数え上げ組合せ論,代数系,離散確率論における典型的な論法を用いて,証明を行うことができる.
(3) 数え上げ組合せ論,代数系,離散確率論を用いて,離散システムや離散アルゴリズムの設計と解析ができる.
前もって履修
しておくべき科目
/Prerequisites
離散数学,プログラミング通論,線形代数学第一,アルゴリズム論第一,確率論
前もって履修しておくこ
とが望ましい科目
/Recommended prerequisites and preparation
線形代数学第二,アルゴリズム論第二,統計学,オペレーションズ・リサーチ基礎,グラフとネットワーク
教科書等
/Course textbooks and materials
教科書:指定しない.講義資料を毎回用意するので,講義webページより各自入手すること.

参考書:
J. マトウシェク,J. ネシェトリル (著),根上生也,中本敦浩 (訳),「離散数学への招待 (上・下)」,丸善出版,2002.
浅野孝夫,「情報数学」,コロナ社,2009.
小島定吉,「離散構造」,朝倉書店,2013.
イジィ・マトウシェク (徳重典英訳),「33の素敵な数学小景」,日本評論社,2014.
高崎金久,「線形代数と数え上げ」,日本評論社,2012.
玉木久夫,「情報科学のための確率入門」,サイエンス社,2002.
伏見正則,「確率と確率過程」,朝倉書店,2004.
授業内容と
その進め方
/Course outline and weekly schedule
(a)授業内容
第1回 数え上げの基礎 (1):二項係数と二項定理
第2回 数え上げの基礎 (2):漸化式の立て方
第3回 数え上げの基礎 (3):漸化式の解き方 (基礎)
第4回 数え上げの基礎 (4):漸化式の解き方 (発展)
第5回 離散代数 (1):行列式とパーマネント
第6回 離散代数 (2):非交差経路の数え上げ
第7回  離散代数 (3):全域木の数え上げ
第8回 前半のまとめ
第9回 離散確率論 (1):確率的離散システムの解析 (基礎)
第10回 離散確率論 (2):確率的離散システムの解析 (発展)
第11回 離散確率論 (3):乱択データ構造とアルゴリズム (基礎)
第12回 離散確率論 (4):乱択データ構造とアルゴリズム (発展)
第13回 離散確率論 (5):マルコフ連鎖 (基礎)
第14回 離散確率論 (6):マルコフ連鎖 (発展)
第15回 後半のまとめ

(b)授業の進め方
はじめの75分に講義を行い,最後の15分で演習を行う.
実務経験を活かした
授業内容
(実務経験内容も含む)
/Course content utilizing practical experience
授業時間外の学習
(予習・復習等)
/Preparation and review outside class
[予習] 後半「離散確率論」においては,講義『確率論』の内容を用いる.そのため,受講者はその部分の復習,あるいはそれに相当する学習を前もって行っておく必要がある.その内容を講義中に補足せよという要求には応えられない.

[復習] 演習問題を解き,レポートとして提出することを推奨する.(なお,レポートは成績評価に勘案されない.)
成績評価方法
および評価基準
(最低達成基準を含む)
/Evaluation and grading
評価方法:中間試験と期末試験による.試験日程は講義中に連絡する.
評価基準:以下の到達レベルをもって合格の最低基準とする.
(1) 数え上げ組合せ論,代数系,離散確率論における用語を正しく使うことができる.
(2) 数え上げ組合せ論,代数系,離散確率論における典型的な論法を用いて,証明を行うことができる.
(3) 数え上げ組合せ論,代数系,離散確率論を用いて,離散システムや離散アルゴリズムの設計と解析ができる.
ただし,用語を暗記する必要はない.
オフィスアワー:
授業相談
/Office hours
アポイントメントによる.
学生へのメッセージ
/Message for students
この講義のテーマは「離散数学を使う」ということにある.
そのために,まず「数える」という人間生活において欠かすことができない行為を見直す.
いままでにも慣れ親しんできたその行為に関して,この講義を通してより深い視点を身につけてもらいたい.そして,「代数」と「確率」を離散数学の立場から学び,使えるようになってもらいたい.
その他
/Others
特になし.
キーワード
/Keyword(s)
組合せ論,数え上げ,漸化式,母関数,行列式,パーマネント,非交差経路,LGV公式,コーシー・ビネの公式,行列木定理,確率,期待値,マルコフの不等式,チェルノフ限界,乱択アルゴリズム,マルコフ連鎖,推移確率,定常分布,ランダムウォーク