大学のレポート内で De Bruijn Sequence について書く機会があった. これまた以前と同じく, 折角なのでこちらのブログにも, 若干内容を変えつつ載せておくことにした.

De Bruijn Sequence は, オランダ人の数学者 Nicolaas de Bruijn に因んで命名された系列で, 特定の長さのすべての組み合わせを含む系列である. 次数 $n$ の $k$ 種類に関する De Bruijn Sequence $B(k, n)$ は, 長さ $n$ で表現可能なすべての部分列によって構成される. 次元数 $2$ (すなわちバイナリ) の De Bruijn Sequence は $B(2, n)$ であり, $n$ ビットの固有な部分系列から成る $2^n$ ビット長の系列である. 例えば, $B(2, 3)$ は $00011101_{(2)}$ であり $n$ に対する有向グラフが下図¹のように示される.

大学の授業で AWS の API を触る機会があり, その際に golang を使うようなので (API 一覧には, C++ 版もあるようなので, 個人的には C++ が良かった), 特に意義のないコードを取り敢えずいくつか書いてみている. ある程度文法がわかったら, まずはともかくクイックソートを書いてみたわけだが…

ふと, C++ でもこんなような記述, 普通に出来るべきなんじゃないかなぁと思った.

Prelude> :m +Data.Tuple.Extra
Prelude Data.Tuple.Extra> uncurry (+) $ first (*2) $ dupe 42
126
Prelude Data.Tuple.Extra> uncurry (+) $ (+42) &&& (*2) $ 42
168

取り敢えず, 似たような構文で同じような処理となるように作ってみた.

お題自由な学校のレポート課題¹内で, ショアのアルゴリズムを説明するために QFT の概要について示したのだが, 折角なのでその内容の一部を抜粋し, こちらのブログのほうにも載せておくことにした. ショアのアルゴリズムについては, 調べればいくらでも出てくるし, 学会誌, 書籍等で分かり易く述べられていることも多いので, 本エントリで特別取り上げることはしないが, その大体は以下のアクティビティ図の手順の通りである².

以前の投稿, ARPパケットに対する挙動からネットワーク上の盗聴者を特定するにて, 実験を行うにあたりリンクレイヤー上のパケットの受信と送信を行なった. このパケットを別のネットワークインタフェースから送出するようにすればブリッジになるし, MAC アドレステーブルと照合して転送すれば L2 スイッチにもなるとのことで, 一応 Linux 上で動くものを作ってみた.

2 枚の NIC が必要であるが, Virtual Box の仮想アダプタを利用すれば良い. 実装の本質的な部分は, 異なるディスクリプタへの書き込みのみである. これを応用して, 複数個のネットワークインタフェースにも対応してみたい.