シラバス参照

授業情報／Course information

科目一覧へ戻る 2020/10/22 現在

授業基本情報
科目名（和文）
／Course		 データ構造とアルゴリズム
科目名（英文）
／Course		 Data Structures and Algorithms
時間割コード
／Registration Code		 22146201
学部（研究科）
／Faculty		 情報工学部
学科（専攻）
／Department		 情報システム工学科
担当教員（○：代表教員）
／Principle Instructor （○） and Instructors		 ○横川　智教
オフィスアワー
／Office Hour		 横川　智教(1〜2Q：火曜 4 限，3〜4Q：火曜 3 限，場所：2504
＊授業に関する質問は随時受け付けます．
＊急な会議・出張等のため不在にすることがあります．)
開講年度
／Year of the Course		 2020年度
開講期間
／Term		 前期
対象学生
／Eligible Students		 2年次生
単位数
／Credits		 2.0
授業概要情報
更新日
／Date of renewal		 2020/03/10
使用言語
／Language of Instruction		 日本語
オムニバス
／Omnibus		 該当なし
授業概略と目的
／Cource Description and Objectives		 計算機プログラムの骨格をなす２つの要素であるデータ構造とアルゴリズムの基礎を習得する．本講義では，Cなど特定のプログラミング言語への依存を極力避けて，プログラムを作成する上で基本となる考え方について講述する．具体的な目標は次の通りである．
１）アルゴリズムとは何かを計算量の概念とともに理解する．
２）リスト中の特定の値を探索するアルゴリズムを理解する
３）リストの要素を整列するアルゴリズムを理解する．
４）文字列検索，経路探索の基本的な手法を理解する
履修に必要な知識・能力・キーワード
／Prerequisites and Keywords		 Ｃ言語またはほかのプログラミング言語に関する基礎知識（簡単なプログラムが組めること）．
初歩的な解析学の知識（極限，オーダー）．
履修上の注意
／Notes
教科書
／Textbook(s)
参考文献等
／References		 近藤嘉雪，”定本　Ｃプログラマのためのアルゴリズムとデータ構造”，ソフトバンククリエイティブ，1998．
自主学習ガイド
／Expected Study Guide outside Coursework/Self-Directed Learning Other Than Coursework
資格等に関する事項
／Attention Relating to Professional License		 情報処理技術者（基本情報，応用情報レベル）の項目である．
備考
／Notes
授業計画詳細情報
No. 単元（授業回数）
／Unit (Lesson Number)		 単元タイトルと概要
／Unit Title and Unit Description		 時間外学習
／Preparation and Review		 配付資料
／Handouts
1 1 [データ構造とアルゴリズムとは?　]
配列の探索を例にアルゴリズムの概念とデータ構造が密接に関係することを学ぶ．
2 2 [リスト構造]
ポインタを利用する連結リストについて，配列との比較を通して学ぶ．
3 3 [アルゴリズムの良さに関する基準]
時間計算量と空間計算量の概念，それを表す「オーダー記法」について理解する．
4 4 [基本的なソーティングアルゴリズム]
基本的なソーティングアルゴリズムとして，選択ソートやバブルソートについて学ぶ．
5 5 [分割統治法]
再帰呼び出しに基づく分割統治法について学ぶ．
6 6 [効率的なソーティングアルゴリズム]
効率的なソーティングアルゴリズムとして，クイックソートやマージソートについて学ぶ．
7 7 [キューとスタック]
キューとスタックの概念について学ぶ．
8 8 [前半のまとめ]
ここまでに学んだ内容の復習を行う．
9 9 [ヒープ]
ヒープの概念について学ぶ
10 10 [木構造]
木の走査，後置記法とスタック，二分探索木について学ぶ．
11 11 [ハッシュ]
ハッシュを用いたアルゴリズムについて学ぶ．
12 12 [グラフに関するアルゴリズム]
グラフ理論について復習し，幅優先・深さ優先などのグラフ探索アルゴリズムや最小全域木などの概念について学ぶ．
13 13 [動的計画法]
動的計画法を用いた部分和問題やナップサック問題の解法について学ぶ．
14 14 [NP完全問題]
問題の難しさという概念について学び，NP完全問題について学ぶ．
15 15 [後半のまとめ]
この講義を振り返るとともに，扱わなかった問題などを含めてさらに学ぶだめのガイドを行う．
16 16 [定期試験]
理解度の確認を行う．
授業評価詳細情報
到達目標及び観点／Learning Goal and Specific Behavioral Viewpoints
No. 到達目標
／Learning Goal		 知識・理解
／Knowledge & Undestanding		 技能・表現
／Skills & Expressions		 思考・判断
／Thoughts & Decisions		 伝達・コミュニケーション
／Communication		 協働
／Cooperative Attitude
1 計算量，計算の複雑さの考え方を理解している ○ ○ ○
2 基本データ構造（配列，連結リスト，スタック，キュー，木構造）を理解し，適切な処理方法を考えることができる． ○ ○ ○
3 配列の探索と整列のデータ構造とアルゴリズムと計算量を理解している． ○ ○ ○
成績評価方法と基準／Evaluation of Achievement
※出席は2/3以上で評価対象となります。
No. 到達目標
／Learning Goal		 定期試験
／Exam.
1 計算量，計算の複雑さの考え方を理解している ○
2 基本データ構造（配列，連結リスト，スタック，キュー，木構造）を理解し，適切な処理方法を考えることができる． ○
3 配列の探索と整列のデータ構造とアルゴリズムと計算量を理解している． ○
評価割合（％）
／Allocation of Marks		 100

科目一覧へ戻る