複雑性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/09/12 06:14 UTC 版)
複雑性（ふくざつせい、英: complexity）という用語は、多数の部品が入り組んで配置された何らかのものを特徴付ける言葉として使われる。科学として複雑性を研究するアプローチはいくつか存在しており、本項目ではそれらを概説する。
- ^ Weaver, Warren (1948), “Science and Complexity”, American Scientist 36: 536 (Retrieved on 2007–11–21.)
- ^ Johnson, Steven (2001). Emergence: the connected lives of ants, brains, cities, and software. New York: Scribner. pp. p.46. ISBN 0-684-86875-X
- ^ Lloyd, Seth (2006). Programming the Universe. Knopf. ISBN 978-1400033867
- ^ Jacobs, Jane (1961). The Death and Life of Great American Cities. New York: Random House
- ^ Ulanowicz, Robert, "Ecology, the Ascendant Perspective", Columbia, 1997
- ^ Greenlaw, N. and Hoover, H.J. Fundamentals of the Theory of Computation, Morgan Kauffman Publishers, San Francisco, 1998
- ^ a b Mark Burgin (2005), Super-recursive algorithms, Monographs in computer science, Springer.
- ^ Blum, M. (1967) On the Size of Machines, Information and Control, v. 11, pp. 257-265
- ^ Burgin, M. (1982) Generalized Kolmogorov complexity and duality in theory of computations, Notices of the Russian Academy of Sciences, v.25, No. 3, pp.19-23
- ^ Burgin, M. and Debnath, N. Hardship of Program Utilization and User-Friendly Software, in Proceedings of the International Conference “Computer Applications in Industry and Engineering”, Las Vegas, Nevada, 2003, pp. 314-317
- ^ Debnath, N.C. and Burgin, M., (2003) Software Metrics from the Algorithmic Perspective, in Proceedings of the ISCA 18th International Conference “Computers and their Applications”, Honolulu, Hawaii, pp. 279-282
- ^ Johnson, Neil F. (2007). Two’s Company, Three is Complexity: A simple guide to the science of all sciences. Oxford: Oneworld. ISBN 978-1-85168-488-5
- ^ Lissack, Michael R.; Johan Roos (2000). The Next Common Sense, The e-Manager’s Guide to Mastering Complexity. Intercultural Press. ISBN 9781857882353
複雑性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/20 10:04 UTC 版)
AOTコンパイラ方式では1つのバイナリを実行するだけでプログラムが機能する。一方インタプリタ方式では、まずインタプリタをインストールしその上でソースコードを動かす必要がある。その結果全体のプログラムサイズが大きくなり、ユーザーの手間が増える場合がある（複雑性が高い）。またJITコンパイル方式でも同様の複雑性が生まれる。
※この「複雑性」の解説は、「インタプリタ」の解説の一部です。
「複雑性」を含む「インタプリタ」の記事については、「インタプリタ」の概要を参照ください。
複雑性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/10/23 06:34 UTC 版)
単純なループでは、ループ制御は単なる管理オーバヘッドである。ループ自体は必要な結果に直接貢献することはなく、単にプログラマが同じコードをいくつもコーディングする手間を省くだけである。それだけであれば、コードの複製はプリプロセッサやエディタの機能を使っても実現できる。同様に if 文などの他の制御構造もコードの複製で置き換えることもできるが、結果として滅茶苦茶なコードが出来上がってしまう。プログラムは組み合わせに絶えず注意することができるが、人間は退屈な作業に我慢できず、間違いを犯す。 通常のループループ展開後 for i:=1:8 do if i mod 2 = 0 then do_evenstuff(i) else do_oddstuff(i); next i; do_oddstuff(1); do_evenstuff(2); do_oddstuff(3); do_evenstuff(4); do_oddstuff(5); do_evenstuff(6); do_oddstuff(7); do_evenstuff(8); しかし、もちろん展開される中身は手続き呼び出しである必要はない。次の例ではインデックス変数の計算が関わっている。 通常のループループ展開後 x(1) = 1; For i:=2:9 do x(i):=x(i - 1)*i; print i,x(i); next i; x(1):=1; x(2):=x(1)*2; print 2,x(2); x(3):=x(2)*3; print 3,x(3); ...etc. . コンパイラのループ展開によって大量のコード（特に print 文）が生成されるとしても、更なる最適化が可能である。この例ではループ内で x(i) と x(i - 1) しか参照しておらず（後者は x(i) の値を作るためにのみ参照）、配列 x に他から参照することがないなら、配列の各要素を単純な変数に置き換えることもできる。しかもこのコードでは各変数の値を定数から求めていて、全て定数とみなすこともできる。すると次のように最適化できる。 print 2,2;print 3,6;print 4,24;...etc. コンパイラが x を階乗のテーブルだと認識したとしたら驚きである。 一般にループの中身は大きく、複雑な配列のインデックス付けに関連している。その場合は最適化コンパイラに展開を任せるのが最善であろう。最も内側のループを展開することで様々な最適化が可能となるかもしれないが、ループ回数が多くない限り効果は限定的である。
※この「複雑性」の解説は、「ループ展開」の解説の一部です。
「複雑性」を含む「ループ展開」の記事については、「ループ展開」の概要を参照ください。
複雑性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/11 04:46 UTC 版)
「誤解を与える統計グラフ」の記事における「複雑性」の解説
グラフは統計データを容易に解釈するために作られるものである。しかし、複雑すぎるグラフはデータを分かりにくくし、解釈するのを難しくする可能性がある。
※この「複雑性」の解説は、「誤解を与える統計グラフ」の解説の一部です。
「複雑性」を含む「誤解を与える統計グラフ」の記事については、「誤解を与える統計グラフ」の概要を参照ください。
複雑性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/23 07:10 UTC 版)
「従業員スケジューリングソフトウェア」の記事における「複雑性」の解説
アルゴリズムは、誰が働いているかだけでなく、労働者に必要な特定の仕事やタスクも決定するために、従業員スケジューリングソフトウェア内で使用されます。システムは引き続き監視する必要があり、詳細の割り当てに関するその他の問題は手動で実行されます。 名簿の問題とモデルのコンテキスト内で、違いを解決するための3つの主な要因があります。休日のスケジュールと作業ラインの構築とタスクの割り当ての統合、名簿の構築、および需要の種類です。 したがって、これらの複雑さにより、すべての職場で、独自のルール、問題、およびニーズのセットに基づいて従業員スケジューリングソフトウェアを最適化する必要があります。 さらに、コストを最小限に抑え、従業員の好みを満たし、シフトを従業員間で公平に分配し、すべての職場の制約を満たす最適なソリューションを決定することは困難です。多くの組織では、名簿の作成に携わる人々は、高レベルの従業員満足度を達成しながら、適切な従業員を適切なタイミングとコストで提供するための意思決定支援ツールを必要としています。 作業環境は絶えず変化するため、ニーズや要求に応じて柔軟性を持たせるために、新しいモデルとアルゴリズムを作成する必要があります。たとえば、総労働力の増加など、多数の新入社員が採用された場合、そのような変更を可能にするために、スケジューリングソフトウェアを更新する必要が生じる可能性があります。
※この「複雑性」の解説は、「従業員スケジューリングソフトウェア」の解説の一部です。
「複雑性」を含む「従業員スケジューリングソフトウェア」の記事については、「従業員スケジューリングソフトウェア」の概要を参照ください。
複雑性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/02/01 06:20 UTC 版)
計算複雑性理論では、乱択アルゴリズムは確率的チューリングマシンとしてモデル化される。ラスベガス法とモンテカルロ法を含むいくつかの「複雑性クラス」が研究されている。 RP 最も基本的な確率的複雑性クラス。決定問題LがRPに属するとは、ある(最悪計算量の意味での)多項式時間乱択アルゴリズムAが存在して、A(x)が「はい」を出力した場合に x ∈ L {\displaystyle x\in {}L} である確率は1/2以上で、「いいえ」を出力した場合に x ∉ L {\displaystyle x\notin {}L} である確率は1であるときに言う。(なお上述の「1/2」を0と1の間にある任意の定数に置き換えても定義は変わらない)。 Co-RP RPの補問題のクラス。すなわち、LcがRPに属するとき、決定問題LはCo-RPに属するという。 BPP 決定問題LがBPPに属するとは、ある(最悪計算量の意味での)多項式時間乱択アルゴリズムAが存在して、A(x)が「はい」を出力した場合に x ∈ L {\displaystyle x\in {}L} である確率も、「いいえ」を出力した場合に x ∉ L {\displaystyle x\notin {}L} である確率も2/3以上であるときに言う。(なお上述の「2/3」を1/2と1の間にある任意の定数に置き換えても定義は変わらない)。 ZPP 決定問題LがZPPに属するとは、(最悪時間は多項式とは限らないが)平均は多項式時間のある乱択アルゴリズムAが存在し、A(x)が「はい」を出力した場合に x ∈ L {\displaystyle x\in {}L} である確率も、「いいえ」を出力した場合に x ∉ L {\displaystyle x\notin {}L} である確率も1であるときに言う。 NP困難問題などのようにこれらのクラスよりも難しい問題では、乱択アルゴリズムでさえも十分ではなく、近似アルゴリズムが必要となる。 歴史的に見れば、1976年にミラー-ラビン素数判定法によって素数判定が乱択アルゴリズムで効率的に解けることが発見され、乱択アルゴリズムの研究が盛んになった。当時、素数判定の実用的な決定的アルゴリズムは知られていなかった。 ミラー-ラビン素数判定法は、2つの正の整数 k と n について「k は n が合成数であることの証拠である」というような二項関係に基づいている。これをもう少し具体化すると、 n が合成数である証拠があるなら、n は合成数（素数でない）である n が合成数なら、n 未満の自然数の少なくとも4分の3は n の合成性の証拠である n と k が与えられたとき、k が n の合成性の証拠かどうかを素早く判定するアルゴリズムがある 以上から、素数判定問題が Co-RP クラスであることを暗示していることがわかる。ある合成数 n より小さい100個のランダムに選ばれた数があるとき、合成数である証拠となる数を見つけられない確率は (1/4)100 であり、多くの実用的な目的にはこれが十分によい素数判定となる。n が大きい場合、これ以外の実用的な素数判定法は存在しないだろう。間違う確率は、乱数を使った判定を行う回数を増やせば増やすほど減っていく。 従って、実際には間違う確率を非常に小さくできるため、間違った場合のことは無視できる。実際、素数判定の多項式時間の決定的アルゴリズムが発見されたが（AKS素数判定法）、暗号ソフトウェアでは未だに乱択アルゴリズムが使われていることも多く、将来的にも全て決定的アルゴリズムに置換されることにはならないだろう。
※この「複雑性」の解説は、「乱択アルゴリズム」の解説の一部です。
「複雑性」を含む「乱択アルゴリズム」の記事については、「乱択アルゴリズム」の概要を参照ください。
複雑性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/04/10 17:31 UTC 版)
「フォード・ファルカーソンのアルゴリズム」の記事における「複雑性」の解説
フロー増加道をグラフ上で既に確立されているフローに追加していくと、最終的にフロー増加道が見つからなくなり、最大フローが得られる。しかし、そのような状態に到達するかどうかは不確実であり、単にアルゴリズムが完了した場合は解が正しいということしか保証できない。アルゴリズムが無限に実行される場合、そのフローは最大フローに近づいているかどうかも不明である。ただし、そのような状態はフローの値が無理数の場合でしか発生しない。容量が整数の場合、フォード・ファルカーソンの実行時間の上限は O(Ef) であり、E はグラフ内の枝数、f はグラフの最大フローである。これは、増加道が O(E) 回まで見つけることができ、毎回少なくともフローが 1 増加するためである。 フォード・ファルカーソンのアルゴリズムの派生として、エドモンズ-カープアルゴリズムがある。これは、終了することが保証されており、最大フローと実行時間が独立で、実行時間は O(VE2) となる。
※この「複雑性」の解説は、「フォード・ファルカーソンのアルゴリズム」の解説の一部です。
「複雑性」を含む「フォード・ファルカーソンのアルゴリズム」の記事については、「フォード・ファルカーソンのアルゴリズム」の概要を参照ください。
複雑性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/02 19:43 UTC 版)
正値定符号行列である Q について楕円体法（英語版）は多項式時間で二次計画問題を解くことができる。一方で、Q の符号が不定ならば、二次計画問題はNP困難となる。実際、Q のただ一つの固有値だけが負であったとしても、二次計画問題はNP困難である。
※この「複雑性」の解説は、「二次計画法」の解説の一部です。
「複雑性」を含む「二次計画法」の記事については、「二次計画法」の概要を参照ください。
「複雑性」の例文・使い方・用例・文例
複雑性と同じ種類の言葉
- 複雑性のページへのリンク
