アルゴリズム論第一(1クラス)

Google Classroom クラスコードは5wy6mia

情報の分野では, 対象とする現実世界の諸問題の離散的な構造を把握・表現して効率的に扱うために, アルゴリズム・データ構造を学ぶことが必須である.
本講義では, データ構造・アルゴリズムの基本と特性について, 理論的および直感的に理解し説明する方法を学び, コンピュータ上での実現方法を修得する. 単純なデータ構造から始めて, ハッシュ法, 木・グラフなどを用いた問題の構造の記述・理解と効率的処理技法を修得する.
本講義によって, 高校数学・大学初年次までに学んだ線形代数・確率統計・数列などの基礎数学と合わせ, 情報分野で必須な基本的な数学の知見を修得することも目標とする.

プログラミング通論, 基礎プログラミングおよび演習

なし

教科書:指定しない. 必要に応じて資料を配布する.
参考書:一般的なものを授業で紹介するが, 以下の2つの教科書は定番である.
・R.Sedgewick. Algorithms in C, Parts 1-4. 及び Part 5. Addison-Wesley Professional. 1997.
(邦訳:Parts 1-4のみ)R.セジウィック著/野下浩平・星守・佐藤創・田口東 共訳:アルゴリズムC・新版─基礎・データ構造・整列・探索, 近代科学社, 2004年.
・T.H.Cormen他. Introduction to Algorithms, 3rd Edition. MIT Press. 2009.
(邦訳)T.コルメン・R.リベスト・C.シュタイン・C.ライザーソン/浅野哲夫ほか訳:アルゴリズムイントロダクション第3版. 総合版(分冊版もあり), 近代科学社, 2013年.

今年度の講義は, 対面講義を基本として行う予定ですが, 状況によっては, オンラインに移行する可能性もあります.
レポート課題, 連絡などは Google Classroom で行う予定です.
講義を Zoom で行う場合には, Google Classroom の方へURLを掲載します.
講義動画を撮った場合は Google Classroom の方からも視聴できるようにします.

第 1回 科目ガイダンス: コンピュータサイエンスとアルゴリズム
第 2回 計算量、抽象データ型
第 3回 線形構造(1):リストと様々な操作
第 4回 線形構造(2):スタック、キュー
第 5回 木構造(1):基本概念、色々な木
第 6回 木構造(2):実現法、応用
第 7回 ハッシング
第 8回 中間試験と解説
第 9回 ヒープ・優先度つき待ち行列
第10回 探索法と2分探索木
第11回 平衡探索木(1):探索木の詳細
第12回 平衡探索木(2):その他の探索木
第13回 グラフと問題(1):グラフの表現法、最短経路問題等
第14回 グラフと問題(2):MST等、問題例の色々
第15回 期末試験と解説

なし

1週間のうちに

1. 講義参加
2. 講義後, 質問等があれば Google Classroom ストリームへ書き込む
3. 講義中に行なう質問に回答することで出席を確認します. また講義後, 確認小テストへの回答でこれを出席確認を代替する場合もあります.

が各週のタスクとなります.

また, これに加えて宿題は別途だしますので, これに任意で回答してください.

講義内容は, その週のうちに理解する(わからないことは積極的に質問する)ことを心がけてください. そのためには, 予習・復習は大事です.

また, 質問は Google Classroom へのストリーム等でおこなってもらってもOKです.

(a) 成績評価方法:宿題と試験による.

(b) 評価基準:以下の到達レベルをもって合格の最低基準とする.
(1) 各種線形構造の操作を理解しており, 具体的な実現法を説明できる.
(2) 木構造の基本的な概念と操作を理解しており, 実現法を説明できる.
(3) ハッシングの原理と実現法を理解している.
(4) 探索木の原理を説明でき, 操作法を理解している.

基本的なオフィスアワーは月曜日4限をあてていますが, 会議等で不在の場合もあるので, メールで事前に調整を行うことが望ましいです.

アルゴリズムとデータ構造は, 構造化プログラミングの基礎となる考え方が多く, 計算量という考え方で評価を行います. この考え方は, 計算機科学で重要な概念となります.

なし