>>184
メモ書きというのが証明のアウトラインと呼べるものならともかく、到底そんなレベルではない
たとえばSₙ₊₁の互換の生成元σ₁‥σₙによるreduced expressionを見つけるアルゴリズムの話とかだと
定理 g∈Sₙ₊₁に対してg(i)>g(i+1)である任意のiに対してgσᵢのreduced expression の長さがgのそれより真に1小さくなるものが存在する
とかがキーになる
そしてこれが証明できれば確かに線形時間で証明ができるのは数学ちょっと学んだ人間ならすぐわかる
前の方のレスで「最後の寿司で場合分け」といっていたけどそれでは指数時間になる、ミソは“g(i)>g(i+1)である任意のiに対して”言えてるのがミソで場合分けの必要がなく以下gσᵢのreduced expressionを求める問題に還元されるので線形時間とわかる
逆に言えばこの定理の証明のキーだけ書いてあれば“アウトライン”と呼べるし、オレはこの定理の勉強した時、“なるほどそうか、なら後は自分で挑戦!”と思ってやっていい練習になったのを覚えてる
そういうのが数学の世界でアウトラインと呼んでもらえるやつ
あのメモはそのレベルにない
探検
プログラミングのお題スレ Part21
■ このスレッドは過去ログ倉庫に格納されています
185デフォルトの名無しさん
2022/11/20(日) 23:19:52.84ID:Z+w66nI6■ このスレッドは過去ログ倉庫に格納されています
ニュース
- 【地震速報】青森県で震度6強 沿岸部に津波警報 ★2 [ぐれ★]
- 【地震速報】青森県で震度6強 沿岸部に津波警報 ★3 [ぐれ★]
- 【地震速報】青森県で震度6強 沿岸部に津波警報 ★4 [ぐれ★]
- 【速報】高市総理が官邸入り [Hitzeschleier★]
- 「日の丸にバツ印」掲げた大学生 あいまいな国旗損壊罪に「怖い」 The Mainichi [少考さん★]
- 【芸能】岡田紗佳、新幹線でありえない迷惑客に遭遇 自分の席に荷物が「ここ私の席ですって言っても…」 [冬月記者★]
- 地震 ★2
- 高市早苗さん、地震が起きてから1時間経ってから津波が来るから避難してXに投稿 [931948549]
- ぺこーら、地震で同僚が次々配信を止めるなか強行し続けるので悪目立ちするwww [268244553]
- 【速報】高市早苗、起床 [779938112]
- 巨大地震 [957955821]
- 00:00:00.000
