どうも華麗なるキャッツパーです。キャットアッパーです。 この記事はCompetitive Programming Advent Calendar Div2013, 12/7の記事です。 私は過去に、暇に任せてこのようなスライドを作ってしまいました。 有名アルゴリズムとそれの計算量について列挙するのが楽しすぎて作ってしまいました。後悔しております。 本記事では「計算量ってどうやって計算するの？」みたいな話を競プロの観点からします。 計算量とはなんぞやということについては上のスライドを読んでください。 計算量の種類 競技プログラミングで気にする計算量は2種類あります。最悪計算量と償却計算量です。 最悪計算量というのは、ある処理にどのような入力を与えても、それ以上に速い計算量になる、というもので、一種の上界です。競技プログラミングでは作問者が最悪計算量になるテストケースをかならず入れてきますから
IBMは米国時間8月17日、人間の脳の認識力、認知力、行動力を模倣する新しい世代の実験的なプロセッサを発表した。これにより、人間の脳の働きに似た機能を備えたコンピュータは、これまでよりかなり実現に近づいた。 今回の発表の3年近く前に、IBMおよび同社と提携する大学数校が米国防高等研究計画局（DARPA）から助成を受けて、人間の脳の認知力や認識力、知覚、相互作用、行動能力を再現し、大きさとエネルギー消費の面で脳の効率の良さを模倣する研究に取りかかった。 この助成は、DARPAによる「Systems of Neuromorphic Adaptive Plastic Scalable Electronics（SyNAPSE）」プロジェクトの第2フェーズの一環だった。IBMによると、目標は「複数の感覚様相からの複雑な情報を瞬時に分析するだけでなく、環境との相互作用の中で動的に自らの配線もつなぎ換え
前の記事 怪獣映画、過去から現代まで：写真ギャラリー 16km間隔での「量子テレポーテーション」に成功 2010年5月21日 サイエンス・テクノロジー コメント： トラックバック (0) フィードサイエンス・テクノロジー Casey Johnston このほど、16キロメートルもの自由空間距離を隔てて、光子(フォトン)の間で情報をテレポーテーションさせる実験が成功した。 この距離は、過去の記録を塗り替えるものだ。この偉業を達成した研究チームは、これによって、従来の信号に頼らない情報のやり取りの実現に一歩近づいたと書いている。今回達成した16キロメートルという距離を、地表と宇宙空間の間隔まで広げることもできるだろうとチームは指摘する。[高度16kmは成層圏相当] 以前の記事(英文記事)にも書いた通り、「量子テレポーテーション」というのは、一般の人がテレポーテーションと聞いて想像するのとはかな
印刷する メールで送る テキスト HTML 電子書籍 PDF ダウンロード テキスト 電子書籍 PDF クリップした記事をMyページから読むことができます Salesforce.com主催のイベント「Dreamforce '09」で一番人を集めた講演はどれだったろうか。通常であれば、初日朝に開催される基調講演だろう。確かにあの時の人の多さはすごかった。会場は満席で、立ち見も出たほどだ。しかし個人的に筆者が席を確保するのに一番苦労し、ぎりぎりで席を替わってもらったものの立ち見を覚悟した講演は、唯一観客からスタンディングオベーションで迎えられた「普通のおじさん」によるものだった。元米国国務長官のColin Powell氏である。 Powell氏が国務長官を退任し、普通のおじさんに戻った日の朝、彼は妻にこう言った。「今日から新しい人生の始まりだ。もう私は朝5時半に起きて6時半に家を出ることはない
東京大学理学部情報科学科のパンフレットがすごい
先日の「ぜひ押さえておきたいコンピューターサイエンスの教科書」というエントリでは、東京大学理学部情報科学科の講義で使われていた教科書を中心に紹介しました。では、実際の授業の様子はどうなのでしょうか？ タイミングの良いことに、情報科学科のカリキュラムのパンフレットがウェブで公開されています。 東京大学理学部 情報科学科 パンフレット かなりの力作で感動しました。なにせ今まで外向けの色気があまりにない学科だったので。。。 （苦笑） 理学部情報科学科と工学系の学科との一番の違いは、パンフレットにもありますが、コンピューターの原理や理論的背景も押さえ（ここが重要）かつ最先端の技術やモノも作り上げていくところでしょうか。そんな雰囲気を、カリキュラムや実際の講義・演習の様子、教授陣のメッセージなどから、感じ取ってもらえることと思います。 一点だけ補足。このパンフレットには普通の学科紹介でよく見かける卒
ぜひ押さえておきたいコンピューターサイエンスの教科書
僕はバイオインフォマティクスという生物と情報の融合分野で研究を行っています。東大の理学部情報科学科にいた頃は同僚のマニアックな知識に驚かされたものですが、そのような計算機専門の世界から一歩外に出ると、それが非常に希有な環境だったことに気が付きました。外の世界では、メモリとディスクの違いから、オートマトン、計算量の概念など、コンピューターサイエンスの基礎知識はあまり知られていませんでした。コンピューターサイエンスを学び始めたばかりの生物系の人と話をしているうちに、僕が学部時代に受けた教育のうち、彼らに欠けている知識についても具体的にわかるようになってきました。 バイオインフォマティクスに限らず、今後コンピュータを専門としていない人がコンピューターサイエンスについて学ぶ機会はますます多くなると思われます。そこで、これからコンピューターサイエンスを学ぼうとする人の手助けとなるように、基礎となる参
前の記事 スレの状況がわかるツール：「多様な意見」を視覚化 パソコンの瞬間オン・オフも可能に：強誘電体トランジスターに新技術 次の記事 未解読のインダス文字を、人工知能で解析 2009年4月24日 Brandon Keim J.M. Kenoyer/Harappa.com 多くの考古学者の挑戦を退けてきた古代文字が、人工知能にその秘密の一部を見破られた。 4000年前のインダス文明で使われていた記号をコンピューターで分析したところ、これらの記号が話し言葉を表している可能性があることがわかったのだ。 「含まれている文法構造は、多くの言語で見られるものと共通しているようだ」と、ワシントン大学のコンピューター科学者、Rajesh Rao博士は語っている。 インダス文字は、紀元前2600年から紀元前1900年に今のパキスタン東部からインド北部にかけて使われていた文字で、エジプト文明やメソポタミア文
以前、とあるシステムのソースコードを読む機会があったのだけどあまりにひどかった。あのひどいコードでまあまあまともに動いているというのが逆に信じられない。今日昼ご飯を食べながら少し話していたのだけど意外と知られていないようなので、話せる範囲でいかにひどいのか説明してみようと思う。 まず、ソースコードが大雑把に見積もって3750万行あるのだけど、その中でまともに機能しているコードは3%しかない。10分の1程度のソースコードで同程度の機能を実現しているシステムもあるのでほんとあのシステムのコードはゴミだと言っても過言じゃない(*1) プログラマとしてはなんでそのプロジェクトはそんな状態になってしまったのか気になるところだけども、まあ多くのプロジェクト同様、真相を知る人は誰もいない。でもまあ、実際に機能しているコードのコピーみたいなものがあちこちに散らばっていることからしてコピー＆ペーストが盛んに
第4の回路素子「memristor」、32コアのCPU、グラフィックボードの終焉、USB 3.0、ワイヤレス電源、64ビットコンピューティング、Windows 7、Googleの提供するデスクトップ向けOS、ジェスチャーベースのリモートコントロールシステム、双方向配信プラットフォーム「tru2way」、DRMの終焉、などなど、テレビや新聞などではあまりIT系の最新テクノロジーというのは思っているよりも報道されていないわけですが、やはり事前に知っておけば必ず役立ちますし、知っておいて損はありません。 というわけで、PC Worldの「15 Hot New Technologies That Will Change Everything（すべてのものを変える15の熱い新技術）」という記事を元にして、あらゆるものを変える可能性のある知っておくべき15個の最新テクノロジーを紹介しておきます。 詳細
ノーベル物理学賞に続き、下村脩氏がノーベル化学賞を受賞し、株価暴落のニュースを各ニュースサイトのトップから追い出すほどのニュースになっています。さて、この下村脩氏というのはどういう方で、どのような研究をされてきたかというのは、各報道に任せるとします。一応Wikipediaも。 ■下村脩 - Wikipedia 今日はそれに関連することから、ネットの人たちにとって非常に興味深い話題をひとつ。 「下村努」という方をご存じでしょうか*1。この方、先の下村脩氏の息子さんだったりします。しかしネットユーザーには、もしかしたら昨日まではこちらの下村努氏の名前のほうを知っている方のほうが多かったかもしれません（それでも知っている方は、かなりディープな知識の持ち主だと思いますが）。実はこの方、ネットセキュリティ方面では非常に有名な人なのです。 この方の名前を知らなくてもインターネットをやっていれば「ケビン
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
