2025年度前期離散数学

曜日・時限 月曜日２時限 期別 前期 週時間数 2
ナンバリング GP320711
開講学科等 情報通信工学部-情報工学科
教員名 上嶋　章宏
上嶋　章宏
職務履歴

https://research.osakac.ac.jp/index.php?%e4%b8%8a%e5%b6%8b%e3%80%80%e7%ab%a0%e5%ae%8f

教員情報データベースに遷移します

目的

近年の情報技術の発展とともに，離散的な事柄を取り扱うことは増々多くなり，離散数学の重要性は非常に高いものとなっている。離散数学は，情報科学やコンピュータ・サイエンスの基礎数学であり，有限のシステムを対象とする離散系の数学である。本講義では情報工学・情報科学のあらゆる分野に現れる数学の理論を身につけ論理的な思考を行う基礎能力の体得を目的とする。離散数学は集合論，グラフ理論，組合せ理論，代数系，命題論理，ブール代数などから構成されるが，本講義では離散数学の中から「組合せ理論」および「グラフ理論」を取り上げ，その基礎について学び，離散数学の基礎的な概念・知識，基本的な定理および証明を理解できるようになる。

授業計画

授業回 形式 学修内容 学修課題
1 A,C 離散数学の基礎 事前学修 シラバスを読んで，関連科目を復習してくる（2時間）
事後学修 現実の諸問題と数理モデルとの関連を復習する（3時間）
2 A,C 証明手法：鳩の巣原理，対偶証明法，背理法，帰納法 事前学修 様々な証明手法について予習してくる（2時間）
事後学修 証明手法の枠組みと適用時の注意点を復習する（3時間）
3 A,C グラフの基礎（１）：グラフの定義，次数の数理 事前学修 離散グラフとその表現法について予習してくる（2時間）
事後学修 グラフの基礎的な概念を整理し、取り上げた証明を復習する（3時間）
4 A,C グラフの基礎（２）：道と閉路の数理 事前学修 隣接行列表現と歩道の数との関係について予習してくる（2時間）
事後学修 用語の定義と行列の取り扱い、講義した証明法を復習する（3時間）
5 A,C グラフの基礎（３）：木構造の数理 事前学修 木構造とグラフ探索について予習してくる（2時間）
事後学修 木構造の数理的性質およびその証明を整理し復習する（3時間）
6 A,C グラフ上の経路 事前学修 根付き木，最短路，最小木について予習してくる（2時間）
事後学修 経路・閉路に関連する概念を整理し復習する（3時間）
7 A,C グラフの連結性 事前学修 連結性について予習してくる（2時間）
事後学修 連結性に関連するグラフの部分構造抽出方法について復習する（3時間）
8 A,C グラフの平面描画 事前学修 グラフの平面描画について予習してくる（2時間）
事後学修 平面描画におけるオイラーの公式に関する証明を復習する（3時間）
9 A,C オイラーグラフ，ハミルトングラフ 事前学修 オイラー路，ハミルトン路について予習してくる（2時間）
事後学修 種々の路・閉路に関する概念および存在性を示す必要十分条件の証明手順を復習する（2時間）
10 A,C グラフ彩色と平面グラフ 事前学修 グラフ彩色について予習してくる（2時間）
事後学修 グラフ彩色および双対グラフに関する性質を復習する（2時間）
11 A,C グラフ彩色と次数の関係 事前学修 閉路長や次数と，彩色可能性の間にある関係を予習してくる（2時間）
事後学修 ノートを整理し復習する（2時間）
12 A,C 2部グラフとマッチング・点被覆 事前学修 グラフ上でのマッチングおよび点被覆，マッチングと点被覆の関係について予習してくる（2時間）
事後学修 2部グラフの定義・特徴づけ，マッチングの概念，マッチングの最大性に関する特徴づけを復習する（2時間）
13 I 学習到達度の最終確認 事前学修 授業で学んできた内容を総合的に復習してくる（2時間）
事後学修 分からなかったところをしっかり復習し，学修到達の不充分な点に取り組む（2時間）

授業形式記号

  • A:一斉授業（通常の講義）
  • B:問題発見・解決学習、プロジェクト学習
  • C:体験、実験、実習、演習など
  • D:調査 分析、解析など
  • E:ものづくり、作品制作
  • F:グループワーク（ディスカッション・ディベートを含む）
  • G:プレゼンテーション
  • H:地域・企業　連携型学習
  • I:その他

到達目標

到達目標は次の通りである。

○修得する資質・能力：知識・理解力【DP-P-1-1】
　・集合，関数，関係などの基礎を理解できる
　・離散グラフと木構造について理解できる
　・グラフ理論とその応用について理解できる

○修得する資質・能力：応用力【DP-P-2-2】
　・様々な証明手法を理解し応用できる
　・組合せ理論およびグラフ理論における基礎概念や性質を理解し応用できる

評価方法と評価観点

評価方法 配点合計知識・理解力応用力コミュニケーション力態度・志向性創造力 合計
定期試験またはレポート試験 0%
小テスト、小論文 50% 80% 20% 100%
グループワーク 0%
プレゼンテーション 0%
レポート、宿題 25% 70% 30% 100%
授業での姿勢（ノート、質疑など） 10% 60% 40% 100%
作品、パフォーマンス（実技、実演） 0%
その他1(具体的に： 授業内で実施する演習形式の課題::::: 15% 80% 20% 100%
その他2(具体的に： 0%
100% 76% 24% 0% 0% 0% 100%

教科書・参考書

講義内で参考書を適時紹介する。

オフィスアワー

研究室を訪問する場合は，電子メールなどで事前にアポイントを取ることが望ましい。
前期月曜5限（A号館2階教員室15）

なお，学内外の用務のため，オフィスアワーでも教員が教員室に不在の可能性がある。

その他

事後学修の内容をレポートや宿題の形で応用力や学習進度を確認するので，授業中の指示を聞き洩らさない。
授業内外の課題について，解答あるいは考え方を適宜解説する。

本講義の内容は，2年次開講の「知能情報科学基礎」と関連があり，3年次の「アルゴリズム設計論」との係わりが深い。

実務経験のある教員による授業科目

戻る