筑波大学教育課程編成支援システム

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

3.0 単位, 2 年次, 秋ABC 月1,2
北川博之, 天笠俊之, 長谷部浩二

授業概要

ソフトウェアを書く上で基本となるデータ構造とアルゴリズムの考え方について学ぶ。線形構造,木構造,グラフ構造,データ整列,データ探索について学習する。

備考

平成25年度までに開設された「データ構造とアルゴリズム」(GB11911, GB11921)の単位を修得した者の履修は認めない。
オンライン(同時双方向型)

授業形態

講義

学位プログラム・コンピテンスとの関係

・専門コンピテンス
1. 情報科学を支える基礎知識

授業の到達目標(学修成果)

プログラミング技術の基本となるデータ構造とアルゴリズムを理解し、これらを用いたアルゴリズム設計やプログラミングができる。
計算量等の概念を理解し、アルゴリズムの効率性等に関する考察ができる。

キーワード

リスト, 木, グラフ, 整列, 探索

授業計画

第1回	アルゴリズムとデータ構造の基本概念: アルゴリズムの正しさ、アルゴリズムの評価、データ構造
第2回	基本的なデータ構造(1): 配列、リンク配置、連結リスト、スタック、キュー
第3回	基本的なデータ構造(2): 木構造、2分木、木の走査、一般の木
第4回	集合とハッシュ集合の表現方法と集合に対する操作、辞書とハッシュ法
第5回	全順序集合(1): ヒープ、2分探索木
第6回	全順序集合(2): AVL木
第7回	整列(1): 単純な整列アルゴリズム、ヒープソート
第8回	整列(2): クイックソート、マージソート、基数ソート
第9回	第8週目までの復習および中間試験
第10回	グラフアルゴリズム (1): グラフの定義、隣接行列、隣接リスト、深さ優先探索、幅優先探索
第11回	グラフアルゴリズム (2): 最短路問題(ダイクストラのアルゴリズム、フロイトのアルゴリズム)
第12回	文字列照合 (1): 文字列照合問題、単純照合法、KMP法
第13回	文字列照合 (2): BM法、発展的なアルゴリズム
第14回	アルゴリズムの設計手法: 分割統治法、グリーディ法、動的計画法、分枝限定法
第15回	第14週目までの復習及び期末試験

履修条件

C言語またはJavaによる簡単なプログラミングの経験があること。
平成25年度までに開設された「データ構造とアルゴリズム」(GB11911, GB11921)の単位を修得した者の履修は認めない。

成績評価方法

各講義の最後にクイズ形式のレポートを出題する。成績は、出題されたレポートの成績を総合して判定する。

学修時間の割り当て及び授業外における学修方法

事前に教科書の該当部分に目を通しておくこと。

教材・参考文献・配付資料等

以下を教科書とする。

1. 原隆浩, 水田智史, 大川剛直,「アルゴリズムとデータ構造」共立出版

題10回〜第13回の内容は以下の参考書に基づくが、必要な資料をmanabaにて配布する。

参考書籍
「Cで学ぶデータ構造とアルゴリズム」(西原清一著)オーム社

オフィスアワー等(連絡先含む)

北川:水 11:45-13:15 総B903.事前にメールで連絡することが望ましい.メールでの質問等は随時対応.
天笠・長谷部:オフィスアワーは設けないので、事前に電子メールで連絡を取ること。

北川博之 1000852 http://www.kde.cs.tsukuba.ac.jp/~kitagawa/
天笠俊之 1002320 http://www.kde.cs.tsukuba.ac.jp/~amagasa/
長谷部浩二 1002109 http://www.cs.tsukuba.ac.jp/~hasebe

その他(受講生にのぞむことや受講上の注意点等)

オンライン講義実施に関する情報
・本講義は「オンライン(同時双方向型)」で実施します。受講生は授業時間に指定のオンラインツールで接続してください。
(各講義は録画し、後日視聴できるようにします。)
この講義ではZoomを利用します。

・講義資料の配付方法
講義資料はmanabaにアップロードします。

他の授業科目との関連

ティーチングフェロー(TF)・ティーチングアシスタント(TA)

TAを4名配置する。

シラバス参照