強連結成分分解のアルゴリズムをゼミでやったのでメモ。 2SATは強連結成分分解を利用して解ける。2SATは多項式時間で解ける。ちなみに3SATはNP完全。解き方は２つある。 (1)ある変数xの割り当てを0で固定すると、2SATなので、xを含む節のxとは異なる変数の割…

明日はICPC

難しいね。テキストみてもよく分んなかったので、 首都大の学生の卒研のページで勉強。(googleで上位に出る) 計算時間の証明はちゃんと乗ってなかったので、テキストで勉強したもののよくわからず

とりあえず、今のテーマについてはゴールが見えてきた。 まぁ、論文はまだ書いてないけど...

最近、メインで取り組んでる問題を変えてみたら面白いように進む。 今日も、ひょっとしたらひょっとするかもしれない結果が出た。 この調子を維持していきたい。

最初の予想より少し弱いが証明できた。 この調子でいろいろ考えていきたい

集中講義終了。 素晴らしい先生の方のおかげでかなり分かりやすかった。

この前まで考えてた問題とは違うが、以前考えていた問題で進展があった。 その問題の大目標を達成したわけではないが、いい形の目標設定を先生にしてもらった。 後は、それが解ければいいのだが．．．

今日は自転車で学校へ行った。 片道90分もかかった。 明日は筋肉痛になりそう

全然いい方法が見つからん。 証明したいことは明確にしてあるけど、証明するための道具がない。 いろいろ調べてみても、今ほしい道具は見つからない。

明日は合宿

今考えている問題のlemmaを1つ証明できた。 もう2つほど証明するともしかしたらもしかするかもしれない

数学に慣れてきたせいか、意外とすらすら読める

卒研の時に(難しすぎて)断念した論文を明日から読み始めよう。 完全に理解しようとせずに、まず論理の流れをつかむことから始める。学部時代の教科書は、ちゃんと見直すと面白いね

最近、勉強内容が偏りすぎている気がする。 来週は、 (1)学部時代のテキストをもう一度見直す (2)卒業研究でやったことをもう一度勉強しなおす が目標。あと、余裕があれば合宿用スライドを完成させる

ねんがんのロードバイクをてにいれたぞ!

この続きLayer Decompositionから幅wで大きさdkのLayerwise separationというものが定義できる。 すると、treewidthが2\sqrt{3dk}+3w-1以下であることが証明でき、多項式時間でそのようなTree Decompositionを求めることができる。 全体的な議論の流れはつか…

使い方忘れてもた...

新しく配属になった3年生のためのJavaの勉強会があった。 研究でJavaを使う人が多いので、毎年やっている。 当時はJavaよりCの方が簡単だと思っていたが、今ではCのプログラムがまともに書けない状態。 後期のTAのために復習せねば

最近恐ろしく研究が進まないので、自分用のメモをつけることにする。 今はplanar graphのvertex coverやindependent setとかのfixed parameter algorithmを勉強中。 Parameterized complexity: exponential speed-up for planar graph problems 著者らによる…

test