| 授業科目名（和文） ［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］ |
プログラムの骨格であるデータ構造とアルゴリズムの基礎を習得する．ここで学習する内容はソフトウエアを作成する上で基本中の基本である． |
| 到達目標 ［Learning Goal］ |
１）計算量，計算の複雑さの考え方を理解する ２）基本データ構造（配列，連結リスト，スタックなど）を理解する ３）配列や文字列の探索，整列，経路探索の手法と計算量を理解する |
| 履修上の注意 ［Notes］ |
１年次でプログラミング言語，ソフトウエア演習等のソフトウエア基礎に関する講義?演習を履修していることが望ましい． 「プログラミング技法」と相補的な内容になっている（重要な項目については双方で扱う） |
| 授業計画とスケジュール ［Course schedule］ |
1. アルゴリズムとは? 2. 配列の探索(1)：線形探索，番兵，二分探索 3. 計算量（時間計算量） 4. データ構造：配列と連結リスト 5. 配列の探索(2)：ハッシュ 6.復習（配列の探索），再帰関数について 7. 整列(1)：バブルソート，挿入ソート 8. 整列(2)：クイックソート 9. 整列(3)：マージソート 10. 整列(4)：ヒープソート 11. 復習（整列） 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］ |
26 |
| 資格等に関する事項 | 基本情報技術者，応用情報技術者のアルゴリズム部分の内容を含む |