シラバス参照

授業情報／Course information

科目一覧へ戻る 2021/09/22 現在

授業基本情報
科目名（和文）
／Course		 データ構造とアルゴリズム
科目名（英文）
／Course		 Data Structures and Algorithms
時間割コード
／Registration Code		 22146201
学部（研究科）
／Faculty		 情報工学部
学科（専攻）
／Department		 情報システム工学科
担当教員（○：代表教員）
／Principle Instructor （○） and Instructors		 ○天嵜　聡介
オフィスアワー
／Office Hour		 天嵜　聡介(火曜 4 限
（＊急な会議・出張等のため不在にすることがあります）)
開講年度
／Year of the Course		 2021年度
開講期間
／Term		 前期
対象学生
／Eligible Students		 2年次生
単位数
／Credits		 2.0
授業概要情報
更新日
／Date of renewal		 2021/03/01
使用言語
／Language of Instruction		 日本語
オムニバス
／Omnibus		 該当なし
授業概略と目的
／Cource Description and Objectives		 計算機プログラムの骨格をなす２つの要素であるデータ構造とアルゴリズムの基礎を習得する．本講義ではプログラムを作成する上で基本となる考え方について講述する．具体的な目標は次の通りである．
１）アルゴリズムとは何かを計算量の概念とともに理解する．
２）リスト中の特定の値を探索するアルゴリズムを理解する
３）リストの要素を整列するアルゴリズムを理解する．
４）文字列検索，経路探索の基本的な手法を理解する
履修に必要な知識・能力・キーワード
／Prerequisites and Keywords		 Ｃ言語またはほかのプログラミング言語に関する基礎知識（簡単なプログラムを作成できること）．
初歩的な解析学の知識（極限，オーダー）．
履修上の注意
／Notes
教科書
／Textbook(s)		 大槻兼資・著　秋葉拓哉・監修 「問題解決力を鍛える！アルゴリズムとデータ構造」，講談社，2020．
参考文献等
／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(1) [アルゴリズム・データ構造とは]
配列の探索を例にアルゴリズムの概念とデータ構造が密接に関係することを学ぶ．		 テキスト第1章を事前に通読すること
2 1(2) [計算量とオーダー記法]
時間計算量と空間計算量の概念，それを表す「オーダー記法」について理解する．		 テキスト第2章を事前に通読すること
テキスト中のコードを実行すること
3 1(3) [再帰と分割統治法]
再帰呼び出しに基づく分割統治法について学ぶ．		 テキスト第3~4章を事前に通読すること
テキスト中のコードを実行すること
4 1(4) [動的計画法]
動的計画法を用いた部分和問題やナップサック問題の解法について学ぶ．		 テキスト第5章を事前に通読すること
テキスト中のコードを実行すること
5 2(5-6) [ソート]
代表的なソートのアルゴリズムについて学ぶ．		 テキスト第12章を事前に通読すること
テキスト中のコードを実行すること
6 2(7-8) [配列・連結リスト・ハッシュテーブル]
配列・連結リスト・ハッシュテーブルについて学ぶ．		 テキスト第8章を事前に通読すること
テキスト中のコードを実行すること
7 1(9) [前半のまとめ]
ここまでに学んだ内容の復習を行う．
8 1(10) [スタックとキュー]
スタックとキューの概念について学ぶ．		 テキスト第9章を事前に通読すること
テキスト中のコードを実行すること
9 1(11) [ヒープ]
ヒープの概念について学ぶ．		 テキスト第6章・第10章を事前に通読すること
テキスト中のコードを実行すること
10 1(12) [木]
木の走査，後置記法とスタック，二分探索木について学ぶ．		 テキスト第10章を事前に通読すること
テキスト中のコードを実行すること
11 1(13) [グラフ]
グラフ理論について復習し，幅優先・深さ優先などのグラフ探索アルゴリズムや最小全域木などの概念について学ぶ．		 テキスト第13~15章を事前に通読すること
テキスト中のコードを実行すること
12 1(14) [PとNP]
問題の難しさという概念について学ぶ．		 テキスト第17章を事前に通読すること
13 1(15) [後半のまとめ]
この講義を振り返るとともに，扱わなかった問題などを含めてさらに学ぶだめのガイドを行う．
14 1(16) [定期試験]
定期試験を行う．
授業評価詳細情報
到達目標及び観点／Learning Goal and Specific Behavioral Viewpoints
No. 到達目標
／Learning Goal		 知識・理解
／Knowledge & Undestanding		 技能・表現
／Skills & Expressions		 思考・判断
／Thoughts & Decisions		 伝達・コミュニケーション
／Communication		 協働
／Cooperative Attitude
1 計算量，計算の複雑さの考え方を説明できる（D） ○ ○ ○
2 基本データ構造（配列，連結リスト，スタック，キュー，木構造）を理解し，適切な処理方法を考えることができる（D） ○ ○ ○
3 配列の探索と整列のデータ構造とアルゴリズムと計算量を説明できる（D） ○ ○ ○
成績評価方法と基準／Evaluation of Achievement
※出席は2/3以上で評価対象となります。
No. 到達目標
／Learning Goal		 定期試験
／Exam.
1 計算量，計算の複雑さの考え方を説明できる（D） ○
2 基本データ構造（配列，連結リスト，スタック，キュー，木構造）を理解し，適切な処理方法を考えることができる（D） ○
3 配列の探索と整列のデータ構造とアルゴリズムと計算量を説明できる（D） ○
評価割合（％）
／Allocation of Marks		 100

科目一覧へ戻る