| 科目名 |
アルゴリズムとデータ構造２ |
| 担当教員 |
妻鳥 貴彦 |
| 対象学年 |
2年 |
クラス |
学部：専門001 |
| 講義室 |
Ａ−ＷＳ |
開講学期 |
１学期 |
| 曜日・時限 |
火４,金４ |
単位区分 |
選択 |
| 授業形態 |
一般講義 |
単位数 |
2 |
| 準備事項 |
|
| 備考 |
|
| 授業の詳細1 |
【授業の目的】
この授業は，情報システム工学科２年次１学期開講科目「情報システム工学実験第１」における実験・実習による学習効果を高めるために実施する．すなわち，同学科同年次２クオータ開講科目「データ構造とアルゴリズム１」で修得した理論的な事柄を本学の計算機実習室において実践するための具体化を行う．本講義の履修を希望する場合には，必ず，「情報システム工学実験第１」も同時に履修しなければならない．
【授業の進め方】
演習形式の授業である．
【達成目標】
(1) アルゴリズムとは何か，データ構造とは何か，その概念を理解できる．
(2) アルゴリズムとデータ構造との間に密接な関係があり，両者を適切に設計することにより，プログラムを正しく効率的に実装することができる．
(3) 配列構造・リスト構造・二分木・ハッシュ等のデータ構造と，その基本操作を理解し，実装することができる．
(4) ソートのアルゴリズムとその効率について理解し，プログラムとして実現することができる． |
| 授業の詳細2 |
【授業計画】
１. 本授業の概要
まず，カリキュラム全体における本授業の占める位置について，特に「計算機言語第２」，「情報システム工学実験第１」，「アルゴリズムとデータ構造１」との関係について説明する．その上で，本授業計画と成績評価についての説明を行う．
２．Javaプログラミングの復習
「計算機言語第２」，「オブジェクト指向プログラミング基礎」および「情報システム工学実験第１」で学んだJavaプログラミングの復習を行い，「アルゴリズムとデータ構造２」を円滑に進めるための準備を行う．
３．配列
データが順番に並んでおり，それぞれのデータを連続する添字によって一意に特定できるようなデータ構造のことを配列と呼ぶ．ここでは，配列を実現するクラスについて理解し，実装を行う．
４〜６．連結リスト
データをそれぞれの要素に格納し，その要素が次の要素とつながってリストを成しているようなデータ構造を連結リストという．ここでは，連結リストの仕組みを理解し，実装を行う．また，双方向リストへの拡張を行う．
７．スタック
データの挿入と取得をリストの特定の一端でのみ行うようなデータ構造をスタックという．ここでは，スタックの仕組みを理解し，実装を行う． |
| 授業の詳細3 |
８．キュー
リストの一方の端ではデータの挿入のみを，もう一方の端では取り出しと削除のみを行うようなデータ構造をキュー（待ち行列）という．ここでは，キューの仕組みを理解し，実装を行う．
９〜10．二分探索木
木構造のうち，各ノードが持てる子の最大数が２であるものを二分木という．二分木のうち，親よりも小さい値を持つ子は左に，親よりも大きい値を持つ子は右に格納した構造を持つものを二分探索木という．ここでは，二分木を実現する方法について理解し，実装を行う．
11〜12．ハッシュテーブル
データ領域上にデータを並べ，各々に対して特定の「鍵」を用いてアクセスするようなデータ構造をハッシュテーブルという．ここでは，ハッシュテーブルの概念を理解し，実装を行う．
13〜15．ソート
あるデータ構造を，指定された指標に従って順序整理する作業をソートという．ここでは，最も基本的なソートアルゴリズムであるバブルソートから学習し，セレクションソート，インサートソート，シェルソートについて学習する．さらに，より高速なクイックソートについて理解し，それぞれ実装を行う．
16．小テスト
17〜18．最終課題 |
| 授業の詳細4 |
【成績評価】
小課題レポート（12回，72点）と小テスト（１回，28点）の結果に基づいて成績評価（一次評価）が行われる．そして，「情報システム工学実験第１」の成績評価点と本講義の成績評価点の小さい方の得点が本講義の評価（二次評価）に採用され，この点（二次評価の点数）によって以下に示す成績評価を行う．したがって，本講義単独での単位取得はできない．
◆AA：小課題レポートに加え小テストがほぼ満点で，さらに最終課題がほぼ完成し，総得点がほぼ100点である場合
◆Ａ：小課題レポートに加え小テストが80%以上できて，さらに最終課題がほぼ完成した場合，または総得点が80点以上である場合
◆Ｂ：小課題レポートに加え小テストが80%以上できて，さらに最終課題を提出した場合，または総得点が70点以上である場合
◆Ｃ：小課題レポートに加え小テストが70%以上できた場合，または総得点が60点以上である場合
◆Ｆ：小課題レポートと小テストの総得点が60点未満である場合
各回のレポートの採点基準についてはその都度具体的な説明を受ける．目安としては，講義を十分に理解してそれをプログラミングで実践できたかどうかが第１関門となり３〜４点程度，独自に応用し，発展させることができたかどうかが第２関門となり２〜３点程度となる．本講義の目標水準への履修者の到達の程度によっては，追加レポートの提出が要求される． |
| 授業の詳細5 |
◇テキスト
岩波講座 ソフトウェア科学３『アルゴリズムとデータ構造』石畑 清著（岩波書店，1989）
◇参考書
『Java アルゴリズム＋データ構造』（有）オングス著（技術評論社，2002，絶版）
『Java によるプログラミング入門』，権藤 克彦 著（サイエンス社，2000）
『Javaで学ぶアルゴリズムとデータ構造』，Robert Lafore 著，岩谷 宏 訳（ソフトバンク，1999）
等
◇備考
履修の前提となる必須科目：「オブジェクト指向プログラミング基礎」
事前の履修が望ましい科目：「計算機言語第２」
同時に履修すべき必須科目：「情報システム工学実験第１」，「アルゴリズムとデータ構造１」 |
| 授業の詳細6 |
|
| 授業の詳細7 |
|
| 授業の詳細8 |
|
| 授業の詳細9 |
|
| 授業の詳細10 |
|