アルゴリズム論（アルゴリズム論１）のシラバス情報
| 科目名称 Course title(Japanese) |
アルゴリズム論 | 科目番号 Course number |
14ISCIP302 | |
|---|---|---|---|---|
| 科目名称（英語） Course title(English) |
Algorithm | |||
| 授業名称 Class name |
アルゴリズム論（アルゴリズム論１） | |||
| 教員名 | 胡 艶楠 |
|---|---|
| Instructor |
| 開講年度学期 | 2022年度 前期 |
|---|---|
| Year/Semester |
| 曜日時限 | 金曜2限 |
|---|---|
| Class hours |
| 開講学科 Department |
理学部第一部 応用数学科 |
|---|---|
| 外国語のみの科目 （使用言語） Course in only foreign languages (languages) |
- |
| 単位 Course credit |
2.0 | 授業の主な実施形態 Main class format |
ハイフレックス型授業/Hybrid-Flexible format |
|---|
| 概要 Descriptions |
与えられた問題をコンピュータで解くにはプログラムが必要である．プログラムの元になる計算手続きをアルゴリズムという．本講義はアルゴリズムを設計するための基礎な技術， 分割統治法，動的計画，欲張り法などを説明する． また， アルゴリズムの計算効率を評価する方法，評価する基準，計算量を求める方法などを紹介する． |
|---|---|
| 目的 Objectives |
本科目はアルゴリズムを設計するための基礎な技術およびアルゴリズムの計算効率（計算量）の評価を修得することを目的とする． |
| 到達目標 Outcomes |
実際の問題を数理的に定式化する能力，および，定式化に基づいて効率的なアルゴリズムを設計する能力を身につける． |
| 履修上の注意 Course notes prerequisites |
特になし |
| アクティブ・ラーニング科目 Teaching type（Active Learning） |
|||
|---|---|---|---|
| 課題に対する作文 Essay |
- | 小テストの実施 Quiz type test |
|
| ディベート・ディスカッション Debate/Discussion |
あり | グループワーク Group work |
あり |
| プレゼンテーション Presentation |
あり | 反転授業 Flipped classroom |
あり |
| その他（自由記述） Other（Describe） |
- | ||
| 準備学習・復習 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 |
・教科書を使用する場合は、MyKiTS(教科書販売サイト)から検索・購入可能ですので以下のURLにアクセスしてください。 https://gomykits.kinokuniya.co.jp/tokyorika/ ・Search and purchase the necessary textbooks from MyKiTS (textbook sales site) with the link below. 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回：まとめ 全体の復習と演習を通して授業全体の理解を深める． |
|---|
| 教職課程 Teacher-training course |
|
|---|---|
| 実務経験 Practical experience |
|
| 教育用ソフトウェア Educational software |
| 備考 Remarks |
|---|
| 9914B71 |
