データ構造とアルゴリズム

科目ナンバリング
1090331656

担当者
神村 伸一

 
常勤
教員研究室
1407
DP
1,3
配当年次
2年次・後期
授業形式
講義
授業時間
30時間
単位
必修 2単位


アクティブ・ラーニング

□協定等に基づく外部機関と連携した課題解決型授業 □ディスカッション・ディベート
 □グループワーク □プレゼンテーション □実習・フィールドワーク ☑該当なし

【授業内容】

コンピュータプログラムを開発・設計する際に必要となる様々なデータ構造とそのデータを操作するアルゴリズムを学ぶ。データ構造は配列と代表的な抽象データ型(ADT)を取り扱う。アルゴリズムは主に整列を取り扱う。アルゴリズムの性能をBig O記法(漸近的時間計算量)の測度で表現し、アルゴリズムとデータ構造の関係を比較・評価を通してプログラム設計時におけるトレードオフの関係を学ぶ。


【学習の到達目標】

基本的なデータ構造(配列、リスト、スタック、キュー、ツリー等)を理解する。代表的な整列アルゴリズム(バブルソート、クイックソート等)の仕組みを理解する。それぞれのアルゴリズムの性能をBigO記法(漸近的時間計算量)で表現できる。


【成績評価方法】

成績は出席率60%以上を評価対象とし、受講姿勢 20%、課題レポート 30%、学期末試験 50%以上の観点と重みで総合評価する。

【課題等のフィードバック方法】

毎週実施する演習課題は翌週にふり返り学習を実施する。また講義の感想や質問等は一括してまとめ、必要に応じて教員のコメントを付けて配布する。


【履修上の注意・予習・復習について】

やむを得ない理由で遅刻や欠席等の場合は事前事後に関わらず担当教員まで連絡すること。


【受講して得られる効果・メリット、その他】

情報処理技術者試験(国家試験)の出題範囲「共通キャリア・スキルフレームワーク テクノロジ系分野/1 基礎理論/2 アルゴリズムとプログラミング」の内容を取り扱う。
システム開発企業でシステム開発の経験を有する教員が、その経験を活かしてデータ構造とアルゴリズムの基礎知識と評価について講義する。

授業計画

担当教員学習内容学習課題・必要な学習時間/予習・学習時間時間(分)
1神村 伸一アルゴリズムとデータ構造について講義内容を復習し、次週の学習テーマについて教科書に基づき予習すること。240
2神村 伸一データ型とデータ構造と計算量(Big O記法)講義内容を復習し、次週の学習テーマについて教科書に基づき予習すること。240
3神村 伸一基本データ構造1(配列)講義内容を復習し、次週の学習テーマについて教科書に基づき予習すること。240
4神村 伸一基本データ構造2(リスト)講義内容を復習し、次週の学習テーマについて教科書に基づき予習すること。240
5神村 伸一基本データ構造3(スタック、キュー)講義内容を復習し、次週の学習テーマについて教科書に基づき予習すること。240
6神村 伸一基本データ構造4(ツリー 1)講義内容を復習し、次週の学習テーマについて教科書に基づき予習すること。240
7神村 伸一基本データ構造5(ツリー 2)講義内容を復習し、次週の学習テーマについて教科書に基づき予習すること。240
8神村 伸一優先度付きキュー講義内容を復習し、次週の学習テーマについて教科書に基づき予習すること。240
9神村 伸一二分探索木講義内容を復習し、次週の学習テーマについて教科書に基づき予習すること。240
10神村 伸一ハッシュ1講義内容を復習し、次週の学習テーマについて教科書に基づき予習すること。240
11神村 伸一ハッシュ2講義内容を復習し、次週の学習テーマについて教科書に基づき予習すること。240
12神村 伸一ソート1(バブル、基数、バケット)講義内容を復習し、次週の学習テーマについて教科書に基づき予習すること。240
13神村 伸一ソート2(選択、挿入)講義内容を復習し、次週の学習テーマについて教科書に基づき予習すること。240
14神村 伸一ソート3(マージ、クイック)講義内容を復習し、次週の学習テーマについて教科書に基づき予習すること。240
15神村 伸一データ構造とアルゴリズムの評価方法講義内容を復習し、次週の学習テーマについて教科書に基づき予習すること。240
教科書
原・水田・大川共著 未来へつなぐデジタルシリーズ10 アルゴリズムとデータ構造(共立出版)
参考書
石畑清著 岩波講座 ソフトウェア科学 3 アルゴリズムとデータ構造(岩波書店)
備考
本講義は特定のプログラミング言語に依存しない普遍的なデータ構造やアルゴリズムを学ぶが、プログラミング基礎演習I と プログラミング基礎演習II を十分に理解していることが望ましい。