Tadachika Oki の日記

私の日々の雑感です。https://sites.google.com/site/tadachikaoki0/

カレンダーにおける予定の圧縮表現

ふと、カレンダーを眺めていると、

「これは表なので、 2 部グラフで表現できるのではないか。」

と思って書いてみた。

 

カレンダーを観察すると、列が曜日、行が第何週かを表すので、これをなるべく簡潔に表現したい。

 

2 部グラフの頂点集合の分割の一方を、第何週かを表す数の集合、もう一方を曜日の集合とすると、辺の存在で予定があることを表現できる。ここで、辺に日のラベルをつける。この表現により、第何週の何曜日、何日にどのような予定があるか圧縮して表現できる。

 

f:id:salmonsnare:20160715234118j:plain

上記の例の場合、予定 A が 第 2 週の 7 日にあり、予定 B が第 5 週の 25 日にあることがわかる。

 

min-cost connectivity problem のサーベイ

大学院生の頃、グラフ連結度周辺の研究をしていた時期があって、今でもたまに文献を読む。

 

Nutov というグラフ連結度に関するアルゴリズムが専門の研究者がいて、サーベイを自身のサイトに上げていたのだが、最近アップデートされていた。リンクを貼る。

 

Node-Connectivity Survivable Network Problems, 

http://www.openu.ac.il/home/nutov/SN.pdf

MEMO: 最小スパニング木問題、巡回セールスマン問題、及び最小スタイナー木問題等の共通の一般化として、サバイバルネットワーク問題とよばれるものがあるのだがそのサーベイ。

 

The k-Connected Subgraph Problem

http://www.openu.ac.il/home/nutov/kCS.pdf

 MEMO: 辺重みつきのグラフ G が与えられたとき、k連結であるような G の部分グラフを算出する問題を k 連結部分グラフ問題とよび、そのサーベイ。辺重みのつけ方で問題を分類している。

Wiring Diagram について

Wiring Diagram は多入力と多出力ポートをもつ箱とその入れ子で表現できる図式で、hierarchical なシステムをモデリングする際に、大変重宝している。
その気になれば XML の入れ子も、プログラミングにおける関数の呼び出しの流れも、シームレスにこれで表現できるし、最近は、データフローを書く際には個人的に全部これでメモしている。
operad とよばれる数学的対象にもとづいているらしい。ここは深堀できていないが、圏の一般化であることはなんとなくわかった。
参考:
[Spivak 2016] Operads as a potential foundation for
systems of systems (slide),http://categoricaldata.net/operadics/OperadicSoS.pdf
MEMO: 導入的な資料。
[Yau 2015] Operads of Wiring Diagrams, http://arxiv.org/pdf/1512.01602v2.pdf
MEMO: 近年の Wiring Diagram に関するサーベイ。Wiring Diagram は有向グラフや無向グラフのようなものがあり、データフローを表現する場合は有向が適している。無向の場合は、入出力の区別の特にないポートをもつような箱を hierarchical に表現する。(SQL 文そのものを無向の Wiring Diagram で書けるらしい。)

Erlang で Hello, World

[はじめに]

本エントリではプログラミング言語 Erlang でどのようにして Hello, World を記述するかを紹介する。 Erlang は並列処理向きのプログラミング言語とのこと。

 

[環境構築]

Step 1. Erlang  を導入。 (各自の利用する OS に合わせて導入されたい。)

Step 2. Eclipse を導入。https://eclipse.org/downloads/

Step 3. Plugin eride を導入。http://erlide.org/

 

f:id:salmonsnare:20160410172207p:plain

 

[コード解説]

-module(test).

ここでのモジュール名は "test"。モジュール名はファイル名と一致する必要がある。

ファイル名は  test.erl。

 

- export([hello_world/0]).

モジュール test は関数　hello_world をもち、

hello_world の引数は 0 個。

 

hello_world() -> io:fwrite("Hello, world!\n").

"test:hello_world()."でこの関数は呼び出され、標準出力する。

 

[実行方法]

erlideにおける実行方法を説明する。 Console が上下に 2 分割されている。

Console の下部に"test:hello()_world()."と入力すると、

上部に出力結果が表示される。

 

[言語を使った感想]

・引数の個数を指定する方法が独特。

・文の最後はピリオドであることに驚き。

・がんばったら結構書けそう。

 

[エントリを書いた経緯]

私は Java プログラマ初級者で、使える言語の幅を広げたく思い、ふと休日にプログラミングをしようと考えた。その際に、数年前に m-hiyama さんのブログ (

http://d.hatena.ne.jp/m-hiyama/20070515/1179203855

) で Erlang とよばれる言語を見たことがあるのをふと思い出した。

 

それから数日後、休日にスーパーボールを部屋で投げながら、特にやりたいこともなくぼうっとしていると、半ば衝動的に環境構築を行い Hello World を書きたくなった。ついでに実名ブログも書きたくなった。モチベーションが高いうちにどんどんやろうと思う。

 

参考文献

[1] [O] これから15分でErlangを始めるための資料