科目ナンバー

SE-IG2-5C07

履修条件・関連科目等

プログラムの経験があることが望ましい。

授業で使用する言語

日本語

授業で使用する言語（その他の言語）

授業の概要

コンピュータを用いて情報処理するには、求める情報（問題の答え）を得るための処理手順だけでなく、処理の過程で必要となるデータを効率良く取り出し／書き込むためのデータの記憶方式が重要である。処理手順をアルゴリズム、データの記憶方式をデータ構造と呼ぶ。
　この科目では、基本的なアルゴリズムとデータ構造について講義する。効率の良いプログラムを自作したい学生だけでなく、プログラムを評価したい学生にも必修の科目である。

科目目的

効率の良いアルゴリズムやデータ構造を修得し，実際の課題への応用力を身につける．

到達目標

まず、整列（ソート）を例に，人の思考とプログラミングの違いを理解すること．
　プログラムの基となるアルゴリズムとデータ構造の概念をプログラミング言語に依存しない形で把握し、アルゴリズムの計算量、プログラムの良さの評価基準、および基本的なデータ構造の特質を理解すること。
　さらに、データとそのデータに対する操作が指定されたとき、それらの操作を効率良く実行する適切なデータ構造を設計できるようになると共に、それらの操作がどのような計算量で実行できるのかを評価できるようになること。

授業計画と内容

第１回　アルゴリズムと計算量
第２回　基本的なデータ構造1（リストとスタック）
第３回　基本的なデータ構造2（キューと木構造）
第４回　集合の表現法1（優先度付きキュー（ヒープ）と２分探索木）
第５回　集合の表現法2（平衡木とハッシュ）
第６回　整列（ソート）1（整列ソートとバブルソート）
第７回　整列（ソート）2（クイックソートとマージソート）
第８回　整列（ソート）3（ヒープソート，バケットソートと基数ソート）
第９回　グラフアルゴリズム１（有向グラフの探索，強連結成分と間接点）
第10回　グラフアルゴリズム２（最小木）
第11回　グラフアルゴリズム３（最短経路）
第12回　文字列の検索
第13回　設計法1（分割統治法と動的計画法）
第14回　設計法2（欲張り法と分枝限定法）

授業時間外の学修の内容

指定したテキストやレジュメを事前に読み込むこと／授業終了後の課題提出

授業時間外の学修の内容（その他の内容等）

　授業計画から次週の講義内容が分かるので、教科書の対応する箇所を読み、疑問点を抽出しておく。また、授業時の演習問題を復習する．１週間あたり４時間の学修を基本とする。

授業時間外の学修に必要な時間数／週

・毎週１回の授業が半期（前期または後期）または通年で完結するもの。１週間あたり４時間の学修を基本とします。
・毎週２回の授業が半期（前期または後期）で完結するもの。１週間あたり８時間の学修を基本とします。

成績評価の方法・基準

成績評価の方法・基準（備考）

2/3以上の出席が必要．評価方法は，期末試験4/６、中間試験１/６、平常点（各回の演習や宿題）１/６

課題や試験のフィードバック方法

授業時間内で講評・解説の時間を設ける

課題や試験のフィードバック方法（その他の内容等）

アクティブ・ラーニングの実施内容

実施しない

アクティブ・ラーニングの実施内容（その他の内容等）

授業におけるICTの活用方法

実施しない

授業におけるICTの活用方法（その他の内容等）

実務経験のある教員による授業

いいえ

【実務経験有の場合】実務経験の内容

【実務経験有の場合】実務経験に関連する授業内容

テキスト・参考文献等

教科書：五十嵐健夫著、「データ構造とアルゴリズム」、（数理工学社発行 / サイエンス社発売）
参考書：茨木俊秀著、「アルゴリズムとデータ構造」、（昭晃堂）
　　　　浅野孝夫著、「情報の構造（上）:データ構造とグラフアルゴリズム」、（日本評論社）
　　　　杉原厚吉著、「データ構造とアルゴリズム」、（共立出版）

その他特記事項

参考URL