離散構造とアルゴリズム

開講元

情報通信系

担当教員

髙橋 篤司

授業形態

講義/演習 (対面型)

メディア利用科目

-

曜日・時限
(講義室)

月5-8 (SL-101(S011)) / 木7-8 (SL-101(S011))

クラス

-

科目コード

ICT.M215

単位数

210

開講時期

2024年度

開講クォーター

4Q

シラバス更新日

2025年3月17日

使用言語

日本語

シラバス

授業の目的（ねらい）、概要

本講義では，コンピュータ及び情報処理において必須となる離散的情報あるいは離散的構造を取り扱うための基本的な考え方を理解し，離散的情報あるいは離散的構造を取り扱う基本的な手法を習得することを目的とします。

到達目標

本講義を履修することによって，グラフ理論の基礎概念を理解し，アルゴリズムの設計と解析に関する基本的な手法を修得することを到達目標とします。さらに，アルゴリズムの原理および離散構造の特徴とアルゴリズムの効率との関連を理解し，基本的な手法を情報通信工学で応用できるようになることを目標とします。

キーワード

グラフ，アルゴリズム，計算複雑度

学生が身につける力

• 専門力
• 教養力
• コミュニケーション力
• 展開力 (探究力又は設定力)
• 展開力 (実践力又は解決力)

授業の進め方

コンピュータ及び情報処理において離散的情報あるいは離散的構造を取り扱うことは必須である。本講義では，アルゴリズム的な観点から基本的なグラフに関する性質を論じるとともに，アルゴリズムの解析に関する基本的な概念，および，グラフの基本的なアルゴリズムを取り扱う。また，アルゴリズムの設計技法の概略，NP完全の理論の概略を紹介する。原則として，２回の講義に対して1回の演習を行います。演習では、直前２回の講義の内容について具体的な問題を取り入れた演習を行い、それによって受講生は座学で学んだ知識と手法を現実的課題に適用できるようになります。

授業計画・課題

準備学修(事前学修・復習)等についての指示

学修効果を上げるため，教科書や配布資料等の該当箇所を参照し，「毎授業」授業内容に関する予習と復習（課題含む）をそれぞれ本学の学修規程で定められた時間を目安に行う。

教科書

情報とアルゴリズム，上野，高橋著，森北出版，2005

参考書、講義資料等

特になし

成績評価の方法及び基準

グラフ理論の基礎概念及びアルゴリズムの設計と解析に関する基本的な手法に関する理解度を評価する。中間試験・期末試験（94％），演習（6％）で成績を評価する。

関連する科目

• ICT.M202 ： 確率と統計（情報通信）
• ICT.M306 ： コンピュータ数学
• ICT.M310 ： 数理計画法
• ICT.M316 ： 数値解析（情報通信）

履修の条件・注意事項

履修の条件を設けない