終了しました
# 連絡 1 : 過去(2004-2005年度版)の講義ノートは 北海道大学学術成果コレクション(HUSCAP) からもダウンロードできます.

# 連絡 2 : レポートの提出状況確認のページを作りました. ここ からどうぞ.

# 連絡 3 : 期末試験は 9/20(水) 9:00〜10:30 B31講義室で行う予定です. 持ち込み不可.
　　　　　　※ 通常の学部3,4年生試験期間(9/6(水) - 9/19(火))外であること, 教室がいつものA21ではないことにご注意ください.

# 連絡 4 : 演習問題12に関する補足 : 各時刻でrandom walker が各バーに居る確率を 求める問題で, 配布資料(7/24)の解答例には 「計算機を使った」と述べただけで, 具体的な手続きを書きませんでしたが, その計算に際し実際に用いたC言語による簡単なプログラム, 各バーに random walker が居る確率の時間発展の図 (pdf) を下に置いておきます. E6 は吸収壁でしたから, 図でp6 は単調に増加し, t=10 程度で全ての確率は E6 に吸収され, random walker は t=10 以降, 確率1でE6に居り (p6=1), 永久にそこから抜け出せない ということになります. もちろん, 全ての確率の流れは 「E6 に食われる」わけですから, p1 〜 p5 はゼロへと向かいます.


◆Cによるプログラム random_walk_prob.c / 出力結果 matprod.txt
◆各確率の時間発展の図 (random_walk_prob.pdf)


「確率の流れ」というのがイメージしづらい場合には, バーE2に10000人の「酔っ払い」が集結し, それぞれ独立にサイコロを振って, 指定された確率で「右」「左」のバーに 移動する状況を考えてみること (※ 世の中にはこうした実例もあります). この際, 1時間後にはおおよそ 5000人の酔っ払いがE1に移動します. そして, 10時間後には 10000人の酔っ払いのほとんどがバーE6に 厄介になることになります.

有向グラフを変更し, random walker の動作規則を様々変えて調べてみたい 場合には行列 a[i][j]　の成分等を適時変えてみてください. なお, Matlab, Mathematica でも同種の計算が可能だと思います.

# 連絡 5 : 当講義の単位が卒業にとって深刻な影響がある電子工学科4年生の 皆さんへの注 : 30分以上の遅刻のため試験を受けられなかった約1名, 成績が思わしくなく60点を下回った者に対して 追加課題を与えます. ここの第1回, 2回演習問題 (解答未公開)を解き, レポートにて提出してください. (※ もちろん, レポートの内容がある基準に達したもののみ 「可」とします.) 〆切は 10/20(金) 午後5時まで . 提出先は情報科学研究科棟8-13ポストへ. 該当者の学籍番号は情報科学研究科棟1階に掲示します. ⇒ 提出のあった5名に単位を出しました (10/24)
※ 期末試験を受けなかった受講生は 期末試験のウェートが50点/100点でしたから 自動的に「不合格」となり, 上記該当者のリストには含まれておりません. 病気等の事情で試験を受けられなかった者は 早めに申し出てください.

自宅のパソコンでPDFファイル を 見るにはAdobeシステムズ からフリーで入手できる Acrobat Reader をダウンロードして使ってください.



講義目的

与えられえた問題の難しさを, 「その解は存在するか ?」「存在するとしたら, どの程度効率の良いアルゴリズムが構成 できるか ?」という観点から解析・評価するための道具を提供 するグラフ理論の基礎的な概念を説明し, 多くの例題にあたることにより, その理解と応用力を深めること を目的とする. 具体的な到達目標としては 下に挙げた教科書の各章末に載っている 演習問題が自力で解けるようになるレベルを目指す.



対象とする学生

情報工学科 3年生 [必修科目], 電子工学科 4年生 [選択科目]



講義時・場所

毎週月曜日 第3講時 A21講義室



受講条件

必要となる知識としては, 初等的な集合論と 線形代数(行列演算)のみです. また, 比較的重要と思われる定理 に関しては, その証明も講義中に説明しますが, その際には「背理法」および「数学的帰納法」 を多用するので, これらの基本的な考え方を 復習しておくと良いでしょう. 受講者はこれら関連科目を履修しているか, もしくは自習していることが望ましいですが, 実際に必要となる際にはこちらで説明をしますので, この意味では特に受講条件はないと言えます. また, 演習問題として簡単な計算機プログラミング を行ってもらう場合もありますが, この際には各受講者 のコンピュータ利用環境, 及び, プログラミング関連科目 の履修度を事前に十分調査の上, 出題することにします.



教科書

当講義は下記の教科書に従って進めますので, 受講者は生協書籍部等で必ず購入して下さい.

「グラフ理論入門」 R. J. ウイルソン著, 西関隆夫・西関裕子共訳 近代科学社 (2001) [定価 2,400円 + 税].


※ 将来的なことを考えると英語の教科書を 読み, 理解する練習をしておくのも良いと思います. その場合には下記に本(ペーパーバック)を一冊挙げておきます.
"Introductory Graph Theory" by Gary Chartrand, Dover Publicarions, New York (1985)
　　難易度は教科書よりかなり易しめなので, 講義でグラフ理論を一通り学んだ後に理解の確認として読んでみるのも よいかも知れない.

※ 上記教科書の他にも適時参考書等を紹介します.
　　また, 担当者作成による演習課題, 及び, その解答例も配布します. これらの資料は当ページからPDFフォーマットの 電子ファイルとしてダウンロード可能です. ご活用下さい.



講義の進め方

上記教科書及び配布資料に沿って担当者(井上)が解説します. なお, ほぼ毎回, 受講者の理解度を確認するための レポート課題を出します. また, 毎回出席をとることに注意してください.

※ 今年度は もう少し学生参加型の講義形態でやりたいと考えてます. レポート課題の解答を黒板 (or OHPスライド, PowerPointスライド)等 で発表した学生さんには積極的に加点する方針で行こうと思います.

情報工学演習 II (B) と関連した注意事項
講義「グラフ理論」には 「情報工学演習 II (B)」の枠中に演習が2講分用意されています.
金曜日第3講時 13:00 〜 14:30 講義室 A13講義室 + 計算機室 M152


★ 第1回 (グラフ理論(1)) : 4/21　　　⇒　　　5/29(月)
★ 第2回 (グラフ理論(2)) : 6/16　　　⇒　　　7/24(月)

※ より効果的な演習とするため, 上記のように 第1回(4/21)と5/29(月)のグラフ理論 通常講義, 第2回(6/16)と7/24(月)の通常講義を交換して行います グラフ理論のみを履修し, 情報工学演習II(B)を履修しない 学生さんは注意して下さい.

この演習では講義「グラフ理論」で学んだ事項 の理解を深めるための問題を出しますので, それを考えてもらいます. 問題等の詳細は演習HPをご覧ください.




成績の付け方

出席点・レポート課題の得点, 及び 学期末試験の成績による総合評価.

それぞれの最終成績に対するパーセンテージは次の通りとします.

★ 毎回演習レポートを課す (40%) ★ 毎回出席をとる (10%) ★ 学期末に試験を行う (50%)




問い合わせ先

当講義に関する質問は随時 : 情報科学研究科棟 8-13室 (706-7225) にて受け付けます.

電子メール : j_inoue[at]complex.eng.hokudai.ac.jp での質問も歓迎します (メールでの質問はポイントを押さえて 簡潔に).

# 注1 : 念のため, メールの件名 (subject) には 「グラフ理論に関する質問」とお書きください.
# 注2 : いかなる場合も添付ファイルは送らないで下さい (添付ファイルは受け取った時点で削除させて頂きます).



配布資料

※ 下記講義スライド(pdf) では講義中に使用した「アニメーション効果」は 見れません.

井上のページへ
2006年度 井上担当講義一覧へ
北海道大学 大学院情報科学研究科 / 井上純一 (Jun-ichi Inoue)