| 対象年度 | 2004 |
| 教育課程名 | 昼間コース 主専門教育課程 学科別科目 |
| 授業科目名 | 情報工学選択演習A |
| Subject Name | Information Engineering Optional Practice A |
| 単位数 | (0.5) |
| 必修・選択の別 | 選択 |
| 対象学科・学年 | 情報工学科3年 |
| 開講時期 | 前期 |
| 授業方法 | 演習と講義 |
| 担当教官 | 施 建明 (Jianming SHI) |
| 教官室番号 | V514 |
| 連絡先（Tel） | 0143-46-5423(内線 5423) |
| 連絡先（E-Mail） | shi@csse.muroran-it.ac.jp |
| 授業のねらい | 離散数学の面白さを、UNIX上でＣ言語を用いる実践的な演習を通して、体験する。たま、理論的な結果と実験でえられる結果との関係を理解し、論理的な考え方の理解を深める。 |
| 授業の目標 | １．離散最適化問題を学び、離散構造とアルゴリズムの理解を深める。 ２．実践的な演習を通して離散最適化問題の理解を深める。 ３．離散数学問題を通じて論理的な思考を養う。 |
| 授業計画 | 1週目：グラブの表現(講義と実験) ２週目：最大流問題と最小カット（講義と実験） ３週目：Ford-Fulkersonのアルゴリズムとその正当性（講義と実験） ４週目：Ford-Fulkersonのアルゴリズムの計算量，欠点とその改善(講義と実験） ５週目：離散最適化の歴史と離散数学の幾つかの話題(講義と実験） |
| 教科書及び教材 | 演習用の資料を配布して、演習時間中に解説する。 |
| 参考書 | 岩野和生（1993），ネットワークフロー問題の最近の発展，藤重 悟 編:離散構造とアルゴリズムII， 近代科学社 pp79-153． （工大図書館にあり） 浅野孝夫（1994），情報の構造ーデータ構造とグラフアルゴリズムー，日本評論社 |
| 成績評価方法 | レポート（5回）の平均で評価する．提出期限までにレポートの提出が無いものは成績評価の対象とせず不合格とする。 |
| 履修条件等 | 本演習は、Ｃ言語によるプログラミングが可能なことを履修条件とする。 |
| 教官からのメッセージ | 離散最適化が難しいが、理論的結果を実践的な演習を通して、その面白さを実感できることが期待されます。 たま、質問があったら、積極的に聞きに来て下さい。 オフィスアワー：13：30-14：30（毎週木曜日） |
| その他 | なし |