授業科目名 データ構造とアルゴリズム
履修期 秋 2単位 履修基準年度 2年
担当者 木庭　淳（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
定期試験　60%
平常リポート　40%（授業中のレポート提出により評価する）
備考 / Note
-
検索キーワード / Keywords
カリキュラム一覧へ