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

授業科目区分

専門科目
専門科目 情報テクノロジーコース

わくラボの使用について:使用しない
情報テクノロジーコース必修 2単位 2年次 後期

教職課程(情報)選択

担当教員

小泉真也

研究室のホームページ,SNSなど

NDC

007.6 / 007.64 / 410.1 / 418

科目分類コード

1001 05

オフィスアワー

この科目のキーワード

データ構造, コンピュータ・アルゴリズム

説明に使用する言語

主として日本語を使用する

使用する教材の言語

日本語で記述された資料を使用する

この科目に必要な日本の文化・事情の知識について

到達目標

オブジェクト指向言語における、目的に応じた、データ構造およびアルゴリズムの活用。 手続き型言語における、データ構造およびアルゴリズムの記述。

ディプロマポリシーとの関連性

情報メディア基礎力:情報メディアの技術的および社会的な変化に対応し得る基盤となる知識とスキル, 専門能力:情報メディアの開発とその多面的な活用ができる能力

授業の簡単な概要

プログラミング言語の構文を理解したのち、さらなるステップアップを図るには、確立された問題解決の手続き−いわゆる「アルゴリズム」−の知識が不可欠です。 問題解決のために、データをどのような仕組みの下に格納し、どのような手順で処理をしていくか。講義ではオブジェクト指向言語を用いて現象を理解し、手続き型言語を用いてこれら現象の再現を記述します。

学習内容

  1. コンピュータによる並べ替え(ソート)の考え方: バブルソート, クイックソート
  2. 再帰呼び出し: 階乗、アッカーマン関数、フィボナッチ数列、ハノイの塔
  3. 問題解決の戦略:アルゴリズムの必須条件、選択条件、計算量、データ構造
  4. 配列とリスト: データの格納
  5. 配列とリスト: データの読み出し
  6. スタックとキュー
  7. ツリー(木)構造
  8. マップとハッシュ
  9. グラフ構造:高さ優先探索・幅優先探索
  10. グラフ構造:最短経路問題
  11. 探索:線型探索、二分探索、ハッシュ探索
  12. 探索:力任せ探索とバックトラック法
  13. 文字列検索
  14. 動的計画法:ナップサック問題を例に
  15. 問題の難しさ:P・NP・NP完全・NP困難、決定問題
  16. 問題の難しさ:組合せ最適化問題

授業時間外での学修

講義資料に基づく予復習の時間として4時間:例題は、書き写しではなく、動作の過程を追った読解を求めます。

成績評価の基準と方法

(S)難易度の高い問題に対して、確立されたアルゴリズムを用いたり、適切なデーター構造を適用したりして、正しい解を効率よく矛盾なく導くこと。
(A)簡単な問題に対して、確立されたアルゴリズムを用いたり、適切なデーター構造を適用したりして、正しい解を効率よく矛盾なく導くこと。
(B)簡単な問題に対して、正しい解を導き、考察の過程におおよその努力が認められること。
(C)簡単な問題に対して、正しい解を導くこと

達成度評価(評価方法:合計100点)

試験:      / 100
レポート:    100 / 100
小テスト(中間テストなど含む): / 100
小レポート(中間レポートなどを含む): / 100
作品:      / 100
ポートフォリオ: / 100
その他:

教科書・テキスト

LMS等を通じて、提供します。

参考図書・参考文献等

■柴田望洋、”新・明解C言語で学ぶアルゴリズムとデータ構造 (明解シリーズ)”、SBクリエイティブ
■奥村晴彦 、”[改訂新版]C言語による標準アルゴリズム事典 (Software Technology)”、技術評論社
■久保幹雄、”組合せ最適化とアルゴリズム (インターネット時代の数学シリーズ 8) ”、共立出版
■C, C++, Java, C# を中心に、「(基本的な)アルゴリズム」や「データ構造」を扱う書物を、できるだけ多く参考とする。

履修もしくは取得していなければいけない科目

”プログラミング基礎” と ”プログラミング言語構造論” は、それぞれ、プログラミング科目のステップ1, 2 にあたり、本科目は3 にあたるため、原則として上記科目の単位取得を要する。

学習支援

質問は、LMSやメール等で逐次受付けます。レポートに対しては、適宜、改善点を提示します。

授業に関連する実務経験

企業に所属・大学での研究で、ソフトウェア開発の経験あり(C++, Java, Basic系、MASM)

その他この科目を履修するために必要な条件

”プログラミング基礎”および”プログラミング言語構造論”の講義を通じて、プログラミング言語C、C++、Java、C#の読解およびプログラミングスキルを有すること。