エラトステネスの篩の高速化 - Qiita
世の中に多くあるエラトステネスの篩の実装、多くあるくせにちょっとしか高速化してないのが悲しいので高速化エラトステネスの篩を書いてみることにします。 エラトステネスの篩の高速化 (1) ← 今ココ エラトステネスの篩の高速化 (2) エラトステネスの篩の高速化 (3) エラトステネスの篩の高速化 (4) エラトステネスの篩の高速化 (5) エラトステネスの篩の高速化 (6) エラトステネスの篩の高速化 (7) 問題設定 とりあえず C++11 くらいで動く物を作りたいと思います。インラインアセンブラや SIMD、並列化は明示的には入れない方針です。あと、エラトステネスの篩自体の高速化を目指すので、結果は一部の具体的な素数の確認と $\pi(x)$ の値で確認することにしますし、その時間は考慮しないことにします。 また、ライブラリ的に使えるよう、将来的には区間篩 (大きな $x$ に対して $
世界1位取った後3年間オセロAIを作り続けたらﾅﾆﾓﾜｶﾗﾅｸなってﾁｮｯﾄﾀﾞｹﾃﾞｷﾙようになった話 - Qiita
2021年、ふとしたきっかけでオセロAIを作り始め、オセロAIコンテストに作ったAIを提出し、なんやかんやあって半年かけてそのコンテストで世界1位になりました。 それで満足…？と思いきや、全然満足せず、コンテスト関係なしにオセロAIを作って早3年。この記事ではオセロAIが色々なところに私を連れて行ってくれた話と、オセロAIが深いという話をします。 この記事は2年ほど前に書いていっぱい読んでいただけた以下の記事「ｶﾝｾﾞﾝﾆﾘｶｲｼﾀ話」の続編、みたいな立ち位置です。単体で読んでも、以下の記事と合わせて読んでも楽しめます。 世界1位からさらに高みを目指す 私が参加したオセロAIのコンテスト(CodinGame Othello)は、コンテストという特性上、かなり厳しい制約が設けられていました。例えば着手する時間です。これは1手あたり0.15秒以下でないといけません。また、コード長にも制限があり
Googleの検索アルゴリズムの内部資料が漏洩か？「SEO業界で長年疑われていたものが明らかに」
Mic King @iPullRank Ok, let's get this party started! A couple weeks ago I said I was publishing the most important thing I ever wrote. I was wrong. Documentation related to the Google Search algorithm leaked and I spent the weekend tearing it apart. ipullrank.com/google-algo-le… ✌🏾 2024-05-28 11:10:19 数週間前、私はこれまで書いた中で最も重要なものを発表すると言いました。それは間違いだった。 Google検索のアルゴリズムに関するドキュメントが漏洩したため、私は週末をかけてそれを徹底的に調
驚異の1ビットLLMを試す。果たして本当に学習できるのか?｜shi3z
昨日話題になった「BitNet」という1ビットで推論するLLMがどうしても試したくなったので早速試してみた。 BitNetというのは、1ビット(-1,0,1の三状態を持つ)まで情報を削ぎ落とすことで高速に推論するというアルゴリズム。だから正確には0か1かではなく、-1か0か1ということ。 この手法の行き着くところは、GPUが不要になり新しいハードウェアが出現する世界であると予言されている。マジかよ。 https://arxiv.org/pdf/2402.17764.pdf ということで早速試してみることにした。 オフィシャルの実装は公開されていないが、そもそも1ビット(と言っていいのかわからない,-1,0,1の三状態を持つからだ。 論文著者はlog2(3)で1.58ビットという主張をしている)量子化のアルゴリズム自体の研究の歴史は古いので、BitNetによるTransformerの野良実装
PNGファイル爆発しろ！
まえがき Web上で広く利用されるPNG(Portable Network Graphics)フォーマットは、デジタル画像を変化させずに小さいデータサイズへ変換する圧縮技術の一種です。PNGフォーマットはオリジナル画像を完全復元可能な可逆(lossless)圧縮ですから、JPEGフォーマットのように画像を歪めてしまう非可逆(lossy)圧縮ほどは小さくできません。それでもオリジナルのデジタル画像データの半分程度まではサイズ削減可能な画像圧縮アルゴリズムと言われています。[1] そげぶ いいぜ てめえが何でも思い通りに圧縮出来るってなら まずはそのふざけた幻想をぶち壊す!! （スペース都合によりAA省略） 本記事では、PNGフォーマットを画像データ圧縮(compress)用途で利用するのではなく、オリジナル画像データよりも遥かに巨大なPNGファイル を生成します。 PNGフォーマットでは任意
Windows 95のプロダクトキーは「111-1111111」や「000-0000000」でも突破できる超単純アルゴリズムで実装されていた
1995年に登場した「Windows 95」のインストール時にはプロダクトキーの入力を求められるのですが、プロダクトキーは「111-1111111」や「000-0000000」といった単純な数字の羅列でも認証されてしまいます。このような単純なプロダクトキーでも認証可能な理由について、セキュリティ研究者のstacksmashing氏が解説しています。 Why 111-1111111 is a valid Windows 95 key - YouTube これが、Windows 95のプロダクトキー入力画面です。不正なプロダクトキーを入力するとインストールを続行できなくなるのですが、「111-1111111」という単純なプロダクトキーでも「正しいプロダクトキー」として認識され、インストールを続行できます。 また、先頭の3桁を「000-1111111」「001-1111111」「567-1111
結城浩とChatGPTの対話
ChatWithChatGPT.md 結城浩とChatGPTの対話 2022年12月2日 「質問」は結城浩の文章です。 「回答」はChatGPTの文章です。 質問 ChatGPTという対話するAIツールがあります。人間が質問を投げかけるとそれらしく対話して回答してくれるツールです。こういうツールに対してどんな質問を投げかけたらおもしろい対話になるでしょうかね。何かアイディアがあったら聞かせてください。具体的な質問を知りたいなあ。 回答 ChatGPTは自然言語処理能力が高いため、人間が自然に投げかける質問をそれらしく受け答えることができます。例えば、ニュースやスポーツに関する話題、人間の心理や行動、哲学的な問題、文化や歴史に関する話題など、様々なテーマについて対話することができます。また、ChatGPTを用いた対話は、人間のようなスムーズな会話のように進むことができますので、おもしろい対話
計算複雑性理論を知らないやつが何をやらかすか教えてやろう。 ある業務用..
計算複雑性理論を知らないやつが何をやらかすか教えてやろう。 ある業務用Webシステムは検索結果の表示件数を5/10/20件から選べるようになっててて，URLのパラメーターで「?n=20」とかやって送ってた。メニューからは三つの値しか選べないが手で書き換えれば100とか200とか選べる穴が空いてた。 で，よりによってメモリ使用量がO(n^2)になるコードを書いていやがった。n=500でOutOfMemoryError。リモートから面白いようにサービスを落とせた。 CSを知ってるやつなら，コードを書いた瞬間から「これnの上限チェック入れないとまずいな」とわかるんだよ。というか，普通にこのコードはまずいと考えてアルゴリズムをなおして，O(1)でDBレコード全件持ってきても落ちないコードにできてたはず。
数理最適化の参考書
専門家が執筆した数理最適化の書籍を紹介しています． 適当に書籍を並べただけですので内容については各自で確認をお願いします． 数理最適化全般 数理最適化の概観を知りたい人向け 穴井宏和，数理最適化の実践ガイド，講談社，2013． 中山舜民，オフィスsawa（作画），橘海里（イラスト），マンガでわかる数理最適化，オーム社，2024． 数理最適化を現実問題の解決に活用するプロセスを知りたい人向け 岩永二郎，石原響太，西村直樹，田中一樹，Pythonではじめる数理最適化（第2版） ―ケーススタディでモデリングのスキルを身につけよう―，オーム社，2024． 三好大悟，Excelで手を動かしながら学ぶ数理最適化：ベストな意思決定を導く技術，インプレス，2023． 数理最適化を初めて学ぶ人が手に取る入門書 福島雅夫，新版 数理計画入門，朝倉書店，2011． 久野誉人，繁野麻衣子，後藤順哉，数理最適化，オ
「ぷよぷよは計算困難」―パズル・ゲームと最適化アルゴリズム― – Ono Laboratory
はじめに 最近，「一般化ぷよぷよのより強い計算困難性」なる研究を発表しました（東北大学の江藤宏先生，九州大学の木谷裕紀先生との共同研究．国内研究会であるゲームプログラミングワークショップで江藤先生による口頭発表．2021年12月30日現在，pdfはここから取れます）． これは有名なビデオゲーム「ぷよぷよ」を一人用のパズルと見立てたとき，かつそれを一般化した場合，どの程度難しいものであるのかを（最適化）アルゴリズム論的に分析したものです．今回「最適化技術の応用・実践」に関する記事を集めよう，ということになりましたので，ちょうどよい題材ということで，この研究をより一般向けに解説してみようと思います．一般向けですので証明自体には踏み込まず，既存の定理と得られた定理の意義をおよそわかっていただくことをこの記事の目標とします．ただし「ぷよぷよ」について関してはおよそルール等がわかっている方を対象とし
アルゴリズムと数学の本を書きました - E869120's Blog
1. はじめに こんにちは、はじめまして。東京大学 1 年生の米田優峻（E869120）と申します。私は競技プログラミングが趣味で、AtCoder や国際情報オリンピックなどの大会に出場しています1。2021 年 11 月時点で、AtCoder では赤色（レッドコーダー）です。また、2020 年以降、アルゴリズムを学べる以下のようなコンテンツや資料を作成してきました。 レッドコーダーが教える、競プロ上達ガイドライン 競プロ典型 90 問 50 分で学ぶアルゴリズム さて、このたびは技術評論社から、書籍を出版させていただくことになりました2。アルゴリズムと数学が同時に学べる新しい入門書です。 「アルゴリズム×数学」が基礎からしっかり身につく本 - amazon 発売日は今年のクリスマス、2021/12/25 です。電子書籍版も同時期に出る予定です。本記事では、この本の内容と想定読者について、
俺氏、将棋が二人零和有限確定完全情報ゲームでないことに気づいてしまうｗｗｗ | やねうら王 公式サイト
このブログをご覧の方は将棋が二人零和有限確定完全情報ゲームであることはご存知でしょう。これは、ゲーム理論や探索アルゴリズムの教科書にでも載っています。「二人零和有限確定完全情報ゲームって何？」って方は、Wikipediaでも見ていただくことにして話を先に進めます。 零和とは？ この「零和」というのは、和が零。英語で言うとゼロサムです。 零和（「ゼロ和」と読むのが一般的だが「レイワ」とも読む）：プレイヤー間の利害が完全に対立し、一方のプレイヤーが利得を得ると、それと同量の損害が他方のプレイヤーに降りかかる https://ja.wikipedia.org/wiki/二人零和有限確定完全情報ゲーム つまり、自分が勝ちなら、相手は負け。相手が勝ちなら自分は負け。勝ちを+1点、負けを-1点、引き分けを0のように定めるなら、(ゲーム終局後に)自分と相手の点数を足すと0になる。なので、ゼロサムゲームと
マギレコ2話の絶交階段を計算機として利用する - Qiita
マギアレコード 魔法少女まどか☆マギカ外伝 第2話 https://abema.tv/video/episode/26-89_s1_p2 マギレコ2話に以下の機能を持つ「絶交階段」がでてきます. 絶交階段の6段目に自分の名前,7段目に絶交したい相手の名前を書いちゃえばそれが絶交証明書！ もしも仮にも万が一仲直りなどしようものなら謝った方が鎖の化け物に攫われちゃう！ この絶交階段を使ったら計算機が作れそうですよね. 本質的には「nandゲートが構成できれば計算機が作れる」ので,この記事では絶交階段を使ってnandゲートを構成するところまで示します. 絶交階段の機能 この絶交階段の機能を理想状態での機能として解釈すると以下の通りになります. 二値($1$:現世に居る, $ 0$:鎖の化け物に攫われている)をとる人間 $a_1,a_2,...$ が無限に存在する ペア$(a_i,a_j)$を絶交
『みんなのデータ構造』でデータ構造の基礎を学んだ - valid,invalid
データ構造とアルゴリズムの学習の一環として『みんなのデータ構造』を読んだ。これまでで最も良いデータ構造の学習になった。 みんなのデータ構造 作者:Pat Morin発売日: 2018/07/20メディア: 単行本（ソフトカバー） 日本語訳がWebで公開されているので気になる方は無料で読める。が、著者や訳者や出版社応援の意味も込めて購入すると良いと思います。また、ラムダノート社のサイトから買うと紙書籍と電子書籍のセットがお得。 内容 データ構造とアルゴリズムに関連する本はアルゴリズム寄りのものが多いが、データ構造に焦点を当て続けていることが本書の特色。 内容の依存関係 p.21より 大学の教科書のように、正確性を優先したハードコアな内容。 アルゴリズムの内容も少しだがある。「11章 整列アルゴリズム」ではそれまでの章で学んだデータ構造がどのように使われるかを一瞥でき、「12章 グラフ」では深
ブルゲ的脱衣将棋のAIの凄さは「強さ」だけじゃない - 緑SM64のいろいろメモ
2003年(2001年の誤りでした。訂正してお詫び申し上げます。)ごろに発売され、アダルトゲームなのに異常に棋力が高いことで話題となったブルゲ的脱衣将棋。 搭載されているAIについてはその棋力にばかり注目されがちですが、このAI、他の将棋ソフトにはない唯一無二のものだと個人的には思います。 そんな訳で、今回はこの将棋ソフトについてレビューしていきたいと思います。 この記事ではR-18な側面には一切触れませんが（というか私がアダルトゲームを基本プレイしないので触れたくても触れられない）、一応18歳未満の方はみないでネ！ ブルゲ的脱衣将棋って？ 異常に強いAI AIが強いだけじゃなく特徴的 この棋風がもたらすもの まとめ ブルゲ的脱衣将棋って？ まずブルゲ的脱衣将棋について説明すると、ブルーゲイル社の人気作品のヒロインが集結した作品です。 ヒロインについては原作の絵師、声優の方を集結し、楽曲も
AI企業としてのAdobeの戦略 （前提編）｜深津 貴之 (fladdict)
今年のAdobe MAXの話題は、人工知能「Adobe Sensei」一色だった。 ステルスぎみのAI企業だったAdobeが、いよいよ浮上してきた今回のMAX 2017。 数年前から「AdobeはAI銘柄」と言い続けてきた僕としては、とても感慨深い。 以下、自身の雑感まとめ。大きな戦略レイヤーの話がメインなので、個々のテックはICSさんの記事などをご参考。 ＊注 筆者はAdobe社から、Adobe MAX 2017への招待を受けて参加しています。ですが、それはそれとして中立で書きます。Adobeさん都合の悪いこと書いてたらごめんなさい。前半エントリではAdobeのAI戦略を理解する前提として、「AdobeがAIや未来に投資しだした背景」、「Adobeのビジネス構造」の2つを論じる。 AI戦略の始まりは月額課金へのシフト まず最初に、AdobeがAIプレイヤーとして、急速に浮上してきた背景を
人間VSコンピュータオセロ 衝撃の6戦全敗から20年、元世界チャンピオン村上健さんに聞いた「負けた後に見えてきたもの」 (1/3) - ねとらぼ
急激に進歩するAIにより生活が激変するといわれる21世紀。2045年、あるいはそれを上回る速度で、人間の知能をAIが決定的に上回る「シンギュラリティ」が来るともいわれ、人間の存在価値すら問われ始めている昨今において、衝撃的な出来事でした。 そのちょうど20年前の1997年。囲碁と将棋のように、人間にとって非常にポピュラーな知的ゲーム2つで人間が敗れた、歴史的な年がありました。 チェスで伝説的世界チャンピオンだったガルリ・カスパロフ氏が、IBMが開発したAIの「ディープ・ブルー」に2勝3敗1分けで敗退。 そしてもう1つがオセロ。当時の世界チャンピオンだった日本人の村上健（たけし）氏が、NEC北米研究所によって作られた「ロジステロ」に6連敗で敗れました。 「コンピュータが人間を凌駕する」瞬間をいち早く、最も間近で迎えていたオセロ元王者・村上さん。彼に話を聞けば、そう遠くない将来に来るかもしれな
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
データベースでユニークキーにUUIDを使うメリットは何ですか？連番やタイムスタンプまたは複合などではいけないのでしょうか？どうも視認性が悪く使いにくく感じますし連番でも衝突しない気もします。
AI 激動の年！2022年の人工知能10大トレンドと必読論文
「人工知能でいい感じの成果を出してくれ」という偉い人の脳内はどうなっているのか – ところてん – Medium
