アロケーションの基本
基本的な定義
以下、a, b, cなどは任意の実数（+∞、-∞を含むかも知れない）、x, y, zなどは0以上1以下の実数だとする。[a, b;x]のような形式を考える。これは、aとbを端点とする区間を表し、それに実数xが付随している。[a, b;x]で表現される対象を重み付き区間（weighted interval）と呼ぶ。
a＞b のとき、[a, b;x]は空集合、[a, a;x]は一点となる。便宜上、空区間を[;x]、1点区間を[a;x]と書く。これらはゴミ扱いされるが、計算の途中では出てくるかもしれない。空でも1点でもない（重み付き）区間をプロパーな区間と呼ぶ。
重み付き区間をα、β、γなどギリシャ小文字で表す。また、単に「区間」と言っても重みが付いているとする。重み（重さ）は、本来実数値だが、現実にはパーセント値として0から100の整数で表す。が、ここでは理屈の話だから実数のまま扱う。
区間α = [a, b;x]に対して、begin(α) = a, end(α) = b, dur(α) = (b - a) とする。空区間は考えない（例外だ）。
区間のリスト[α1, α2, ...]を考える。begin(α1)≦begin(α2)≦ ... となっているとき、このリストは整列されているという。以下で区間のリストを考えるとき、たいていは整列されているとする（整列されてなかったら、まずは整列する）。
区間のリストがあるとき、それをより簡略な形にすることを考える。まず、一点区間は除いておく（空区間は最初から入らないようにすべき）。つまり、すべての区間はプロパーだとしよう。
リストの正規化
[a, b;x]と[c, d;y]がリスト内で隣り合う区間だとする。次の条件を満たすとき、縮約可能という。
- x = y （重みが等しい）
- b = c （ピッタリくっついている）
このとき、[a, b;x]と[c, d;y]を[a, d;x]に置き換える操作を縮約（contraction）と呼ぶ。縮約すると、リストの長さが1つ短くなる。縮約は何度も繰り返し行えるかもしれない。
[a, b;x]と[c, d;y]がリスト内で隣り合う区間だとするとき、c＜b なら、その区間対はオーバラップしているという。オーバラップしている区間対を次の3つの区間に分ける。
- [a, c;x]
- [c, b;x+y]
- [b, b;y]
a=cのときは、最初の区間が点区間になるので捨てる。b=dのときは、3つ目の区間が点区間になるので捨てる。この操作を（うまい名前がないので）オーバラップ解消と呼ぶ。オーバラップ解消で、2つの区間が3つ、または2つ、または1つになる。
次の条件をすべて満たすリストは正規形と呼ぶ。
- 整列されている。
- すべての区間はプロパーである。
- 簡約可能な対が存在しない。
- オーバラップしている対が存在しない。
任意に与えられたリストを正規形にすることを正規化と呼ぶ。normalizeを正規化する関数だとすると、
- Aが正規形 ⇔ normalize(A) = A
- normalize(normalize(A)) = normalize(A)
であることに注意せよ。
オーバーフローとアロケーション
リスト[α1, ...]があるとき、これを正規化すると、重みが1を超える区間が生じることがある。正規化後に重みが1を超える区間を持つようなリストはオーバーフローしているという。
consをLispの意味でのリスト操作として、cons(α, A) がオーバーフローしないとき、区間αはリストAにconsableと呼ぼう。
区間とは別に、(d, x)という形を考える。これは「durationがd、重みがx」という意味で、beginが指定されてない（未定な）区間の表現と考える。区間[a, b;x]が、b - a = dのとき、(d, x)の実現とか具体化と呼ぶ。
[追記]以下のアロケーションの記述で、αの位置に関して上限と下限の条件が抜けている。実際には、実数s, tがあって、アロケート可能な範囲は[s, t]内に限定する。この条件がないと、無意味なアロケーションを許すことになる。[/追記]
リストAが与えられたとき、(d, x)の適当な実現αが存在して、αがAにconsableなとき、(d, x)はAにおいてアロケート可能という。αは、(d, x)のAにおけるアロケーションであるという。アロケーションはたくさん（無限に）あるかもしれないので、特定のアロケーションをアロケーション・インスタンスとも呼ぶ。
オーバーフローしてないリストAと、(d, x)を与えられて、アロケート可能かどうかを判定する問題、そして、アロケート可能ならアロケーション・インスタンスを決定する問題をアロケーション問題と呼ぶ。アロケーション問題が解けるのはあきらかなので、効率的なアルゴリズムや美しい(?)データ構造を求めることが興味の対象となる。
さらに
上に述べたアロケーション問題は、もっとも簡単なケースであり、実際にはもっと複雑になる。簡単なケースが解けないでは複雑はケースが解けるわけがないので、簡単なケースを十分に理解する。
