授業科目

アルゴリズムとデータ構造
Algorithms and Data Structures

担当者

教授   森田 光
後 火2
准教授 西澤 弘毅
後 水2

単位

2

到達目標

 本講義の到達目標は、受講生が、情報処理分野共通で頻繁に扱われる①算法とデータ構造の観点から講義を受け、②プログラム体験を通して、③その知識を具体的に活用できるようになることである。また、情報処理技術者試験などで要求される④知識を理解し図で説明できるようになり、⑤修得した知識に基づいた抽象的な概念をプログラム上で実現できるようになることを含む。
 これらの目標設定は、情報システム創成学科のカリキュラムポリシーにある「専門知識の獲得・創成能力の修得」の理念に基づくものであり、情報科目における「コンピュータ及び情報処理(実習を含む。)」の区分における社会的要請に、受講生が応えられるようになるためである。

授業内容

 コンピュータに合ったデータの運用・蓄積方法(データ構造)と計算手順(アルゴリズム、算法)などの基盤となる知識無しには、コンピュータを使って問題を解いたり、情報システムを構築することはできない。そこで、受講生は、人間の思考をコンピュータへ移すために概念(考え方)を整理し、コンピュータを操作しながらその効果を評価検証する作業を通じて理解を深める。なお、この科目は、情報システム創成学科のカリキュラムポリシーにおける情報環工学の一つとして位置づけられている。教育課程体系図でも示されている通り、プログラミングしつつ理解を深めるためには、情報システム創成学科が実施している「プログラミング演習ⅠおよびⅡ」のプログラミングの知識が前提となる。従って、他学科受講者にあっては、同様のプログラミング知識の準備を願いたい。

授業計画

 本計画では修得範囲を明示するものであり、実習、演習ならびにテストの与え方は、進度により前後することがある。なお、個人の予習として、①事前に指定された範囲のテキストを読んでおき、②分からないことについて事前に意識しておくことで、講義に臨むことが効果的である。また、復習として、③理解しにくかったことをコンピュータ操作を通じて納得すること、④プログラミングを自らすること、⑤次回の授業の準備をすることで、受講生の記憶に定着することを期待する。また、予習・復習に各回あたり4時間程度の自己学習を想定している.


第Ⅰ部:アルゴリズムはなぜ重要か
1. オリエンテーション(シラバス記載事項の確認を含む)、繰り返し計算と解析解、計算量、データ構造、Python の導入
【予習】自らの計算機環境にPythonをインストールし、四則演算などの簡単な処理ができることを確認する.
2. アルゴリズムを表現する様々な方法、Python の文法、アルゴリズムの表現(図、言葉、フローチャート、疑似コード)
【予習】教科書の例題を読むとともにPythonのプログラムをあらかじめ動かし、疑問点を整理する.
3. ソートとは、選択ソート、最悪計算量、最良計算量、平均計算量
【予習】教科書のソート説明部分を読み、例えば、{7, 3, 4, 2, 6, 5, 1}を昇順に並べる手順を考える.

第Ⅱ部:アルゴリズムを設計するには
4. 挿入ソート、バケットソート
【予習】選択ソートも含め、同じソートでも何が違うのかについて比較しておく.
5. バブルソート、バブルソートの改良版
【予習】新たに加わったソートも含め、それらの違いについて比較する.
6. 分割統治法、動的計画法、フィボナッチ数列
【予習】教科書の例題を読んでおき、疑問点を整理する.

第Ⅲ部:アルゴリズム設計法を応用するには
7. フラクタル図形、「ハノイの塔」問題、最短経路問題
【予習】ハノイの塔の実際に動かすディスクの枚数として3, 4, 5の3ケースについて、紙の上で解いてみる.
8. マージソート
【予習】既に学んだソートの方法とマージソートの違いについて整理しておく.
9. クイックソート、整列の安定性
【予習】クイックソートとマージソートとの違いについて整理しておく.

第Ⅳ部:データ構造はなぜ重要か
10. 探索、線形探索、二分探索、木、二分木、二分探索木、グラフ
【予習】教科書を読み、二分木について疑問点を整理しておく.
11. スタック、キュー、深さ優先探索(バックトラック)、幅優先探索、リングバッファ
【予習】各種データ構造の違いについて疑問点を整理しておく.
12. 全順序集合、優先度つきキュー、ヒープ、ヒープソート
【予習】二分木などのツリー構造を用いてソートを実施するにはどんなことがありうるか考えを整理しておく.

第Ⅴ部:アルゴリズムとデータ構造を設計するには
13. 貪欲法、釣り銭のアルゴリズム、最良優先探索、最短路問題、ダイクストラ法
【予習】教科書の例題にある経路問題について、自分なりのやり方の考えを整理しておく.
14. 力まかせ探索、ミニマックス法、分岐限定法、枝刈り
  0-1ナップサック問題、分割ナップサック問題
  最後に、本講義全体に関わる問題形式のまとめとそれに対する質疑応答の時間を設ける。
【予習】教科書の例題にあるナップザック問題について、自分なりに解き疑問点を整理しておく.また、講義全体についても疑問点を整理し、講義中に質疑するための準備をする.

※ 授業とは別に、定期試験を実施する。

授業運営

1. 大学の授業支援システム(dotCampus)を通じて情報を提供するので、チェックを欠かさず行うこと。
2. 授業中のトイレ等の途中出入りは原則できない。事前に体調管理・時間的余裕をもって行動すること。
3. 指定使用書を持参すること。
4. PCを活用して講義の理解に努めること。
5. 個人的に、神奈川大学のメールアドレス(r2XXX00000xx@jindai.jpなど)に連絡をとることがあるので、日頃必ずチェックするメールアドレス(携帯電話メールなど)への転送設定などし、伝達漏れが起きないようにすること。

評価方法

 定期試験により評価する。また、講義中の演習提出とdotCampusへの課題提出などで解答状況が良い場合、それを加味して評価を上げる場合がある。なお、出席状況は評価の対象にしない.

オフィスアワー

 以下の時間帯と場所を設定する。
・森田:月曜日12:40~13:20、23号館4F411号室または412号室。
・西澤:木曜日12:40~14:00、6号館4F418号室。
 なお、長時間に及びそうな相談の場合は、Email等で別の時間を予約の上、来訪すること。

使用書

西澤弘毅、森田光『Python によるアルゴリズムとデータ構造(仮題)』[近代科学社]2018予定

参考書

原 隆浩、ほか『アルゴリズムとデータ構造』[共立出版(未来へつなぐ デジタルシリーズ 10)]2012
柴田望洋、辻亮介『新・明解C言語によるアルゴリズムとデータ構造』[ソフトバンククリエイティブ]2011
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein,Introduction to Algorithms,3rd Ed.,The MIT Press,2009

Copyright© 2017 Kanagawa University. All Rights Reserved.