nkhrlab~

140字超の記事

無向グラフに関する頂点数・染色数制約下での辺数の最大化

グラフ アルゴリズム

この記事で扱う問い

無向グラフ G = (V, E)の染色数を \chi(G)と表すとき，グラフ Gに対する頂点数についての制約 |V| = mおよび染色数についての制約 \chi(G) = nを同時に満たす無向グラフのうちで，辺数が最大であるものはいかなるグラフであろうか．ただし， 2 \leq n \leq m.

特殊な m, nに対する答え

まず，特殊な m, nについて考えよう．

m = 7, n = 2について考える*1．すると，この問題は「頂点数 7，染色数 2である無向グラフ G = (V, E)のうち，辺数最大なるグラフとはどのようなものか？」という問いになる．

染色数が 2であるから，グラフ Gの頂点集合 Vはちょうど 2個の独立集合への分割 S \in 2^{2^V}, S = \{S_1, S_2\}をもつはずである．さらに， |S_1| = x_1, |S_2| = x_2とおくと，制約を満たすグラフのうち辺数が最大となる Gについて，辺数は x_1, x_2のみによって決まる．まずはこのことを確認しよう．

*1:この m, nの組み合わせに対する問題は大学院の入学試験でも出題例がある．

続きを読む

WhiteHat Challenge 01 (2017/02/26) - Writeup

Writeup CTF セキュリティ

チーム「Harekaze」のメンバーとしてCTF「WhiteHat Challenge 01」に参加した．わずか1個ではあったものの初めてセキュリティの問題でフラグが取れたので，Writeupを書く．

[Mics 25] Mics001

準備

サーバに接続してフラグを取る問題．とりあえず問題文に示されたサーバに接続を試みた．

$ nc 103.237.98.32 3737
< Inject me if you can >
         --------------------
         \   ^__^
          \  (oo)\_______
             (__)\       )\/\
                 ||----w |
                 ||     ||

input name to check pass, ex:linh, trang...:

cowsayとはなかなかに挑発的．どうやら名前となる文字列を入力すれば良いらしい．

続きを読む

情報処理技術者試験の選択肢の順序は人間が決定しているか？

統計 情報処理技術者

背景と目的

定期試験や入学試験などの試験中，択一式の問題で解答に迷ったら，あなたはどうするだろうか．おそらく，答えがわからなくてもとりあえずどれか一つを選ぶのではないだろうか．一般的な方式の試験では，白紙のまま提出するよりもまぐれで当たる可能性を狙ってとりあえず何か選んでおくほうが合理的である．

それでは，まぐれ当たりを狙うべくどの選択肢を解答すべきであろうか．計算機によって，すべての問題に対して選択肢の順序が等確率で，しかも問題の間で独立に決定される場合は，どのように解答を決定しても，得点の期待値はランダムに決定した場合と変わらないだろう．一方で，選択肢の順序の決定にある傾向がある場合は，その傾向に合わせた解答の決定を行うことで得点の期待値を改善できると考えられる．例えば，「大学入試センター試験」の対策において，「迷ったら2番か3番だ」*1などの解答に迷った場合の「対策」が(時に冗談として)論じられることがある．これは，あらかじめ解答に迷った場合の行動を決めておくことで，正答できるか不確かな問題につまづいていたずらに時間を消費することを防ぐ意味のほか，「最初や最後の選択肢より中間の選択肢を正答として選びやすいのではないか」という，問題作成者の心理などに関する推測をも含んでいると考えられる．

同種の試験が繰り返し行われ，十分な量のデータが蓄積していれば，統計的手法によって選択肢の決定を人間が行っているかを推測できるだろう．この記事では，人間が「最初や最後の選択肢より中間の選択肢を正答として選びやすい」という仮定のもとで，「情報処理技術者試験」の択一式問題を対象に\chi^2検定を行い，選択肢の決定に偏りがあるかを推測する．

*1:私が高校生だったころ，社会科の先生にこう教わった．

続きを読む

ワーシャル-フロイド法による最短経路の導出 - SQLによる解法

DB SQL グラフ

本文は後で書こう．

次に示すSQL文は，有向グラフG = (V, A)および辺に対する重みを与える写像f : A \to \mathbb{R}について，最短経路のコストを導く．これをそのまま実行すると，次のV, A, fについて，すべての2頂点間の最短経路のコストc : V^{2} \to \mathbb{R}を導く．
V = \{1, 2, 3, 4, 5\}
A = \{ (1, 2), (2, 3), (2, 4), (3, 4), (3, 5), (4, 3), (4, 5), (5, 2) \}
f( (1, 2) ) = 2, f( (2, 3) ) = 3, f( (2, 4) ) = 5, f( (3, 4) ) = 1,
f( (3, 5) ) = 1, f( (4, 3) ) = 2, f( (4, 5) ) = 4, f( (5, 2) ) = 3

続きを読む

RDBMSごとのWITH句の実装の差異

DB SQL

WITH句は一時表を作成する句で，SQL99より規格に取り入れられた．しかしながら，各RDBMSのWITH句の実装はまちまちである．

次のSQL文を見てみよう．

WITH foo(a, b) AS
(
  SELECT 1, 2
  UNION
  SELECT 3, 4
)
SELECT * FROM foo

このSQL文を実行すると，PostgreSQLとSQL Serverでは次のような結果を得る．(表示形式はRDBMSによって若干異なる．)

  a |  b 
----+----
  1 |  2 
  3 |  4
続きを読む

二部グラフの最大マッチングの発見問題 - SQLによる解法

DB SQL グラフ

本文は後で書こう．

とりあえず使えそうなSQL文だけ載せておく．次に示すSQL文は，二部グラフG = (A, B, E)について，最大マッチングを発見する．これをそのまま実行すると，次のA, B, Eに対して最大マッチングを発見する．
A = \{1, 2, 3, 4, 5\}
B = \{6, 7, 8, 9, 10\}
E = \{\{1, 6\}, \{1, 7\}, \{2, 9\}, \{3, 6\}, \{4, 8\}, \{4, 9\}, \{5, 10\}\}

続きを読む