マルコフアルゴリズムとは [単語記事] - ニコニコ大百科
マルコフアルゴリズム単語 マルコフアルゴリズム 4.5千文字の記事 13 0pt ほめる 掲示板へ 記事編集 概要定義マルコフアルゴリズムはチューリング完全関連リンク関連項目掲示板マルコフアルゴリズムとは、複数の文字列置換規則から構成される文字列書き換え系である。 概要 マルコフアルゴリズムはアンドレイ・マルコフ・ジュニアによって考案された文字列書き換え系である。他の文字列書き換え系として有名なものにチョムスキーの生成文法があり、これなら知ってるという人も多いのではないだろうか。 定義を述べる前に簡単な例から見ていこう。 マルコフアルゴリズムはいくつかの置換規則によって構成される。規則は一つでもよい。例えば次のようなもの。 Hello:World このルールは 「"Hello" という文字列を "World" に置換する」と読む。置換の前後をコロンで区切る書き方は後述する Markov A
![マルコフアルゴリズムとは [単語記事] - ニコニコ大百科](https://cdn-ak-scissors.b.st-hatena.com/image/square/252a11a5273459076774f059e02c76e277e5e02d/height=288;version=1;width=512/https%3A%2F%2Fdic.nicovideo.jp%2Fimg%2Fog_b.webp)
競技プログラミングで解法を思いつくための典型的な考え方 | アルゴリズムロジック
競技プログラミングの問題を解くためには２つのステップがあります。 問題で要求されていることを言い換える知っているアルゴリズムやデータ構造を組み合わせて解く 必要な（知っておくべき）アルゴリズムやデータ構造は色々なところで学ぶことができます。 しかし、「問題の言い換え」や「アルゴリズムを思いつく」というのは、非常に様々なバリエーションがあり、問題をたくさん解かないとなかなか身につきません。 そこで、この記事は以下のことを言語化し、練習のための例題を提示することを目標とします。 問われていることを、計算しやすい同値なことに置き換える方法アルゴリズムを思いつくための考え方競技プログラミングで「典型的」と思われる考え方 ※一部問題のネタバレを含むので注意 ※良く用いられるアルゴリズムやデータ構造については競技プログラミングでの典型アルゴリズムとデータ構造 を参考にして下さい。 入力の大きさ(制約)
コーディング面接対策のために解きたいLeetCode 60問
自分がコーディング面接対策のために解いてよかった LeetCode の問題をコンセプトごとにまとめました。カバーするコンセプトは LinkedList Stack Heap, PriorityQueue HashMap Graph, BFS, DFS Tree, BT, BST Sort Dynamic Programming Binary search Recursion Sliding window Greedy + Backtracking です。 これらの問題が 30 分以内に実装できれば面接の準備は整ったと言っていいと思います。Easy と Medium で問題は構成されてます。進捗を管理するためにGoogle Spreadsheetを用意しました。コピペしてご自由にお使いください。 これらの問題は、LeetCode のリスト機能でも公開されています。クローンすれば自分がすでにど
コーディング面接対策のために解きたいLeetCode 60問
自分がコーディング面接対策のために解いてよかった LeetCode の問題をコンセプトごとにまとめました。カバーするコンセプトは LinkedList Stack Heap, PriorityQueue HashMap Graph, BFS, DFS Tree, BT, BST Sort Dynamic Programming Binary search Recursion Sliding window Greedy + Backtracking です。 これらの問題が 30 分以内に実装できれば面接の準備は整ったと言っていいと思います。Easy と Medium で問題は構成されてます。進捗を管理するためにGoogle Spreadsheetを用意しました。コピペしてご自由にお使いください。 これらの問題は、LeetCode のリスト機能でも公開されています。クローンすれば自分がすでにど
JavaScriptで始めるジェネラティブアート - 生物アルゴリズムの応用 - ICS MEDIA
ジェネラティブアートという言葉をご存知でしょうか？ アルゴリズムによって作られる芸術作品を指す名称です。Pinterestで「generative art」と検索すると静止画、動画ともにたくさんの作品を見ることができます。 無機質さを感じさせるものもあれば、まるで生きているように感じる作品もあります。創作者たちはどのようなところから着想を得ているのでしょうか？ 彼らの中には数学的な幾何学模様や物理現象、果ては生物が織りなす複雑なパターンをコンピューターで再現することにより作品を作る者もいます。 本記事では特に「生物」に焦点を当てます。生物の複雑な営みを紐解いた背景や、それをアルゴリズムに落とし込むことで可能になった表現を紹介します。 本記事を読むことで日常に潜むあらゆる現象が芸術の種に見える喜びを感じていただければ幸いです。 サンプルはHTML CanvasとJavaScriptで作成して
最短経路問題総特集！！！～BFSから拡張ダイクストラまで～ - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 基本的アルゴリズム（幅優先探索など）から応用（経路復元、拡張ダイクストラなど）まで、最短経路問題に関するアルゴリズムを総特集しました。 基本的なグラフ理論の用語については、次を参考にしてください。 グラフ理論 用語集 queueなどのデータ構造の用語については、次のスライドの後半を参考にしてください。 C++ STL講習会 by @e869120 最短経路問題とは 一般的に、次のような問題とされます。 $V$ 頂点と $E$ 辺からなるグラフが与えられる。頂点 $u$ と 頂点 $v$ を結ぶパスのうち、重みの総和が最も小さいものはどれ
二分木 - Rustではじめるデータ構造とアルゴリズム（第1回）
Rustの特徴のひとつは、所有権(ownership)・移動(move)・借用(borrow)の概念です。これらがコンパイル時に厳格にチェックされることにより、古くから未定義挙動でプログラマを悩ませてきたダングリングポインタなどの問題がなくなり、メモリ安全性がもたらされます。 しかし一方で、自分で多少複雑なデータ構造を定義しようとする場合にはコンパイルを通すだけでもかなりの知識・力量が要求されます。 この（不定期）連載では、 Rustではじめるデータ構造とアルゴリズム と題し、プログラミングコンテストなどでよく見かける基礎的なデータ構造とアルゴリズムを、できるだけシンプルにRustで実装していきます。 &, &mut, Box, Rc, Cell, RefCell などの使い分けや、なぜそれを使う必要があるかの解説を、実例を通して行います。 第1回は、最もシンプルな木構造である 二分木 を
状態機械を合成してデッドロックを検出できる Go 言語パッケージを作ってみました - チェシャ猫の消滅定理
はじめに マルチスレッドで動作するプログラムの設計は難しい問題です。個々のスレッドの動作は単純に見えても、複数が並行して動作する場合の動作は組み合わせ論的に複雑になります。また、タイミングに依存する不具合は狙って再現することが難しく、通常の単体テストによる検出にも限界があります。 そんなとき、有効な手法がモデル検査です。システムの取りうる状態をあらかじめ網羅的に探索することで、「実際に動作させた際にごく低い確率で踏むバグ」であっても、動作させることなく設計段階で発見することが可能になります。 ところでちょうど先日、デッドロック発見器を自作するハンズオンに参加する機会がありました。内容は非常にシンプルなモデル検査器を実装するというもので、せっかくなのでそのときの成果物を Go のパッケージとしてまとめたものを以下に公開しました。 github.com 以下、このパッケージで何ができるのかを具
スーパーマリオのジャンプのアルゴリズム - Qiita
先日、気持ちのいいジャンプを目指してというQiitaの記事を見かけました。記事中では、マリオのジャンプについても触れられています。マリオというと、マリオブラザースやスーパーマリオブラザース等々、色々あるのですが、これはおそらくスーパーマリオブラザースの事だと思われます。ジャンプアクションゲームといったらスーマリですね。 そのマリオのジャンプの仕組みは「マリオの速度ベクトルを保存しておいて座標を計算するんじゃなくて～」と書かれていて、別サイトのブログへのリンクが張られています。 マリオのジャンプ実装法とVerlet積分 ただ、この記述については不正確であるという別のブログもあったりします。 マリオの完コピvol.28 ジャンプの解析と修正 ホントのところはどうなんでしょうか？世界で最も有名なゲームのジャンプがどのように処理されているのか気になったので調べてみることにしました。 原典にあたる
気持ちのいいジャンプを目指して - Qiita
ジャンプを実装するとき，重力をイメージして放物軌道を作りがちです． だがHAL研の方はかく語りき． キャラクターを動かすプログラムでは、ときに自然法則を無視して気持ちよさを追求する、ということをよく行います。 自然界の物理法則よりも気持ちいいジャンプ，探求したいと思いませんか？ この記事ではジャンプの実装方法をいくつか紹介します．結局重力使えばいいやと思わなくもないですが… 初めに 今回はヒヨコ🐤ちゃんがジャンプします！以下ヒヨコちゃんの座標は $(x, y)$ と表記します．ただし画面左上が原点で，画面下方向にyの値が増えていくことに注意です．この辺は使用したゲームエンジン pyxel の仕様です．（あとクラスで書いてないので，邪悪なグローバル変数だらけです…．先に謝ります） 最初に実装の全体像を示します． import pyxel def drawHiyoko(x, y): # ヒヨ
作って理解するOS x86系コンピュータを動かす理論と実装 | 技術評論社
概要 現在広く普及している、x86系CPU搭載のコンピュータ。 本書はOSの機能を実装しながら、その姿を明らかにしていきます。 第1部ではまず、ハードウェア、ソフトウェアの基本概念や、CPUとOSの関係など、コンピュータの核となる理論を丁寧に解説します。 第2部では、x86系コンピュータに対象を絞り、レジスタの構成や、機械語命令の使い方などを詳細に検討します。 第3部は、いよいよOSの実装パートです。第1部、第2部で得た知識を生かして、マルチタスクなどのOSの機能を楽しみながら実装することができるでしょう。 なおイントロダクションでは、初学者向けの基礎知識を解説。 「2進数って何？」という方でも、x86系コンピュータとOSへの理解を深めることを可能にする一冊です。 目次 イントロダクション コンピュータが数を数えるしくみとC言語への応用 0.1 コンピュータが数を数えるしくみ 0.2 C言
いい感じのビジュアルをランダムになんとなく作り出す - ABAの日誌
なにかを作った。めざせジェネレーティブアートジェネレータ！ クリック／タップで別の絵を作ります。 この手のものの難しさは、 >RT ランダムにものを作ると自由度と打率のトレードオフになると思うんですが、この自由度でこの打率はかなりすごい気がします…… しかもパラメータがURLに埋め込まれている！（例 https://t.co/w4Ov3PXkY7 ） しかも p5.js + TypeScript！— FAL @STG制作とプログラミングお絵かき (@falworks_ja) 2019年7月30日 という具合に自由度を高くしていろんなバリエーションを作ろうとすると見てて面白いものができあがる打率が減って、逆に打率を上げようと面白くなさそうなものをフィルタリングしていくと自由度が低くなること。 自由度を高くするにはランダムにするものを増やせばいい。今回は座標と線の太さと色を表す数式を乱数で作っ
inconvergent · Generative art by Anders Hoff
About inconvergent is a generative art project by anders hoff. the project explores complex behaviour arising from simple rules. sometimes i write about generative algorithms, programming. and more recently, domain specific languages, datalog and metaprogramming. other subjects include 3d rendering, vector art, asemic writing; and some experiments with abstract geometry and architecture. you will
プログラマだったら当然知ってるよね？という知識一覧
2019年11月11日追記 ただのタイトルで煽ってるだけの記事に半年経っても未だに大量のアクセスがあるので追記しておきます。 ここで言いたいことは、「プログラマならコンピュータサイエンスを勉強してると役に立つよね」、ということ だけ です。 この一文以上に有用な言葉は以降の文章では出てきません。みなさんの時間を無駄にしないために注意書きをしました。 それでも良いという人は読んでみてください。 Twitterで「〇〇ができるという人が面接に来たけど、『じゃあXXXやYYYって知ってます？』というと知らないという人が多いんだよねぇ」とかいうツイートを見かけて、私はXXXやYYYってのを知らなかったので調べた見たところ、常識とまでは言えない概念だったり、名前は知らなくても誰もが知ってる概念だったり、むしろもっと良いアプローチがあるのではという思想だったりでなんだかなぁと思っていたところ、半日くら
競技プログラミングで使う有名グラフアルゴリズムまとめ
0. はじめに AtCoderなどでは、グラフを扱った問題が多く出るが、その度に一から実装していると時間が掛かりすぎてしまうため、有名なものをあらかじめ持っておく必要がありそう。そこで、Pythonを用いて、ダイクストラ法、ベルマンフォード法、プリム法、クラスカル法、ワーシャルフロイド法を実装した。 コメント、意見等ある方は是非! お待ちしてます! 1. ダイクストラ法 1.1. ダイクストラ法(defaultdictで実装) defaultdictで実装すると、リストで実装するよりも、ノード数$N$が大きい際には高速に動作する。ただし、経路復元の関数は、うまく書けなかった......。 (2019/7/6 追記)結局できました。1.1.1. を参照してください。 import collections import heapq class Dijkstra: def __init__(se
再帰関数を学ぶと、どんな世界が広がるか - Qiita
0. はじめに 再帰関数は初めて学ぶときに壁になりがちで なんとなくわかった...けれど どんな場面で使えるのだろう...いい感じの例を探したい！ という気持ちになりがちです。再帰関数は、なかなかその動きを直感的に想像することが難しいため、掴み所が無いと感じてしまいそうです。 そこで本記事では 再帰関数の動きを追いまくることで、再帰関数自体に慣れる 再帰的なアルゴリズムの実例に多数触れることで、世界を大きく広げる！ ことを目標とします。特に「再帰関数がどういうものかはわかったけど、使いどころがわからない」という方のモヤモヤ感を少しでも晴らすことができたら嬉しいです。なお本記事では、ソースコード例に用いるプログラミング言語として C++ を用いておりますが、基本的にはプログラミング言語に依存しない部分についての解説を行っています。 追記 1. 再帰関数とは 再帰の意味はとても広いです。自分自
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Eulerroom Equinox 2020
ピューロランドでオールナイト！ 一夜限りのスペシャルハロウィンパーティー開催 | PARTY CHANNEL［パーティーチャンネル］
アルゴリズムビジュアル大事典
Generative Photography - An Interview With Gottfried Jäger — Artnome