|
|
| 1行目: |
1行目: |
| − | {{for|準多項式で表される計算時間|w:Quasi-polynomial time}} | + | {{テンプレート:20180815sk}} __NOINDEX__ |
| − | '''準多項式'''（じゅんたこうしき、quasi-polynomial、pseudo-polynomial）は[[多項式]]を一般化したものである。多項式の係数は[[環 (数学)|環]]の元になっているが、準多項式の係数は整数周期を持つ[[周期関数]]である。準多項式は[[組合せ数学]]の多くの理論でさまざまな対象の列挙子として用いられる。
| |
| − | | |
| − | 準多項式は <math>q(k) = c_d(k) k^d + c_{d-1}(k) k^{d-1} + \cdots + c_0(k)</math> と表される。ここで <math>c_{i}(k)</math> は整数周期を持つ周期関数である。<math>c_d(k)</math> が 0 でなければ ''q'' の次数は ''d'' である。また <math>n \equiv i \bmod s</math> で <math>f(n) = p_i(n)</math> であるような多項式 <math>p_0, \dots, p_{s-1}</math> が存在するとき、関数 <math>f \colon \mathbb{N} \to \mathbb{N}</math> は準多項式である。多項式 <math>p_i</math> を ''f'' の成分という。
| |
| − | | |
| − | == 例 ==
| |
| − | * [[有理点]] <math>v_1,\dots,v_n</math> を頂点とする ''d'' 次の[[ポリトープ]] ''P''について、''tP'' を <math>tv_1,\dots,tv_n</math> の凸包と定義する。関数 <math>L(P,t) = \#(tP \cap \mathbb{Z}^d)</math> は ''t'' による ''d'' 次の準多項式である。このとき ''L(P,t)'' は <math>\mathbb{N} \to \mathbb{N}</math> 関数である。これはウジェーヌ・エルハート（Eugène Ehrhart）にちなみ'''エルハート準多項式'''と呼ばれる。
| |
| − | * 2つの準多項式 ''F''、''G'' の[[畳み込み|合成積]]は
| |
| − | :<math>(F*G)(k) = \sum_{m=0}^k F(m)G(k-m)</math>
| |
| − | と定義される。これは次数 <math>\le \deg F + \deg G + 1</math> の準多項式になっている。
| |
| − | | |
| − | == 関連項目 ==
| |
| − | * [[エルハート多項式]]
| |
| − | | |
| − | == 参考文献 ==
| |
| − | * [[w:Richard P. Stanley|Stanley, Richard P.]] (1997). [http://www-math.mit.edu/~rstan/ec/ ''Enumerative Combinatorics'', Volume 1]. Cambridge University Press. ISBN 0-521-55309-1, 0-521-56069-1.
| |
| − | | |
| − | {{Math-stub}}
| |
| − | {{DEFAULTSORT:しゆんたこうしき}}
| |
| − | [[Category:多項式]]
| |
| − | [[Category:組合せ論]]
| |
| − | [[Category:代数的組合せ論]]
| |
| − | [[Category:数学に関する記事]]
| |