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

科目名	データ構造とアルゴリズムⅠ

単位数	学年配当	開講期間	担　当　教　員
2	2	前期開講	大場和久

テーマ

情報処理技術者試験の出題範囲にもなっているデータ構造とアルゴリズムについて基本的事項を学ぶ．

科目のねらい

＜キーワード＞
データ構造　　アルゴリズム
プログラミング　　計算量の評価

＜内容の要約＞
演算時間の短縮や使用メモリの節減など、プログラミングの際に考えておかなければならないことがある。本講義では、そのための基礎となるデータ構造とアルゴリズムについて学び、 Euclid 互除法、探索、ソート、データの挿入・削除などのプログラムの設計方法を学ぶ。探索アルゴリズム、ソートアルゴリズムでは、グループごとの調べ学習と発表により主体的に課題に取り組む姿勢を身につける．

＜学習目標＞
データ構造とアルゴリズムについて学ぶことで適切にプログラムを設計できる。
課題の解決に向けて，計算量やデータ構造に配慮したプログラムを設計できる。
主体的に課題に取り組む姿勢を身につけることができる。

授業のながれ

データ構造とアルゴリズムの概要とプログラミングの復習
アルゴリズムの基本　Euclid 互除法の理解と演習（テキストp.45），再帰関数
計算量の評価（テキストp.11）
（事前のグループでの学習と発表）　線形探索法のアルゴリズムと計算量評価（テキストp.12，p.30）
（事前のグループでの学習と発表）　二分探索法のアルゴリズムと計算量評価（テキストp.12，p.30　p.91），二分探索法のプログラム
（事前のグループでの学習と発表）　ソートアルゴリズム　選択ソート，バブルソート（どちらもテキストにはない），小テスト
（事前のグループでの学習と発表）　ソートアルゴリズム　挿入ソート（テキストp.196），シェルソート（テキストにはない），小テスト
（事前のグループでの学習と発表）　ソートアルゴリズム　マージソート（テキストp.198），バケットソート（テキストp.212　事前のグループでの学習と発表），小テスト
探索法，ソート法のまとめ．ハッシュ法，クイックソートの紹介．
確認テスト
データ構造の基本　概論、配列
（事前のグループでの学習と発表）　データ構造　リスト（テキストp.126），スタック，キュー（テキストp.145），小テスト
（事前のグループでの学習と発表）　データ構造　グラフ（テキストp.155），木構造二分木（テキストp.167），小テスト
（事前のグループでの学習と発表）　データ構造　ヒープ木（テキストp.172），ヒープソートのアルゴリズムとプログラム（テキストp.209），小テスト
まとめ

準備学習の内容・学ぶ上での注意

データ構造やアルゴリズムの演習課題としてプログラムの提出を求める。プログラミング演習IIの内容を習熟している必要がある。変数、配列、繰り返し（for、while）、関数に加え、特にポインタ、構造体についてしっかりと復習しておくこと。グループ学習としてアルゴリズムの学習と発表を課します。しっかりと準備して、他の学生が理解できるように発表することが必要となります。他の受講生の迷惑になる行為（私語、講義中に席を離れるなど）は厳禁。

事前事後	学習内容	時間数
事前	プログラミングの復習	15
事前	グループ課題の事前学習	5
事後	講義内で学習したアルゴリズムのプログラミング	15
事後	学習内容の理解	15

本科目の関連科目

プログラミング演習I、II、システム設計論を始めとして、情報系科目全て。

成績評価の方法

期末試験（筆記・Web・レポート・最終授業内）	40％
授業内でのレポート・課題等	40％
その他	20％

成績はグループでの課題発表，課題提出状況，試験を総合して評価する．課題は遅滞なく提出すること．

テキスト

■テキストを使用する
■レジュメを使用する
■未定（最初の授業で指示する）

＜著者＞大槻兼資，秋葉拓哉　＜テキスト名＞問題解決力を鍛える！　アルゴリズムとデータ構造　＜出版社＞講談社