[過去ﾛｸﾞ] プログラミングのお題スレ Part21 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
185(1): デフォルトの名無しさん [sage] 2022/11/20(日) 23:19:52.84 ID:Z+w66nI6(1/4) AAS
>>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を求める問題に還元されるので線形時間とわかる
逆に言えばこの定理の証明のキーだけ書いてあれば“アウトライン”と呼べるし、オレはこの定理の勉強した時、“なるほどそうか、なら後は自分で挑戦！”と思ってやっていい練習になったのを覚えてる
そういうのが数学の世界でアウトラインと呼んでもらえるやつ
あのメモはそのレベルにない
201: デフォルトの名無しさん [sage] 2022/11/21(月) 01:58:04.34 ID:KDDXOYAA(4/5) AAS
× 簡潔明瞭なレス書かないで
〇 簡潔明瞭なレス書けないので
典型例 ⇒ >>185
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.041s