小内山晶: /* 関連項目 */

2010-08-19T17:30:29Z

‎関連項目

2007年5月17日 (木) 13:43にキリカによる

2007-05-17T13:43:32Z

キリカ: http://ja.wikipedia.org/w/index.php?title=算法&oldid=9394451

2007-05-17T13:43:15Z

http://ja.wikipedia.org/w/index.php?title=算法&oldid=9394451

新規ページ

'''算法'''（'''さんぽう'''）には主に次の二通りの用法がある。

# [[計算機科学]]の分野で[[アルゴリズム]]の訳語として用いられる。
# [[数学]]の分野で「演算」と同義で用いられる。これについては本稿で詳述する。


----

''' ''n'' 項算法'''（'''エヌこうさんぽう'''）とは、最も広義には、[[集合]] ''A'' の[[直積|直積集合]] ''An'' の[[部分集合]] ''D'' から ''A'' への[[写像]] ''f'' のことをいい、''D'' をこの算法の定義域という。''n'' は任意の[[順序数]]でよい。
これを（仮に）''f'' の項数とよぶ。
''An'' は ''i'' < ''n'' をみたす順序数 ''i'' を添数とする ''A'' の元の族 (''ai'')''i''<''n'' すべてからなる集合を表す。
集合 ''A'' とそこにおける算法の族 ''R'' との組み (''A'', ''R'') を[[代数系]]という。

== 全域的算法 ==

通常は、''D'' = ''An'' の場合を考えることが多く、そういう算法 ''f'' を（仮に）全域的算法とよぶ。
また、''n'' が有限順序数の場合を考えることが多い。
その場合、''An'' は ''A'' の ''n'' 個の元の組み (''a''0, ''a''1, ..., ''a''''n''-1) の全体であって、''f'' によってこれをうつしたものは ''f''(''a''0, ''a''1, ..., ''a''''n''-1) と書くことができる。
しかしさらに、''n = 2'' の場合を考えることが多く、この場合、 ''f''(''a''0, ''a''1) を ''a''0 ''f'' ''a''1 とか ''a''0 ''a''1 ''f'' とか書くことが多い。

従って、全域的な 2 項算法とは、''A'' の元の二つ組み (''a'', ''b'') の各々に ''A'' の何らかの元を対応させる写像のことである。

例えば、二つの[[実数]] ''a'', ''b'' にその和 ''a'' + ''b'' を対応させる写像は、実数すべての集合における全域的 2 項算法であって、和の記号 + はこの算法（すなわち[[加法]]）の上記二番目の記法 ''a''0 ''f'' ''a''1 の ''f'' に当たるものと解される。
加法は普通の[[中置記法]]では ''a'' + ''b'' と書くが、[[逆ポーランド記法]]では ''a b'' + と書く。
これは、上記の ''a''0 ''a''1 ''f'' という記法に当たるものと解される。
実数の[[減法]]・[[乗法]]・[[除法]]についても同様である。
ただし除法は、0 で割ることができないから、全域的ではない。

1 項算法も珍しくはない。
例えば、[[複素数]]にその共役複素数を対応させる写像は 1 項算法である。
また、[[体 (数学)|体]] ''K'' 上の[[線型空間]] ''V'' においては、 ''K'' の任意の元 ''a'' と ''V'' の任意の元 ''v'' に対して ''V'' の元 ''av'' が存在するが、これは、''K'' を添数集合とする ''V'' の 1 項算法族 (''fa'')''a''∈''K'' があって ''fav'' を ''av'' で表していると解される。
こう考えれば、例えば[[環論|環]] ''R'' 上の[[加群]] ''M'' における ''R'' の元の ''M'' への作用のような「外的算法」は、すべて 1 項算法とみなされる。
なお、1 項算法は単項算法とよぶ方が語呂がいい。

== 非全域的算法 ==

非全域的（あるいは局所的）な算法も珍しくはない。
例えば、あらゆるサイズの[[行列]]の全体を ''M'' で表すとき、''M'' の二元 ''A'', ''B'' にその和 ''A + B'' を対応させる写像は ''M'' における 2 項算法であるが、''A'', ''B'' が同サイズのときにしか ''A + B'' が定義されないから、非全域的算法である。
''A'', ''B'' にその積 ''AB'' を対応させる写像も ''M'' における 2 項算法であるが、''A'' の列の個数と ''B'' の行の個数が等しいときにしか ''AB'' が定義されないから、やはり非全域的算法である。

[[形式言語]]における算法は、非全域的のものが一般的である。
例えば、述語言語（論理式と項とから成る）における論理記号は、論理式に対してのみ適用可能な 2 項または 1 項の非全域的算法を表すと解される。

項数が 2 より多い非全域的算法も珍しくはない。
例えば、述語言語における ''n'' 変数関数記号や ''n'' 変数述語記号は、項に対してのみ適用可能な ''n'' 項算法を表すと解される。

== 超限的な項数を持つ算法 ==

超限順序数を項数とする算法もある。
例えば、最小の超限順序数（非負整数の全体の順序型）を ω で表し、実数の全体を '''R''' で表すと、直積 '''R'''ω は実[[数列]] ''a''0, ''a''1, ... の全体であるが、収束する実数列にその[[極限]]を対応させる写像は、非全域的の ω 項算法である。
数列の極限をこのように ω 項算法とみなすことには効用もある。
たとえば、数列の極限の ε-''n'' 式定義を ω 項算法の代数的条件によって書き換えて、極限を公理化することができる。
つまり、'''R''' における次の六条件をみたす ω 項算法 ''L'' が極限に他ならない。
# ''L''(''a'', ''a'', ...) = ''a''
# ''L''(''a''1, ''a''2, ...) = ''a'', ''L''(''b''1, ''b''2, ...) = ''b'', ''an'' ≤ ''bn'' (''n''=1,2,...) なら ''a'' ≤ ''b''
# ''L''(''a''1, ''a''2, ...) = ''a'' なら ''a''1, ''a''2, ... の任意の部分列 ''b''1, ''b''2, ... に対して ''L''(''b''1, ''b''2, ...) = ''a''
# （[[はさみうちの原理]]）''L''(''a''1, ''a''2, ...) = ''L''(''b''1, ''b''2, ...) = ''a'', ''an'' ≤ ''cn'' ≤ ''bn'' (''n''=1,2,...) なら ''L''(''c''1, ''c''2, ...) = ''a''
# （[[アルキメデスの原理]]）''L''(''a''±(1/1), ''a''±(1/2), ''a''±(1/3), ...) = ''a'' （複号同順）
# ''a''1, ''a''2, ... の任意の部分列 ''b''1, ''b''2, ... に ''L''(''c''1, ''c''2, ...) = ''a'' なる部分列 ''c''1, ''c''2, ... があれば ''L''(''a''1, ''a''2, ...) = ''a''
大学 1, 2 年次の学生や高校生に「行列の算法は非全域的算法である」とか「極限は ω 項算法である」とか教えるのは勧められないが、数理科学者がそういうことを認識するのは、視野が広がるので好ましいであろう。

== 算法概念の拡張 ==

冒頭に定義したとおり、''f'' が集合 ''A'' における ''n'' 項算法であるとは、''f'' が ''An'' のある部分集合 ''D'' から ''A'' への写像であることをいう。
そうすると ''f'' は、''An''×''A'' の部分集合 {((''x''1, ... , ''x''n), ''y'') | (''x''1, ... , ''x''n)∈''D'', ''f''(''x''1, ... , ''x''n) = ''y'' } と同一視される。
従って、もしも ''f, g, ... '' が ''n'' 項算法なら、それらの集合としての和を考えることができる。
しかし一般には、''f'' を動かせば、それに応じて ''n'' も動く。
そこで、より一般に、''An'' (''n'' = 0, 1, 2, ... < ω) の集合としての直和を ''A''* で表し、''A''* × ''A'' の部分集合 ''R'' のことまでも算法とよぶことにする。
ただしこういう''広義'' の算法については、α ∈ ''A''* と ''y'' ∈ ''A'' とが (α, ''y'') ∈ ''R'' をみたすことを通常の算法のように ''R''(α) = ''y'' と書き表すことはできず、α ''R'' ''y'' と書かなければならない。
一つの α ∈ ''A''* に対して (α, ''y'') ∈ ''R'' をみたす ''y'' が唯一つとは限らないからである。
この意味でこれは、もはや算法ではなく（やはり''広義の'' ）関係とよぶべきかもしれない。

こういう広義の算法・関係は、[[数理論理学]]にしばしば現れる。
例えば述語言語 ''A'' において、意味写像 ''f'' * の下で inf {''f'' *(''a''1), ... , ''f'' *(''a''n)} ≤ ''f'' *(''b'') をみたす論理式 ''a''1, ... , ''a''n, ''b'' （''n'' は任意）から出来る ''A''*×''A'' の元 ((''a''1, ... , ''a''n), ''b'') の全体を ''R'' で表せば、これは上記の意味での広義の算法・関係である。

このように算法の概念と関係の概念をともに拡張して統合すると、算法と関係とを統一的に扱うことができて極めて有効である。

== 命名について ==

算法を「演算」とよぶことも多い。
しかし、ここで考えた「算法の概念」の名前としては、「算法」も「演算」も相応しくはないであろう。
「算法」は「計算の規則」あるいは「計算の方法」を連想させ、「演算」は「計算を演ずるという行為」を連想させ、ともに「写像」としての「算法の概念」を連想させにくい。
一つの写像に対しても、それの「計算の方法」は一般に複数あり、「計算する方法」も「計算の規則」も具体的に記述できない場合さえあり、人や機械が「計算を演ずるという行為」はもちろん写像とは異なるからである。
「写像」という概念が未発達で「計算」と「計算の仕方」の違いも曖昧であった時代に生まれた「算法」とか「演算」とかの言葉を用いるのが間違っているのであろう。

冒頭に記したとおり、計算機科学の分野ではアルゴリズムを「算法」とよぶこともあり、その場合には上記の意味での「算法」は「演算」とよぶ方がよいかもしれない。
しかし数学の分野では、上記の意味での「算法」という術語も昔から定着している。
むしろアルゴリズムを「算法」ではなく「計算手順」とする方が、意味からいっても先例を尊ぶ点でも、好ましいであろう。

== 関連項目 ==
*[[代数系]]
*[[代数学]]
*[[演算子]]
*[[単項演算]]
*[[二項演算]]

[[Category:代数的構造|さんほう]]
[[Category:数学に関する記事|さんほう]]

[[en:Operation_(mathematics)]]
[[fr:Opération_(mathématiques)]]
[[hu:Művelet]]

@@ 94行目: / 94行目: @@
 *[[単項演算]]
 *[[二項演算]]
 [[Category:代数的構造|さんほう]]
@@ 99行目: / 100行目: @@
 [[en:Operation_(mathematics)]]

@@ 99行目: / 99行目: @@
 [[en:Operation_(mathematics)]]
-[[fr:Opération_(mathématiques)]]
-[[hu:Művelet]]
+<div style="margin:0.5em 0;background-color:#f6f6f6;border:1px solid #ccc;padding:3px;font-size:80%">

算法 - 変更履歴

小内山晶: /* 関連項目 */

2007年5月17日 (木) 13:43にキリカによる

キリカ: http://ja.wikipedia.org/w/index.php?title=算法&oldid=9394451