「解けない方程式」
よくアニソンとかの歌詞で「解けない方程式」みたいなフレーズが出てくるが、代数方程式だって5次方程式（たった5次！）以上になったら一般には解けないし、微分方程式に至っては「ミレニアム懸賞問題」として100万ドルの懸賞金が懸かってたりする難しさなわけで、たいていの方程式は解けなくて当たり前なんだよ！って、聞くたびにツッコミたくなる。 つまり、「解ける方程式」なんてほとんど無いのだから、「解けない方程式」に悩むなんて、空が飛べる翼がないことに悩むくらい実現不可能な空想であり、そもそも悩み方として間違っている。 というかまずは、お前の歌詞で求める「解」は近似解ではダメなのか、どうしてダメなのか、歌詞はせいぜい10分も無いけど、小一時間膝を付き合わせて問い詰めたい。ゼミを開いてお前の意図を詳らかにしたい。 ガロア群が可解にならないからって諦める前に、最適化のための近似アルゴリズムを試せよ。ニュートン
スーパーマリオのジャンプのアルゴリズム - Qiita
先日、気持ちのいいジャンプを目指してというQiitaの記事を見かけました。記事中では、マリオのジャンプについても触れられています。マリオというと、マリオブラザースやスーパーマリオブラザース等々、色々あるのですが、これはおそらくスーパーマリオブラザースの事だと思われます。ジャンプアクションゲームといったらスーマリですね。 そのマリオのジャンプの仕組みは「マリオの速度ベクトルを保存しておいて座標を計算するんじゃなくて～」と書かれていて、別サイトのブログへのリンクが張られています。 マリオのジャンプ実装法とVerlet積分 ただ、この記述については不正確であるという別のブログもあったりします。 マリオの完コピvol.28 ジャンプの解析と修正 ホントのところはどうなんでしょうか？世界で最も有名なゲームのジャンプがどのように処理されているのか気になったので調べてみることにしました。 原典にあたる
低解像度ビデオもすぐに高解像度に変換できる超解像アルゴリズムTecoGANがすごい
3つの要点 ✔️ 低解像から高解像へ変換 ✔️ 時間的に一貫したフレームを生成するために双方向損失関数を採用 ✔️ 超解像度へ変換するTecoGANを提案 Learning Temporal Coherence via Self-Supervision for GAN-based Video Generation Temporally Coherent GANs for Video Super-Resolution (TecoGAN) written by Mengyu Chu, You Xie, Jonas Mayer, Laura Leal-Taixé, Nils Thuerey (Submitted on 23 Nov 2018 (v1), last revised 21 May 2020 (this version, v4)) Comments: Published by arXi
プログラマの採用面接で聞かれる、データ構造とアルゴリズムに関する50以上の質問 | POSTD
情報科学科の卒業生やプログラマの中には、UberやNetflixのような新興企業や、 Amazon 、 Microsoft 、 Google のような大企業や、InfosysやLuxsoftのようなサービスを基本とする企業で、プログラミング、コーディング、ソフトウェア開発の仕事に就きたいと考える人が大勢います。しかし、実際にそういった企業で面接を受ける場合、大半の人が プログラミングに関してどのような質問をされるか 見当もつきません。 この記事では、 新卒生からプログラマになって1〜2年までの 経験値が異なる人たち向けに、それぞれの プログラミングの面接でよく聞かれる質問 をいくつか紹介していきます。 コーディングの面接では、主に データ構造とアルゴリズムに基づいた質問 がされますが、 一時変数を使わずにどのように2つの整数をスワップするのか 、というような論理的な質問もされるでしょう。
Alpha Zeroの衝撃と技術的失業｜山本一成🚗TURING
2016年、Google DeepMind社から恐ろしい論文が出された、AlphaGoその名を冠した囲碁プログラムが既存の囲碁ソフトに勝率99％を叩き出したのだ。AlphaGoは強化学習とDeep Learningを組み合わせた囲碁プログラムで、その年に最強の囲碁棋士の一人である李世ドルさんに4勝1負で勝利した。その後も進歩を続けて今のAlphaGoの強さは人類が体感できるレベルを超えるほど強くなったと予想される。 2017年も終わりのころ、Google DeepMind社からまた途方もない論文が発表された。囲碁とほぼ同じ手法で最強レベルのチェスや将棋プログラムを超えたということだった。実際のところ正確に超えたのかどうかちょっとだけ疑問もあるのだが、まず前提として彼らの新手法が途方もない成果をあげたこと素直に祝福したい。彼らは自分たちのプログラムをAlpha Zeroと名付けた。 コンピュ
タワマンのゴミ捨て場にはお金になるものがたくさんある
タワマンに住んでる。 各フロアに24時間出せるゴミ捨て場があって、そこにはご近所さんが捨てた「まだ使えるもの」がけっこうある。 自分の過ちに気づけた。増田に書いてよかった。
エレベータに見るアルゴリズムの性能と公平性のバランス｜Rui Ueyama
現実世界でもコンピュータの中でも、何らかの性能指標だけを追求すると参加者にとって極端に不公平になってしまうことがある。例えばエレベータとHDDは共通点がありそうに思えないが、この2つは性能特性的にとてもよく似ていて、リーズナブルな性能と公平性を両立させるために同じ制御方法が使われている。これについてちょっと説明してみよう。 1基しかない場合のエレベータの動き方は単純だ。一度上に動き出すと、上で待ってる人や降りる人がいる限り上昇し続ける。同じように、一度下に動き出すと、下で待っている人や降りる人がいる限り下降し続ける。これ以外の動き方をするエレベータはまず存在しないので、これが唯一の制御方法のように思えるけど、別にこうしなければいけないというルールはない。 エレベータの平均待ち時間を最適化することを考えてみよう。そうすると、一方向に動き続ける代わりに、エレベータが現在存在する階に一番近い人の
「プログラミングの常識」を時々見直す必要性について｜Rui Ueyama
自分の中のプログラミングの常識というものは、ときどき現実のハードウェアに合わせて調節しないといけない。ハードウェアが進歩し続けているので、コンピュータで簡単にできることと相対的に難しいことのバランスが変化し続けているからだ。ここでは特にストレージにフォーカスして書こうと思う。 昔はメモリが相対的にとても貴重な資源だったので多くのプログラマがメモリを節約することに血道を上げていた。例えばWindowsの初期の頃に設計されたデータ構造には、メモリをバイト単位ででもいいから節約したいという意図の痕跡がいまでも多く見受けられる。DRAMの次に速い記憶装置はHDDだったので、メモリが足りなくなればHDDにデータを保存せざるを得ないのだが、DRAMとHDDのランダムアクセスの速度差は、机の上の本の開いているページを見るのと、その本をAmazonで注文して到着するのを待つのと同じくらいのスケールで違うの
差分検出アルゴリズム三種盛り - Object.create(null)
こんばんは. 気がつけばもうずいぶんと涼しくなってきました. 勢い余って凍ってしまったりせぬよう, くれぐれも普段の言動にはお気をつけください. はじめに さて, 我々人類にはどうしても二つの文字列 (あるいは行ごとに区切られたテキスト) 間の差分を求めなければいけない瞬間が発生します. 先人たちはそういった時のために diff のようなツールを開発し, それを利用することで文明はめざましい発展を遂げてきました. しかしながら, 使用するアルゴリズムを比較検討したい場合, 「差分」の定義を変えるなどして既存のアルゴリズムに変更を加えたい場合, diff のない異世界に飛ばされて自分で実装しなければいけない時などにおいては, 差分検出アルゴリズムについての理解が必要不可欠です. というわけで, この記事では文字列間の差分検出とは何かということと, 差分を求める三種類のアルゴリズムの紹介・解説
円周率の16進数表現100億桁目を求めてみた！ ― 円周率の世界記録をどのように検証するか ― - プログラムモグモグ
あなたは円周率を何桁言えますか。3.14159…という、あの数字です。 円周率の小数部分は無限に続き、循環することもありません。 古来より、数学者は円周率の値を様々な幾何学的な近似や公式を用いて計算してきました。 その桁数は計算機の発明により飛躍的に伸び、収束の速い公式の発見や効率の良いアルゴリズムの発明などによって加速してきました *1。 5年前、私がまだ学生だった頃、円周率1億桁の計算に挑んだことがありました。 私にとって高精度計算の初めての挑戦で、様々な試行錯誤で苦労したのをよく覚えています。 itchyny.hatenablog.com 2017年現在、円周率計算の世界記録は22兆桁です。 円周率計算の歴史をご覧いただくとよく分かると思いますが、近年の円周率計算の世界記録からは次のような特徴が読み取れます。 2002年に1兆を超え、最新の記録 (2016年) は22兆桁 (10進数
Brainfuck interpreter in Ruby's Regexp - 兼雑記
Ruby の正規表現だけで Brainfuck インタプリタを作ることができました。正規表現の実行は =~ だけなので、ループなども正規表現の内部で実行してます。 https://github.com/shinh/hack/blob/master/bf_rb_reg/bf.rb つまりどういうことができるかというと、 BF_REG という Regexp と BF_SUFFIX という文字列定数があって、 bf という文字列に格納された Brainfuck のコードを BF_REG =~ bf + BF_SUFFIX で実行することができます。出力は $~['o0'], $~['o1'], ... に入っているので、 output = '' 256.times do |i| o = $~["o#{i}"] break if !o output += o end 的なコードで取り出すことができ
Linuxカーネルのコードを読んで勉強になったこと - φ(・・*)ゞ ｳｰﾝ カーネルとか弄ったりのメモ
Linuxカーネルのコードを読んでて、なるほど〜と思うことはよくあるけど、その中でも特に今までの考え方をぶち壊してくれたのはなんだっけと思ったところ、やっぱりリスト構造かなと言うところ。 c言語でリスト構造を作る場合、一般的な教科書方式だと↓のようにデータとnextポインタは密結合になってると思います。これの場合、struct foobarのポインタをnext要素に使っているので、他の構造体（例えば、struct hogehoge）で同じことをしようとすると、その構造体ではstruct hogehoge *nextというメンバ変数を持つ必要があります。 ヘッド要素はstruct foobarです。 struct foobar { int n; char s[64]; struct foobar *next; }; struct foobar head; Linuxカーネルの場合、データとリ
ドワンゴで産まれた超人工生命LIS、ハッカソンでカンブリア紀に突入!
ドワンゴで産まれた超人工生命LIS、ハッカソンでカンブリア紀に突入! Childhood's End. she's rising to real life 2016.04.12 Updated by Ryo Shimizu on April 12, 2016, 02:51 am JST ニコニコ動画で知られるドワンゴは日本のベンチャー企業としては珍しく２つの専門的な学術研究機関を設置しています。 ひとつは、筆者が設立した西田友是東大名誉教授を所長とするコンピュータグラフィックスの専門研究機関、UEIリサーチであり、もう一つは、全能アーキテクチャイニシアチブの山川宏氏を所長とするドワンゴ人工知能研究所です。 全能アーキテクチャイニシアチブとは、これまで個別の要素技術としてしか発展してこなかったAI(人工知能)技術を、それぞれ視覚野、運動野、言語野、海馬などの役割をもたせ、全体として一つの人間
本当に実用的なたったひとつのソートアルゴリズム - CARTA TECH BLOG
コンテンツメディア事業本部の新卒エンジニア坂本がお送りいたします。 突然ですが、皆さんの好きなソートアルゴリズムはなんですか？ 私は基数ソートのスマートでストイックな雰囲気に惹かれます。 とはいえ、普段の開発では「どのソートアルゴリズムを使うか」を意識することは少ないのではないでしょうか。 むしろ現実世界で「トランプが全部揃ってるか」を手作業で確認するときとかのほうが、実はソートアルゴリズムが必要なのかもしれません。 ということで（？）、そのような現実的な場面で、本当に実用的なソートアルゴリズムを決める戦いが始まりました。 選手紹介 今回試したソートアルゴリズムは、独断と偏見で選んだ以下の5種類。 1 挿入ソート シンプル・イズ・ベスト！正直言ってベンチマークの噛ませ犬！ 2 クイックソート 「クイック」の名前はダテじゃない！王者の貫禄を見せてやれ！ 3 マージソート 安定感のある隠れた実
競技プログラミング特有の変な実装テク - ichyo.jp
初めに この記事はCompetitive Programming Advent Calendar 2014の15日目の記事です． 競技プログラミングでは，アルゴリズムをひらめく力や，数学やアルゴリズムの知識量などが強さを決める大きな要素ではありますが， もちろん，プログラミングを使った競技である以上は，コードの実装力が勝敗を分けることもあります． 例えば，ICPC系のコンテストでは，アルゴリズムを考える能力よりも，実装量の多いプログラムをいかにバグなく高速に実装するかが重要な 問題セットが与えられることが時々あります． 競技プログラミングと無縁なプログラマーは，実装力と聞くと， クラスの構造をうまく設計したり，変更に強い美しいコードを実装する能力だと想像する人がいるかもしれません． ですが，プログラミングコンテストに必要な実装力は，そうした保守性や拡張性ではなく， 「目的の処理をシンプルな
バブルソートよりも非効率なソートアルゴリズムを探して ―― ストゥージソートとスローソート - Line 1: Error: Invalid Blog('by Esehara' )
はじめに 恐らく、プログラマの中で配列内の要素を整列させたりするソートにお世話にならなかった人、というのは余り考えられないのではないでしょうか。しかし、とはいえ、大抵はソートを自前で実装せず、組み込み関数であったり、あるいは何らかのライブラリで済ませることが殆どだと思う。 車輪の再発明というよりも、バグとか、自分が考慮していなかった挙動などを避けるために、自前でソートを組むことは余りないのですが、とはいえ、自分なりにソートを実装して見ると、それがどういう特徴を持ったソートであるか、というのがわかりますし、また、ソートというのはいったいどういう操作で実現されるのかという洞察が深まってくるなあ、という実感があったりする。 なので、今回はあるソート二つについての話を書くのが趣旨です。 最高のアルゴリズムはある、だが最悪のアルゴリズムは何か 一口にソートといったところで、ソート自体にも銀の弾丸があ
竹内関数で音楽生成 - aike’s blog
Lisperの人ならみんな知ってる竹内関数（たらいまわし関数）という関数があります。 定義としてはこんな感じ。 そのシンプルな定義からは想像もつかないほど複雑で膨大な再帰呼び出しがおこなわれるとても興味深い関数です。たとえば引数にTarai(10,5,0)を与えると343,073回も再帰呼び出しされたりします。 この関数呼び出しの引数がどのように変化するか知りたくてプログラムを書いて調べてみたところ、Tarai(10,5,0)の場合は3つの引数がそれぞれ0〜10（xは-1〜10）の間で少しずつ変化するなかで、2つの値を固定してひとつの値が下降していくような挙動があったりして、なんだか音楽の3和音のコード進行を思わせるような動き方です。 そういうことなら、ということで実際に音にして聴いてみました。Tarai関数が呼ばれるたびに引数のx、y、zを、0=ミ、1=ファ、2=ソ、……、のように音に割
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
CPUに適度に間違わせることで節電する技術