hotchpotch/wikipedia-multilingual-ir-pairs huggingface dataset:
1905年 周年
以下に、過去の主な出来事からの区切りの良い年数（周年）を記す。
1907年
1907年（1907 ねん）は、西暦（グレゴリオ暦）による、火曜日から始まる平年。明治40年。
1908年
1908年（1908 ねん）は、西暦（グレゴリオ暦）による、水曜日から始まる閏年。明治41年。
1909年
1909年（1909 ねん）は、西暦（グレゴリオ暦）による、金曜日から始まる平年。明治42年。
1910年
1910年（1910 ねん）は、西暦（グレゴリオ暦）による、土曜日から始まる平年。明治43年。
検索
検索（けんさく、英: search）とは、データの集合の中から目的のデータを探し出すことである。また、目的のデータが存在しないことの確認行為も含まれる。古くは図書館の所蔵物を探し出したり、辞書の項目を引いたりといった人手で行うのが主だったが、コンピューターの発達により、テキスト文字列の検索（文書検索、文字列探索）、画像データの検索（画像検索）、音声データの検索（音声検索）など、大規模かつマルチメディアの情報に関する検索技術が発展した。さらにデータベースの発展とインターネットの普及に伴い、分散保管されているデータに対する検索技術が研究されている。ファイルの内容に対して文字列探索を行う機能も検索と呼ばれる。
また、要人警護において警察犬や潜水士などを動員して不審物の有無を確認する作業を検索と呼ぶことがある。
検索 歴史
日本ではコンピュータ技術の発達により1970年代に「情報検索システム」が始まり、言葉としての｢検索｣は次第に広く使われ始めた。英語の文化圏では言葉としての「検索」は犬のゴールデン・レトリバーに見るように「探し出す」を意味する「retrieval」や「retrieve」として古くから使われている。
日本語における言葉「検索」の意味合いと使用例において大まかに次のような変遷が見られる。
広辞苑（1998年11月改訂）第5版までは、「検索」の意味として単に「調べさがすこと」、用例として「索引で語を検索する」と書かれている。この頃までは、一冊または複数冊の本の中に記述される事柄を探すことが、言葉としての「検索」の主な使われ方であった。一般的な言葉としてなじんで使われていたのは、｢検索｣より、むしろ単に「見つける」、「探す」、「探索」といった言葉であった。検索した結果、目的とする言葉が見つからなければ、他の本を手にとって調べてみることになる。このことはコンピュータによる情報検索が行える現代においても、図書館や書店において誰しも試みることである。一方、図書館では蔵書に対して「目録カード」や「カード目録」などと呼ぶ名刺大から葉書大程度のカードから所要の本を探し出したが、このような検索は蔵書検索と呼ばれ、現在でもコンピュータなどによる情報検索と併用されている。
検索 歴史
広辞苑第6版（2008年1月改訂）では、「検索」の意味として「データの中から、必要な事項をさがし出すこと」とし、コンピューターの中のデータや、紙やマイクロフィルムに記録されたデータの中から探し出す、現在の検索への意味合いへと変化が見られる。用例は変わっていない（なお、広辞苑5版から6版が出るまでの10年間にも、別の出版社から毎年刊行されている「現代用語の基礎知識」には「検索エンジン」などの用語の解説はあった。ただし、「検索」という言葉そのものの解説はない）。
「検索」という言葉の意味を日本語と英語で比較すると、「情報検索」に対応する英語は「information retrieval」であり、「検索」は「retrieval」である。retrieval（名詞）の動詞形は retrieve である。
検索 歴史
日本語を対象としたコンピュータの文書やファイルに終始する中での言葉や句の検索は、「検索」の機能を備えた1978年9月に東芝が発表した世界初の日本語ワードプロセッサJW-10に始まり、その後OASYSなどのワードプロセッサや1983年の一太郎の元となるPC-100用日本語ワープロソフト「JS-WORD」などが開発され市場に出されたことより、コンピュータを使った｢検索｣とはどのような意味か、どのように速くて便利なものかをコンピュータのユーザーの立場で体感できることとなる。1983年には米国で作られた表計算ソフトLotus 1-2-3を日本でも一部の者が使い始めたが、これにも表内の検索やLotus 1-2-3独自のマクロ言語による検索の機能を備えていた。
1989年にはパソコン通信を用いて遠隔地からデータベースの情報を探し出す｢G-Search｣の検索サービスが開始された。これは新聞・雑誌記事、企業情報、特許、科学技術、図書、人物プロファイルなど、さまざまな分野の情報を扱ってきた。これは膨大なデータや情報を｢検索｣によって見つけられることを示した日本での実例の始まりであった。その後、インターネットの通信技術向上による速度向上とサービスの多様化によってパソコン通信による「G-Search」の検索は2005年9月にサービスを終え、インターネットを介したものとなっている。
2006年頃までは紙を主体にした宣伝広告や広報のなかでURLを表記して広告内容の詳細を更に調べたい者に対して案内としたが、インターネットの利用が極めて一般的となった2007年ないし2008年頃からは広告の最後に「○○○ 検索」の様な形式で（同時にマウスのクリック音が挿入される広告も多く存在）、紙の媒体だけでなく、テレビ放送の広告にまで広告主の案内や広告のテーマや話題を直ちに検索する事を促す手法が一般化した。その手法は欧米でも2010年以降ハッシュタグとして生かされている。
検索 情報検索
情報検索 (英: information retrieval) は、広義には、あらかじめ蓄積されている情報の中から必要な情報を探し出すことを指し、しばしば検索と略される。
情報科学においては、文書（あるいは画像や音声）集合の中からユーザーの要求にもっともよく適合する文書を取り出すシステムのことを情報検索システムと呼ぶ。情報検索システムにおいては、本来形式化されていないユーザーの要求をコンピュータで取り扱えるようにするために検索モデルが設定される。たとえば、ベクトル空間モデルは、文書に索引を与えて、問い合わせとして与えられたキーワード集合と索引の重複の度合いから目的の文書を探し出す検索モデルであり、全文検索は、問い合わせとして与えられた文字列やパターンに完全に一致する部分を文書集合から探し出す検索モデルである。
文字列探索は文字列の中から別の文字列を探し出すとこと。全文検索は複数のファイルにまたがって文字列探索をすること。
検索 探索
情報科学における探索 (英: search) とは、いくつもの候補を列挙し、それぞれをひとつずつ評価していくことによって、最適解を得る手法を指す。探索に用いられるアルゴリズムとデータ構造は、問題の性質や構造によって異なる。たとえば、木構造やグラフの探索に用いられる深さ優先探索、ランダムアクセスが可能なデータ構造が使える状況でソート済みの入力に対して用いられる二分探索、よいハッシュ関数が作れる場合に用いられるハッシュテーブルなどがある。
混合基底
混合基底（こんごうきてい、英: mixed basis）は、2種類以上の基底を混ぜてバンド計算を行う手法。通常は、平面波基底＋局在基底（ガウス基底を使う場合が多い）という形が一般的である。擬ポテンシャルが深い場合（例：炭素や、3d遷移金属など）、平面波基底だけだと大量の平面波数が必要だが、局在基底を混ぜてやれば、ポテンシャルの深い部分を局在基底で対応させることができるので、その分必要な平面波の数が減り、全体としての計算量を減らすことができる。特にガウス基底だと行列要素の計算部分が解析的に解けるのでさらに有利になる。ただし、異なる基底を混ぜるので正規直交系でなくなるのが欠点である。また、力やストレスを求めるための表式の導出が難しくなる。これはプログラムのコード化や、実際の計算も難しくさせる。
ソート
ソート (英: sort) は、データの集合を一定の規則に従って並べること。日本語では整列（せいれつ）、並べ替え（ならべかえ）、分類（ぶんるい）などと訳される。
主に配列や連結リストのような、リストデータ構造に分類されるコレクション（コンテナ）に格納されている要素データを、全順序関係によって並べ替えることを指す。また、単に「ソート」といった場合、値の小さい方から大きい方へ順に並べる昇順（しょうじゅん、英: ascending order）を指すことが多い。その反対に値を大きい方から小さい方へ順に並べることを降順（こうじゅん、英: descending order）という。
対象となるコレクションのデータ構造や必要とされる出力、また時間的コストと空間的コストの兼ね合いによって、ソートに使われるアルゴリズムは異なる。
ソート 概要
効率的なソートは、ソート済みのデータを必要とする他のアルゴリズム（探索やマージ）の最適化にとっても重要である。また、ソートされたデータの方が人間にとっても読みやすい。形式的には、その出力は以下の2つの条件を満たさなければならない。
情報工学や計算機科学の黎明期から、ソートは単純な問題でありながら効率的に解くことが難しく、そのためもあって盛んに研究されてきた。例えばバブルソートについては、早くも1956年には解析が行われている。しかし、21世紀初にも新たなソートアルゴリズムが発明されている（例えば、Timsortは2002年に、図書館ソートは2004年に発表された）。すでに考案されているソートにも様々なアルゴリズムがあり、またアルゴリズムという概念を学習するのに最適なので、情報工学や計算機科学での入門的題材として広く親しまれている。例えば、分割統治法、データ構造、乱択アルゴリズム、計算量解析、O記法、時間と空間のトレードオフ、下限などが含まれる。
グラフィカルユーザインタフェース (GUI) においてよく使われるウィジェットのひとつとしてリストビュー (list view) が挙げられるが、各レコードのフィールドを表す任意のカラムについてリスト中のアイテムを昇順／降順ソートできるようになっていることが多い。
ソート 分類
計算機科学では、ソートアルゴリズムを次のように分類する。
同じ値に関して、ソート前の順序がソート後も維持されているソートを安定ソートという。
安定ソートでないソートであっても、ソート条件に元の順序を含めることで必ず安定ソートにすることが可能である。しかしながら、別途元の順序を記憶する領域が必要になることから、内部ソートであっても外部ソートになってしまう。（→#内部ソートと外部ソート）
ソートされるデータの格納領域を変更して処理を進めていくIn-placeのソートを内部ソートという。クイックソートのような再帰を利用するアルゴリズムは、再帰のために O(log n) の領域を必要とすることからIn-placeであるか否かは議論が分かれるところであるが、これも内部ソートに含めるのが一般的である。このことから内部ソートは、ソートされるデータの格納域以外には O(1) か O(log n) の領域しか必要としない。
逆に、ソートされるデータの格納領域以外に O(n) 以上の一時的な記憶領域が必要であるソートを外部ソートという。
ソート 分類
メモリ使用量（およびその他の計算資源の使用量）による分類である。すべての内部ソートは、インデックスや参照、複製を作成して処理することで事実上の外部ソートにすることができる。アルゴリズムとしての本質ではないので一般的には無視されるが、高速化や柔軟な処理のために冗長な記憶領域を使用する場合がある。例えば、非安定ソートアルゴリズムで安定ソートを実現する場合など。（→#安定ソート）
個々の項目を比較演算で大小判定することを基本とするソートを比較ソートという。
比較ソートには#比較ソートの理論限界が存在する。
入力されるリストの項目数 n に基づいた計算量による分類。典型的なソートアルゴリズムでは、最善で O(n log n) 、最悪で O(n2) である。理想は O(n) である。
比較ソートでは、一般的な（ランダムに並んだ）データの並べ替えに対しては少なくとも O(n log n) の比較回数が必要である。（→#比較ソートの理論限界）
汎用手法による分類。挿入、交換、選択、マージなどがある。交換ソートにはバブルソートやシェーカーソートやコムソートなどが含まれる。選択ソートにはヒープソートなどが含まれる。
再帰が必須、不可能、どちらでも可能、という分類。実装上の都合で再帰に関わる制限がある場合に注目される。
ソート 一覧
配列に格納されたn個のデータをソートする場合について、各アルゴリズムの性能を示す。
計算時間の表記に用いている記号 O（オー）については、ランダウの記号を参照。
以下の表で、n はソートすべきデータ要素数である。平均実行時間と最悪実行時間は時間計算量を示している。このとき、ソートキーの長さは一定と仮定しており、比較や交換といった操作は定数時間で行われるとする。メモリ使用量は、入力データの格納域以外に必要となる領域を示している。これらは、いずれも比較ソートである。
次の表は、比較ソート以外のソートアルゴリズムの一覧である。そのため、下限が O(n log n) で制限されない。k はキーの長さ、s は実装で使われるチャンクのサイズである。これらの一部は、キーが十分に長く、各要素のキーが重複しないことを前提としている。すなわち、n << 2k を仮定している（<< は「十分小さい」）。
次の表は、あまりにも性能が悪いので通常は用いられないソートアルゴリズム、および特別なハードウェアが必要なソートアルゴリズムの一覧である。
ソート 比較ソートアルゴリズムの最悪計算量の下界
ソートを行う際、要素間の順序の決定を2要素の大小関係の比較処理のみを用いて行うことにする。この時、要素からなるリストをソートするアルゴリズムの最悪比較回数は回となる。すなわち、どんな比較ソートアルゴリズムであっても入力によっては（一般的な入力に対しては）漸近的に回の比較が必要となる。
この理由を説明する。ある比較ソートアルゴリズムが与えられた際、様々な入力に対する処理の手順を二分決定木として表すことができる。内部ノードは2要素の比較処理を表し、内部ノードから子ノードへの2本の枝は比較結果に応じた処理を表す。また、葉は処理の終了を表す。この時、木の高さが最悪比較回数となる。要素からなるリストが入力される時、どのような二分決定木を作ったとしても、木の高さがになることを示す。二分決定木の高さをとした時、木の形によらず、葉の数は以下になる。要素からなるリストの（添字の）置換は個存在するが、任意の入力に対してアルゴリズムが正しい出力をするためには、個の異なるリストを入力した際、それらがすべて異なる葉に到達できるようにしなければならない。よって、葉の数は以上でなければならない。以上より、である。スターリングの公式よりなので、。よって、。よって。
ソート 比較ソートアルゴリズムの最悪計算量の下界
以上より、任意の比較ソートアルゴリズムの最悪計算量はとなる。すなわち、比較ソートアルゴリズムの最悪計算量の下界は漸近的にはとなる。
マージソート、ヒープソートなどの比較ソートアルゴリズムの最悪計算量はであるため、これらのアルゴリズムの最悪計算量は上記の下界と漸近的に一致していると言える。つまり、これらのアルゴリズムの最悪計算量は漸近的に最適である。
ソート メモリ使用パターンとインデックスソート
ソート対象の配列が主記憶を使い切るような（あるいは越えるような）大きさであった場合、より低速な補助記憶装置が使われるので、アルゴリズムのメモリ使用パターンが重要となる。そのような状況では、主記憶上ですべてソートできることを前提としたアルゴリズムは効率が極端に悪化する可能性がある。このような状況では、比較演算回数はあまり重要ではなくなり、ディスクとのメモリ領域のスワップ回数が重要となる。したがって、なるべくスワップ回数を増やさないようにするために、配列全体を走査する回数や比較の局所性が比較回数よりも重要となる。
例えば、再帰型のクイックソートは主記憶上では性能が良いが、ソート対象の配列が主記憶に収まらない場合はスワップが頻繁に発生して、性能が極端に低下する。したがって、そのような場合は比較回数が多くても他のアルゴリズムを使った方がよい。
ソート メモリ使用パターンとインデックスソート
対策の一つとして、ソート対象の配列の要素が（関係データベースのような）複雑なレコードだった場合、その配列をそのままソートするのではなく、比較的小さいインデックスを生成して、インデックスの配列をソートするという方法がある。インデックスをソートすれば、元の配列のソートは一回の走査で可能であるが、インデックス経由でアクセスするだけならそれをする必要もない。インデックスは元の配列のレコードよりも小さいので、メモリに収まる可能性が高くなり、スワップ問題を削減することができる。この方式を「タグソート（tag sort）」などと呼ぶこともある。
別の技法として、2つのアルゴリズムを組み合わせて、それぞれの利点を利用する方法がある。例えば、配列をチャンクに分割して個々のチャンクが主記憶上でソートできる大きさにする。チャンク内のソートはメモリ上で効率的に動作するソートアルゴリズムを使い、その結果をマージソートでマージする。これは、元の配列を単純にマージソートでソートするよりも効率が悪いが、全体をクイックソートでソートするよりもメモリ使用量が少なくてすむ。
これらの技法を組み合わせることも可能である。あまりにも巨大なデータをソートする場合、インデックスのソートにも複数のアルゴリズムを組み合わせて仮想記憶の性質に合うよう設計する必要がある。
1912年
1912年（1912 ねん）は、西暦（グレゴリオ暦）による、月曜日から始まる閏年。明治45年/大正元年。
1912年 できごと
7月14日 - ストックホルム五輪マラソン競技に日本代表として参加した金栗四三がレース中に倒れるも一般家庭に介抱されその後帰国、主催者に棄権の意思表示がされなかったため、記録上「競技中に失踪し行方不明」となる。その後金栗は1967年3月21日、ストックホルム五輪開催55周年を記念する式典に招待され正式ゴール、54年8ヶ月6日5時間32分20秒3の記録を残す。
1913年
1913年（1913 ねん）は、西暦（グレゴリオ暦）による、水曜日から始まる平年。大正2年。
1913年 芸術・文化・ファッション
クラシック音楽
世界初の交響曲全曲録音。ベートーヴェンの交響曲第五番。オデオン・オーケストラ、指揮者不詳。長らく、この演奏は弦楽合奏のみであるといわれてきたが、近年、管楽器も加えたフル編成であり、一小節のカットもない完全な全曲録音であることが判明した。ちなみに二番目の演奏はブルーノ・ザイドラー＝ヴィンクラー指揮、ベルリン新フィルハーモニカーのベートーヴェンの第五交響曲。三番目の録音が有名なアルトゥール・ニキシュ指揮、ベルリン・フィルハーモニー管弦楽団によるベートーヴェン第五交響曲である。いずれもこの年。
1914年
1914年（1914 ねん）は、西暦（グレゴリオ暦）による、木曜日から始まる平年。大正3年。
なお、この年に第一次世界大戦が開戦したため、世界史の大きな転換点となっている。
1915年
1915年（1915 ねん）は、西暦（グレゴリオ暦）による、金曜日から始まる平年。大正4年。
1915年 周年
以下に、過去の主な出来事からの区切りの良い年数（周年）を記す。
1916年
1916年（1916 ねん）は、西暦（グレゴリオ暦）による、土曜日から始まる閏年。大正5年。
1916年 周年
以下に、過去の主な出来事からの区切りの良い年数（周年）を記す。
1918年
1918年（1918 ねん）は、西暦（グレゴリオ暦）による、火曜日から始まる平年。大正7年。
1920年
1920年（1920 ねん）は、西暦（グレゴリオ暦）による、木曜日から始まる閏年。大正9年。
1921年
1921年（1921 ねん）は、西暦（グレゴリオ暦）による、土曜日から始まる平年。大正10年。
1922年
1922年（1922 ねん）は、西暦（グレゴリオ暦）による、日曜日から始まる平年。大正11年。
1923年
1923年（1923 ねん）は、西暦（グレゴリオ暦）による、月曜日から始まる平年。大正12年。
1924年
1924年（1924 ねん）は、西暦（グレゴリオ暦）による、火曜日から始まる閏年。大正13年。
1925年
1925年（1925 ねん）は、西暦（グレゴリオ暦）による、木曜日から始まる平年。大正14年。
1925年 周年
以下に、過去の主な出来事からの区切りの良い年数（周年）を記す。
1926年
1926年（1926 ねん）は、西暦（グレゴリオ暦）による、金曜日から始まる平年。大正15年/昭和元年。
1926年 周年
以下に、過去の主な出来事からの区切りの良い年数（周年）を記す。
1927年
1927年（1927 ねん）は、西暦（グレゴリオ暦）による、土曜日から始まる平年。昭和2年。
1928年
1928年（1928 ねん）は、西暦（グレゴリオ暦）による、日曜日から始まる閏年。昭和3年。
1929年
1929年（1929 ねん）は、西暦（グレゴリオ暦）による、火曜日から始まる平年。昭和4年。
1930年
1930年（1930 ねん）は、西暦（グレゴリオ暦）による、水曜日から始まる平年。昭和5年。
1931年
1931年（1931 ねん）は、西暦（グレゴリオ暦）による、木曜日から始まる平年。昭和6年。
1931年 芸術・文化・ファッション
1931年の映画
1931年の演劇
1931年の流行語
1931年の世相
計算複雑性理論
計算複雑性理論（けいさんふくざつせいりろん、英: computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。
計算複雑性理論 概要
計算複雑性理論は計算可能関数の計算の複雑さを扱う。計算理論のもう一つの重要な分野である計算可能性理論では問題の解法があるかどうかだけを扱い、その複雑さや必要とする計算資源量は問わない点が異なる。
具体的には、計算複雑性理論は「あるアルゴリズムへの入力データの長さを増やしたとき、実行時間や必要な記憶量はどのように増えるか？」という問いに答える。これは、計算機の実際的な限界を与えるものであり、この理論は産業や社会にとって重要な意味を持つ。なぜならば、計算機の性能は向上しているが、解析すべき情報も増加しているため、アルゴリズムが入力データ長の増大にうまく対応できるか否かで、計算機が現実的な問題を解決するのに役に立つか否かが決まるからである。
計算複雑性理論では、計算問題やそれを解くアルゴリズムを、NPやPといった複雑性クラスに分類する。個々の計算問題を少ない計算資源で解くアルゴリズムを発見することはもちろん計算機科学の重要な課題だが、複雑性理論ではこれにとどまらず、計算問題が何らかの複雑性クラスに属すること、あるいは属しないことを証明したり、クラス間の階層構造を解明することも目標とする。
計算複雑性理論 概要
計算量 tC をもつ複雑性クラス C に 或る計算問題 X が属する とは、あるアルゴリズム A が存在して、問題 X が A により tC以下で解決されることを意味し、問題 X の複雑性の上界を与える。そして、よりよい上界を求めることは、問題 X をより少ない計算資源で解くアルゴリズムを発見する(あるいはその存在を示す)ことに他ならず、産業界において有意義である。また、ある計算問題 X が、ある複雑性クラス C に属しないとは、問題 X は、いかなるアルゴリズムをもってしても、計算量 tC 以下では解決できないことを意味し、問題 X の複雑性の下界を与える。計算問題の下界を示すことは、理論的意義を有するだけではなくて、暗号理論においては、ある暗号方式が計算量的に解読不能であることを示すことを意味し、実際的な価値がある。
現在の計算複雑性理論の最も重要な課題は、P≠NP予想の証明である。この予想は提起された当初それほど重要とは見なされなかったが、産業において重要なオペレーションズリサーチの問題の多くがNPの部分クラスに属するNP完全問題であることが明らかになるにつれて重要性を増してきた。NP完全問題は、解が正しいかどうかは簡単に確かめられるが、正確な解を探す方法はスケーラブルではない問題である。NPクラスがPクラスより範囲が広いことが確定すると、それらの問題にはスケーラブルな解が存在しないことが確定する。このため、P≠NP予想の証明は重要とされているのである。
計算複雑性理論 計算問題と計算量・複雑性
計算複雑性理論で扱う問題とは、ある一連の問いの集合があり、各問いは有限長の文字列で表され、与えられた問いに対して解を求めて出力する計算問題である。例えば、FACTORIZE問題とは「二進数で書かれた1つの整数について、その素因数を全部求めて返す」という問題である。問題に属する個別の問いをインスタンスと呼ぶ。例えば、「15 の素因数を求めよ」は FACTORIZE 問題のインスタンスである。
アルゴリズムの計算量（けいさんりょう）とは、計算機がそのアルゴリズムの実行に要する計算資源の量をいい、アルゴリズムのスケーラビリティを示す。形式的には計算機をチューリング機械やランダムアクセス機械（random access machine）などの計算モデルとして定式化したうえで、アルゴリズムの使用する資源の量を入力データ長などに対する関数として表す。計算モデルの瑣末な詳細に影響を受けないよう、計算量はその漸近的な挙動のみに注目し、定数倍を無視するO記法で書き表すことが多い。計算モデルとしては、チューリング機械や論理回路などがある。計算資源の量としては、チューリング機械における時間計算量（動作ステップ数）や空間計算量（テープ長）、また論理回路における素子数や深さなどがある。
計算複雑性理論 計算問題と計算量・複雑性
時間計算量は、あるアルゴリズムを使ったときに問題のインスタンスを解くのに要するステップ数を意味し、入力データの長さ（ビット数などで表現できる）の関数として表される。シンプルな例として、ある問題に対する解法が nビットの入力に対して、ある計算モデルで n2 ステップで動作する場合、時間計算量は n2 であるが、他のほとんどの計算モデルでも、時間計算量は漸近的には定数倍の違いしかなく、O記法を使えば計算モデルによらず問題の時間計算量をO(n2) と表せる。計算を芝生を刈る作業にたとえれば、その時間計算量は線型であり、芝生の面積が2倍になれば時間も2倍かかる。この面積が2倍になれば時間も2倍になるという関係は、芝刈機の速度には関係しない。しかし、辞書を二分探索する場合の時間計算量は対数時間であり、辞書の厚さが2倍になっても、二分探索のステップが1増加するだけである。
計算複雑性理論 計算問題と計算量・複雑性
計算モデルによっては、これらとは異なる計算量が使われることもあり、例えば回路計算量がある。これは問題の解法をブール論理による論理回路ゲートに置き換え、その回路の規模で計算量を現すものである。これは集積回路の設計などで利用される。
計算問題の複雑性（または計算量）とは、それがどの計算モデルにおいて、どれほどの計算量のアルゴリズムによって解けるかで測られる。直感的には、問題の計算量は、最も効率のよいアルゴリズムを使ったときに問題のインスタンスを解くのに要する計算量だと考えるのが自然である。しかし、最良のアルゴリズムであることを示すのは通常困難で、多くの場合、O記法を用いて「ある時間以下で計算できる」ことを示すことになる。そのため、複雑性クラスを導入し、クラス間の相互関係を示すことで、計算問題の複雑性を明らかにする。
計算複雑性理論 決定問題
計算複雑性理論で扱う計算問題の多くは決定問題である。決定問題とは、答えが「はい」か「いいえ」になる問題を指す。
決定問題を主に扱うのは、任意の計算問題を何らかの決定問題に還元することが常に可能だからである。例えば、HAS-FACTOR を与えられた整数 n と k（どちらも二進数で与えるとする）について、n が k より小さい素因数をもつかどうかに答える決定問題とする。すると、計算問題 FACTORIZE（素因数分解）の解法は、HAS-FACTOR を使って実現でき、その際に追加の資源はそれほど要しない。具体的には k について二分探索を行い、n の最小素因数を探索し、その値で n を割る。そして、商について再び同じ作業を繰り返していけばよい。このことは、HAS-FACTOR の解法をある計算資源量で実現できるか否かが分れば、FACTORIZE の解法についても分るということを意味する。
計算複雑性理論では、答えが「はい」かどうかを確認する問題と、答えが「いいえ」かどうかを確認する問題を区別する。「はい」と「いいえ」を逆転させた問題は、元の問題の補問題と呼ばれる。
計算複雑性理論 決定問題
例えば、決定問題 IS-PRIME（素数判定問題）は、入力が素数の場合に「はい」、そうでなければ「いいえ」を返す。一方、問題 IS-COMPOSITE は与えられた整数が素数でない（すなわち合成数である）ことを決定する。IS-PRIME が「はい」を返すなら、IS-COMPOSITE は「いいえ」を返す。逆も成り立つ。したがって IS-COMPOSITE は IS-PRIME の補問題であり、同様に IS-PRIME は IS-COMPOSITE の補問題である。
ある問題の解を求める計算量とその補問題の解を求める計算量は同じであるが、問題のあるインスタンスについて「はい」となる証拠を与えられて、その証拠が正しいかを判定する計算量は同じとは限らない。例えば、IS-COMPOSITE問題で、ある整数について、証拠として素因子を一つ与えられれば、除算を行うことで検算することができる。しかし、IS-PRIME問題では、どのような証拠を与えればよいかは、しばらくの間、自明ではなかった。補問題を区別することは、後述する複雑性クラスNPとco-NPなどで重要となる。
計算複雑性理論の重要な成果の1つとして、ある難しい問題があったとき（それがいかに大量の時間資源や空間資源を要したとしても）、それよりさらに難しい問題が必ず存在するという事実がある。時間計算量については時間階層定理によってこれが証明されている。同様に領域階層定理も導かれる。
計算複雑性理論 計算資源
計算複雑性理論は計算問題の難しさを様々な計算資源の観点で分析する。時間、空間、無作為性、反復性、その他のより直観的でない尺度などで必要とする計算資源量によって、同じ問題を説明する。複雑性クラスはある特定の計算資源をある特定の量つかって解くことができる全計算問題の集合である。
最も研究が進んでいる計算資源は決定性時間(DTIME) と決定性空間(DSPACE) である。これらの資源はそれぞれ、決定性のある計算機（例えば実在する普通の計算機）で問題を解くのに必要な「計算時間（演算回数）」と「記憶装置」の量に対応している。これらの資源の使用量を求めることは実用的な意味もあり、研究が進んでいるのである。
いくつかの計算問題は非現実的な量の資源を想定すれば、より容易に解析可能である。例えば、非決定性チューリング機械は、分岐して様々な可能性を同時にチェックできるという計算モデルである。したがって、非決定性チューリング機械はアルゴリズムを使って具体的に計算する作業とは全く関係ないが、その分岐によって分析したい計算モデルの大部分を捉える。このため非決定性時間は計算問題を分析するにあたって非常に重要な資源である。
計算複雑性理論では他にもいろいろな計算資源を考慮する。技術的には、複雑性尺度として計算資源量が扱われ、これに関してはブラムの公理で非常に一般的な定義が与えられている。
計算複雑性理論 複雑性クラス
ある量の計算資源を使って解くことができるすべての計算問題の集合を複雑性クラスという。
複雑性クラス P は、チューリング機械で多項式時間で解ける決定問題の集合である。このクラスは、直感的に言えば最悪の場合でも効率的に解くことができる問題である。
複雑性クラス NP は、非決定性チューリング機械で多項式時間で解ける決定問題の集合である。このクラスには効率的に解くことが望ましいとされる様々な問題が含まれている。例えば、充足可能性問題、ハミルトン閉路問題、頂点被覆問題などである。このクラスの全問題は、その解法を効率的に検証する方法があるという特徴を持つ。
多くの複雑性クラスは、それを表現するのに必要となる論理体系によって特徴付けられる。これは、記述計算量の概念と関係がある。
各クラスに対し、そのクラスの完全問題を考えることがある。クラスCの完全問題とはCに属する問題のうちで最も計算するのが難しい問題のことである。具体的な定義は以下のようになる。
計算複雑性理論 複雑性クラス
—困難 (英: — hard)
クラスCに対して、問題PがC困難であるとは、Cに属する任意の問題をPに帰着（多くの場合多項式時間帰着を考えるが、そうでない場合もある）できるということである。すなわちPはCに属するいかなる問題よりも、同等かそれ以上に難しいということである。ただし、C完全と異なり、P自身はCに属するとは限らない。
—完全 (英: — complete)
クラスCに対して、問題PがC完全であるとは、PがCに属しかつC困難ということである。すなわちPはCに属する問題の中で、本質的に最も難しい問題であるということである。
計算複雑性理論 未解決の問題
NPがPと同じかどうかという疑問（換言すれば、非決定的な多項式時間で解くことのできる問題は決定的な多項式時間でも解くことができるか）は、理論計算機科学における最重要問題の1つであり、その解決が様々な意味を持っている。同じであった場合に都合が悪い影響として、暗号理論の多くがNPの困難さに依存しているため、Pと同じであることが判明すると使い物にならなくなるのである。しかし、よい影響も多々あり、様々な重要な問題に効率的な解法があることが明らかとなることが重要である。例えば、オペレーションズリサーチにおける整数計画問題、物流合理化、生物学におけるタンパク質構造予測、純粋数学の定理を計算機で効率的に形式的に証明する可能性などがある。クレイ数学研究所は2000年に、この問題を最初に解いた人に100万ドルを支払うと発表した。
計算複雑性理論 未解決の問題
この問題を考えるにあたって重要となるのは、NP完全の概念である。NP完全な問題はNPの中では最もPから遠い問題ということになる。P = NPが証明されていないため、ある問題をNP完全と判明している問題に還元できるということは、その問題の多項式時間の解法が未知であることを示している。逆に、すべての NP問題はNP完全問題に還元できるため、NP完全問題の多項式時間の解法を発見すれば、P = NPが証明される。（一方、たとえP = NPが成立しても、NP困難な問題は多項式時間で解けるとは限らない。理由はNP困難のページを参照のこと）
上の問題に関連して、NPクラスに属する問題でPクラスには属しないがNP完全でもない問題は存在するか、という問題もある。つまり、非決定的な多項式時間の解法はあるが、NP完全問題から多項式時間で還元できない問題ということである。このような問題のクラスをNP-intermediateと呼び、候補としてグラフ同型問題や整数の因数分解、離散対数問題などがある。もしP ≠ NPが真ならば、そのような問題が存在することが証明されている。
co-NPクラスはNP問題の補問題の集合である（すなわち、「はい」と「いいえ」が逆転している問題）。両者は等しくないと考えられているが証明されていない。2つの複雑性クラスが等しくないことが判明すると、NP完全問題は co-NP には含まれず、co-NP完全問題は NP には含まれないことが明らかになる。
計算複雑性理論 イントラクタブル
理論上計算可能な問題であっても、実際に解くことができない問題をイントラクタブル (英: intractable, 手に負えない、処理しにくい) であるという。「実際に」解けるとはどういうことかという問題もあるが、多項式時間の解法がある問題が一般に（小さな入力だけでなく）解けるとされている。イントラクタブルな問題として知られているものとしては、EXPTIME完全な問題がある。NP が P と同じでなかった場合、NP完全な問題もイントラクタブルだということになる。
指数関数時間の解法がなぜ実際には使えないかを考えるため、2n 回の操作を必要とする問題を考える（n は入力のサイズである）。比較的小さな入力数 n = 100 のときについて、1秒間に 1010（10 ギガ）回命令を実行できる計算機を想定すると、その問題を解くには約 4 × 1012 年かかる。これは現在の宇宙の年齢よりも長い。
1932年
1932年（1932 ねん）は、西暦（グレゴリオ暦）による、金曜日から始まる閏年。昭和7年。
1932年 芸術・文化・ファッション
1932年のスポーツ
1932年の音楽
1932年の映画
1933年
1933年（1933 ねん）は、西暦（グレゴリオ暦）による、日曜日から始まる平年。昭和8年。
1933年 できごと
ヴェント・ア・フード社が初の台所用換気装置を発明した。
1934年
1934年（1934 ねん）は、西暦（グレゴリオ暦）による、月曜日から始まる平年。昭和9年。
1935年
1935年（1935 ねん）は、西暦（グレゴリオ暦）による、火曜日から始まる平年。昭和10年。
1935年 周年
以下に、過去の主な出来事からの区切りの良い年数（周年）を記す。
1935年 芸術・文化・ファッション
1935年のスポーツ
中等学校野球
全国選抜中等学校野球大会 - 優勝：岐阜商業（岐阜）。準優勝：広陵中（広島）。
全国中等学校選手権大会 - 優勝：松山商業（愛媛）。準優勝：育英商業（兵庫）。
サッカー
全国中等学校蹴球選手権大会 - 優勝：第一神戸中。準優勝：天王寺師範。
大相撲（幕内最高優勝）
春場所 - 玉錦三右衛門
夏場所 - 玉錦三右衛門
マラソン - この年は日本陸上競技界の当たり年で世界記録が3回も更新された。
3月、鈴木房重 - 日本大学、2時間27分49秒
4月、池中康雄 - 東洋大学、2時間26分44秒
9月、孫基禎 - 養正商業高等学校（現在の韓国）、2時間26分42秒
1936年
1936年（1936 ねん）は、西暦（グレゴリオ暦）による、水曜日から始まる閏年。昭和11年。
1936年 周年
以下に、過去の主な出来事からの区切りの良い年数（周年）を記す。
1936年 芸術・文化・ファッション
1936年のスポーツ
プロ野球 この年からプロ野球が開催される。当時は職業野球と呼ばれていた。
春優勝 優勝チーム決定なし。
夏優勝 予定されていた優勝決定戦が行われず
秋優勝 読売ジャイアンツ
個人タイトル
首位打者 中根之（名古屋）.376
本塁打王 古谷倉之助（金鯱）2本
本塁打王 山下実（阪急）
本塁打王 藤村富美男（タイガース）
打点王 古谷倉之助（金鯱）23点
盗塁王 苅田久徳（セネタース）16個
最多安打 藤井勇（タイガース）40本
最優秀防御率 景浦將（タイガース）0.79
最多勝利 沢村栄治（巨人）13勝
最多奪三振 内藤幸三（金鯱）139個
最高勝率 景浦將（タイガース）1.000
中等学校野球
全国選抜中等学校野球大会 - 優勝：岐阜商業（岐阜）。準優勝：広陵中（広島）。
全国中等学校選手権大会 - 優勝：松山商業（愛媛）。準優勝：育英商業（兵庫）。
サッカー
全国中等学校蹴球選手権大会 - 優勝：第一神戸中。準優勝：天王寺師範。
大相撲（幕内最高優勝）
春場所 - 玉錦三右衛門
夏場所 - 双葉山定兵衛
スケジューリング
計算機科学においてスケジューリング（英: scheduling）は、スレッドやプロセスやデータの流れについて、システム資源（例えば、プロセッサ時間、通信帯域など）へのアクセスを与える方法の一つ。スケジューラはスケジューリングを実行するソフトウェア。
スケジューリング 概要
システムを効果的に負荷分散するため、あるいはターゲットの Quality of Service を保証するためになされる。スケジューリングアルゴリズムは、マルチタスク（同時に複数のプロセスを実行）や多重化（複数のデータの流れを同時に転送）の発展とともに進化してきた。
スケジューラの主な関心事は以下の通りである。
スループットを最大化し、レイテンシを最小化するのがスケジューリングの目標である。しかし実際にはこれらの目標は同時に満たすのが難しく、スケジューラは適当なところで妥協した実装とすることが多い。ユーザーのニーズと目的によって上記のいずれかに力点を置く。
ファクトリーオートメーションのための組み込みシステム（例えば産業用ロボット）などのリアルタイム環境では、スケジューラがプロセスの時間制限（デッドライン）を満たすことを保証する必要がある。これは、システムの安定性を保つ上で重要である。
近年では消費電力を考慮したローパワースケジューリングの研究が盛んに行われている。
スケジューリング スケジューラの分類
スケジューラは3種類に分類される。「長期スケジューラ」、「中期スケジューラ」、「短期スケジューラ」である。名称が示唆するとおり、その機能が実行される頻度が異なる。スケジューラは、システムに次に入れるべきジョブを決定し、次の実行すべきプロセスを決定する。
長期スケジューラはジョブやプロセスを実行可能キューに載せるかどうかを決定する。つまり、あるプログラムを実行しようとしたとき、それを実行可能なプロセス群にすぐに追加するか、それとも遅延させるかを長期スケジューラが決定するのである。この種のスケジューラはシステム上で実行すべきプロセス群を決定し、ある時点の並列性の度合いをも決定すると言える。つまり、同時並行的に実行すべきプロセス群を決め、I/Oバウンドなプロセス群とCPUバウンドなプロセス群の比率を決める（I/Oバウンドなプロセスとは記憶媒体すなわちディスクやメモリの入出力待ちとなることが多いプロセスを意味し、CPUバウンドなプロセスとは計算処理主体のプロセスを意味する）。一般的なパーソナルコンピュータなどでは長期スケジューラは存在せず、プロセスは生成されると自動的に実行可能状態となる。しかし、RTOSなどのリアルタイムシステムでは長期スケジューラが重要であり、応答時間の保証のために同時並行的に実行するプロセス数を制限するなどの機能によって、より確実な制御がなされる。
スケジューリング スケジューラの分類
長期スケジューラはバッチ処理システム、コンピュータ・クラスター、スーパーコンピュータ、レンダーファームなどの大規模システムでも重要である。その場合、専用のジョブ管理システムが長期スケジューラの役目を果たす。
なお、「長期スケジューラ」という用語で別の機能を表す場合もある。プロセスの優先度を自動的に変化させて平等性を確保する場合、CPUバウンドなプロセスは徐々に優先度が下げられ、最終的には最低優先度となる。そのようなプロセスは他に高優先度のプロセスが存在する限り、ディスパッチされないことになってしまう。そのため、実行可能状態でありながら長期間実行されていないプロセスの優先度を上げる処理が定期的に実行される。これを長期スケジューラと呼ぶ場合がある。
スケジューリング スケジューラの分類
中期スケジューラは仮想記憶方式のシステムに必ず存在し、プロセスを主記憶から二次記憶（ディスクなど）に一時的に退避したり、その逆に二次記憶から主記憶にプロセスを戻したりする。このような処理を「スワップアウト」および「スワップイン」と呼ぶ。中期スケジューラは、長期間ブロックされているプロセスや優先度の低いプロセス、頻繁にページフォールトの発生するプロセスや大量のメモリを確保しているプロセスなどをスワップアウトして主記憶を他のプロセスのために空ける。また、主記憶に余裕が生じたときやブロックされていたプロセスが起動した場合などに、スワップアウトされていたプロセスをスワップインする。
スケジューリング スケジューラの分類
多くのシステムではスワップアウトが発生する前にページ置換アルゴリズムが働いて主記憶の空き容量を増やそうとする。そのため、中期スケジューラはある意味で長期スケジューラとも呼べるような位置づけとなっている。ページ置換は一般に特定のプロセスの使用している全メモリを一度に解放するような動作はせず、システム全体で使用頻度の低いページをターゲットとする。そのように置換されて対応する物理メモリのなくなった仮想ページへのアクセスはページフォールトを発生し、例外処理の延長でページインが行われる。実際、スワップアウトが発生するほどメモリ容量が逼迫する状況では、システムは設計段階で予定されていた性能を発揮できない可能性が高く、なるべくページ置換で済むようにメモリ負荷の事前予測を立てるのが通例である。
短期スケジューラ（またはCPUスケジューラ）は、実行可能状態でメモリ上にあるプロセス群の中で次に実行すべき（CPUを割り当てるべき）プロセスを決定する。そのタイミングとしては、クロック割り込み、I/O割り込み、システムコール、その他の何らかの契機がある。従って、短期スケジューラは長期/中期スケジューラよりも頻繁にスケジューリングを行っている。少なくともタイムスライス毎にスケジューリング処理が行われる可能性があり、その間隔は非常に短い。プリエンプティブなスケジューラでは、プロセスを切り替える必要があると判断したときには強制的にディスパッチを行う。一方、非プリエンプティブなスケジューラでは強制的にディスパッチすることはなく、実行中のプロセスが何らかの資源を待つためにブロックするかプログラム上明示的にプロセッサを明け渡したときだけディスパッチを行う。
CPUのスケジューリング機能に関わるもう1つのコンポーネントとしてディスパッチャがある。ディスパッチャは短期スケジューラが選択したプロセスにCPUの制御を与えるモジュールである。次のようなことを行う。
プロセスを切り換える際に必ず実行されるので、ディスパッチャは性能が重視される。ディスパッチャがあるプロセスを一時停止させ、別のプロセスを実行再開させるのにかかる時間を「ディスパッチ・レイテンシ」と呼ぶ。
スケジューリング スケジューリングアルゴリズム
スケジューリングアルゴリズムは、ポリシーに従って同時かつ非同期に要求されるリソースを分配するアルゴリズムである。スレッドやプロセスにCPU時間を分配するスケジューリングアルゴリズムだけでなく、パケットのトラフィックを制御するルーターのスケジューリングアルゴリズム、ハードディスクへのリード/ライト要求に関するスケジューリングアルゴリズム、プリンターのスプーリングのスケジューリングアルゴリズムなどがある。
スケジューリングアルゴリズムの主要な目的は、リソーススタベーションを無くし、リソースの使用者間で公平さを保証することである。スケジューリングは、未処理の要求のどれに資源を割り当てるかを決定する。様々なスケジューリングアルゴリズムがあり、以下ではその一部を紹介する。
FIFOは最も単純なスケジューリングアルゴリズムで、実行可能キューにプロセスが到着した順番にプロセスをキューイングし、先頭から順に実行する。FCFS (First-Come, First-Served) とも。
最小残余時間優先 (SRT) 方式は、最短ジョブ優先 (SJF) 方式とも似ている。この戦略では、キュー内で残り処理時間の推定値が最も短いプロセスをスケジューラが選択する。これはプロセスの完了までにかかる時間についての高度な知識または評価を必要とする。
スケジューリング スケジューリングアルゴリズム
固定優先度プリエンプティブ・スケジューリング (FPPS) は、全てのプロセスに固定の優先度を付与し、その優先度順にプロセスをキューイングする。新たに高優先度のプロセスが到着すると、現に実行中だった低優先度のプロセスは中断される。
スケジューラは各プロセスにある一定時間単位を割り当て、次々にその割り当てを実行させる。
これは、プロセスを容易に複数のグループに分類できる場合に使われる、例えば典型的な分類はフォアグラウンド（対話型）プロセスとバックグラウンド（バッチ）プロセスである。このように分けると、それぞれ応答時間の要求がグループによって異なるので、スケジューリングに求められることがグループによって異なる。
パケット交換コンピュータネットワークや他の統計多重化では、データパケットのFIFOキューがスケジューリングアルゴリズムとほぼ同義である。
最も単純なベストエフォートなスケジューリングアルゴリズムとしてラウンドロビン・スケジューリング、均等化キューイング（最大最小公平なスケジューリングアルゴリズム）、比例公平スケジューリング、最大スループットスケジューリングなどがある。ベストエフォートではなくQoSの保証を行う場合、重み付け均等化キューイングなどが使われる。
スケジューリング スケジューリングアルゴリズム
3.5G携帯システムの High-Speed Downlink Packet Access (HSDPA) などの無線パケットネットワークは、チャネル状態情報を利用した channel-dependent scheduling  を採用している。チャネル状態が良好なら、スループットとスペクトル効率も向上する。LTEなどのさらに進んだシステムでは、スケジューリングはパケット単位の動的チャネル割り当てと組み合わされたり、OFDMAマルチキャリアや周波数領域等化コンポーネントを最も有効利用できるユーザーに割り当てることでなされる。
ディスクのアームやヘッダを移動させる時間を減少させるようにスケジュールすることで、高速化が期待できる。
スケジューリング スケジューリングアルゴリズム
OS設計の際、そのシステムを使用するにあたって最善のスケジューリングアルゴリズムは何かを検討する必要がある。あらゆる用途に最善といえる単一のスケジューリングアルゴリズムは存在せず、上述の各種スケジューリングアルゴリズムを組み合わせたり拡張したりして使っているOSが多い。例えば、Windows NT/XP/Vista は固定優先度プリエンプティブ・スケジューリングとラウンドロビンとFIFOを組み合わせた多段フィードバックキューを採用している。このシステムでは、プロセスがそれまでに動作してきた状況や待ち続けた状況に従い、優先度を動的に調整する。優先度ごとにキューがあり、高優先度のキューではラウンドロビン・スケジューリング、低優先度のキューではFIFOを採用している。応答時間はほとんどのプロセスで短くなり、短いが重要なプロセスは特に素早く完了する。高優先度のキューはラウンドロビンなのでプロセスが一定時間単位しか動作しないため、スタベーションは起こりにくい。
スケジューリング リアルタイム性を保証するスケジューリング
スケジューリングにおいて、リアルタイム制約を満たすということは以下のどちらかを指す。
後者についての研究はさかんに行われているが、
スケジューリングが複雑になるために実際のシステムで利用されることは極めて少ない。
スケジューリング オペレーティングシステムのスケジューラ実装
当然のことながら、OSの数だけスケジューリング方式がある。
ラウンドロビンのような単純なアルゴリズムを採用すると、各プロセスに同じ時間（一般に1ミリ秒から100ミリ秒）が割り当てられ、それが巡回するように実際に実行されていく。従って、プロセスとして A、B、C の3つがあるとき、Aを1ミリ秒実行し、次にB、次にCと実行していき、再びAを実行するというようになる。
より進んだアルゴリズムではプロセスに優先度を設定したり、プロセスの重要度を判断したりする。それによって特定のプロセスが他のプロセスよりも優先してCPU時間を割り当てられることになる。カーネルはシステムを正しく機能させるのに必要な資源を必要なだけ使用するので、ある意味では無限の優先度があるとも言える。対称型マルチプロセッシング (SMP) システムでは、プロセッサ親和性を考慮することでシステム全体性能を向上させようとするが、個々のプロセスはそれによって動作がゆっくりになることもありうる。これは一般にキャッシュスラッシングを低減させることで性能を向上させる。
スケジューリング オペレーティングシステムのスケジューラ実装
マルチプロセッシングでは、各プロセッサをなるべく平等に使用するようスケジューリングするのが一般的である。スケジューリングをプロセッサ単位に行う方式とシステム全体で行う方式があり、前者ではプロセッサ毎の実行可能プロセスのキューが存在し、後者ではシステムに唯一の実行可能プロセスキューが存在する。システム全体の方が優先順位の逆転が発生しにくく、プロセッサ間の負荷バランスをとりやすいという利点がある。しかし、実行効率を考えた場合、各プロセッサのキャッシュメモリの内容などを生かすにはプロセスはなるべく同じプロセッサ上で実行された方がよい。この性質をアフィニティ (affinity) と呼ぶ。そのため、プロセッサ単位のスケジューラを使用し、負荷バランスが大きく崩れたときだけ調整を行う方式を採用するシステムもある。また、システム全体をひとつのスケジューラで制御しようとすると、実行可能プロセスキューへのアクセスで衝突が発生し性能が低下するという問題もある。
スケジューリング オペレーティングシステムのスケジューラ実装
NUMAでは、SMPシステムが相互接続されている。このSMPシステム間でのプロセスの移動はSMP内よりもさらに性能に悪影響を与える。そのため各SMPシステムでスケジューラを動作させ、SMPシステム間の負荷バランスは別途調整するのが一般的である。Linuxではexec()によるオーバーレイの際にバランス調整を行う。exec()ではプロセスのアドレス空間の内容が置き換えられるので、ノード間の移動をさせるのにちょうどよいタイミングと言える。
初期のDOSやWindowsシステムはマルチタスクではないので、スケジューラも存在しなかった。Windows 3.1系のOSは単純な非プリエンプティブ・スケジューラを使用しており、プログラマはプロセスが明示的にCPUを明け渡す (yield) ように設計してCPU時間を他のプロセスに使わせる必要があった。これにより協調的マルチタスクをサポートしていた。Windows 95 で初歩的なプリエンプティブ・スケジューラを導入したが、互換性を維持するため16ビットアプリケーションはプリエンプションなしで動作した。
スケジューリング オペレーティングシステムのスケジューラ実装
Windows NT系のOSは多段フィードバックキューを使っている。優先度は32段階で0から31まであり、0から15がノーマル優先度、16から31がリアルタイム優先度と呼ばれている。リアルタイム優先度はアドミニストレータ特権がないと設定できない。0はOSが予約している。ユーザーはタスクマネージャまたはスレッド管理APIから動作中アプリケーションの優先度を5段階に設定できる。カーネルはスレッドのI/OおよびCPU使用具合を見て優先度を更新しており、対話的（ユーザーとのやりとりを行っている）なI/O中心のプロセスの優先度は高くし、CPU中心のプロセスの優先度は低くする。それによってアプリケーションの応答性を向上させる。Windows Vistaではスケジューラが修正され、タイムスタンプカウンタを使って各スレッドが実際に動作したCPUサイクル数をカウントするようになった。また、I/Oキューも優先度付きとなり、ディスクのデフラグメンテーションなどのプログラムが通常の処理を邪魔しないようになった。