$\newcommand{\set}[1]{\{#1\}}$ $\newcommand{\inset}[2]{\{#1 \mid #2\}}$ $\newcommand{\name}[1]{\emph{#1}}$ $\newcommand{\size}[2][]{\left| #2^{#1} \right|}$ $\newcommand{\sig}[1]{\mathcal{#1}}$

Chordal Graph: Maximum Cardinality Search

今回はグラフの性質のお話ではなくPEOを求めるためのアルゴリズムのお話をします. MCSとLex BFSというアルゴリズムのお話をします. chordal graphの性質についてはこの2つのアルゴリズムを説明した後にもまだまだ書きます. 今回は長くなるので,2回に分け…

Chordal Graph: Perfect elimination ordering

3回目のChordal Graph回です. 知識的にストックがあるのと,始めたばかりでやる気があるので,更新ペースがめちゃくちゃ早いです. 今回はPerfect elimination orderingについて説明します. Perfect elimination ordering (PEO) もchordal graphの重要で面…

Chordal Graph: Simplicial vertex

なんか意外に反響があった(アクセスログを見ていたらみんなが見ていてくれた)のでやる気を出したのと,少し今回の内容が簡単だったのもあって が〜っと書いてしまいました.2回目のChordal Graph回です. 今回は次回にやる予定のPerfect elimination order…

Chordal Graph: Minimal vertex separators

chocobaby-aporo.hatenablog.com Chordal Graph回の第一回目です.今回はMinimal vertex separatorsを紹介します. Minimal vertex separators まず,$G = (V, E)$中の頂点集合$S \subseteq V$が,vertex separator (separator)とは 次のような2頂点$u, v$が…

Chordal Graph

最近Chordal Graphがマイブームです. このシリーズの記事でわからないところやこれ間違っているぞっというのがあったら Twitterで教えてくれると僕が喜びます. Twitter ID: kazu0x17 Chordal Graphとは Chordal Graphとは任意の長さ4以上のサイクルに対し…

CodeFestival2016本戦の問題

この前Code Festival2016に行ってきました.問題はこんな感じでした. A問題 Where's sunuke まあ,A問題なのでやるだけ問題です. #include<iostream> using namespace std; int main(){ int h, w; std::cin >> h >> w; string s; for (int i = 0; i < h; i++) { for </iostream>…

ビームスタックサーチ

この前,ビームサーチを書いてみたので,今度はビームスタックサーチを書いてみました.この辺のサイトを参考に勉強しました. chokudaiサーチのメモ このサイトに載っているchokudaiさんのスライドが(ビームサーチをわかっている人なら)結構わかりやすい…

Code Festival 2016に参加しました

今年もCode Festivalを開催していただけて(しかも,本戦まで行けて)本当に楽しかったです.問題セットも良問ぞろいでした.下の方に今回解いた問題セットがあるのですが,どのコンテストでも1問以上はこの問題考えた人頭いいなと思う問題があってすごかっ…

初めての機械学習

なんやかんやあって初めて機械学習のアルゴリズムを実装しました.機械学習アルゴリズムの実装といっても大したことなくて,PRLMという教科書の最初にある多項式フィッティングというものを実装してみました.点が$N$点与えられるので誤差関数$E(\vec{w})$を…

ビームサーチ

研究室の後輩がマラソンに出るというので一緒に参加してみようかと思いました.ただ,まだ運営がvisualizerを用意してくれないので,とりあえず練習のため,ビームサーチを実装してみました.ビームサーチは名前は聞いたことがあるけどよくわからないアルゴ…

マークダウンでtexマクロを定義したい

最近マークダウンの書き方を少し覚えて,メモをとるのにマークダウンを使い始めました.基本ペンで文字を書くのを面倒臭がるのですが,PCでメモを取るのは苦じゃないので,マークダウンを使ってメモを取ることにしました. でも,メモとるのに結構数学の記法…