2025年度 (最新) 学院等開講科目 工学院 経営工学系
プログラミング応用
- 開講元
- 経営工学系
- 担当教員
- 塩浦 昭義 / 清水 伸高
- 授業形態
- 講義/演習
- メディア利用科目
- -
- 曜日・時限
(講義室) - クラス
- -
- 科目コード
- IEE.A230
- 単位数
- 110
- 開講時期
- 2025年度
- 開講クォーター
- 3Q
- シラバス更新日
- 2025年3月19日
- 使用言語
- 日本語
シラバス
授業の目的（ねらい）、概要
本講義では、Pythonを用いて基本的なデータ構造とアルゴリズムについて学ぶ。
講義と演習(各100分ずつ)を通して、問題解決のためにプログラミングを用いる能力を養う。
到達目標
本講義を履修することにより、以下の知識と能力を習得する。
1) 基本的なPythonの使い方の習得
2) 基本的なデータ構造とアルゴリズムの理解
3) アルゴリズムによる効率性の違いを理解
4) アルゴリズムを実装する力
キーワード
Python、プログラミング、アルゴリズム
学生が身につける力
- 専門力
- 教養力
- コミュニケーション力
- 展開力 (探究力又は設定力)
- 展開力 (実践力又は解決力)
- 様々なアルゴリズムとそれをPythonのコードに翻訳する能力
授業の進め方
各講義の1/2は講義形式で行い、残りの1/2は演習に充てる。
授業計画・課題
| 授業計画 | 課題 | |
|---|---|---|
| 第1回 | ガイダンス アルゴリズムの基礎 再帰関数 演習 | Pythonによる基礎的なアルゴリズムや再帰関数を理解し実装する。 |
| 第2回 | アルゴリズムの計算量 グラフの定義の導入 幅優先探索と深さ優先探索 演習 | アルゴリズムの計算量のオーダー記法による概念と計算機上でのグラフの表現(隣接行列と隣接リスト)を理解し、これに基づいてグラフ上の探索問題に対するアルゴリズムを応用する。 |
| 第3回 | 貪欲法 最小全域木問題 演習 | 組合せ最適化アルゴリズムの中で最も基礎的な貪欲法の枠組みを説明し、その応用として最小全域木問題をはじめとして様々な問題の解法を理解し応用する。 |
| 第4回 | 最短経路問題 ダイクストラ法とヒープ 演習 | グラフ上の最短経路問題とダイクストラ法による解法を説明する。効率的なダイクストラ法の実装に用いるためにヒープと呼ばれるデータ構造の内部も説明し、演習ではこれらを応用した問題を出題する。 |
| 第5回 | 動的計画法 ナップザック問題 演習 | 動的計画法の枠組みその応用としてナップザック問題をはじめとした様々な問題の解法を説明する。 |
| 第6回 | マッチング フロー 演習 | グラフ上の基礎的な組合せ最適化問題として最大マッチング問題と最大フロー問題を説明し、交互路に基づくアルゴリズムやフォードファルカーソン法について説明する。演習ではこれらのアルゴリズムを応用して解く問題を出題する。 |
| 第7回 | 計算量理論の入門 帰着とNP困難性 演習 | 問題が効率的に解けないことの論拠の一つとして帰着やNP困難性の概念を導入する。 |
準備学修(事前学修・復習)等についての指示
学修効果を上げるため，教科書や配布資料等の該当箇所を参照し，「毎授業」授業内容に関する予習と復習（課題含む）をそれぞれ概ね100分を目安に行うこと。
教科書
特になし
参考書、講義資料等
Guido van Rossum: Pythonチュートリアル 第２版
Mark Lutz: 初めてのPython 第3版
成績評価の方法及び基準
毎週出題される演習課題によって評価
関連する科目
- IEE.A207 ： プログラミング基礎（経営工学）
履修の条件・注意事項
受講は経営工学系の学部生に限定する。
Pythonの基礎的な使い方の習得を前提とする。プログラミング基礎（経営工学）の履修を強く推奨する。
その他
対面授業の際はPCを持参すること。
講義資料はipynbファイルで配布するため、Googleアカウント（無料）を作成しgoogle colaboratoryを開くまたはjupyter notebookをインストールするなどでipynbファイルが開ける環境が必須（詳細は初回講義で説明する）。
主にSlackを用いて連絡することもあるので、全学Slackを利用できるようにすることが非常に望ましい。
全学Slackの利用方法は以下のURLを参照:
https://www.dx.titech.ac.jp/fresh_st/