情報科学部Faculty of Computer and Information Sciences
PRI310KA-CS-261(情報学基礎 / Principles of informatics 300)アルゴリズムの設計と解析Design and Analysis of Algorithm
黄 潤和Huang RUNHE
授業コードなどClass code etc
学部・研究科Faculty/Graduate school | 情報科学部Faculty of Computer and Information Sciences |
添付ファイル名Attached documents | |
年度Year | 2022 |
授業コードClass code | J0441 |
旧授業コードPrevious Class code | |
旧科目名Previous Class title | |
開講時期Term | 春学期授業/Spring |
曜日・時限Day/Period | 水4/Wed.4 |
科目種別Class Type | |
キャンパスCampus | 小金井 / Koganei |
教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
配当年次Grade | |
単位数Credit(s) | 2 |
備考(履修条件等)Notes | |
他学部公開科目Open Program | |
他学部公開(履修条件等)Open Program (Notes) | |
グローバル・オープン科目Global Open Program | |
成績優秀者の他学部科目履修制度対象Interdepartmental class taking system for Academic Achievers | ○ |
成績優秀者の他学部科目履修(履修条件等)Interdepartmental class taking system for Academic Achievers (Notes) |
(1) 受講希望者 (受講検討中の者も含む) は、情報科学部学部Googleフォーム(https://forms.gle/ECvwxVe2NcxmrbTK9)で初回講義前までに希望申請をしてください。(※以下URLのご案内があるGoogleフォームとは異なるのでご注意ください。) (2) 以下のURLと教育開発支援機構事務局の案内に従って、履修希望の申請を行ってください。 https://www.hoseikyoiku.jp/risyu/index.html (3) 履修取消については、ご自身の所属学部の履修取消期間内に必ず同時に履修削除を行ってください。 |
実務経験のある教員による授業科目Class taught by instructors with practical experience | |
SDGsCPSDGs CP | |
アーバンデザインCPUrban Design CP | |
ダイバーシティCPDiversity CP | |
未来教室CPLearning for the Future CP | |
カーボンニュートラルCPCarbon Neutral CP | |
千代田コンソ単位互換提供(他大学向け)Chiyoda Campus Consortium | |
選択・必修Optional/Compulsory | |
カテゴリー(2022年度以降入学者)Category (2022~) | |
カテゴリー(2021年度以前入学者)Category (~2021) | |
カテゴリーCategory |
専門教育科目 専門科目 |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
The goal of this course is to enhance students' knowledge of data strcture and skill of applying associated algorithms. This course will cover the content review of learned data structures and algorithms related tree and graph, and plus algorithm analysis and design techniques.
授業で使用する言語Default language used in class
日本語・英語併用 / Japanese & English
授業の概要と目的(何を学ぶか)Outline and objectives
The goal of this course is to enhance students' knowledge of data strcture and skills of applying associated algorithms. This course will cover the content review of learned data structures and algorithms related tree and graph, and plus algorithm analysis and design techniques.
到達目標Goal
The objectives of this course are to make students firmly laying good foundation of data structures and algorithms, and one-step further comprehensively understanding of algorithm analysis, and having design skills and techniques as general problem solving strategies.
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか(該当授業科目と学位授与方針に明示された学習成果との関連)Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち「DP2」と「DP4-1」に関連
授業で使用する言語Default language used in class
日本語・英語併用 / Japanese & English
授業の進め方と方法Method(s)(学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. )
- Review data structures and algorithms learned previously
- Introduce some contents on algorithm analysis techniques
- Learn some design techniques for problem solving
[Feedback] Students are given questions to think about and answer in-class and exercises to do as home work. Solutions to the questions and the exercises will be explained in the next class, and students will do self-checking and evaluation of their exercises and make corrections or re-do to the exercises they make mistakes.
アクティブラーニング(グループディスカッション、ディベート等)の実施Active learning in class (Group discussion, Debate.etc.)
あり / Yes
フィールドワーク(学外での実習等)の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching:対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
1[未定/undecided]:Fundamentals of the Analysis of Efficiency
- what is an algorithm?
- how to design?
- how to analyze?
2[未定/undecided]:Basic algorithm analyses (1): Divide and Conquer
- Merge sort
- quick sort
3[未定/undecided]:Basic algorithm analyses (2): Dynamic Programming
- Fibonacci numbers
- Coin exchange
4[未定/undecided]:Trees structure and analysis (1)
- Binary Trees
- Tree traversal
- Arithmetic expressions
5[未定/undecided]:Trees structure and analysis (2)
- AVL Tree
6[未定/undecided]:Trees structure and analysis (3)
- 2-3-4 Tree
7[未定/undecided]:Trees structure and analysis (4)
- red-black trees
8[未定/undecided]:Mid-term exercises
- Work in class
(1) do exercises
(2) explain solutions
9[未定/undecided]:Fundamentals of Graph
- DFS(Depth-first searching algorithm) and BFS (Breadth-first searching algorithm)
10[未定/undecided]:Weighted Graph
- Shortest path algorithms
11[未定/undecided]:Single source shortest paths
- Dijkstra Algorithm
12[未定/undecided]:Minimal spanning trees
- Prim's algorithm
- Kruskal's algorithm
13[未定/undecided]:All-pairs shortest paths
- Matrix production
- Floyd-warshall algorithm
14[未定/undecided]:Review
- The contents of L1-L13
授業時間外の学習(準備学習・復習・宿題等)Work to be done outside of class (preparation, etc.)
Read related contents and topics from the Internet
本授業の準備・復習時間は、計4時間を標準とします。
テキスト(教科書)Textbooks
"Introduction to
The design and Analysis of Algorithms", Anany Levitin,
Pubisher: Pearson,
ISBN-13: 978-0-13-231681-1
参考書References
書名: Introduction to Algorithms, Third Edition
著者: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
出版社: The MIT Press
出版年: 2009年
成績評価の方法と基準Grading criteria
平常点(14%)、授業内ミニテストで(26%)、授業内期末テストで(60%)
学生の意見等からの気づきChanges following student comments
Interested in students' requirements and put efforts accordingly
その他の重要事項Others
授業中は主に英語を使用し、日本語も一部併用して使用する。