シラバス参照

授業情報／Course information

科目一覧へ戻る 2019/08/20 現在

授業基本情報
科目名（和文）
／Course		 データ構造とアルゴリズム
科目名（英文）
／Course		 Data Structures and Algorithms
時間割コード
／Registration Code		 23181001
学部（研究科）
／Faculty		 情報工学部
学科（専攻）
／Department		 人間情報工学科/スポーツシステム工学科
担当教員（○：代表教員）
／Principle Instructor （○） and Instructors		 ○菊井　玄一郎
オフィスアワー
／Office Hour		 菊井　玄一郎(火曜５時限)
開講年度
／Year of the Course		 2017年度
開講期間
／Term		 第2クォーター
対象学生
／Eligible Students		 2年
単位数
／Credits		 2.0
授業概要情報
更新日
／Date of renewal		 2017/03/27
使用言語
／Language of Instruction		 日本語
オムニバス
／Omnibus		 該当なし
授業概略と目的
／Cource Description and Objectives		 計算機プログラムの骨格を決める，データ構造とアルゴリズムの基礎を習得する．本講義では，Cなど特定のプログラミング言語への依存を極力避けて，プログラムを作成する上で基本となる考え方について講述する．　
履修に必要な知識・能力・キーワード
／Prerequisites and Keywords		 Ｃ言語またはほかのプログラミング言語に関する基礎知識（簡単なプログラムが組めること）
初歩的な代数の知識（極限，オーダー）
履修上の注意
／Notes
教科書
／Textbook(s)		 教書：なし．授業中に資料を配布する．
参考文献等
／References		 近藤嘉雪，”定本　Ｃプログラマのためのアルゴリズムとデータ構造”，ソフトバンククリエイティブ，1998　B>
書名に「アルゴリズムとデータ構造」（あるいは「データ構造とアルゴリズム」）ということばを含むものなら何でもよい．
自分の好みに合ったものを見つけて学習して欲しい．少し変わったものとして，
結城浩，”数学ガール（乱択アルゴリズム）”，ソ フトバンククリエイティブ，2011
は対話調でアルゴリズムや計算量の考え方が丁寧に書かれている（やさしく書かれている
自主学習ガイド
／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-11 [整列(1-4)]
整列（ソート）のアルゴリズムについて学ぶ
１）単純ソート（選択ソート，バブルソート，挿入ソート）
２）クイックソート
３）マージソート
４）ヒープソート
最後にソートに関する総復習を行う
7 12 [経路探索]
Dijkstra法による最短経路探索について学ぶ
8 13 [文字列の探索]
Boyer-Moore法を中心に文字列探索アルゴリズムについて考える
9 14 [アルゴリズムの限界]
計算量的に難しい問題とはどういうものか，既に学んだアルゴリズムとどういう関係にあるのかについて理解する
10 15 [まとめ]
この講義を振り返るとともに，扱わなかった問題などを含めてさらに学ぶだめのガイドを行う．
11 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		 50 40 10

科目一覧へ戻る