シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
計算機構特論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Topics on Theory of Computation | ||
| 科目番号 /Code |
|||
| 開講年度 /Academic year |
2020年度 | 開講年次 /Year offered |
全学年 |
| 開講学期 /Semester(s) offered |
前学期 | 開講コース・課程 /Faculty offering the course |
博士前期課程、博士後期課程 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 科目区分 /Category |
大学院専門教育科目 - 専門科目Ⅱ | ||
| 開講学科・専攻 /Cluster/Department |
情報・ネットワーク工学専攻 | ||
| 担当教員名 /Lecturer(s) |
伊藤 大雄 | ||
| 居室 /Office |
西9-505 | ||
| 公開E-Mail |
itohiro@uec.ac.jp | ||
| 授業関連Webページ /Course website |
なし | ||
| 更新日 /Last updated |
2020/03/19 20:34:42 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標 /Topic and goals |
離散アルゴリズムについて、基礎技術だけでなく最先端の知識を得る。 Learning on discrete algorithms, not only the basis but also the cutting-edge knowledges |
|---|---|
| 前もって履修 しておくべき科目 /Prerequisites |
離散数学 Discrete mathematics |
| 前もって履修しておくこ とが望ましい科目 /Recommended prerequisites and preparation |
離散数学、離散アルゴリズム関係の講義 Lectures on discrete mathematics and discrete algorithms |
| 教科書等 /Course textbooks and materials |
伊藤大雄「データ構造とアルゴリズム」コロナ社，２０１７． |
| 授業内容と その進め方 /Course outline and weekly schedule |
第１回：定数時間アルゴリズムとは何か：考え方 1. Constant time algorithms: basic concepts 第２回：定数時間アルゴリズムとは何か：諸定義 2. Constant time algorithms: definitions 第３回：密グラフの無三角性検査：定義と基本アルゴリズム 3. The dense graph model: testing triangle-freeness: definitions and the basic algorithm 第４回：密グラフの無三角性検査：正則性補題とは何か 4. The dense graph model: testing triangle-freeness: what is the Regularity Lemma 第５回：密グラフの無三角性検査：正則性補題のアルゴリズム 5. The dense graph model: testing triangle-freeness: an algorithm for the Regularity Lemma 第６回：密グラフの無三角性検査：正則性補題の証明 6. The dense graph model: testing triangle-freeness: the proof of the Regularity Lemma 第７回：密グラフの無三角性検査：定理の証明 7. The dense graph model: testingr triangle-freeness: the proof of the theorem 第８回：密グラフ上のモノトーンな性質の検査：無H性 8. The dense graph model: testing monotone properties: H-freeness 第９回：密グラフ上のモノトーンな性質の検査：定理の証明 9. The dense graph model: testing monotone properties: The proof of the theorem 第１０回：次数制限グラフの無三角性検査 10. The bounded degree graph model: testing triangle-freeness 第１１回：次数制限グラフの辺数の推定 11. The bounded degree graph model: approximating the number of edges 第１２回：次数制限グラフの無閉路性検査 12. The bounded degree graph model: testing cycle-freeness 第１３回：グラフアルゴリズムの基本 13. The basis of graph algorithms 第１４回：グラフマイナー 14. Graph minor 第１５回：グラフ操作とアルゴリズム 15. Graph operations and algorithms |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等） /Preparation and review outside class |
復習をすること。 To review is important |
| 成績評価方法 および評価基準 （最低達成基準を含む） /Evaluation and grading |
期末のレポートで評価する。出席状況と講義中の発言も考慮する。評価基準：授業で取り上げる基本的概念について理解できていることが合格の最低基準である。 Evaluating basically by reports on the term end. Attendance performance and remarks may be also considered. The performance evaluation standard is understanding the basic concepts explained in the lectures. |
| オフィスアワー： 授業相談 /Office hours |
原則として講義終了後に質問に来ること。またはメールで予約すること。 Come just after the lecture or make an appointment by e-mail. |
| 学生へのメッセージ /Message for students |
特に無し None |
| その他 /Others |
本講義は一部英語で行う可能性がある。 A part of this lecture may be given in English. |
| キーワード /Keyword(s) |
離散アルゴリズム、離散数学、グラフ理論 discrete algorithms, discrete mathematics, graph theory |