理工学部Faculty of Science and Engineering
PRI200XE（情報学基礎 / Principles of informatics 200）データ構造とアルゴリズムData structure and algorithm
李 磊Lilei LILEI
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学部Faculty of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2022 |
| 授業コードClass code | H6004 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 春学期授業/Spring |
| 曜日・時限Day/Period | 水3/Wed.3 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 |
| 教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
| 配当年次Grade | |
| 単位数Credit(s) | |
| 備考（履修条件等）Notes | |
| 他学部公開科目Open Program | |
| 他学部公開（履修条件等）Open Program (Notes) | |
| グローバル・オープン科目Global Open Program | |
| 成績優秀者の他学部科目履修制度対象Interdepartmental class taking system for Academic Achievers | |
| 成績優秀者の他学部科目履修（履修条件等）Interdepartmental class taking system for Academic Achievers (Notes) | |
| 実務経験のある教員による授業科目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 | |
| カテゴリー＜理工学部＞Category |
応用情報工学科 学科専門科目 |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
This lecture will include the following topics : (1) Analysis of algorithms, (2) Sorting, (3) Searching, (4) Pattern matching, (5) Graph, (6) P and NP problems. The goal is learning foundation of algorithms and efficient program technology. C or C++ Programming Language is needed for preparation using about 4 hours outside of the class. Grading criteria is based on the score of final exam, 60% or more is needed for pass.
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
授業のテーマは下記の通りである。（１）アルゴリズム解析、（２）ソーティング、（３）探索、（４）パターン照合、（５）グラフ、（６）さらに学ぶために。
到達目標Goal
授業の到達目標として、アルゴリズムの基礎を学び，効率の良いプログラム作成技術を習得することを目標とする。
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち、「DP1」と「DP2」と「DP4」に関連
授業で使用する言語Default language used in class
日本語 / Japanese
授業の進め方と方法Method(s)（学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. ）
アルゴリズムの基本概念、C疑似言語によるアルゴリズムの表現を用いて、基本的なアルゴリズムの設計方法及び計算量解析を行う。問題解決へのアルゴリズムによるチャレンジ能力を身につけてもらう。課題等に対し、授業期間中で回答における評価及び解説を行う。
アクティブラーニング（グループディスカッション、ディベート等）の実施Active learning in class (Group discussion, Debate.etc.)
あり / Yes
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
第1回[対面/face to face]：アルゴリズム解析1
アルゴリズムとは？アルゴリズムの記法
第2回[対面/face to face]：アルゴリズム解析2
アルゴリズムの計算量、計算量の漸近的評価
第3回[対面/face to face]：アルゴリズム解析3
アルゴリズムの正当性と停止性
第4回[対面/face to face]：アルゴリズム解析4
アルゴリズムの設計
第5回[対面/face to face]：ソーティング1
ソーティング問題とは？簡単なソーティングアルゴリズム
第6回[対面/face to face]：ソーティング2
ヒープソートとクイックソート
第7回[対面/face to face]：ソーティング3
ソーティングアルゴリズムの数理
第8回[対面/face to face]：探索
逐次探索と2分探索、ハッシュ法
第9回[対面/face to face]：パターン照合1
素朴なアルゴリズムとクヌース・モーリス・プラット法
第10回[対面/face to face]：パターン照合2
ボイヤー・ムーア法と実験的な比較
第11回[対面/face to face]：グラフ
グラフとは？グラフのデータ表現、最短経路の問題
第12回[対面/face to face]：さらに学ぶために1
計算可能性と計算の複雑さ
第13回[対面/face to face]：さらに学ぶために2
クラスPの問題とNP完全問題
第14回[対面/face to face]：さらに学ぶために3
NP完全性の証明への入門
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
【本授業の準備・復習等の授業時間外学習は、4時間を標準とする】CまたはC++プログラミング言語の履修
テキスト（教科書）Textbooks
大森克史・木村晴彦・広瀬貞樹著、“アルゴリズムの基礎”、共立出版
参考書References
エイホ・ホップクロフト・ウルマン著、“アルゴリズムの設計と解析I・II”、サイエンス社
成績評価の方法と基準Grading criteria
期末の定期試験の成績で評価する。6割以上の得点を合格基準とする。
学生の意見等からの気づきChanges following student comments
予習及び復習することは授業内容の理解に役立つ。
学生が準備すべき機器他Equipment student needs to prepare
液晶プロジェクト等を利用する。
その他の重要事項Others
特になし。