シラバス参照

授業情報／Course information

科目一覧へ戻る 2019/01/02 現在

授業基本情報
科目名（和文）
／Course		 データ構造とアルゴリズム
科目名（英文）
／Course		 Data Structures and Algorithms
時間割コード
／Registration Code		 23181001
学部（研究科）
／Faculty		 情報工学部
学科（専攻）
／Department		 人間情報工学科/スポーツシステム工学科
担当教員（○：代表教員）
／Principle Instructor （○） and Instructors		 ○菊井　玄一郎
オフィスアワー
／Office Hour		 菊井　玄一郎(火曜５時限，2606室)
開講年度
／Year of the Course		 2018年度
開講期間
／Term		 前期
対象学生
／Eligible Students		 2年
単位数
／Credits		 2.0
授業概要情報
更新日
／Date of renewal		 2018/03/05
使用言語
／Language of Instruction		 日本語
オムニバス
／Omnibus		 該当なし
授業概略と目的
／Cource Description and Objectives		 計算機プログラムの骨格をなす２つの要素であるデータ構造とアルゴリズムの基礎を習得する．本講義では，Cなど特定のプログラミング言語への依存を極力避けて，プログラムを作成する上で基本となる考え方について講述する．具体的な目標は次の通りである．
１）アルゴリズムとは何かを計算量の概念とともに理解する．
２）リスト中の特定の値を探索するアルゴリズムを理解する
３）リストの要素を整列するアルゴリズムを理解する．
４）文字列検索，経路探索の基本的な手法を理解する
履修に必要な知識?能力?キーワード
／Prerequisites and Keywords		 Ｃ言語またはほかのプログラミング言語に関する基礎知識（簡単なプログラムが組めること）．
初歩的な解析学の知識（極限，オーダー）．
履修上の注意
／Notes		 この授業の第二回目以降はグループ単位での演習中心で行います．事前に講義資料を読んでアルゴリズムを理解しておいてください．分からなければ図書館に色々な本があるので勉強してください．ウエブ検索しても良いが時々ウソの内容があるので注意すること．
教科書
／Textbook(s)		 教科書はありません．
次のサイトに資料を置いておきますので各自ダウンロードしてください．一部の内容は解説がついています．
https://iis.cse.oka-pu.ac.jp/courses/dsa/
参考文献等
／References		 近藤嘉雪，”定本　Ｃプログラマのためのアルゴリズムとデータ構造”，ソフトバンククリエイティブ，1998．
書名に「アルゴリズムとデータ構造」（あるいは「データ構造とアルゴリズム」）ということばを含むものなら何でもよい．
自分の好みに合ったものを見つけて学習して欲しい．
少し変わったものとして，
結城浩，”数学ガール（乱択アルゴリズム）”，ソ フトバンククリエイティブ，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 配列の探索と整列のデータ構造とアルゴリズムと計算量を理解している． ○ ○ ○
4 経路探索，文字列探索のデータ構造とアルゴリズムと計算量を理解している． ○ ○
成績評価方法と基準／Evaluation of Achievement
※出席は2/3以上で評価対象となります。
No. 到達目標
／Learning Goal		 定期試験
／Exam.		 ミニテスト 受講態度（発言）
1 計算量，計算の複雑さの考え方を理解している ○ ○ ○
2 基本データ構造（配列，連結リスト，スタック，キュー，木構造）を理解し，適切な処理方法を考えることができる． ○ ○ ○
3 配列の探索と整列のデータ構造とアルゴリズムと計算量を理解している． ○ ○ ○
4 経路探索，文字列探索のデータ構造とアルゴリズムと計算量を理解している． ○ ○
評価割合（％）
／Allocation of Marks		 50 40 10

科目一覧へ戻る