隣接行列 - Wikipedia
辺の重みを持ち、多重辺を 持つ有向グラフ ループを持たない左のグラフの 可約隣接行列 グラフ理論および計算機科学において、隣接行列（りんせつぎょうれつ、英: adjacency matrix）は、有限グラフを表わすために使われる正方行列である。この行列の要素は、頂点の対がグラフ中で隣接（英語版）しているか否かを示す。 有限単純グラフの特別な例では、隣接行列はその対角上に0を持つ (0,1)-行列（英語版）である。もしグラフが無向ならば、隣接行列は対称である。グラフとその隣接行列の固有値および固有ベクトルとの間の関係はスペクトラルグラフ理論において研究される。 隣接行列はグラフに関する接続行列および次数行列と区別されなければならない。接続行列は、その要素が頂点-辺の対が接続しているか否かを示す行列表現であり、次数行列は個々の頂点の次数に関する情報を含む行列表現である。 頂点の組Vを持つ単純グ
Subset sum problem - Wikipedia
The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset of integers and a target-sum , and the question is to decide whether any subset of the integers sum to precisely .[1] The problem is known to be NP-complete. Moreover, some restricted variants of it are NP-complete too, for example:[1] The variant in which all inputs are pos
中置記法 - Wikipedia
中置記法（ちゅうちきほう、infix notation）とは、数式やプログラムを記述する方法（記法）の一種。演算子を操作対象の中間に記述することから、このように呼ばれる。 その他の記法として、演算子を操作対象の前（左）に記述する前置記法（ポーランド記法）、演算子を操作対象の後（右）に記述する後置記法（逆ポーランド記法）がある。 四則演算など初歩的な算術においては、もっぱら中置記法が多用されている。 次のようなBNFの構文規則群で定義される中置記法の文法について考える。 <expr> = <infix> | <num> <infix> = <expr> <op> <expr> <num> = 0 | 1 | 2 | 3 | 4 | ... <op> = ＋ | - | × | ÷ この文法には多義性（ambiguity。曖昧さ、とも言うが、「曖昧」という語には「輪郭がはっきりしない」というよ
グーグル面接難問集15
Silicon Alley InsiderブログがGoogleの面接で出た難問を特集してましたよね。｢スクールバスにゴルフボールは何個入る？｣、｢8歳児に分かるようにデータベー スを3つの文章で説明せよ｣などです。 ギズもさっそく15題ご用意してみました。 1. 夫婦100組が住む村で夫が全員浮気した... 妻はみんな他人の夫が浮気するとすぐ気づくのに、自分の夫の浮気には気づけない。村には不貞禁止の掟があり、夫の不倫を証明できた妻はその日のうちに夫を殺さなくてはならない。村の女は決してこの掟に背けないものとする。 ある日、村の女王がやって来て、この中に浮気をしてる夫が最低ひとりいると宣言した。さあ、どうなる？ 読者Olivier Coudertさんからのベスト回答： この浮気夫の問題は、帰納法でよく出題されるものだね。 浮気夫が最低ひとりいると女全員が知った途端、あとはその後の成り行きから
FrontPage - PukiWiki: 2012年度夏学期「実践的プログラミング」へようこそ
授業について 「実践的プログラミング」は教養学部前期課程で開講されている。全学自由研究ゼミナールです。 履修希望の方はUTAS等をご覧ください。2020年夏学期は月曜5限にオンラインで開講されました。 内容に興味がある方はPDFの資料等をご覧ください。(授業で扱う範囲はこの一部で、また細かくは差異があります) ウェブページについて 現在CMS変更に伴う更新作業中です。過去のページも引き続き閲覧可能です。 なお、国際大学対抗プログラミングコンテスト(ICPC)については、現在は多少状況が変化していますので、過去のページをご覧の際はご留意ください。 ACM-ICPCは、2018年12月までにはACMの後援が外れて、ICPCとなりました。 2020年度は、COVID-19の影響で、各チーム分散した環境で国内予選が行われています。教員による「監督」制度も適用されていません。 なお、来年度以降は未定
素数判定 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "素数判定" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2018年1月) 素数判定（そすうはんてい、英: primality test）とは、与えられた自然数が素数か合成数かを判定することである。素数判定を行うアルゴリズムを素数判定法という。 RSA暗号の鍵生成のように素数性の判定は応用上重要であるので、素数性を高速に判定するアルゴリズムは計算理論において強い関心の対象である。 仮定なしで決定的かつ多項式時間で終了する（クラスPに含まれる）素数判定法が存在するか否かは長らく未解決の問題だったが、2002年にそのような素数判定法が存在
「馬券の配当160億円」をどうやって実現したのか - 朝日新聞の補足記事 - アフター・パンデミック
ちまたの競馬予想会社のうさん臭さは、「そんなに儲かるならなぜ自分で買わない」という言葉で表されるが、ほんとに儲かる人間はやはり自分で馬券を買っていることを証明した事件だと言える。 asahi.com（朝日新聞）が競馬の配当１６０億円隠す 英国人社長のデータ分析会社という記事を報じているが、新聞紙面ではその隣に関連記事も掲載されているので、これを引用する。 「なぜそんなに稼げた - 3連単を分散買い」（2009年10月9日付朝日新聞より） ユープロ関係者らによると、同社は、天候や出走馬の血統、騎手などの各データを入力、解析する競馬必勝プログラムを使い、高確率で配当金を得ていたという。だが、億単位の資金を使い、ほとんどの組み合わせの馬券を買うという、一般の競馬ファンにはまねできないやり方だった。 05年設立の同社が目をつけたのは、「3連単」という馬券。1着から3着までを順番通り当てるもので、配
ユークリッドの互除法 - Wikipedia
英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Euclidean algorithm|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針につい
素数判別、素因数分解＜アルゴリズム＜Ｗｅｂ教材＜木暮
学習のポイント 素数判別、素因数分解の基本的なアルゴリズムを理解します。 キーワード アルゴリズム、素数、剰余、素数判別、エラトステネスのふるい、素因数分解 これまでは、素数研究が社会に直接関係することはあまりありませんでした。ところが、電子メールなどの暗号化が必要になりました。その暗号鍵、復号鍵では、「非常に大きいを素因数分解する計算には非常に時間がかかる」ことをベースにしています（→参考：「公開鍵暗号方式の原理」）。そのため、素数に関する関心が高まっているのです。 ２，３，５，７，１１，１３，１７，…など、１と自分自身でしか割り切れない数を素数といいます。１２＝４×３や、１８＝２×９のように、素数ではない数のことを合成数といい、２、３、４、９など、合成数を割り切れる数を約数といいます。そして、２や３など約数自体が素数であるとき、その約数を素因数といいます。 素数を扱うアルゴリズムは、大
ユークリッドの互除法 - inamori’s diary
ユークリッドの互除法（Euclidean algorithm）は、最大公約数を求めるためのアルゴリズムです。 割り切れるまで割り算を繰り返します。例えば、234と177の最大公約数を求めるには、 234 ÷ 177 = 1 余り 57 177 ÷ 57 = 3 余り 6 57 ÷ 6 = 9 余り 3 6 ÷ 3 = 2 余り 0 だから、最大公約数は3となります。 コードは、再帰を使って書くと簡単です。Cで書くと、 #include int GCD_core(int a, int b) { int d = a % b; if(d == 0) return b; else return GCD_core(b, d); } int GCD(int a, int b) { /* Pythonの仕様に合わせてある */ if(a == 0) return b; else if(b == 0) r
互いに素 - inamori’s diary
互いに素（coprime）とは、与えられた2つの整数が共通の素因数を持たないことを意味します。 例えば、4と6なら、 4 = 22 6 = 2•3 だから、2が共通の素因数となり、互いに素ではありません。12と25なら、 12 = 22•3 25 = 52 だから、互いに素です。 プログラムでこれを調べたいときは、最大公約数が1かどうかを調べます。1なら互いに素、そうでなければ互いに素でないことになります（負数を扱うときは注意）。 互いに素は、Project Eulerを解いていても意外とよく出てくる概念です。例えば、辺の長さがa, b, cの三角形を考えるとき、これらが互いに素でなければ、最大公約数で割った辺の長さの三角形と相似なので、こちらだけ考えればよい、などというように使われます。 関連 ユークリッドの互除法
順列 - Wikipedia
この項目では、順列について説明しています。初等組合せ論における permutationについては「置換」をご覧ください。 数え上げ数学における順列（じゅんれつ、英: sequence without repetition, partial permutation、仏: arrangement）は、区別可能な特定の元から有限個を選んで作られる重複の無い列をいう[1]。 初等組合せ論における「写像12相」はともに 有限集合から k-個の元を取り出す方法として可能なものを数え上げる問題に関するものである[2]。取り出す順番を勘案するのが k-順列、順番を無視するのが k-組合せである。 定義 1 位数 n の有限集合 E と自然数 k に対し、E の元からなる k-順列とは {1, 2, …, k} から E への単射を言う。 定義 2 位数 n の有限集合 E と自然数 k に対し、E の元か
決定的アルゴリズム - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "決定的アルゴリズム" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2022年3月) 決定的アルゴリズム（けっていてきアルゴリズム、英: deterministic algorithm）は、計算機科学におけるアルゴリズムの種類であり、その動作が予測可能なものをいう。入力を与えられたとき、決定的アルゴリズムは常に同じ経路で計算を行い、常に同じ結果を返す。決定的アルゴリズムは最も研究の進んでいるアルゴリズムであり、その多くは実際のコンピュータで効率的に実行できる実用性を備えている。決定性アルゴリズムと言うことも多い。 決定的アルゴリズムは
乱択アルゴリズム - Wikipedia
乱択アルゴリズム（らんたくアルゴリズム）、ランダム・アルゴリズム（英: randomized algorithm）または確率的アルゴリズム（かくりつてきアルゴリズム、（英: probabilistic algorithm）は、その論理の一部に無作為性を導入したアルゴリズムである。通常のアルゴリズムでは自然数を順番にあてはめるような決定的な部分で、乱数による非決定的な選択を入れることで、「平均的に」よい性能を実現することを目的とすることがある。形式的には、乱択アルゴリズムの性能はランダムビット列で決定される確率変数となる。その期待値を期待実行時間[1]と呼ぶ。最悪の場合に関して「無視できる」ほどに低い確率であることが、一般に、この類のアルゴリズムが効果的である要件となる。 n 個の要素からなる配列から「a」という要素を探す問題を考える。この配列の各要素は半分が「a」で残りが「b」である。単純
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://gamma.cs.unc.edu/users/gottschalk/main.pdf
ページランクとは(PageRank)
http://next1.msi.sk.shibaura-it.ac.jp/MULTIMEDIA/numeanal2/numeanal2.html
Erlang: 組合せをやってみる | | プログラマ2.0日報 | あすなろBLOG
単調増加関数とは何か？
マルチジッタードサンプリング - Raytracing-Wiki, to make the world a better place