| 授業科目名 | データ構造とアルゴリズム実習 |
|---|---|
| 履修期 秋 1単位 履修基準年度 3年 | |
| 担当者 | 木庭 淳（KINIWA JUN） |
| 授業目的 / Course Objectives |
|---|
| プログラミングにおいて基本的アルゴリズム、基本的データ構造を選択し、組み合わせて適切なアルゴリズムを設計する能力を身につける。さらに実習によりデータの配置が計算結果にどのような影響を及ぼすかを体験し、データ構造とアルゴリズムの知識が役に立つことを知る。 |
| 到達目標 / Attainment Objectives |
| 本授業では、下記３点を到達目標とする。 （１）データ構造とアルゴリズムの関係を知り、それぞれのデータ構造の概念とアルゴリズムの概要を説明することができる。 （２）最悪計算時間量の考え方を理解し、代表的なアルゴリズムの時間計算量を求めることができる。 （３）なぜ様々なデータ構造が考え出されてきたかという理由を知り、データ構造とアルゴリズムが実際にはどのように役立っているのかを説明することができる。 |
| 教科書 / Textbook(s) |
| アディティア.Y.バーガバ：なっとく！アルゴリズム（翔泳社 2017年、ISBN:4798143359） |
| 参考書 References Materials |
| 柴田 望洋：新・明解C言語で学ぶアルゴリズムとデータ構造（SBクリエイティブ 2017年、ISBN:4797390522）
鈴木たかのり、 杉谷弥月：いちばんやさしいPythonの教本 人気講師が教える基礎からサーバサイド開発まで（インプレス 2017年、ISBN:4295002089） |
| 授業時間外の学習 (準備学習等について) / Study Required Outside of Class (Preparation etc.) |
| 数列と級数、定積分に関する高等学校の知識が必要である。何か一つの手続き型プログラミング言語を習得することが望ましい。 |
| 授業計画 / Class Overall Plan |
|
第1回．プログラミング言語について 授業中に例示するプログラミング言語の概略を説明する。また授業の方針を示し、簡単な例題を出題する。 第2回．アルゴリズムの基本 データ構造とアルゴリズムとは何か、二分探索を例に時間計算量とは何かを解説する。 第3回．二分探索の実習 二分探索の動きと線型探索の動きの違いについて例題を通して実習する。 第4回．ソート 配列とリンクリストという基本的なデータ構造をもとに整列アルゴリズムについて解説する。 第5回．ソートの実習 整列アルゴリズムの動きについて例題を通して実習する。 第6回．再帰 再帰という概念について解説する。初心者には難解な考え方なので時間をかけて説明する。 第7回．再帰の実習 いくつかの再帰アルゴリズムの動きを例題を通して実習する。 第8回．クイックソート 再帰の応用例としてクイックソートを説明する。 第9回．クイックソートの実習 クイックソートの動きを例題を通して実習する。 第10回．ハッシュテーブル ハッシュ関数を考え、衝突が起こったときどう対処するかについて解説する。 第11回．ハッシュテーブルの実習 ハッシュテーブルの動きを例題を通して実習する。 第12回．幅優先探索 グラフアルゴリズムの一つである幅優先探索について解説する。 第13回．幅優先探索の実習 幅優先探索の動きを例題を通して実習する。 第14回．小テスト 授業中の内容について小テストを行う。なお小テストは期末に実施するとは限らない。 |
| 授業方法 / Method of Instruction |
| 講義の後、例題を各自で解いてもらい、アルゴリズムの動きを理解しつつ進める。 授業の内容が理解できたかどうかを小テストをしばしば実施してチェックする。 |
| 成績評価 / Evaluation Criteria/Method |
|
定期試験に代わるリポート 50% 授業中試験 30% その他 20%（授業中の発表により評価する） |
| 備考 / Note |
| - |
| 検索キーワード / Keywords |