シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/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 |
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)：二項係数と二項定理 第２回 数え上げの基礎 (2)：漸化式の立て方 第３回 数え上げの基礎 (3)：漸化式の解き方 (基礎) 第４回 数え上げの基礎 (4)：漸化式の解き方 (発展) 第５回 離散代数 (1)：行列式とパーマネント 第６回 離散代数 (2)：非交差経路の数え上げ 第７回 離散代数 (3)：全域木の数え上げ 第８回 前半のまとめ 第９回 離散確率論 (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公式，コーシー・ビネの公式，行列木定理，確率，期待値，マルコフの不等式，チェルノフ限界，乱択アルゴリズム，マルコフ連鎖，推移確率，定常分布，ランダムウォーク |