ネットワークシステムへの不正アクセスは, 機密情報の漏洩や, ネットワークサービスの妨害など, システム全体に甚大な被害をもたらす. 不正アクセスを検知するシステムとして侵入検知システム（IDS,$~$Intrusion Detection System）が広く用いられている. ネットワーク分散型IDSは, ネットワーク上に分散配置された複数のIDSで不正検出を行うものであるが, IDSの配置数, 配置ホストおよび攻撃シナリオの分割を決定するアルゴリズムは場あたり的なものしか知られていない. そこで, 本研究では, この問題をIDS分割配置問題として形式的に定義し, これを単純化した問題について効率よく解くアルゴリズムを設計した.また,状態遷移型IDSに特定した場合のIDS分割配置問題を解くアルゴリズムについて考察した.さらに,関連する問題としてProbe数最小化IDS分割配置問題がNP完全であることを証明した.