日記

2003/10/31

ようやく採点を始めた。
やはりグラフ理論の証明というのはちゃんとやろうとするとなかなか難しいものなので訓練が必要なのだけれども、
学生さんにとってその訓練になって、そういう思考法に慣れてもらいたい、ということを目標にして、
ちゃんと書けてるとことはちゃんと書けてるとちゃんと指摘して、
ちゃんと書けていないところはちゃんと書けていないとちゃんと指摘するようにしたい。
しかし、こういう当たり前のことがなかなか難しいのだけれども。

2003/10/30

今日は演習問題を解くのに時間をつかった。
演習問題を解くのはとても大事なので、時間を見つけてしっかりとやっていきたい。

今日からAngelika Stegerのランダムグラフの授業が始まったので参加した。
トピックも面白い上に講義も分かりやすく、とてもよい感じがする。

磯田浩先生がお亡くなりになったというニュースが入ってきた。
磯田先生といえば、基礎二創成に関わった先生であり、卒研でもお世話になり、思い出深いことがいろいろある。
御冥福をお祈りいたします。

2003/10/29

やっぱり証明になっていなかった。
まぁそれが分かったということなのでよかったのですが。

2003/10/27

宮沢くん来訪。御元気そうでなによりでございます。
明日もくるそうです。

2003/10/24

とうとうEmoの授業も始まった。
なんか教室が満員なんですけど。
でも良い感じだと思います。今後の展開に期待です。

森山さんとのディスカッションの続き。
何となく証明したことがようやく証明できたような気になっていたけども、まだ油断できないので、もう少ししっかりと詰めていきたい。
あと、グラフの問題の方ももう少し詰めれば何か研究論文になりそうなので、そちらも何とか継続してやっていきたい。

2003/10/22

とうとう授業がはじまった。
なかなかよい調子で進んでると思う。
自分の説明があまりよくなかったので、もう少しちゃんと準備をしておくべきだった。
反省点。

やっぱり論文間に合わないと思うので、無理にやるのはやめにしたい。
だって後1週間しかないのだから。

2003/10/20

全然論文書きをやっていない。本当に間に合うのだろうか。
10/14のところに書いたアルゴリズムも穴があったし。
授業も始まるし。
段々時間がなくなってきてる気もする。

今日は近似不可能性の証明をしたけれども、一般のグラフに対する証明だったので、
もう少し特殊なクラスのグラフに対しても証明したい。
例えば平面的グラフに対してもそんなふうになったりしないものだろうか。

2003/10/15

ようやく先学期に指導していた学生のプロジェクトが終わりを迎えそうになっている。
とてもめでたい。
ETHの情報科学では、だいぶ進んできた学期に学生はプロジェクトをやらないといけない。
(これは情報科学だけではないと思うけれども、他のところではどんな感じなのか具体的に知らない。)
だいたいは、各研究室のスタッフ・大学院生がテーマを掲示して、そこから学生が選んでいくような形になっている。
今回のプロジェクトは自分としてはじめての指導になったのだけれども、なかなか難しいテーマで自分ではやらないようなものなのだったけれども、
それでも楽しんでもらえたようでとてもよかった。
理論的なテーマだと結果を出すのが難しくて、結果といえるようなものはほとんどないのだけど、
捉えどころのないような問題からちょっとずつ糸口を見つけていくようなことを経験してもらえたのはよかったと思う。
とりあえず、お疲れ様でした、と言いたいし、こちらからも感謝の気持ちでいっぱいです。
ということで、明日ぐらいにその最終稿が来る予定。

2003/10/14

ある (割と新しい) 論文が前から気になっていたので、とうとう読んでみたのだけれども、
そこに書いてあるアルゴリズムよりもシンプルなものを発見してしまった。
と思ったら、自分の証明に穴があった。
と思ったら、また違うシンプルなアルゴリズムを発見してしまった。
今度は穴がないと思うんだけどどうだろうか。

EUROCOMBのSpecial Issue論文が全然書けていない！
〆切は今月末だというのに。

今日のメモ。ハミルトン・パスについて。
与えられた3連結3正則平面的グラフがハミルトン・パスを持つかどうかという判定問題はNP完全。
出典は
M.R. Garey, D.S. Johnson and R.E. Tarjan.
The planar Hamiltonian circuit problem is NP-complete.
SIAM Journal on Computing 5 (1976) 704--714.

2003/10/13

ある幾何学的な定理を凸幾何（あるいはアンチマトロイド）に拡張しようとしてうまくいかなかった。
この定理では次元がうまくきいているのだけれども、そういうものを凸幾何のどのようなパラメータとしてよいかはいまいち不明である。
ということで、有向マトロイドを考えてみる。
有向マトロイドでは次元がランクとして入ってくるので、そこで考えてみると自然な一般化を書き下すことはすぐにできる。
ただ証明がまだできていないのでちょっとがんばりたいところ。

2003/10/10

今日のディスカッションはほとんど進まなかったというか、雑談っぽくなってしまった。
もう少し準備してきたほうがよいかもしれなかった。

2003/10/9

森山さんと毎日のようにディスカッションしてるのだけども、進んでいるようで進んでいない、というか、
だんだん分かってきたので、余計に分からなくなっている、という訳の分からない状態が続いている。
もう少し視点を変えた議論が必要かもしれない。

2003/10/8

試験採点終了。
いきなり明日までに、とかいうことになったので急いで終らせてしまった。
採点した問題は最小カットのアルゴリズムの動作を例を使って試すもの。
このアルゴリズムは組合せ最適化の世界では「Ibaraki-Nagamochiのアルゴリズム」として名が通っていますが、授業では「Stoer-Wagnerのアルゴリズム」として教えられたので、
私が激しく反撃して、なんとか「Stoer-Wagner-Ibaraki-Nagamochiのアルゴリズム」という名前にしてもらうところまでもっていったものです。
Stoer-Wagnerの論文がJ. ACMにでてしまったので、それが大きいのかもしれませんが、歴史的な経緯や分野でどのように呼ばれているのかということはしっかりと押えておきたいものです。
このアルゴリズムはNagamochi-Ibarakiによって原形が作られて、
その後Stoer-WagnerとFrankによって独立に単純化されたという経緯を持っています。
Frankのものは未発表原稿ということで私も見たことがありません。
その後、このアルゴリズムはKargerによってランダマイズされ、
また、Queyranneによって対称劣モジュラ関数最小化問題にも拡張されました。
その他、このアルゴリズムの基礎となっている技法は連結度やフローに関する様々な問題に対しても有効であることが分かっています。
グラフアルゴリズムとしては面白いところです。

ただ難点があって、それはアルゴリズム自体が出力のoptimalityのcertificateを出してこないことです。
これは教育的にはあまりよくなくて、つまり実際にアルゴリズムを動かしてみて出力を見てみても、これが正しいという保証がないわけです。
stフローとstカットに対しては、いわゆる最大フロー最小カット定理があるわけですが、
ここでは大域的な最小カットを求めているので直接この定理は利用できないことになります。
どうしたらよいものでしょうか。なかなか際どいところだとも思います。

2003/10/6

CGCワークショップならびに秋の学校も終わり、いよいよ10月で、
有意義な夏が終わったという感じです。
写真の整理も終わりました。
チューリッヒに戻ってきたら、天気はすっかり秋を通りこして冬という感じです。
いきなりジャンパー着てます。
ちょっと今年は寒すぎないか。大丈夫でしょうか。

森山さんが来ています。
1学期間の滞在です。よろしくお願いします。

明日セミナーで話すので少し準備。

9月の日記
 過去の日記のリスト

[トップ]

okamotoy@uec.ac.jp

Last modified:Fri Oct 31 18:20:08 2003