グラフとネットワーク
電気通信大学情報理工学域I類 (情報系)
2018年度前学期
月曜2限 (10:40-12:10)
教室：西2-101
岡本 吉央
ショートカット：
講義資料 |
コメント |
試験・成績 |
公式シラバス |
スケジュール |
過去の講義 |
過去の試験問題
講義資料
新たに掲載したとき，つぶやきます
- 7/30 (12) 平面グラフ：モデル化
- 7/23 (11) 平面グラフ：数理
- 7/2 (10) 彩色：モデル化
- 6/25 (9) 彩色：数理
- 6/18 (8) 最大流：モデル化 (2)
- 6/11 (7) 最大流：モデル化 (1)
- 5/28 (6) 最大流：数理
- 5/21 (5) マッチング：モデル化
- 5/7 (4) マッチング：数理
- 4/23 (3) 木：数理
-
スライド (5/12改訂) |
印刷用スライド (5/12改訂) |
演習問題 |
用語集 |
Jupyter Notebook (4/23改訂)
- CEDでJupyter Notebookを動かすには，Ubuntuを起動して，ターミナルに「jupyter notebook」と入力し，実行すればよいです．
- 演習問題3.5と3.11の提出締切は延長
- 4/16 (2) 道と閉路：数理
- 4/9 (1) グラフの定義と次数：数理
コメント
- 7/30 (12) 平面グラフ：モデル化
- コメントありがとうございました．
-
そういえばこんなに暑いのに「これは地球温暖化の影響」だという声を聞きません．なぜでしょうか？
---
私は聞きます．;-) トランプ大統領は地球温暖化が起きていない，という主張を持っているようなので，その意見を尊重しているのかもしれませんね．
-
範囲は6〜11回講義とのことなので、7/30の分は含まれないのですか？
---
第11回のスライドの最後まで，なので，7/23に終わらず，7/30にやった分で，第11回のスライドに含まれる内容は範囲に含まれます．
-
グラフとネットワークさん対戦よろしくお願します。
---
私はグラフとネットワークさんではありません．
-
期末テスト頑張ります．
---
私も頑張ります．
-
期末をがんばります。
---
私もがんばります．
-
試験対策を行います
---
私も行います
-
テスト頑張ります。
---
私もがんばります．
-
期末試験の勉強とレポートに追われてしんどいです
---
学期末とはそういうものなのです．「末」がつくものは大抵しんどいのです．皆さんは体験していないからわからないかもしれませんが，世紀末もそういうものだったのです．もっとしんどかったと思います．
-
ありがとうございました
---
こちらこそありがとうございました．
-
半年ありがとうございました。
---
こちらこそありがとうございました．
-
Thx:)
---
こちらこそありがとうございました．
-
:)
---
．
-
ありがとうございました。ペンシルパズルに興味があるので実験第二で教授の実験を受ける事になったらまたよろしくお願いします．
---
はい，こちらこそよろしくおねがいします．
-
演習問題が難しすぎてハゲそう．
---
ぜひ，励んで下さい．
-
「何が解決できるのか」が分かりとても良かったです．ありがとうございました．
---
「問題解決に数学を使う」という立場を強調したかったので，それが勉強できたのなら，甲斐があったと思います．ありがとうございました．
-
東北民として，東北地方の県の名前と位置が一致していて，とてもうれしかった。
---
間違えないか，いつもどきどきします．;-)
-
4色の証明が気になります
---
おそらく2時間ぐらいあれば，証明のアイディア程度は説明することができると思いますが，細かい所はコンピュータ頼りとなってしまいます．
-
美術館の監視問題が想像していたよりもシンプルで驚いた。
---
監視問題の設定やモデル化にはいろいろなものがあり，いまでも盛んに研究されています．
-
美術館定理を用いても最小の値が求められるわけではないということですか？
---
その通りですね．n/3人の監視員がいれば十分なのですが，それよりも少ない人数で監視できる場合ももちろんあるわけです．どれだけ少なく出来るのか，ということについて，美術館定理は何も教えてくれないのです．
- 7/23 (11) 平面グラフ：数理
- コメントありがとうございました．次回が最終回となります．
-
暑いです．毎日少なくとも1人熱中症で病院に運ばれているので東京オリンピックがますます不安になっています．
---
昔，バルセロナオリンピックというのがあったので，大丈夫だと思います．スペインでは，昼間の熱いときにはシエスタという昼寝をする習慣があるそうなのですが，そのように日本も変えていけばよいのではないかと思います．(もちろん，その代わりに，早朝や夜に働くことになりますが．)
-
生協のヨーグルッペが安い！嬉しい！
---
生協以外で売っているのを見たことがありません．どの辺りで入手できるのでしょうか？
-
課題が多すぎて死にそう
---
生きて下さい．
-
岡本研究室のオープンラボにあった辺の重なりを失くすゲームが平面的グラフのゲームであったと今日の授業でわかった。あのゲームは面白かった。
---
お越し頂きありがとうございました．:-)
-
試験対策がんばります。
---
はい，しっかりと準備してきてください．
-
期末試験が近いのでコツコツ対策を行っていきたいです
---
はい，しっかりと準備してきてください．
-
再提出の問題をきちんと出したいです
---
よろしくお願いします．
-
オイラーの証明が思っていたより普通に理解できて驚きました．
---
名前が付いている定理や公式は難しいものかと先入観を持ってしまいがちですが，そうでもないことがあるので，しっかりと理解したいですね．
-
オイラーの公式についてよくわかった．
---
演習問題を通して，さらに理解を深めて下さい．
-
おいらもオイラーみたいになりたいな
---
リーマンを志すよりは目標が高いように思います ;-)
-
正多面体が限られたものしかない証明が興味深かったです。
---
そうですね．実際，グラフの「頂点」や「辺」という用語は多面体の「頂点」「辺」から来ています．グラフと多面体はとても関係が深いのです．
-
小学生の時になんとなく教わったものが証明されていくのがおもしろかったです
---
そうですね．証明するということは抽象的なので，それができるようになるほど思考力が鍛えられてきているのだと思います．
- 7/2 (10) 彩色：モデル化
- コメントありがとうございました．掲載が遅くなりすみません．
-
お久しぶりです。
---
小柳ルミ子でしょうか？
-
最近暑いです。喉の渇きを覚えることが多くなりました。
---
そうですね．熱中症には十分注意して下さい．
-
西2にある自習室の設定温度が20度になっていることに驚きました．
---
低すぎますね ;-) 気付いたら，あげておいて下さい．
-
:D
---
;-)
-
昨日の試合すごかったです．世の中1発逆転は起こりうるのだなぁと思いました．岡本先生はそのような経験がありますか？
---
悪い方にはよくある気がします．;-)
-
岡本教授は学部3, 4年の際に何の分野を重点的に学んでいらっしゃいましたか
---
4年生になってからは卒業研究が中心になったと思います．3年生のときには，何かを重点的に学んだということはないと思います．
-
おにぎりっておいしいですよね。僕は昆布が好きです．
---
私は明太子が好きです．
-
2週間の休講中でたまった問題を解いてきます…… (T∧T)
---
ぜひよろしくお願いします．
-
区間グラフの図の書き方がまたよくわからなかった
---
直接質問していただければ，解決はより早いと思いますので，ぜひ直接質問をして下さい．
-
単位円グラフがしっかり理解できなかったのでがんばりたいです
---
はい，よろしくお願いします．
- 6/25 (9) 彩色：数理
- コメントありがとうございました．
-
サッカーワールドカップ
日本は一次予選突破できると思いますか？
---
応援しています ;-)
-
最近寝不足です...
---
しっかりと寝てきてください ;-)
-
普段通学に片道1時間半かかるのですが、昨日はW杯観戦で調布の友人宅に泊まったため10分で大学に着きました。調布で一人暮らししたい...
---
通学や通勤の時間をどのように使うのか，というのはとても重要だと思います．私の経験上，通学時間が短い人の行動範囲は小さくなりがちだと思います．
-
今日は天気がよくて気持ちがいいですね．
---
そうですねー．夏が近づいてきていますね．
-
最近いそがしくて演習に手をつけられてません。今週こそは!!
---
ぜひぜひ，よろしくお願いします．(^^)
-
「貪」と「貧」を書き間違えそうです。
---
「どん」と「ひん」と，読み方も違いますので，注意して下さい．
-
岡本教授は科学哲学をお好みですか．また、科学である条件に関してどうお考えですか
---
好みかどうか，という観点でいえば，好みであるわけでも好みでないわけでもありません．
○○が何であるのか，ということを規定することは，○○が何であっても重要だと思います．
-
第7回の内容が今の所一番難しかった
---
しっかりと復習をしてください．
-
最近ちょっと内容がわからないところがふえてるので復習をしっかりします．
---
わからないところは直接質問してください．そのために，まず，何がわからないのか，ということがしっかりと分かるようにして下さい．よろしくお願いします．
-
中間試験の結果が良かったので油断せず勉強して期末に向けた準備をしたい．
---
はい，よろしくお願いします．
-
直感ではわかるけれど、それを証明するのは難しいと思いました．
---
証明は文章です．「文章として表現する」ことは重要な記述ですので，しっかりと身に付けて下さい．
-
4色問題については触れないんですか!?
---
触れます．第12回の講義の内容に関係します．
-
四色定理はこれらの定理を用いて考えたんだなと感じた。
---
今日の内容との関係は第12回の講義で扱います．お楽しみに．
-
彩色の応用例に興味がでた。
---
講義ではモデル化の部分に時間を使い過ぎて，他の部分がおろそかになってしまったので，反省しています．(-_-;
- 6/17 (8) 最大流：モデル化 (2)
- コメントありがとうございました．
-
全体的な中間試験はどれ位ですか？ (平均とか)
---
すみません，何を聞かれているかわかりません．
-
答案は返してもらえますか？
---
答案は返してもらえません．
-
先週の金曜日、寒くて夏カゼをひきました．幸い熱はおさりましたがのどがすごく痛いです
---
お大事に．
-
今日大阪で大きな地震がありましたね．友人もいるので安全を願っています．
---
そうですね．日本は地震大国なので，地震とつきあって生きていくことは必然ですね．そのための備えを常に考えておくことが大切ですね．
-
日本のプロ野球での優勝可能性判定問題を問いてみたい。
---
問題を問うことは簡単にできます．ぜひ解いて，説いて下さい．
-
大リーグがお好きなのですか？
---
大リーグが好きなわけではないです．この例題は最大流の話をするときに「よく出てくる」例で，極めて標準的なのです．
-
定理を証明できないが、使える。
---
証明できることも重要ですし，使えることも重要なので，どちらもできるようになって下さい．
-
最大流の問題をこういうところで使えるのはおもしろいなと思いました
---
そうですね．その味わいをこの講義では楽しんでもらいたいのです ;-)
-
フロー難しいけどおもしろいです
---
おもしろく思っていただけて，よかったです．
-
最大流の証明は難しかったですが、現実問題に応用する方法を知って関心が強まりました。
---
残念ながら，最大流のはなしはもうおしまいです．他にもたくさん応用はありますが，それをやるには時間が足りないのです．
-
アルゴリズムの種類がたくさんあって難しい
---
覚えようとしないでください．覚えようとすると余計に難しく感じます．「忘れたら思い出せばよい」というぐらいの意識で勉強すれば十分だと思います．
-
岡本教授の中で``教養''とは何ですか。ちなみに、私の周りの文科系の大人の言う``教養''とは、膨大な知識のことでした
---
「人間らしい生活を営むための根源的な力」です．
-
文科系の方のおっしゃる``批判的思考力''、``論理的思考''がよく分からないと私は思います
---
文科系・理科系という分け方をしがちですが，あまり意味がないと思います．電通大のなかでも3つの類があって，その違いは何なのか，と，違いを強調しようとする人は多いですが，あまり意味ないと思います．
-
XD
---
(^-^;)
- 6/11 (7) 最大流：モデル化 (1)
- コメントありがとうございました．次週は今回の続きから行います．
-
実験1の意味がようやく分かりました．
---
それはよかったです ;-)
-
実験をする前にこの講義をうけたかったなと思いました．
---
講義と実験・演習は補完的であるので，合わせて，理解が深まればよいと思います．
-
中間試験お疲れ様でした．5文字のランダム文字列 (?) と成績の紐付け，面白いと思いました．
---
よい方法だと思うので用いています．他によい方法がございましたら，ご提案下さい．;-)
-
中間テストの結果が気になるので、発表時にtwitterでつぶやいていただけると助かります。
---
わかりました．そうします．
-
中間試験の採点はいつ頃に終わりそうですか。
---
終わるか，というよりは，まだ始められる状況にないので，はじめていません．
-
---
なるほど ;-)
-
ムズイ
---
簡単ならば勉強する意味はないので，難しいと感じるぐらいがよいと思っています．
-
複雑な証明だと思った。
---
「アルゴリズム」というものに慣れてくると，とても自然な発想で証明をしていることが分かると思います．一方で，アルゴリズムというものに慣れるというのはなかなか大変で，それだからこそ勉強する意味があるのだと思います．
-
とても興味深かったので家でもトランプを並べて遊んでみます
---
自分で試してみることが重要なので，ぜひ実践してみて下さい．:-)
-
テストなどで、初見の問題を時間内に解く力は、数学の能力として必要だと思いますか？
---
「数学」というものが何であるのかと規定するのかによって答えは変わってくるかもしれませんが，私にとって，数学と言うのはテストで問題を解くことではないので，その意味では必要だと思わないです．ただ，ご質問は「テスト」などで「初見」の問題を「時間内」に解くことを考えていて，その3点をどのように加味するか，慎重に考える必要もあるかもしれません．
「テストなどで」を外して，「初見の問題を時間内に解く力」というのは数学に限らず重要だと思います．人生は初見の問題ばかりです．また，人生は時間に限りがあります．つまり，人生は初見の問題を時間内に解くことをずっと行っていることになります．そのような営みが生活であるわけですから，それが重要でないわけがありません．勉強するということが，問題を解くための技術と知恵を身に付けて，人間としての生活を営んでいくための基盤を育むことだとしっかりと理解する必要があると思います．
-
数学の専門書をひたすらお読みになって、数学を学ばれましたか．
---
数学の専門書をひたすら読んだことはないので，質問に対する回答はNoです．「ひたすら」でなければ，回答はYesだと思います．講義を聞いたり，論文を読んだりして学ぶこともあります．
-
レポートがたてこんでいてしんどいです。
---
お疲れ様です．
-
提出日が近い課題にほとんど手がついていなくて、かつ、意欲も湧かないということは、岡本教授にはありませんか。もし、ありましたら、その際に、何をなさるか教えてください。
---
あると思います．その時に何をするのか，ということは，次の質問へ．
-
意欲がなくなって、その日のノルマを達成できないということは岡本教授にはありませんか。そうならないような量のノルマを適切にお決めになって納期を守りますか。それとも、ある日のノルマを達成できなくなった際に、何かなさいますか
---
何もしません．「達成できなかった」という事実がまず残ります．その後はなるようになります．それですべての終わりが訪れるわけではないので，気を確かに持ち，そのときにできることをしていけばよいと思います．もちろん，「達成できなかった」ということには，代償が伴います．その代償とは付き合わなければなりません．
-
教授が理解なさろうとして大変難しかった、もしくはできなかった、数学や物理の分野はありますか。
---
質問の内容をよく理解できていませんが，そもそも理解しようとして理解できないから，研究をしているわけで，私が真に理解できていることなど何もないと思ってます．
-
東工と名古屋の高安教授が経済物理学で市場の解析をなさって非常に成果を上げていらっしゃるそうですが、どうお考えでしょうか。
---
私は評論家ではないので，私が専門としない分野において，私以外の特定の研究者がしている活動に対して何かをいう立場に私はありません．
- 5/28 (6) 最大流：数理
- コメントありがとうございました．来週は中間試験です．しっかりと準備をしてきてください．
-
テスト頑張ります。
---
しっかりと準備をしてきてください．
-
対戦よろしくお願します。
---
対戦している気は私に全くありませんが．;-)
-
中間のアドバイスを...
---
演習問題に取り組んで下さい．
-
中間は難しいですか？
---
難しいかどうかは私が決めることではないので，分かりません．
評価基準はシラバスに書いてあります．
-
復習が追いついていないので、来週までにがんばります。
---
はい，よろしくお願いします．
-
:(
---
(-_-;
-
「完全マッチングが存在するか？」という問題は
例えば上の場合 {a, b} と {a, c} の一方はマッチングの要素であるが，結局両方の場合でも完全マッチングが構成できない ⇒ 存在しない
という考え方でも可能ですか？
(でないと2014年度中間の問4Bが解けそうになくなる…)
---
最初に注意なのですが，2014年度中間試験の問4Bは今年度の中間試験の範囲に入っていません．
それを踏まえた上で答えようと思いますが，その考え方は可能です．つまり，場合分けになります．
-
レポート中で正しさが良くわからないとコメントを頂きました。これは記述が不十分ということですか、それとも見やすく書きなおすべきということですか？
---
「記述が不十分」だと思って下さい．読めない場合は「読めない」と書きます．
-
$f^+(v)$ で $+$ であるのに，流出であることがイメージに合わない。 ($+$ はたくわえられるイメージがする)
---
分かりにくいことは想像できます．出次数も $+$ で表してましたので，それと同じだと思って下さい．流れはたくわえられず，入ってもすぐ出ていくものだと思って下さい．
-
弱双対性の理解が深まりました。
---
そうですね．重要な道具なので正しく使えるようになって下さい．
-
最大龍はどの龍だと思いますか？
---
五嶋龍だと思います．
-
アルゴリズムを利用した証明がむずかしそうだなと思いました。
---
これは次回やります．お楽しみに．
-
マッチングに続いて流れの問題でも増加道が活躍するんですね
---
そうですね．重要な道具になります．
-
東大入学の為にどれほど勉強なさいましたか
---
すみませんが，忘れました．
-
高校時代、どんな小説をお読みになりましたか
---
すみませんが，忘れました．(大学生のときと混同します．) おそらく『遠い海から来たCOO』は読んでます．
-
先生は朝型ですか，夜型ですか？
---
あまり気にしていませんが，朝の方が集中できる気がします．
-
経済の数理的分析では、経済物理学が最も有効ですか
---
何が有効なのかは知りませんが，経済を数理的に分析する分野は普通「理論経済学」と呼ぶと思います．
- 5/21 (5) マッチング：モデル化
- コメントありがとうございました．掲載が遅くなりすみません．
-
第4回スライドp45アルゴリズムの[1] $M:=\emptyset$, $C:=\emptyset$ は $C:=V$ ではないでしょうか？
---
ご指摘通りです．修正しました．
-
演習4.9-11に全く歯が立ちませんでした… (´；ω；`)
---
直接質問して下さい．よろしくお願いします．
-
追加問題4.9〜4.11がわからなかった。
---
直接質問して下さい．よろしくお願いします．
-
オイラー回路を持つための必要十分条件
$C_1 ... C_k$ と $C$ を組み合わせることで $G$ のオイラー回路を構成できる ← ここのところがわからなかった
---
これは演習問題の内容ですので，演習問題として取り組んで下さい．
-
カゼひいた
---
お大事に
-
作業や仕事の効率を上げるコツを教えて下さい
---
私も知りたいです．教えて下さい．
-
:(
---
;-)
-
D:
---
:-D
-
この授業は1回休むとしんどくなる ーみちをー
---
授業とはそういうものだと思います．
-
だんだん暑くなってきましたね。先生は夏は好きですか？
---
冬よりはよいと思います．
-
どんなジャンルでも良いので、最近読んでおもしろかった本を教えて下さい。
---
すみません，最近本を読んでいないです．読みたい本はたくさんありますが．
-
用語が増えてきて、以前の物を忘れてしまいそう．用語集を活用しようと思う．
---
用語は覚えようと思わないことが大事です．忘れても，調べて，思い出せればよいので，それができるように整理しておいて下さい．
-
完全グラフであったり最大マッチングであったり最大重みマッチングであったり最小重み完全マッチングであったり、日本語がややこしくて違いを理解するのが大変だなと思いました．
---
そうですね．用語によっては，文字面から意味を推測できる場合があるかもしれないですが，定義に基づいてそれらを理解することが要求されていますので，直感と論理をうまく使い分けて理解するようにして下さい．
-
スライドの説明がわかりやすく，少なくとも復習問題はスライドを読んで書いてみると理解できました．
---
追加問題もぜひ取り組んで下さい．
-
マッチングのアルゴリズムを用いた問題も解いていきたい
---
はい，ぜひぜひ．
-
p.11の話し
ベン図は強い (弱点はある)
---
そういうことですね．そのように自分で整理できるととてもよいです :-)
-
最大マッチングの証明がむずかしかったです．
---
重要なので，演習問題でしっかりと身に付けて下さい．
-
モデル化とはどういう意味ですか？
---
「見立てを行う」ことをモデル化と言います．特に，数理モデル化という場合は，世の中の現象を数学の枠組みを用いて表現すること，または，表現しようとすることをモデル化と言います．数学を使って問題解決を行う際に，必ず行うことです．
-
一筆書きとマッチングは関係あるんだなと感じた。
---
そうですね．思いもよらない関係性に驚かされることが今後もあるかもしれないです．
-
仮想的にひと筆書き出来るようにする，という発想になるほどと思いました．
---
そうですね．そのように考えることで，問題を解きやすくしているわけですね．
- 5/7 (4) マッチング：数理
- コメントありがとうございました．5月14日は休講です．
-
帰納法と再帰が関係あるとは思っていませんでした。
---
帰納法は再帰そのものです．そのように理解することに慣れて下さい．
-
GW明けで頭が働かず眠かったです。
---
では，GWを廃止しましょう．
-
今週と先週のニュース
- 山口メンバーTOKIO脱退．…鉄腕DASH好きだったのにな．
- 青学で爆破予告、7日休校．…うらやましい (不謹慎)
---
テロの標的になっていることをうらやましがってはいけません ;-)
-
申し訳ないですが、今回は眠かった。次回は寝てから来ます。
---
はい，しっかりと寝てきてください．
-
この講義の不合格率がなぜか高い理由が何となく分かった気がしてきました．
---
私には分からないので是非教えて下さい．
-
ずいぶん人が減ったような気がします。授業がうけやすくていいですね。
---
私もそう思います．
-
あいうえお
---
かきくけこ 鐘がなるなり 法隆寺
-
スライドがとても分かり易い
---
すぐに分からなくなるので，油断しないようにしてください．
-
だんだんややこしくなってきました…
---
同感です．私もそう思います．
-
最大マッチングと増加道のところの証明が難しい
---
自分で思いつくことは難しいと思います．しっかりと復習をして下さい．やっていることは数を数えることだけです．
-
証明のとき，色々な方法の中からスムーズに証明する方法を瞬時に得られるようになりたい．
---
私もそうなりたい，と思う反面，そうなってしまうと試行錯誤する楽しみもなくなってしまう気がします．
-
演習問題を解くことである程度理解できるようになった
---
演習問題に取り組むことは重要ですので，励行して下さい．
-
実験でふれたことの理解を深めれてよかった。
---
それはよかったです．
-
増加道のはなし，先にしてほしかったです。(最初の実験がこれだった)
---
実験のテキストだけで独立して理解できるようになっているはずですので，しっかりと見直してみて下さい．
-
上の図でのマッチング $\{(v_1,v_2), (v_3, v_4)\}$ がなぜ、完全マッチングといえないのですか。
---
完全マッチングなので，完全マッチングだと言えます．
-
学部生時代、どれほど本をお読みになって、どれほど学問に時間を費やしましたか
---
学問に時間を費やした気はないですが，いろいろな本を読んでいたとは思います．小説は高校生のときにたくさん読んだので，それに比べて，新書や学術書を読むようになった気がします．ただし，読むのがとても遅いので，多くても1ヶ月に1冊程度です．
-
今のご専門外で興味のお持ちになっている分野は何ですか
---
何でも興味があります．圧倒的に時間が足りないですが．
-
岡本教授が教授をおつとめになることとなった経緯を教えて下さい．
---
何を聞かれているのかよくわかりませんが，昇進しただけです．
-
代数学入門 (群・環・体など) の本の序文に「これは"離散数学"の講義をもとにして作られた本です．」と書いてありました．このような代数学の内容も離散数学ということがあるのですか？
---
「離散数学ということがあるのか？」という問いに対する答えはYESです．それは，その本の著者のようにそう言う人がいるからです．しかし，これは求められている答えではない気がします．
では「代数学入門は離散数学なのか？」という問いにしますが，それに対する答えは私にとってNOです．代数学入門は代数学入門です．それがなぜ"離散数学"という講義で扱われてたのか，私は分かりません．
- 4/23 (3) 木：数理
- コメントありがとうございました．
-
この紙を授業の始めに配ってほしいです。
---
はじめだとまだ来ていない人もいるので，難しい部分もあるかもしれませんが，一度試してみましょう．
-
眠い。
---
しっかりと寝てきてください．
-
レポートの添削ありがとうございます。レポートないのチェックマークは悪い部分でしょうか．それとも単に確認したということでしょうか。
---
「単に確認した」ということです．なお，私は添削をしているわけではないので，その点はご注意ください．
-
予盾
---
×
-
先生の指摘を受けて自分のレポートを確認したら「矛盾」と「予盾」が混在していて何とも言えない気持ちになりました (´・ω・`)
---
「矛盾」と書く自分が「予盾」と書く自分と矛盾してしまったということですね．
-
「白紙でだしたレポートは解いていないので再提出できない」とのことでしたが、解こうとした形跡や考察などがあれば、その問題は次の講義で再提出してもいいのえしょうか (;;)
---
その場合は再提出してもよいです．書いていただいた考察に沿って私からヒントが与えられる可能性もあります．
-
演習問題の答え欲しいです．
---
「答え」はありません．
-
発展問題は，試験には出ないので，単位が目的ならば解く理由は少ないように感じますが，自身の数学力の向上のためにやっていきたいと思います。(実際，僕目線では難しいと感じました。)
---
私目線でも難しいと感じるので，無理のない範囲でチャレンジして下さい．
-
様々な証明があるので，どれを使うのが良いか選ぶのが難しい
---
そうですね．いろいろと試行錯誤する必要があると思います．そのような経験を積んで下さい．
-
証明系は苦手です．証明系で良い書物はありますか？
---
日本語の「証明系」は英語の「proof system」を指すものなので，ここで，proof systemに関するよい書物を挙げるという，期待されていない行動を私がすることも考えられますが，それではコミュニケーション不全ですので，期待されていると思われる回答をします．
回答：「証明の書き方については前回のコメントにも挙げているので，そちらを参考にして下さい．」
-
BGMは教室内には流さず、聴きたい人が勝手にイヤホン等をつけて聴く形式をとって欲しいです．BGMが邪魔な人もいるので、よろしくおねがいします．
---
ご意見ありがとうございます．では，次回はそうします．
-
BGMはねむくなります
---
次回はBGMがなくなります．よろしくお願いします．
-
演習時間にBGMがあって、良かったです．
---
次回はBGMがないので，自分で用意してきてください．
-
BGMのピアノの音楽がとてもリラックスできる感じでよかったです．
---
次回はBGMがないので，自分で用意してきてください．
-
普段使っているBGMを教えて下さい．(勉強用とか)
---
YouTubeで「bgm」と検索すれば，それらしいものがたくさん引っ掛かります．それを使ってます．適当なクラシックを流すこともあります．
-
音楽で思い出しました．Avicii亡くなられたんですね．知っている曲ばかりだったので悲しいです．
---
突然のニュースでしたね．旅行先の訃報であるということもあり，謎が多いような気もします．
-
4/21(土)にYouTubeで銀魂の動画を見倒して勉強が出来ませんでした。意欲も底をついていました。私のやる気は頻繁になくなります。生活習慣もたびたび壊れます。意欲の持続，生活習慣を整え続ける良い方法はありますか？ご存知であればお教えください。
---
銀魂の動画を見倒すことの是非はおいておきますが，短い期間 (例えば，1日とか) の目標を決めるとよいと思います．続けることは難しいかもしれませんが，目標を決めた日は割とスムーズにいろいろなことができるような気がします．
-
朝食
---
あまりバランスがよいようには見えないですね (^^;
-
無向グラフを向向グラフと書いてしまう
---
「むきむきグラフ」でしょうか？
-
教授は1本だけしか生えていない木を見て「森だ！」と感じますか？
---
日常生活では，感じませんね．;-)
-
離散数学が苦手でしたががんばります．
---
はい，がんばってください :-)
-
先週の内容ですいませんが、有向閉路は有向道に含まれますか。また、含む場合始点と終点はどこになりますか。
---
有向閉路は有向道ではありません．
-
「木から葉を除去しても木」の証明の連結であることを示すとき任意の2頂点u, wを考えていますが u=wのときでも大丈夫と考えて平気でしょうか？ (|V|=2の場合もあるし...)
もしそれでいいのならある頂点から同じ頂点に至る道が存在するという言い方は少し不思議な気持ちになります．
---
「平気でしょうか？」という質問に対する回答は「平気です」になります．頂点数1の道の長さは0であって，それは「ある頂点から同じ頂点に至る道」になります．不思議な気持ちになるという感覚は同意できますが，それを許すように用語が作られていることになります．
-
講義資料中のグラフの画像は何を使って描いているのでしょうか
---
Ipeを使っています．
-
最大性論法の理解が深まった．
---
今後もでてきますので，お楽しみに．
-
帰納法は便利ですねー
---
そだねー
-
結論からはじめようか、仮定から始めようか、手順がだいたい同じで、納得できなかった．
---
講義中に「＜余談＞」として説明した部分は，どちらでも正しいので，問題はないわけですが，実際に一方が正しくない場合もあるので，ご注意ください．
-
仮定から始めて結論を導くと間違える例でわかりやすいものは他にありますか？
---
わかりやすいかどうか判断できませんが，次のような例を考えてみました．
nは1以上の整数であるとして，n個の開きカッコとn個の閉じカッコを適当に並べます．例えば，n=4のとき，「))()(()(」のようなカッコの並びを考える，ということです．証明したいことは，どのように並べても，それをうまく巡回シフトさせると，必ずカッコの対応がとれた形にできる，ということです．ここで，カッコの対応がとれた形というのは，左から右へ向かってカッコを順に見て行くとき，開きカッコの数が必ず閉じカッコの数以上になっていることを意味するとします．
例えば，上の例「))()(()(」は左に2つ巡回シフトをさせると「()(()())」となり，これはカッコの対応がとれた形になっています．
では，今から，数学的帰納法っぽい間違った証明をしてみます．
n=1のとき，並べ方は「()」と「)(」の2通りあります．前者は既にカッコの対応がとれた形になっているので，つまり，巡回シフトさせなくてもカッコの対応がとれた形になっています．(あるいは，左に2つ巡回シフトをさせる，と思ってもよいです．) 後者の方は左に1つ巡回シフトをさせると「()」になり，カッコの対応がとれた形になります．つまり，n=1のとき，証明したいことは正しいと分かります．
では，任意の自然数k≧1に対して，n=kのときに正しいと仮定して，n=k+1のときに正しいことを証明しましょう．
開きカッコk個と閉じカッコk個を適当に並べたものを考えます．帰納法の仮定から，これにうまく巡回シフトを施すと，カッコの対応がとれた形になります．では，このカッコの対応がとれた形の右端に「()」をつなげましょう．そうすると，開きカッコk+1個と閉じカッコk+1個を並べたものができ，なおかつ，それはカッコの対応がとれた形になっています．つまり，k+1個の開きカッコと閉じカッコを並べてカッコの対応がとれるように巡回シフトができました．
これで証明終了です．
もう一度強調しますが，この証明は間違っています．どこが間違っているのか，考えてみることは重要です．いかがでしょうか．
-
今まで使っていた帰納法がよくない方の帰納法だったので気をつけたいと思いました．
---
今後も数学的帰納法は何度もでてきますので，気をつけていって下さい．
-
数学的帰納法の難しさを知りました。
---
数学的帰納法は高校や高専で習うものだと思うのですが，思いの外，正しく書くことができないものとして，私の中では有名です．ウェブ上でも数学的帰納法による正しくない証明があたかも正しいかのように紹介されていることがあります．具体例を挙げると角が立ちますが，例えば，ここの数学的帰納法は私が講義で挙げた理由とは違う理由で間違っています (あるいは，不正確です)．どこが間違っているのか (あるいは不正確なのか)，吟味してみて下さい．この例からも分かるように，高校や予備校・塾で数学的帰納法が不正確に教えられている可能性は十分あります．または，正しく教えられていても，皆さんが勝手に間違って理解している可能性もあります．何事も，皆さん自身が批判的にいろいろなものを理解しようとする態度が問われていると思って下さい．
- 4/16 (2) 道と閉路：数理
- コメントありがとうございました．
-
レポートは表紙をつけたほうが良いですか？
---
どちらでも構いませんが，氏名と学籍番号はどこかに記載して下さい．そうでないと返却できません．
-
レポートは提出後に解答はもらえますか？
---
「解答」が何を意味するのかによって細かいニュアンスが変わってきますが，想定される意味に対する私の回答は「もらえない」です．
-
課題を提出するときは，レポート用紙の方が良いですか。ルーズリーフで提出することは可能ですか。
---
どちらでも構いませんが，紙が複数になる場合はとじて下さい．
-
レポートで解かなかった問題があった場合に、後にそれを解いてレポートを再提出することは可能ですか？
---
その部分については「再」と考えることができないので，私の回答は「可能ではない」です．
-
HPのジュピターノートブックのリンクをクリックするとソースが直接出てきて見れない…
---
直接出てきているならば，見れています．それをダウンロードして，実行する必要があります．
-
XD
---
:-)
-
CSの懇親会もあれば良かったのにと思います．
---
CSプログラムの先生にご相談下さい．
-
俺は悲しいぜ。CS懇談会が無いのがよぉ。
---
CSプログラムの先生にご相談下さい．
-
証明難しい
---
証明が書けるようになることには慣れが必要だと思います．演習問題を通して身に付けて下さい．
-
直感でわかったことを文字に直すのは難しいです。
---
それができるようになることが重要です．情報科学の本質の1つは「人間が無意識に行うことを意識する」ことだと思っています．コンピュータに何かを理解させる，ということは，それを筋道立てて説明することととても似ています．大学ではそのための技法も学んでいるのだと思って下さい．
-
証明問題を解くのが苦手なのでがんばらないとなと思いました
---
「証明問題」を特別なものだと思うと，難しく感じるかもしれません．心理的なものだと思います．例えば，「$\sin^2 x$ の微分は何か」と問われるよりも，「$\sin^2 x$ の微分が $\sin 2x$ になることを証明せよ」と問われる方が答えるのは簡単なわけですが，後者は「証明せよ」と書いてあるので証明問題です．問われ方に惑わされてはいけないわけです．
-
証明が鮮やかでした。自分も証明かけるようになりたいです！
---
証明ができるようになることは目標の1つですので，しっかりと身につけて下さい．
-
証明が上手くできないです。証明の仕方が分からないです。
---
これはどのような教育を受けてきたのか，ということに依存する可能性がありますが，私が担当していた『離散数学』では，証明の書き方をやりました．昔の記録を参考にしていただければ，と思います．証明の書き方については，書籍として，『だれでも証明が書ける』や『その理屈、証明できますか？』に記述があり，参考になります．
-
証明がスタートとゴールを先に説明していて，直感的な説明もあるのが分かりやすいです．
---
はじめの数回は，直感的な部分と形式的な部分を分けて説明しようとしてみます．慣れてきたら，形式的な説明の中に直感を混ぜるような形にするかもしれません．
-
イメージ図は最初に全ての頂点を表示しておくと分かりやすいと思います
---
なるほど．確かにそうだと思います．直してみます．
-
しっかりと学んでいきたい。
---
はい，分からないところが出てきたら，是非質問して下さい．
-
最大性論法について，とても感心した。
---
最大性論法は離散数学の味わい深いものなので，しっかりと身に付けて下さい．
-
最大性論法をしっかり理解して使えるよう努力したいと思いました。
---
はい，演習問題に取り組んでみて下さい．
-
最大性論法が難しいです。
---
慣れないと難しいですね．演習問題を通して身に付けて下さい．
-
握手補題を使うと簡けつな式で辺数が導出できて良い
---
そうですね．握手補題はどんな無向グラフに対しても成り立つ「法則」ですから，使える場面が多いのです．
-
問題が難しかった
---
ひとりでやろうとは思わないでください．相談しながらやることを推奨します．
-
演習問題難しかったです．
---
ひとりでやろうとは思わないでください．相談しながらやることを推奨します．
-
追加問題難しいです。
---
ひとりでやろうとは思わないでください．相談しながらやることを推奨します．
-
BGM流せば相談しやすくなると思う。
---
なるほど．試してみましょう．では，次回は演習の時間にBGMを流してみようと思います．
-
グラフの構成についての用語がたくさん出てきたのでしっかり覚えようと思います．
---
授業中にも言っているのですが，覚えようと思わないでください．覚えようとしてもすぐ忘れますし，忘れてもらってもよいのです．思い出そうと思ったときに，すぐに思い出せるように (頭の中でなくてもよいので) 整理しておくことが重要だと思います．記憶力を競うのはクイズです．クイズ自体はそれはそれで楽しいものですが，講義の目的はクイズをやることではないので，ご注意ください．
-
$P_1$ の道は辺がないので次数0だと思うのですが次数が1でないので端点と呼びませんか？
---
するどい指摘ですね ;-)
講義スライドに従うと，呼ばないことになります．しかし，場合によっては，端点と呼ぶことにすると都合がよいこともあるので，そうすることもあります．
-
$\delta(G) \geq k-1$ $\Rightarrow$ $G \supseteq P_k$ の証明が理解できませんでした。
⇒ やっぱり理解できました．
---
それはよかったです :-) 分からない所は演習の時間やこの紙でぜひ質問して下さい．
-
$\delta(G) \geq k-1$ $\Rightarrow$ $G$ は $P_k$ を含むの証明において なぜ $\ell \geq k$ であることを示せばよいのかがわからなかったです。
---
$\ell$ は長さ最大の道の頂点数ですから，$\ell \geq k$ であれば，その道の頂点数が $k$ 以上であることになり，つまり，その道の一部分として，$P_k$ が見つかる，ということになります．それが理由です．
-
部分グラフの定義に従うと，
は
の部分グラフになってしまいますが，これは正しいですか？
---
するどい質問です ;-)
残念ながら正しくないです．部分グラフを定義したところでは，まず，G1とG2は無向グラフであるという前提があります．しかし，頂いた例において，G1は無向グラフではありません．具体的には，辺として頂点集合の要素数2の部分集合ではないものが存在してしまっています．つまり，部分グラフを定義する際の前提を満たしていないので，正しくない，ということになります．
-
たくさんの頂点を持つグラフでも，最小次数が小さいと長い道が存在するとは限らないというのは不思議ですね．
---
よい視点ですね．実際に，最小次数が小さく，長い道を持たないグラフの例を考えてみるとよいと思います．そうすると，不思議なのか，そうでないのか，より深く理解できる気がします．
-
切断辺、切断点がいくつあるかの判断は、グラフを見て「これが無かったらこうなる、これが無かったらこうなる…」と1つ1つ試していくしかないのでしょうか．
---
そうではない方法もあります．グラフの深さ優先探索というのをどこかで習ったり聞いたりしたことがあるかもしれませんが，それをうまく使うことで，切断辺や切断点をすべて簡単に見つけることができるようになります．
-
わかりやすくて好きです。
---
でもゾウさんの方がもっと好きです．
-
スライドが分かりやすいです．
---
「スライドだけで分かる」ようには作っていないつもりなので，講義の中で内容をしっかりと補強して下さい．
-
岡崎高校、東京大学、スイス工科大学チューリッヒ校、各々での岡本教授の同級生で、教授の尊敬なさる、もしくは驚くべき方がいらっしゃれば、お教えください。また、先生の日課は何ですか。成功する方にはルーティンがある傾向にあると聞きました。
---
私は成功しているつもりは全くないのですが ;-) 特別な日課はないです．強いて上げれば，寝て起きることです．
とりたててある特定の人を特別に尊敬するということは私の人生においてない気がします．むしろ，どんな人にも尊敬できる面と尊敬できない面というのがある，という感覚を持っています．その意味では，すべての人を尊敬しています．
-
朝食
サラダチキンはおいしいです。スモーク味が好きです。
---
おいしいんですね．では，スモーク味から試してみます (^^)
-
火垂るの墓見ましたか．自分は辛くなるので見ませんでした。
---
質問だけに答えると，「見ていません」ということになります．
- 4/9 (1) グラフの定義と次数：数理
- コメントありがとうございました．いただいたコメントとその回答は以下のように掲載されます．
-
よろしくお願いします。
---
こちらこそよろしくお願いします．
-
よろしくおねがいします。
---
こちらこそよろしくお願いします．
-
半年間よろしくお願いします．
---
はい，よろしくお願いします．
-
難しそうですがすこし興味が出てきたので受講しようと思った．
---
すこしなんですね ;-) よろしくお願いします．
-
学部生I科2コースですが受講します．
---
すばらしいです．よろしくお願いします．
-
再履なので頑張ります。
---
はい，がんばって下さい :-)
-
そろそろ進級したいです．．．がんばります
---
はい，よろしくお願いします．
-
履修したいと思いますので、よろしくお願いします．
---
こちらこそよろしくお願いします．
-
興味のある内容なので履修します
---
はい，よろしくお願いします．
-
頑張ってみようと思います．
---
ぜひ頑張ってみて下さい．
-
：）
---
;-)
-
よろしくお願いします。
---
こちらこそ，よろしくお願いします．
-
1年次の離散数学で心を折られていたのでこの講義も理解できるか不安です…
---
私の口から軽々しく「大丈夫です」とは言えませんが，しっかりと復習をしてきてください．
-
レポートの締め切りが講義終了時となっていますが、終了時に提出しても大丈夫ですか？
---
はい，終了時に提出して下さい．
-
しゃべるのが早くて聞こえないことがあるので、もう少しゆっくりしゃべってください。
---
そうですね．自分でも自分が何を言っているのか分からないことがあるので，気をつけます．(´・ω・`)
-
テストの4問のうち演習問題と同一でない問題は比較的難しいですか？
---
難易というのは主観的なものなので，皆さんにとって難しいかどうかという判断を私はできません．
-
用語や言葉の定義を大切にする姿勢がよく伝わってきました。
---
それが達成目標の1つですからね．;-)
-
入次数，出次数の読み方がめんどくさいです。
---
同感です．
-
英語の用語も記入してください．
---
英語は「用語集」の方にありますので，そちらを参照してください．
-
講義資料が分かりやすくてよかったです。
---
ありがとうございます．分からない所がでてきたら質問して下さい．
-
過去の講義資料，試験問題が公開されているのが大変ありがたいです．全講義そうであればいいのに．
---
講義や授業の進め方には人それぞれ考え方があり，また，向き不向き・相性もあると思います．この形式が合うと感じる方もいれば，そうでない方もいるものだと思っています．絶対的によい形式というものはなく，関係の中でしかそのような考え方は生まれないと私は思っています．ご了承ください．
-
まだなんとかついていけそうです．
---
だんだんと込み入った内容になっていくので，しっかりと復習をするようにして下さい．
-
証明の導入を考えることが苦手ですが、がんばっていきたいです。
---
証明ができるようになることは達成目標の1つなので，演習問題を通して身に付けていって下さい．
-
わかりやすかったです。握手補題はP36の表のおかげですぐ理解できました。(表なしで理解できた方が良いのでしょうが...)
---
いろいろな理解の仕方があると思うので，自分に合う方法で理解できればよいと思います．ただ，「自分が理解する」ことと「自分が理解したことを他人に伝える」ということは大きく違います．「証明を書く」というのは後者を行うことですから，そのつもりで，証明というものに向き合うとよいと思います．
-
握手補題の証明のスライド37/47の $\displaystyle \sum_{e \in E}\left(\sum_{v \in V} M_{v,e}\right) = \sum_{e \in E} 2$
ここの変換がよくわからなかったです。
---
$\displaystyle \sum_{v \in V}M_{v,e} = 2$ が成り立つということですね．36ページの行列において，辺 $e$ に対応する列の成分の和が左辺の $\displaystyle \sum_{v \in V}M_{v,e}$ でそれが2に等しい，ということです．
-
証明が分かりやすかった．
---
分からない所がでてきたら，是非質問して下さい．
-
離散数学は苦手であるが，丁寧に説明してくださり，今日のところは理解できました。
---
それはよかったです :-) 分からない所がでてきたら，質問をお願いします．
-
$A=\{(1,1), \ldots \}$ みたいなの自分自身へのが無いのは直積の定義からですか？
---
実際はあります．スライド23ページを見て頂くと，$(4, 4)$ という弧があることに気付けると思います．一方で，無向グラフの場合，$\{4, 4\}$ というような辺はありません．これは $\{4, 4\}$ という集合は $\{4\}$ という集合と等しく，この要素数が2ではないためです．
-
新3年生歓迎会は具体的に何時まで開催されるか、具体的に何をするかなどは決まってますか？また、バイトがあるので参加できなそうなのですが、参加できなくても問題はありませんか？
---
18:00から2時間ぐらいです．具体的には飲食をしながら懇親します ;-)
参加できなくても問題はありませんが，都合がつけば是非ご参加ください．
-
歓迎会の告知に使っていたテキストエディタがNotepad++だった気がして自分のメインテキストエディタもそれなので「おなじだ〜」と思っていた
---
残念ながらEmEditorを使っています．そして，メインのエディタはEmacsです．EmEditorは補助的に用いています．
-
土曜日に補講をやるという話はどうなったのですか？
---
すみません，忘れてました．この紙に希望や意見を書いていただこうと思っていましたが，そう言うのを忘れていました．
-
土曜の補講はなしがいいです。
---
分かりました．では，なしにします．
-
土曜はやめて欲しいです。
---
分かりました．では，なしにします．
-
たぶん受けます。土曜はイヤです。
---
分かりました．では，なしにします．
-
土曜の補講は嫌です．
---
分かりました．では，なしにします．
-
土曜日にやらない事で別日に詰めて授業をする可能性があるなら授業を土曜日にしていただいて全然OKです。早い時間はキツいのでこの時間でお願いします．
---
詰めることにはしませんので，その点はご心配なく ;-)
-
工房のあと質問しても大丈夫ですか？
---
はい，大丈夫です．
-
朝食
---
最近サラダチキンが流行ってますよね．おいしいですか？
-
岡本教授は岡崎高校、東大、スイス工科大学チューリッヒ校を卒業なさったそうですが、今まで挫折をなさった経験はありますか。
---
幸か不幸か，挫折ばかりです．人生とはそういうものだと思います．
試験・成績
- 中間試験と期末試験により，成績の評価を行います．
- 成績 = min{100, 中間試験の素点+期末試験の素点} (小数点以下切り捨て)
- 得点分布 (中間試験と期末試験の一方でも受験した人に限る)
- 受講者数 (履修登録者数相当) は69で，
90点以上 (S) が7人 (約10%)，
90点未満80点以上 (A) が8人 (約12%)，
80点未満70点以上 (B) が13人 (約19%)，
70点未満60点以上 (C) が9人 (約13%)，
60点未満 (D) が32人 (約46%) です．
- 中間試験と期末試験の一方でも受験した人の総数は61で，
90点以上 (S) が7人 (約11%)，
90点未満80点以上 (A) が8人 (約13%)，
80点未満70点以上 (B) が13人 (約21%)，
70点未満60点以上 (C) が9人 (約14%)，
60点未満 (D) が24人 (約39%) です．
- 期末試験
- 日程：8月6日(月) 第2時限 (10:40-12:10)
- 教室：西2-101 (いつもの教室)
- 持ち込み：A4用紙1枚分 (裏表自筆書き込み) のみ可
- 出題範囲：第6回講義の最初から第11回講義の最後まで
- 形式：
- 演習問題と同じ形式の問題を4題出題する
- その中の2題は演習問題として提示されたものと同一である
(ただし，「発展」として提示された演習問題は出題されない)
- 配点：1題15点満点，計60点満点 (0.5点刻み)
- 試験問題
- 得点分布
- 受験した人の数は52，平均点は30.6 (60点満点)．
45点以上 (S相当) が5人 (約10％)，
45点未満40点以上 (A相当) が8人 (約15％)，
40点未満35点以上 (B相当) が7人 (約13％)，
35点未満30点以上 (C相当) が7人 (約13％)，
30点未満 (D相当) が25人 (約48％) です．
- 得点掲示 (辞書順に並べています)
| 0x057 | 39 |
| 123abc. | 27 |
| 1H87H1S | 2 |
| 777tworai | 37 |
| a3b5y | 29 |
| ababa | 11 |
| AGOTO | 17 |
| AmZrS | 40 |
| AOTRS | 33 |
| asdfg | 39 |
| axy05 | 43 |
| B6f1H4 | 32 |
| bdfe | 19 |
| bengi | 19 |
| canon | 27 |
| ddon8 | 8 |
| folk | 50 |
| frkgs | 49 |
| ggwp | 23 |
| hage2 | 34 |
| Illya | 32 |
| kalf1 | 43 |
| kasen | 39.5 |
| mu58m | 36 |
| Nyaan | 28 |
| ogmax | 50.5 |
| PLASTIC5 | 31.5 |
| ramen | 29 |
| rayma | 46 |
| rktnz | 28 |
| rlio3 | 28 |
| ry006 | 20 |
| sTcuT | 21 |
| takeoff | 41.5 |
| tkhshre. | 41 |
| TTnK5 | 24.5 |
| URDRP | 42 |
| W2143 | 27 |
| wine3 | 43 |
| ying | 30 |
| zf375 | 25 |
| ポチカすこ | 23 |
- 念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
- 講評
- 総評：全体的にできていなかったです．問題4が比較的解かれないのは想定内だったのですが，問題2と問題3のできが悪かったです．そのため，平均点が下がってしまったと思います．
今後，いろいろな場面で気をつけてもらいたいことがあります．それは，皆さん自身が自分の書いたことに責任を持つということです．それは，試験の答案であっても，実験のレポートであっても，ブログの記事であっても，twitterのつぶやきであっても，他の人の目に触れるものならば，何でも同じです．皆さんは，日本語を自由に操ることができるように錯覚をしているかもしれませんが，残念ながら，そうであるとは限らないでしょう．私自身も日本語を自由に操れるという感覚を持っていません．皆さんが日本語を自由に操れないということを前提とすれば，皆さん自身がよく分かっていないことを文章にしたら，それは誰にも伝わりません．「よく分からないけど，何か書けば，勝手に相手が解釈して，うまくいくだろう」という態度では，大体うまくいきません．残念ながら，そういう態度の文章は見て分かりますし，それが答案に書いてあっても，点はありません．今，「書く」ときの話として説明をしましたが，「読む」ときや「聴く」ときも同じです．そして，総体として意思疎通，つまり，コミュニケーションができるようになります．それがコミュニケーション能力と呼ばれるべきものだと思っています．
以下，各問題に対するコメントです．
- 問題1：最大流に関する問題．平均点は12.3．演習問題6.7と同じ問題．よくできていました．できていない人は，そもそも最大流とか双対性というものが何であるか，理解できていないような気がします．最大流であることの証明は補助ネットワークを用いておこなっても構いません (がお薦めしません)．
- 問題2：染色数と辺数の関係を問う問題．平均点は5.47．あまりできていませんでした．これは比較的「あたりまえ」のことを聞いています．気づけば4行ぐらいで証明できます．染色数がkのグラフが頂点数kのクリークを含むとは限りません．(染色数が10000以上なのに，頂点数3のクリークを含まないグラフが存在します)．また，染色数がkのグラフの最大次数がk以下 (あるいはk+1以下) であるとも限りません．(染色数が2なのに，最大次数が10000のグラフは存在します．) 注意して下さい．
- 問題3：オイラーの公式に関する問題．平均点は8.77．演習問題11.8と同じ問題．思いの外，できていませんでした．「各面が正五角形か正六角形である」という日本語が通じていないことに困惑しました．「各」というのは「それぞれ」という意味です．つまり，「各面が正五角形か正六角形である」という表現は，例えば，面が全部でAとBとCと3つあったら，「Aが正五角形か正六角形」であって，それとは別に「Bが正五角形か正六角形」であり，それとは別に「Cが正五角形か正六角形」である，という意味です．「A, B, Cがすべて正五角形である」か，そうでなければ，「A, B, Cがすべて正六角形である」という意味とは違います．
- 問題4：二部グラフのマッチングに関する問題．平均点は4.04．あまりできていませんでしたし，この問題で満点を獲得した答案はありませんでした．演習問題7.5.2をやっていなければ，難しいかもしれませんが，これは演習問題7.3の類題で，それは授業で扱ったものです．そもそもこの問題の設定は演習問題7.5の設定を含んでいるので，演習問題7.5.2の考え方はとても有効です．つまり，Hallの結婚定理を使おうと思うことがまず大事なのですが，問題はどのように使うのか，ということです．任意の $u\in A$ に対して，$\deg(u)\geq 1$ という条件は，$A$ の頂点をすべて飽和するマッチングが存在するためには必要なので，この条件を証明の中で用いていない場合，その証明は正しくないということが分かります．また，$\deg(u) \geq \deg(v)$ という不等式は $\{u,v\} \in E$ でないと成り立たないことに注意しないといけません．つまり，適当に $u\in A$ と $v\in B$ を持ってきただけでは，$\deg(u) < \deg(v)$ が成り立っているのかもしれないわけです．
- 中間試験
- 日程：6月4日(月) 第2時限 (10:40-12:10)
- 教室：西2-101 (いつもの教室)
- 持ち込み：A4用紙1枚分 (裏表自筆書き込み) のみ可
- 出題範囲：第1回講義の最初から第5回講義の最後まで
- 形式：
- 演習問題と同じ形式の問題を4題出題する
- その中の2題は演習問題として提示されたものと同一である
(ただし，「発展」として提示された演習問題は出題されない)
- 配点：1題15点満点，計60点満点 (0.5点刻み)
- 試験問題
- 得点分布
- 受験した人の数は61，平均点は37.3 (60点満点)．
45点以上 (S相当) が16人 (約26％)，
45点未満40点以上 (A相当) が5人 (約8％)，
40点未満35点以上 (B相当) が13人 (約21％)，
35点未満30点以上 (C相当) が15人 (約25％)，
30点未満 (D相当) が12人 (約20％) です．
- 得点掲示 (辞書順に並べています)
| 226 | 28.5 |
| 58237 | 33 |
| 512810 | 30.5 |
| a135 | 45 |
| abxdc | 20.5 |
| AcEgI | 34 |
| AG0T | 41 |
| AHB95 | 60 |
| aMzRs | 60 |
| AOTRS | 33 |
| axy05 | 32 |
| bandit | 37 |
| blue6 | 31.5 |
| caket | 37 |
| cotan | 25 |
| fkRfw | 49 |
| fork | 45 |
| grntps | 24 |
| hage1 | 33 |
| i1618 | 37 |
| Illya | 43.5 |
| int x= | 37.5 |
| J | 25.5 |
| kaito | 40 |
| kaluf | 60 |
| kg17gk | 49 |
| kl1r3 | 46 |
| KSiSB | 36 |
| kxm57 | 37 |
| LAPIS | 37 |
| naraii | 34.5 |
| omukp | 37 |
| popai7 | 32 |
| QQBBq | 27 |
| rktnz | 42 |
| rsgs | 49 |
| rur1g | 36 |
| rybg | 37.5 |
| sabde | 25 |
| smash | 49 |
| STOTK. | 30 |
| takeoff | 45 |
| tanishi | 31 |
| tetsu | 30 |
| tkhshre | 37 |
| Tombow | 49 |
| tzska | 26 |
| ugajin | 29 |
| URRDP | 34 |
| W261 | 26 |
| wine3 | 49 |
| X80 | 26 |
| yktn | 43.5 |
| 今年も留年説． | 37 |
| しゅうかつ | 48 |
| ずんどこべ | 36 |
| むずかしい | 48 |
| ランドセル | 33 |
- 念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
- 講評
- 総評：問題1と問題3はよくできていて，問題2と問題4はほとんどできていませんでした．45点以上とれている人はだいたい問題1, 2, 3が出来た人で，それができれば講義に十分ついていけていると思います．期末試験では油断をしないようにして下さい．一方で，問題1と問題3ができていない人は重要な部分が理解できていないと思いました．30点に満たない人であっても期末試験で挽回できないほどではないと思うので，しっかりと復習と準備をするようにして下さい．以下，各問題に対するコメントです．
- 問題1：次数に関する問題．平均点は14.7．よくできていました．
「30≠32だから存在しない」というのは理由として不十分です．文章の中で
「30＜32だから存在しない」という意図が読み取れない場合は減点しています．
- 問題2：木であるための必要条件を証明する問題．演習問題と同じ問題．平均点は5.66．あまりできていませんでした．演習問題と同じ問題なので，事前に解いていた人はできて，そうでない人はできない，という単純な分け方ができたような気がします．その場で正解にたどりつくのは不可能ではありませんが，難しいかもしれません．数学的帰納法の作法が身についていない答案や，数学的帰納法で何を証明しようとしているのか明確ではない答案も多く，苦慮しました．
- 問題3：最大マッチングを見つける問題．演習問題と同じ問題．平均点は13.2点．よくできていました．最大マッチングであるために増加道がないことを主張したい答案がいくつかありましたが，増加道がないことが証明できていませんでした．「探そうとしても見つからない」というのは説得に足りる説明 (つまり証明) ではないので，注意して下さい．講義で扱った方法がわかっていれば，頂点被覆を考える方法がよいと分かります．
- 問題4：切断点に関する問題．平均点は3.8点．ほとんどできていませんでした．証明の主要な部分は1文で終わりますが，なかなか思いつかなかったようです．閉路の頂点が切断点になることはありえます．そのため，「閉路を含むとき，閉路の頂点は切断点ではない頂点である」という回答は間違いになります．また，数学的帰納法で証明することは困難だと思います．
公式シラバス
こちらをご覧ください
スケジュール (予定)
- 4/9 (1) グラフの定義と次数：数理
- 4/16 (2) 道と閉路：数理
- 4/23 (3) 木：数理
- 4/30 休日
- 5/7 (4) マッチング：数理
- 5/14 休講
- 5/21 (5) マッチング：モデル化
- 5/28 (6) 最大流：数理
- 6/4 中間試験
- 6/11 (7) 最大流：モデル化 (1)
- 6/18 (8) 最大流：モデル化 (2)
- 6/25 (9) 彩色：数理
- 7/2 (10) 彩色：モデル化
- 7/9 休講
- 7/16 祝日
- 7/23 (11) 平面グラフ：数理
- 7/30 (12) 平面グラフ：モデル化
- 8/6？ 期末試験
過去の講義
注意：内容や説明法は毎年少しずつ変わっています
過去の試験問題
注意：内容や説明法，試験範囲は毎年変化しています．
[Teaching Top]
[Top]
okamotoy@uec.ac.jp
