「解けない問題」を知ろう「解けない問題」を知ろう 保坂 和宏 (東京大学 B2) 第 11 回 JOI 春合宿 2012/03/19 概要 • 計算量に関して • P と NP • NP 完全 • 決定不能 • いろいろな問題 • コンテストにおいて Turing 機械 • コンピュータの計算のモデル ▫ 「計算」を数学的に厳密に扱うためのもの • メモリのテープ (0/1 の列)，ポインタ，機械の 内部状態を持ち，規則に従って状態遷移をする • 本講義では C 言語等で，入力を受け取って何か 計算して出力を返すもの，とイメージしてよい ▫ 入力は適切な形式で 0/1 の列になっているとする 計算量 • 計算に必要な資源 • 入力のサイズ (0/1 のビット列の長さ) の関数と して表される • 時間計算量 ▫ 動作するステップ数 • 空間計算量 ▫ 使用するメモリの量 計算量 • 単位などは実はあまり気にしない
