はなちるのマイノート

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

勉強メモ

【論文】「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記法 Ω記法 Θ記法 多…