アルゴリズム論（アルゴリズム論１）

科目授業名称（和文）　Name of the subject/class (in Japanese)

アルゴリズム論（アルゴリズム論１）

科目授業名称（英文）　Name of the subject/class (in English)

Algorithm （アルゴリズム論１）

授業コード　Class code

9914B71

科目番号　Course number

14ISCIP302

教員名

胡　艶楠

Instructor

Yannan Hu

開講年度学期

2023年度前期

Year/Semester

2023, first semester

曜日時限

金曜2限

Class hours

Friday, 2nd period

開講学科・専攻　Department

理学部第一部　応用数学科

Department of Applied Mathematics, Faculty of Science Division Ⅰ

単位数　Course credit

2.0単位

授業の方法　Teaching method

講義

Lecture

外国語のみの科目（使用言語）　Course in only foreign languages (languages)

-

授業の主な実施形態　Main class format

対面/on-site

概要　Description

与えられた問題をコンピュータで解くにはプログラムが必要である．プログラムの元になる計算手続きをアルゴリズムという．本講義はアルゴリズムを設計するための基礎な技術，分割統治法，動的計画，欲張り法などを説明する．また，アルゴリズムの計算効率を評価する方法，評価する基準，計算量を求める方法などを紹介する．

目的　Objectives

本科目はアルゴリズムを設計するための基礎な技術およびアルゴリズムの計算効率（計算量）の評価を修得することを目的とする．

到達目標　Outcomes

実際の問題を数理的に定式化する能力，および，定式化に基づいて効率的なアルゴリズムを設計する能力を身につける．

卒業認定・学位授与の方針との関係（学部科目のみ）

専門応用能力

履修上の注意　Course notes prerequisites

特になし

アクティブ・ラーニング科目　Teaching type（Active Learning）

小テストの実施　Quiz type test／ディベート・ディスカッション　Debate/Discussion／グループワーク　Group work／プレゼンテーション　Presentation

-

準備学習・復習　Preparation and review

前回の内容のノートを見返して復習し，やり残した部分を完成しておく．クラスメイト同士でディスカッションをしておく．

成績評価方法　Performance grading policy

授業中に課題を与える．またグループに分かれて演習問題に取り組み，プレゼンテーションしてもらう．演習課題とプレゼンテーションにより成績を総合的に評価する．

学修成果の評価　Evaluation of academic achievement

・S：到達目標を十分に達成し、極めて優秀な成果を収めている
・A：到達目標を十分に達成している
・B：到達目標を達成している
・C：到達目標を最低限達成している
・D：到達目標を達成していない
・-：学修成果の評価を判断する要件を欠格している

・S：Achieved outcomes, excellent result
・A：Achieved outcomes, good result
・B：Achieved outcomes
・C：Minimally achieved outcomes
・D：Did not achieve outcomes
・-：Failed to meet even the minimal requirements for evaluation

教科書　Textbooks/Readings

教科書の使用有無（有=Y , 無=N）　Textbook used(Y for yes, N for no)

N

書誌情報　Bibliographic information

-

MyKiTSのURL（教科書販売サイト）　URL for MyKiTS(textbook sales site)

教科書および一部の参考書は、MyKiTS (教科書販売サイト) から検索・購入可能です。
It is possible to search for and purchase textbooks and certain reference materials at MyKiTS (online textbook store).
https://gomykits.kinokuniya.co.jp/tokyorika/

参考書・その他資料　Reference and other materials

【参考書】
・　茨木俊秀，「Cによるアルゴリズムとデータ構造」，オーム社
・　T. H. Cormen et al., Introduction to Algorithms, MIT press
・　J. Kleinberg and E. Tardos, Algorithm Design, Addison-Wesley
・　M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman

授業計画　Class plan

第1回：アルゴリズムの一般的定義
この授業の概要およびアルゴリズムについて理解する．
専門用語などを覚える．

第2回~第3回：計算量の評価
計算量の上下界の評価とオーダー表記を理解する．
基本的な関数の増加速度を理解する．
計算量を求める際の数学基礎を紹介する．

第4回：整列アルゴリズム
代表的なソーティングアルゴリズム，　挿入ソート，バブルソート，ヒープソート，バケットソート，基数ソートを学習する．

第5-7回：分割統治法
マージソートとクイックソートをを用いて，問題の再帰的な構造と分割統治法のアイデアを学習する．
最近点対の発見問題と整数の積の計算問題に対する分割統治法を通じて分割統治法の枠組みの理解を深める．

第8-10回：　動的計画法
最短路問題を用いて，動的計画法のアイデアを学習する．
部分和問題と重み付き区間スケジューリング問題を通じて動的計画法の枠組みの理解を深める．

第11-13回：欲張り法
活動選択問題を用いて，欲張り法の原理を学習する．
Huffman符号問題と最小全域木問題に対する欲張り法を通じて枠組みの理解を深める．

第14回：ネットワークフロー
最大フロー問題とFord-Fulkersonアルゴリズムを学習する．

第15回：まとめ
全体の復習と演習を通して授業全体の理解を深める．

授業担当者の実務経験　Work experience of the instructor of the class

教育用ソフトウェア　Educational software

-

備考　Remarks

シラバス情報