| 授業科目名（和文） ［Course］ |
データ構造とアルゴリズム |
| 授業科目名（英文） ［Course］ |
Data Structures and Algorithms |
| 学部（研究科） ［Faculty］ |
情報工学部 |
| 学科（専攻） ［Department］ |
スポーツシステム工学科 |
| 担当教員（○：代表教員） [Principle Instructor(○) and Instructors] |
○菊井 玄一郎 自室番号（2606）、電子メール（kikui**cse.oka-pu.ac.jp） ※利用の際は,** を @に置き換えてください |
| 単位数 ［Point(Credit)］ |
2単位 |
| 対象学生 ［Eligible students］ |
2年次生 |
| 授業概略と目標 ［Course description and Objects］ |
プログラムの骨格であるデータ構造とアルゴリズムの基礎を習得する．本講義では，Cなど特定のプログラミング言語への依存を極力避けて，プログラムを作成する上で基本となる考え方について講述する． |
| 到達目標 ［Learning Goal］ |
１）計算量，計算の複雑さの考え方を理解する ２）基本データ構造（配列，連結リスト，スタックなど）を理解する ３）配列や文字列の探索，整列，経路探索の手法と計算量を理解する |
| 履修上の注意 ［Notes］ |
１年次でプログラミング言語，ソフトウエア関連の講義?演習を履修していることが望ましい． 「プログラミング技法」と相補的な内容になっている（重要な項目については角度を変えて双方で扱う） |
| 授業計画とスケジュール ［Course schedule］ |
1. アルゴリズムとは? 2. アルゴリズムの表現 3. データ構造：連結リストと木 4. 配列の探索(1)：線形探索，二分探索 5. 計算量（時間計算量） 6. 配列の探索(2)：ハッシュ 7. 復習（配列の探索） 8. 整列(1)：バブルソート，挿入ソート 9. 整列(2)：クイックソート 10. 整列(3)：マージソート 11. 整列(4)：ヒープソート 12. 経路探索：dijkstra法 13. 文字列の探索：Boyer-Moore法 14.アルゴリズムの限界：P,NP 15. まとめ |
| 成績評価方法と基準 ［Grading policy (Evaluation)］ |
期末試験，および授業中に行う，演習，ミニテスト，受講態度，により総合的に評価する |
| 教科書 ［Textbook］ |
教科書：なし．講義で使うプレゼン資料を配布する． 参考書： ?近藤嘉雪，”定本 Ｃプログラマのためのアルゴリズムとデータ構造”，ソフトバンククリエイティブ，1998 その他，書名に「アルゴリズムとデータ構造」（あるいは「データ構造とアルゴリズム」）ということばを含むものなら何でもよい．自分のテイストに合ったものを見つけて学習して欲しい．少し変わったものとして， ?結城浩，”数学ガール（乱択アルゴリズム）”，ソフトバンククリエイティブ，2011 は対話調でアルゴリズムや計算量の考え方が丁寧に書かれている（やさしく書かれているがレベルは高い）．本講義と関連深いのは特に1-3,6章． |
| 自主学習ガイド及び キーワード ［Self learning］ |
資料は http://iis.cse.oka-pu.ac.jp/courses/dsa/ で公開する（アクセス制限あり） Cやpython, Perlなどを用いて実際にプログラムを作成すること．より理解が深まる． |
| 開講年度 ［Year of the course］ |
25 |