アルゴリズムと計算量

摘要

昨今，Web上のデータの処理など，非常に大規模なデータを扱う分野は珍しくない．しかもシステム統合など，小さな実験を総て，いきなり大規模かつ重要な「本別を迎え．る状況も，しばしば見られる．こうした閉題をコンビュけ夕で扱う場合，小規模な実験でうまく行ったからと言って，本番でうまく行くとは限らない．1000個のデータでは高速に動作したプログラムが，1億個のデータを処理しようとしたら，いつまでも答を出してくれないこともある，また，それほど大規模な問題でなくても，工夫のない単純なプログラムではいつまでたっても答が出てこない，という問題は，世の中にはとてもたくさhある．例えば「大学の授業と担当教官と教室の公正な割振り」，「病院の看護師の勤務の平等な割当て」，「世界の名所をめぐる旅の効率の良いスケジュール」などなど，こうした問題は経験的に何となくやられている場合が多いが，「最適な解」を見つけることは，実は壌新のスーパーコンピュータでも離しい（…だから何となくやらざるを得ない！ ？ ）．