シラバス参照

講義概要/Course Information
2024/06/20 現在

科目基礎情報/General Information
授業科目名
/Course title (Japanese)		 アルゴリズム論第一（３クラス）
英文授業科目名
/Course title (English)		 Algorithms Ⅰ
科目番号
/Code		 COM402a COM402b COM402c COM402d COM402e
開講年度
/Academic year		 2024年度 開講年次
/Year offered		 2
開講学期
/Semester(s) offered		 後学期 開講コース・課程
/Faculty offering the course		 情報理工学域
授業の方法
/Teaching method		 講義 単位数
/Credits		 2
科目区分
/Category		 専門科目
開講類・専攻
/Cluster/Department		 Ⅰ類
担当教員名
/Lecturer(s)		 大森・新谷
居室
/Office		 西10-528
公開E-mail
/e-mail		 omori[at]is.uec.ac.jp, shintani[at]is.uec.ac.jp
授業関連Webページ
/Course website		 Google Classroom を2024年度用に用意する．
更新日
/Last update		 2024/03/05 22:12:28 更新状況
/Update status		 公開中
/now open to public
講義情報/Course Description
主題および
達成目標（2,000文字以内）
/Themes and goals（up to 2,000 letters）		 情報の分野では，対象とする現実世界の諸問題の離散的な構造を把握・表現して効率的に扱うために，アルゴリズム・データ構造を学ぶことが必須である．本講義では，データ構造・アルゴリズムの基本と特性について， 理論的および直感的に理解し説明する方法を学び，コンピュータ上での実現方法を修得する．単純なデータ構造から始めて，ハッシュ法， 木・グラフなどを用いた問題の構造の記述・理解と効率的処理技法を修得する．
　本講義によって，高校数学・大学初年次までに学んだ線形代数・確率統計・数列などの基礎数学と合わせ，情報分野で必須な基本的な数学の知見を修得することも目標とする．
前もって履修
しておくべき科目（1,000文字以内）
/Prerequisites（up to 1,000 letters）		 C言語によるプログラミングの履修が望ましい．特に，プログラミング通論．基礎プログラミングおよび演習.

前もって履修しておくこ
とが望ましい科目（1,000文字以内）
/Recommended prerequisites and preparation（up to 1,000 letters）		 同上．
教科書等（1,000文字以内）
/Course textbooks and materials（up to 1,000 letters）		 資料は毎回独自のものを作成し配布しています．毎年の講義資料はほぼ安定しているので今年度のGoogle Classroomには，昨年度の授業資料を最初にまとめて掲載する予定です．また，毎回の授業資料はこのクラスルームに前の週には掲載します．　代表的な学部教科書15回に相当する入門的な教科書や専門的教科書は，授業初回に紹介します．2023年度の授業資料PDFを今年度クラスルームの最初に，まとめて掲載する予定．

参考書として，最近出た学部2年・3年向け授業15回のために作られた以下の本をあげておきます：

西尾章治郎　監修，原，水田，大川著，
「アルゴリズムとデータ構造」，（未来へつなぐデジタルシリーズ10），
共立出版　（2400円）．

他に，アルゴリズムの専門的な授業で必須とされる教科書は，以下の2種類です．上記で載っていない項目については，これらが参考に，なります．分厚いので，項目を選んで調べるのに適す：

*1 (i) 　R.セジウィック著，「アルゴリズムC」　第１巻～第３巻．近代科学社，
   (ii) R.セジウィック著／野下浩平・星守・佐藤創・田口東 共訳：アルゴリズムＣ・新版─基礎・データ構造・整列・探索，近代科学社，2004年．（内容は(i)と近く，こちらのほうが新しい本です）．


*2  T.コルメン他著，「アルゴリズムイントロダクション第３版」全3巻．
　　特に，第１巻（計算量，ヒープ，3章のデータ構造）と第２巻（VI.グラフ）
　　近代科学社，（2013年に，1冊にまとめた統合版が出ています）.
    MITの標準教科書です．

専門書は分厚いので，学部向け日本語教科書は断片的に話題をとりあげて編集されています．そのため一冊の学部向け入門書ではなかなかこの講義全体をカバーしきれません．講義のうち特に後半の，平衡探索木（2－3木），グラフのアルゴリズム，の紹介は，下記の入門書も参考になります：

＊「データ構造とアルゴリズム」（五十嵐建夫，数理工学社）（サイエンス社）．
　（比較的最近の新しい入門書．前半のうちハッシュやヒープ，2分探索，後半の平衡木以後，などの解説は簡潔にまとまっている．疑似コードによる解説．演習解答つき）

＊「アルゴリズムとデータ構造」（岩波講座ソフトウェア科学３）（石畑清，岩波書店）
　　　　（かなり古くて絶版に近いが図書館などにはある．疑似コードがPascal. 内容は充実している）

です．
授業内容と
その進め方（2,000文字以内）
/Course outline and weekly schedule（up to 2,000 letters）		 I類の2年後期科目として3クラスでの編成実施のうち第3クラスを大森・新谷で担当します．扱う項目はクラス間でほぼ合わせてあります．初回がガイダンス，新谷が前半7回を担当し，後半７回を大森が担当．前半後半の回数は状況によって多少変動します．
-------------------------------
本授業の内容は，下記を基本として行います．項目ごとの講義の回数や順序は多少変更する可能性があります．また，前半7回か8回目の時点で，学生の理解度を調べるため，復習まとめに相当する回を入れる場合があります．これは，最後の「先進的話題」の回も，同様です．

0．ガイダンス（第1回）
1．アルゴリズムと計算量、抽象データ型（第2回）
2．基本データ構造(第3, 4回）
　　- 線形構造(1)：リストと様々な操作
　　- 線形構造(2)：スタック、キュー
3．木（第5回）
　　- (1)：基本概念、色々な木
　　- (2)：実現法、応用

４．ハッシュ法，トライなど　（第6回）
   - 集合を扱うデータ構造

5．ヒープと優先度つき待ち行列　（第7回）
6．２分探索木　（第8回）
---------------
6'. 基数探索とトライ　　(第9回）
7．平衡探索木　（第10，11回）
　　(1)：平衡探索木の詳細(2-3木，AVL木）(第10回）
　　(2)：その他の平衡探索木(2-3-4木，B木, 赤黒木)　（第11回）

8．グラフのアルゴリズム　（第12，13, 14回）
　　(1)：グラフの表現法、単一出発点最短経路問題　（第12回）
　　(2): 全頂点間の最短経路問題，グラフの深さ優先探索　（第13回）
　　(3)：コスト最小極大木，二重連結問題，など応用編　（第14回）

9．まとめと計算量・マスター定理など先進的な話題　（第15回）

（全15回）．
実務経験を活かした
授業内容
(実務経験内容も含む)
/Course content utilizing practical experience
授業時間外の学習
（予習・復習等）（1,000文字以内）
/Preparation and review outside class（up to 1,000 letters）		 離散系の数学とアルゴリズム論は表裏一体であり，情報系のシステムソフトウェア設計や問題解決法を考えるときの基本的な言語です．微積分や確率とは異なるため，情報やIT，ビッグデータなどに興味があって入学したものの「数学的な基本」の違いに戸惑う学生諸君もいるでしょう．履修学生がアルゴリズム系の教科書やネット解説を自分で読んで，そこに書かれた文章の意味を理解し，教員へ積極的に質問できる，ようになってもらうと良いです．授業時間外でも積極的に質問に来てください．
成績評価方法
および評価基準
（最低達成基準を含む）
（1,000文字以内）
/Evaluation and grading
（up to 1,000 letters）		 途中の宿題と，期末筆記試験によります．
以下の到達レベルをもって合格の最低基準としています．
    (1) 各種線形構造の操作を理解しており，具体的な実現法を説明できる．
    (2) 木構造の基本的な概念と操作を理解しており，実現法を説明できる．
    (3) ハッシングの原理と実現法を理解している．
    (4) 探索木の原理を説明でき，操作法を理解し再現できる．
　 (5)グラフを用いた初等的な問題と解法アルゴリズムの理解と事例に適用できる．

成績評点は，全15回にわたる宿題の得点をX, 期末筆記試験の得点率をY％としたとき，総合点= X + (100-X)*Y  を100点満点における最終的な成績点とします．宿題の大半は必須としていませんでしたが最近の履修者の傾向を見た結果，必須扱いの回を増やすなどして読解力・記述力の向上を図る可能性があり，そのときは総合点計算式は若干変更されます．
オフィスアワー：
授業相談（1,000文字以内）
/Office hours（up to 1,000 letters）		 平日午後なら6時までなら随時．授業終了後にその場で質問いただいたり，電子メールで時間を相談して居室（西10号館528号室）にて相談とします．新谷・大森どちらでも対応します．
学生へのメッセージ（1,000文字以内）
/Message for students（up to 1,000 letters）		 資料や授業の内容が，その解説に向き合ったとき，言語として頭に入ってこない場合があるかもしれません．そのときは，自分で読んでわかる，アルゴリズムの薄い教科書を探して，それを最初に通して読むことを勧めます．参考書で挙げたもののうち，解説の平明な日本語教科書はそのためのものです．アルゴリズムの基本を理解することはCプログラミングを読み書きすることとも違うので，Cで学ぶアルゴリズム，などのC言語主体のプログラミングの教科書とは違う視点からの講義として考えていただき，毎回の授業や宿題などで疑問に感じた点を積極的に質問してください．
その他
/Others		 過年次の学生はどのクラス1~3のどのクラスを選択しても良い．現役学生については，合理的理由があれば希望クラス担当教員の了解をとってもらえば他クラスを履修して良いです．履修登録締め切り後のクラス変更はお断りします．
キーワード
/Keywords		 アルゴリズム，正当性，停止性，計算量，データ構造，線形構造，木構造，ハッシュ法，ヒープ，探索木，平衡探索木，グラフ