論理の一部に乱数など無作為性を導入したアルゴリズム。
Gerd AltmannによるPixabayからの画像 秋山です。Python好きのエンジニアです。プログラミングにおけるアルゴリズムというと「正確に計算し、正しい結果を得るための効率のよい方法」といったイメージがありますよね。このブログでもアルゴリズムに関する記事はいくつか書いてきましたが、単純ループだと時間がかかる処理をアルゴリズムを用いて計算量を減らそうとか、目的の値を効率よく探索しようとかそういった話が多かったと思います。今回はこれまでとは少し違ったタイプの「乱択アルゴリズム」（ランダム・アルゴリズム、確率的アルゴリズムとも）というものを紹介したいと思います。乱択アルゴリズムとは大雑把…
準備期間 問題所感 A B C D E F 作問に対する感想 昨日の記事でも書いた通り，ARC175 の writer をやった．この 3 人でのコンテスト開催というのはずっと前からチーム内で言われていた野望の一つであり，しかもそれが自分にとって一番愛着のあるコンテストである ARC として開催できたことがとても嬉しい．今年度の ICPC でも結構良い結果を出せたし，もう本当にこのチームで思い残すことはないかもしれない． 準備期間 チーム SPJ の Discord サーバで，私がそろそろ ARC やらね？と言い始めたことが開催のきっかけだった． よく考えると (考えなくても) 作問経験が豊富…
Library CheckerのFactorizeという問題でfastestを取ったので、そのコードの解説です（速度ランキング）。 Factorizeは、までの整数が高々100個与えられ、それらを素因数分解せよ、という問題です。 概要 上位陣（13ms～15ms）の解法では、ECM（楕円曲線を用いた素因数分解法）が使われているようですが、よくわからないのでこれには手を出しません。 ECMを用いていない提出の中で最速の提出はhqztrue氏の16msであり、20%以上の差があります。 この提出では、ポラードのロー法という手軽に実装できるアルゴリズムが用いられていました。 これを効率化してみます。…
昨年、このような記事を書きました。 modernclothes24music.hatenablog.com 内容は、「科学技術（テック）＆社会派コラム、という観点からSF小説を読んでいきたい」というものです。 この記事を公開してから、記事中でご紹介している書評ブログ「止まり木に羽根を休めて」管理人・feeさんから、私に向けてのお薦め記事を書いて頂きました。本当にありがとうございます。現在、このお薦めに従ってSF小説を開拓していっています。 toolatetoolate.dreamlog.jp では、前回からSF小説をどう読んでいったかについて、レポートのような形でお話します。 www.haya…
はじめに この記事はUEC 2 Advent Calendar 2023の23日目の記事です。 adventar.org 前日の記事はツナマヨさんの「積んでたコンテンツを消化していくよ」でした。 tunamayo1412.hatenablog.com 買ったけど未だ読めていない本は自分の本棚にもそこそこありますね…。(本当はこの記事でもちょっと紹介する予定でしたが締め切りを過ぎたのでカットしました) はじめに 自己紹介 突然ですが、読書していますか？ 学生向け LaTeX超入門 スペースキーで見た目を整えるのはやめなさい エクセル方眼紙で文書を作るのはやめなさい 分析者のためのデータ解釈学入門…
DLPやECDLPを解く手法。乱択アルゴリズム [** Pollard's for ECDLP] def pollard_rho(P, Q, G, order): """ Q = xP G: generator """ a, b, x = 0, 0, (1, 0) A, B, X = a, b, x def walk(a, b, x): if x[0] % 3 == 0: return (a*2) % order, (b*2) % order, multiply(x, 2) elif x[0] % 3 == 1: return a, (b + 1) % order, add_points(x,…
こんにちは！エンジニアの藤井（touyou）です！ この記事はGoodpatch Advent Calendar 2023の二日目の記事になります。 今回テーマにするのは昨年末のChatGPTリリースに始まり全世界を巻き込む社会現象となった「AI」についてのお話です。 ChatGPTの影響が大きかった一番の要因はチャット形式かつその性能の高さが今までAIに直接触ってなかった層を巻き込めるようになったから、というのはわりとメジャーな見方かと思いますが、一方でこれによってAIもとい機械学習がどういう仕組みで動いているのかという理解があまりないまま生成AIを触っている人も増えてきたのかなと思います。…
世界標準MIT教科書 アルゴリズムイントロダクション第4版 第1巻-基礎・ソートと順序統計量・データ構造・数学的基礎- 「世界標準MIT教科書 アルゴリズムイントロダクション第4版 第1巻-基礎・ソートと順序統計量・データ構造・数学的基礎-」内容紹介 「世界標準MIT教科書 アルゴリズムイントロダクション第4版 第1巻-基礎・ソートと順序統計量・データ構造・数学的基礎-」目次 「世界標準MIT教科書 アルゴリズムイントロダクション第4版 第1巻-基礎・ソートと順序統計量・データ構造・数学的基礎-」Amazonでの購入はこちら 「世界標準MIT教科書 アルゴリズムイントロダクション第4版 第1巻…
アルゴリズムの計算量を最悪評価するか平均評価するかとか細かい話があります。恥ずかしながら割と遅くまでクイックソートの最悪計算量が n^2 ということをちゃんとは把握していませんでした。乱択アルゴリズムは基本的にランダムネスを入れることで最悪の場合をできるだけ回避して平均計算量を減らせるという話だと思います。 その計算量の理論解析にはεネットの話とか学習理論と重なる部分もあって興味深いのですが、これまで自分で深く計算量の研究をしてきませんでした。学習理論の研究をしていると、サンプル計算量が主体なのですが、時間計算量や空間計算量も当然気になってはきます。ただ、そうやって全部入りの計算量を解析する話…
2023年7月17日～2023年7月23日に読んだ中で気になったニュースとメモ書き（TLSらじお*1第115回の原稿）です。全文を公開している投銭スタイルです。 [RFC 9446 Reflections on Ten Years Past the Snowden Revelations] [Reverse HTTP Transportドラフト] [Cloudflareの耐量子鍵交換確認サイト] [その他のニュース] ▼Who Writes OpenSSL? ▼群と楕円曲線とECDH鍵共有 ▼PQCデジタル署名の追加候補 ▼CAT: CryptAttackTester [暗認本：14 確率的ア…
kotatsugame，tsutajさんリスペクト． 研究 学振を書いた 大学の奨学金の申請書を書いた 趣味 ジムに通い始めた その他 The Design of Approximation Algorithms を買った． 帰省 歯医者 献血 勉強（研究に関係ないもの） Subset Sum の弱 NP 困難性 Karger のアルゴリズム PAC leraning ランチ Bistro Chez Harmonie 個室 自然・食彩・浪漫 おしか oshika 反省 研究 kotatsugame.hatenablog.com tsutaj.hatenablog.com 研究 学振を書いた 3…
www.slideshare.net
dankogai.livedoor.blog
www.amazon.co.jp
tech.preferred.jp
www.hyuki.com
qiita.com
tech.preferred.jp
tech.preferred.jp
ja.wikipedia.org
