はなちるのマイノート

Unityをメインとした技術ブログ。自分らしくまったりやっていきたいと思いますー!

勉強メモ

アルゴリズムイントロダクション第15章後半の個人まとめ

はじめに 前回前半をやったので、後半やっていきます。 www.hanachiru-blog.com テーマは同じく「動的計画法」です。 はじめに 動的計画法の基本要素 部分構造最適性 重みなし最短路問題 重みなし最長単純道問題 部分問題重複性 最長共通部分列問題 部分列 …

アルゴリズムイントロダクション第15章前半の個人まとめ

はじめに 少し飛びましたが、前回の続きやっていきます。 www.hanachiru-blog.com 今回のテーマは「動的計画法」になります。 はじめに 概要 ロッド切り出し問題 動的計画法適応 トップダウン型の動的計画法 ボトムアップ型の動的計画法 部分問題グラフ 連鎖…

アルゴリズムイントロダクション第5章の個人まとめ

はじめに 前回の続きをやっていきたいと思います。 www.hanachiru-blog.com 今回のテーマは「確率的解析と乱択アルゴリズム」になります。 はじめに 確率的解析 指標確率変数 乱択アルゴリズム 確率的解析 確率的解析は確率を用いる問題の解析手法である。入…

アルゴリズムイントロダクション第4章の個人まとめ

はじめに 前回の続きをやっていきたいと思います。 www.hanachiru-blog.com今回のテーマは「分割統治法」になります。www.hanachiru-blog.com はじめに 分割統治法 置き換え法 1. 推定 2. 数学的帰納法 再帰木法 マスター法 マスター定理 分割統治法 分割統…

アルゴリズムイントロダクション第3章の個人まとめ

はじめに 前回の続きをやっていきたいと思います。 www.hanachiru-blog.comちなみに内容的には昔書いたこの記事とかなり似ている感じでした。 www.hanachiru-blog.com はじめに 第3章「関数の増加」 Θ記法 O記法 Ω記法 o記法 ω記法 さいごに 第3章「関数の増…

アルゴリズムイントロダクション第1~2章の個人まとめ

はじめに 今回はアルゴリズムの名著とも言われている以下の本を読み、そのまとめを備忘録の意味合いも兼ねて書き残しておきたいと思います。 はじめに 第1章「計算におけるアルゴリズムの役割」 第2章「さあ,始めよう」 挿入ソート アルゴリズムの正当性 …

【数学】命題と論理式,その証明のチートシート

ド・モルガンの法則 存在記号 ex. の否定 の証明 How to prove Find x so that P(x) is true. Prove that Q(x) is true. 全称記号 ex. の否定 の証明 How to prove Let x be any element satisfying P(x). Prove Q(x) 命題が偽であることの証明 Statement X.…

【論文】「Algorithms for Gerrymandering over Graphs」を自分なりにまとめてみた

はじめに 今回は今までの記事とは少し違い、論文紹介をしたいと思います。読まさせていただいた論文はこちら。kyushu-u.pure.elsevier.com http://www.ifaamas.org/Proceedings/aamas2019/pdfs/p1413.pdfテーマは選挙の区分けをグラフ理論の視点からみるとい…

グラフ理論の基礎についてのメモ①

はじめに 今回はグラフ理論の基礎について書きたいと思います。細かい証明などは一切なく、色々な用語や定理などを爆速で列挙していきます。 はじめに グラフ 単純グラフ・多重グラフ 有限グラフと無限グラフ 次数 部分グラフ 歩道 連結性 完全グラフ 2部グ…

P,NP,NP完全,NP困難についてのメモ

はじめに 今回はP,NP,NP完全,NP困難について書いていきたいと思います。私自身習いたてなので、本当に備忘録というかメモ程度なのであしからず。 はじめに 前置き P NP NP困難 NP完全 多項式時間帰着 参考 前置き 問題はそれぞれ異なる難しさを持っていま…

多項式時間アルゴリズムの種類についてのメモ

はじめに 昨日の記事で多項式時間アルゴリズムについて少し触れたのですが、その種類について書いていきたいと思います。 強多項式時間アルゴリズム 弱多項式時間アルゴリズム 擬多項式時間アルゴリズム 多項式時間アルゴリズムは強多項式時間アルゴリズムと…

オーダー記法(O記法,Ω記法,Θ記法)の定義についてのメモ

はじめに 今回はオーダー記法の定義について書いていきたいと思います。オーダー記法とは関数の値の発散の速さを漸近的に評価するものです。実用の仕方というよりはどのように定義をされているかという視点からみていきます。 はじめに O記法 Ω記法 Θ記法 多…