はてなブックマーク

こんにちは、ももやまです。 今回は前回の基本3ソートアルゴリズムに引き続き、基本ソートよりもより実用的で高速な応用4ソートアルゴリズム（クイックソート・マージソート・シェルソート・ヒープソート）について説明していきたいと思います。 なお、応用4ソートのうち、クイックソート・シェルソート・ヒープソートの3つは基本情報に頻繁に出てくるので基本情報を受ける人はそれぞれのソートの仕組みを頭に入れておきましょう。 残りのマージソートも応用情報に出てくるので、応用情報まで目指している人はマージソートについても軽く理解しておくといいかもしれません。 前回の基本3ソートアルゴリズムについては、下の記事をご覧ください。 www.momoyama-usagi.com

こんにちは、ももやまです。 動的計画法は、アルゴリズムでもかなり重要な内容です。AtCoderやらプログラミングコンテストとかでもよく出てきます。 ですが、動的計画法は「アルゴリズムを学ぶ上での壁・登竜門」とも呼ばれるとおり、かなり難易度の高いアルゴリズムとなっています。どの参考書を見てもなかなかわかりやすくは書かれていません。 そんな動的計画法を今回はうさぎでもわかるようにわかりやすくかみ砕いて説明したいと思います。 １．動的計画法とは 動的計画法とは、 問題をいくつかの簡単で小さな問題に分割 それぞれの問題の計算結果を表に記録 同じ問題に対しては表から計算結果を参照する の3つの特徴を持ったアルゴリズムです。 といきなり言われてもわけがわからないと思うので、動的計画法のイメージを説明しましょう。 動的計画法のイメージ 例えば、\[ 28 \times 37 \]の計算を解きなさい。 と

こんにちは、ももやまです。 今回は「P vs NP問題」について少しわかりやすめにまとめました。 この問題は、数学上の未解決問題となっており、2019年6月現在でも6つが解決していません。その問題の1つが「P vs NP問題」となっています。 これらの未解決問題は、アメリカのクレイ数学研究所によって、100万ドル（約1億円）の懸賞金がかけられています。*1トリビアの泉でも紹介されました。 No.681 「数学の世界には解くと賞金１億円がもらえる問題がある」 （番組評価 85/100へえ） もちろん「P vs NP問題」も懸賞金がかけられている問題の1つです。 そんな「P vs NP問題」とはどんな問題なのかをわかりやすく説明していきたいと思います。 ※注意 今回は問題はYesかNoかを判定する問題だけを考えます。このような問題を決定問題と言います。決定問題の例としては、 300円以内で50

２．2分探索木とは 親の左側のノードの値が必ず親よりも小さく、右側のノードの値が必ず親よりも大きくなっている2分木のことを2分探索木と呼びます。 2分探索木では、下の図のようにどの親に対しても値が必ず左の子＜親＜右の子となっています。 さらに左の子だけでなく、左部分木のすべてのノードの値が親よりも小さくなる特性があります。 右部分木のすべてのノードの値も同様に親よりも大きくなる特性があります。 つまり左部分木のそれぞれのノード＜親＜右部分木のそれぞれのノードの関係も成立します。 よって、上の図にある2分探索木のそれぞれのノードに入る値の範囲は下のようになります。 スポンサードリンク ３．2分探索木を用いた探索 2分探索木では、それぞれのノードに対し、「左部分木のそれぞれのノード＜基準ノード＜右部分木のそれぞれのノード」が成り立つので、データの探索を簡単に行うことができます。 実際に上の木構

こんにちは、ももやまです。 今回は2分探索木の4つの走査方法、具体的には 行きがけ順による走査通りがけ順による走査帰りがけ順による走査幅優先探索による走査 の4つの違いについてわかりやすく説明していきたいと思います！ 「2分探索木ってどんなやつだっけ」、「2分探索木忘れちゃったよ」という人は下にある記事でわかりやすく2分探索木について説明しているのでぜひご覧ください！ www.momoyama-usagi.com １．2分探索木の全探索 木構造にある各ノードを1度だけ訪問することを探索（走査）と呼びます。 全探索の仕方をおおまかに分けると、 深さ優先探索(DFS)幅優先探索(BFS) の2つとなります。 さらに、深さ優先探索はさらに 行きがけ順（先行順 / 前順 / preorder）通りがけ順（中間順 / 間順 / inorder）帰りがけ順（後行順 / 後順 / postorder）

こんにちは、ももやまです。 今回は基本情報にもよく出てくる探索アルゴリズム（線形探索・2分探索・ハッシュ探索）について説明していきたいと思います。 １．探索とは 配列やリストなどのデータ構造の中から目的のデータを探した出すことを探索といいます。 「データなんて最初から順番に探し出していけばいいじゃん！」 と思うかもしれません。 しかし、もしデータ数が100億あったらどうでしょう。 地道に計算すると日がくれそうです。もっといいアルゴリズムがないかなぁと思いたくなりますよね。 そこで今回はコンピュータ上でよく使う探索アルゴリズム、具体的には 線形探索二分探索ハッシュ探索 の3つを紹介していきたいと思います。 スポンサードリンク ２．線形探索 (1) 線形探索とは 配列の先頭から順番に目的のデータかどうかを調べていく方法を線形探索と呼びます。 しらみつぶしに探していく最も単純な探索アルゴリズムで

こんにちは、ももやまです！ 今回は情報理論で習う「情報量」について簡単にまとめてみたいと思います！ 情報量、エントロピーの理解には「確率」に関する知識が必須です。 確率についてあまりよく分かってない、苦手だなと思う人のために確率の要点をまとめた記事を下に用意したので、ぜひご覧ください。 www.momoyama-usagi.com １．「情報量」とは…？ 皆さんは、情報といえばどんな情報を浮かびますか？ 昨日の天気は晴れのち雪 今年のK大学の入試問題 NくんとCさんが付き合っている 今ならLINE Payを使うとポイント5%アップ などなど様々な情報を浮かべると思います。 しかし、その情報がどれほどの大きさを持っているかは文章だけでは比べることができません。そんなときに使われるのが情報量です。 情報量の大きさは、以下のようにして定義することができます。 POINT1 情報量は起こる確率 \

記事修正　2019/05/25　一部極限式やオーダーの \( n \) が \( x \) になっていたのを修正 こんにちは、ももやまです。 今日は久しぶりに情報系のまとめです。 皆さん、効率のよいアルゴリズムってどんなアルゴリズムだと思いますか？ 時間がかからない、メモリを食わない、などなど様々な評価の仕方があると思います。 今回は「どうやってアルゴリズムの良し悪しを評価するか」、そして「アルゴリズムの評価でよく使われるオーダー表記 O( )」についてまとめてみようと思います。 １．計算量ってなに…？ 何人かが作ったアルゴリズムの良し悪しを評価したいとします。 評価の方法には様々な方法があるのですが今回は、かかった時間で評価してみるとします。 例えば、Aさんの作ったアルゴリズムは実行に30秒かかりました。 しかしBさんの作ったアルゴリズムはたったの10秒で計算できちゃいました。 あ、Bさ

こんにちは！　ももやまです！ 今回は離散数学（情報数学）ってどんなことするの？　何の役にたつの？　というのを少しまとめてみました。わかりやすく書いたので厳密な定義では説明できてません…… １．離散数学って何？　前提科目は？ 高校時代、数学の様々な科目を履修したはずです。二次関数、図形と方程式、三角関数、指数関数、対数関数、微積、理系の人なら複素数平面などなど……。 でも離散数学という名前だけではどんなことをするのか全然わかりませんよね。 ということで、まずは離散数学とはどんな数学なのかを見てみましょう。 微分積分学の極限に関係しない数学。すなわち〈連続の数学〉に対して離散的な構造を扱う数学。計算可能性の理論，符号理論，オートマトンの理論，計算量の理論，証明論，組合せ論などの幅広い分野が含まれる。 有限でかつ離散的な，非計量の分野を対象とする数学。集合論，整数論，グラフ理論，組合せ論などの分