ミケ猫の小部屋

情報学、数学、語学および料理(暫定)について発信します

【世にも奇妙な関数】行列の指数関数とは?

実数の指数関数は と書けるように、行列の指数関数は に書ける。時々思うけど級数って連続な関数を離散の和形式に変換して扱いやすいだろう。 この指数関数はなにかおかしい! この関数はを満たしていない。まずはを展開してみよう。 何の変哲もない級数です…

大学の線形代数で扱う帰納法

帰納法は証明手法として極めて重要なものです。特に証明する途中、証明する目標となる命題と似たような形の子問題がでる時帰納法は定番化される。帰納法は特に自然数などの構造で役立つけど、線形代数の場合はそう簡単ではない。行列や線形変換や線形空間な…

正則線形変換Tを分解してみた

ユニタリー空間の任意の正則線形変換は正値エルミート変換HとユニタリーUの積として表せる。この定理の証明ではと置いた後ひたすら式変形したら証明できる。しかし、そこから生み出した疑問は「なぜはこういう形を持つの?」。 この疑問を解くには[tex: T^]…

【線形代数あるある】行列の掛け算とベクトル内積はどんな関係?

最近卒論関係で、論理行列と01列の掛け算に触れる。そこで思ったが、実ベクトルと実行列の掛け算は行列の行とベクトルの内積に掛ける。01列と論理行列はなかなかそうとはいかない。 01列からなる線形空間と論理行列 01列の集合は線形空間なり 長さが3の01列…

よく出るあの級数!情報系なら絶対覚えるべき計算量の話!

皆さん、久しぶり!競プロを始めてから実装の話ばかりしていた。いよいよアルゴリズムの原点に戻った!今回は例のを見に行きたいと思う。 この級数はどこで出るの? まずは結論から言うと、この級数はクラスに属す。これでちょっと見覚えがあるのか?セット…

RE:ゼロから始めるLIS問題

最長部分増加列(LIS)問題は序列の単調増加の部分列の中で一番長い部分列の長さを求める問題である。最近ARC 104の問題 atcoder.jp を見ていたらLIS問題を振り替えようと思います。 貪欲アルゴリズム 配列]があるとする。dp[i]は長さがiの部分増加列の最後…

シュミット分解を軽く証明した

まずはシュミット分解は何かを軽く説明する。ある純粋量子状態があるとする。元の量子システムをAとBの二つのシステムに分けた後、サブシステムの基底をととする。が成立する。ここのrはAとBの中で次元数が低いシステムの次元数に相当する。 AとBが同じ次元…

ICPC2020国内予選のFに挑んでみた!

11/06にICPC国内予選に参加して、三問完で何とかギリギリ予選突破しそうなみけ(チームxjubichanx)です。試合最中にFが昔のJOIのある問題とよく似ていることに気づきながらも解けなかった。 挑戦の第一歩:基本方針 始まる前に、まずは問題を目に通してくだ…

【自称】世界一分かりやすいBITの解説

こんにちは!一ヶ月ぶりのブログ更新です~今度はBITを解説しに行きます。実は一年前ほど研究室でBITとセグツリーを解説しましたが、あの頃解説はちょっと不明なところもあったので、このブログのきっかけになります。 BITはRSQ問題を解決するデータ構造で、…

ベクトルから見るフーリエ級数

「フーリエ級数は周期関数を周期の異なる三角関数に分解する」と学部の一年から教え込まれたが、その公式がなかなか覚えられないダメ人間です(笑)。たぶん私と同感してる人はかなり多いと思います。この記事は公式を頭の中に焼き付けるためでも、一時の発…