QuickSyllabus

アルゴリズム論

前期水曜日２講時. 単位数/Credit(s): 2. 対象学科・専攻/Departments: 情報基礎科学専攻、システム情報科学専攻、応用情報科学専攻. 学期/Term: 前期. 履修年度: 2024. 使用言語: 日本語（ただし配布資料や定期試験における出題等は英語）.

開講年度

2024

授業題目/Class Subject

　アルゴリズム論　Introduction to Algorithm Theory

授業の目的・概要及び達成方法等

アルゴリズムは、今やシステムの信頼性や高速性を握る重要な鍵となっている。とりわけ、高い信頼性を実現するためには、正しいアルゴリズム開発の知識が必須である。本講義では、アルゴリズムを計算機科学の観点から理論的に学び、その基本的な設計法や解析法を体得する事を目的とする。本講義では、並列アルゴリズム、近似アルゴリズム、確率的アルゴリズムなども取り入れ、アルゴリズムの身近な応用についても触れていきたい。

授業の目的・概要及び達成方法等(Ｅ）

Algorithms now play a very important role for the reliability and efficiency in several social systems. This course focuses on design and analysis of algorithms from the viewpoint of theoretical computer science. We deal with parallel algorithms, approximation algorithms, randomized algorithms etc. We also show some applications of algorithm theory to practical problems.

学修の到達目標/Goal of Study

本講義では、アルゴリズムを計算機科学の観点から理論的に学び、その基本的な設計法や解析法を体得する事を目標とする。

This course focuses on design and analysis of algorithms from the viewpoint of theoretical computer science.

授業内容・方法と進度予定/Contents and progress schedule of the class

［Google Classroomのコード： nrykyf5 ］

１．概要説明
２．アルゴリズムの評価
３．分割統治法
４．演習１
５．動的計画法
６．よくばり法
７．演習２
８．NP完全
９．前処理
１０．演習３
１１．並列アルゴリズム
１２．近似アルゴリズム
１３．確率的アルゴリズム
１４．演習４
１５．本講義のまとめと試験

(The code for Google Classroom: nrykyf5 )
1. Introduction
2. Evaluation of Algorithms
3. Divide and Conquer
4. Exercise 1
5. Dynamic Programming
6. Greedy Algorithms
7. Exercise 2
8. NP-Completeness
9. Preprocessing
10. Exercise 3
11. Parallel Algorithms
12. Approximation Algorithms
13. Randomized Algorithms
14. Exercise 4
15. Conclusions and Examination

成績評価方法/Evaluation Method

出席、レポート、試験により総合的に評価する。

Evaluation is performed comprehensively based on attendance count, reports, and examination.

教科書および参考書/Textbook and references

Introduction to Algorithms, T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, The MIT Press (2009)

授業時間外学修

授業前は、関連ウェブサイトに掲載する講義スライドを予習し、疑問点を整理しておくこと。授業後は、講義の復習（自分自身で計算過程を追う、証明の再構築など）を行うこと。また、講義で学んだ事柄を基に適宜文献を参照し、知識を広げ深化させることが望ましい。

授業時間外学修（Ｅ）

As a preparation for each class, students are required to check the lecture slides uploaded to the website. After the lecture, students are also required to review the lecture (in particular, reviewing the calculations and proofs by themselves). It is desirable to extend and deepen their knowledge by reading references.

オフィスアワー

随時対応しますが、メールにて予約してください。

オフィスアワー（Ｅ）

Please make an appointment by email.