シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
計算機構特論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Topics on Theory of Computation | ||
| 科目番号 /Code |
|||
| 開講年度 /Academic year |
2021年度 | 開講年次 /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 update |
2021/03/22 09:48:48 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
主題：離散アルゴリズムについて、基礎技術だけでなく最先端の知識を得る。 達成目標：定数時間アルゴリズムを中心とし、各回の講義で説明した定義と技法を理解する。 Theme: Learning on discrete algorithms, not only the basis but also the cutting-edge knowledges Target: Understanding the definitions and techniques on constant-time algorithms and the area explained in each lecture. |
|---|---|
| 前もって履修 しておくべき科目（1,000文字以内） /Prerequisites（up to 1,000 letters） |
離散数学 Discrete mathematics |
| 前もって履修しておくこ とが望ましい科目（1,000文字以内） /Recommended prerequisites and preparation（up to 1,000 letters） |
離散数学、離散アルゴリズム関係の講義 Lectures on discrete mathematics and discrete algorithms |
| 教科書等（1,000文字以内） /Course textbooks and materials（up to 1,000 letters） |
伊藤大雄「データ構造とアルゴリズム」コロナ社，２０１７． |
| 授業内容と その進め方（2,000文字以内） /Course outline and weekly schedule（up to 2,000 letters） |
第１回：定数時間アルゴリズムとは何か：考え方 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. Cuckoo hush 第１４回：四色問題 14. Four-color problem 第１５回：グラフマイナー 15. Graph minor |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等）（1,000文字以内） /Preparation and review outside class（up to 1,000 letters） |
教科書を購入して予習・復習をすること。 Buy the textbook. Prepare and review. |
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
期末のレポートで評価する。出席状況と講義中の発言も考慮する。評価基準：授業で取り上げる基本的概念について理解できていることが合格の最低基準である。 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. |
| オフィスアワー： 授業相談（1,000文字以内） /Office hours（up to 1,000 letters） |
講義終了後に質問に来る（対面講義の場合）かまたはメールで質問すること。 Come just after the class (in case of a face-to-face lecture) or send e-mail. |
| 学生へのメッセージ（1,000文字以内） /Message for students（up to 1,000 letters） |
特に無し None |
| その他 /Others |
特に無し None |
| キーワード /Keywords |
離散アルゴリズム、離散数学、グラフ理論 discrete algorithms, discrete mathematics, graph theory |