プログラミング

置換法（代入法）による漸化式の解き方アルゴリズムの計算量を評価する際、再帰的な処理の実行時間は「漸化式」として表されることがあります。本記事では、置換法（代入法）を用いて漸化式を解き、計算量を導出する手順を解説します。理解を深めるために、二分探索とマージソートという2つの代表的なアルゴリズムを例に取り上げます。例1：二分探索の計算量まずは二分探索（バイナリサーチ）から見ていきましょう。二分探索では、配列の中央に目的の要素が存在するかどうかを確認します。中央に存在すればアルゴリズムは終了し、存在しない場合は、元の配列の左半分または右半分の部分配列に対して同じ操作を繰り返します。そのため、各ステッ

データベースの可用性やパフォーマンスを向上させる技術として、「ミラーリング」と「レプリケーション」があります。どちらもデータのコピーを作る仕組みですが、目的や適用範囲、コストなどに明確な違いがあります。本記事では、それぞれの概要と主な相違点を解説します。 ミラーリング(Mirroring)とは ミラーリングとは、マスターデータベースサーバーに対して、バックアップ用のデータベースサーバーを別途用意しておく技術です。何らかの障害によってマスター側のデータベースがダウンした場合でも、ミラー側のデータベースを代替として利用できるため、システムの継続稼働(高可用性)を実現できます。 原則として、ある時点

データ構造は、その要素の配置方法によって大きく「線形データ構造」と「非線形データ構造」の2種類に分類されます。本記事では、それぞれの特徴を解説したうえで、両者の違いを比較表を使ってわかりやすく整理します。 線形データ構造とは 線形データ構造では、データ要素が一列に（逐次的に）配置され、各要素は前後の要素と連結されています。この連結によって、単一のレベルを一度の走査でたどることができるのが大きな特徴です。また、コンピュータのメモリ自体も逐次構造であるため、線形データ構造は実装が比較的容易です。代表例としては、配列、リスト、キュー、スタックなどが挙げられます。 非線形データ構造とは 非線形データ構

ビッグデータとは、膨大な量のデータとその処理全般を扱う概念です。扱うデータ量が非常に大きいため、データがどのように整理・体系化されているかという観点から、大きく「構造化データ」「半構造化データ」「非構造化データ」の3種類に分類されています。 3つのデータタイプの概要 構造化データとは 行と列で厳密に整理されたデータです。リレーショナルデータベース(RDB)のテーブルやExcelの表が代表例で、氏名・住所・電話番号のようにあらかじめ決められたスキーマ(構造定義)に従って格納されます。 半構造化データとは 一定のルールや構造は持っているものの、リレーショナルデータベースのような厳密な表形式に

ブールの不等式とは確率論におけるブールの不等式（Booles inequality）は、「和の上界（union bound）」とも呼ばれる重要な定理です。有限個または可算個の事象の集合に対して、それらのうち少なくとも1つの事象が起こる確率は、個々の事象の確率の総和を超えないことを示しています。確率論の基礎確率論とは、ランダムな事象の起こる確率を研究する数学の重要な分野です。確率とは、実験の結果として現れる事象が起こる「起こりやすさ」を測る尺度のことです。具体例：コイン投げ例えば、コインを投げる行為は「実験」、表または裏が出ることは「事象」と呼ばれます。理想的なコインであれば、表が出る確率も裏が

ベイズの定理とはベイズの定理（ベイズの規則）とは、新しい関連する証拠が得られたときに、それまで持っていた信念や確率の推定値を合理的に更新するための数学的手法です。データ構造やアルゴリズムの分野にとどまらず、機械学習、統計的推論、スパムメールフィルタリングなど、幅広い領域で応用されています。具体的な例として、ある人物ががんに罹患している確率を求める場面を考えてみましょう。追加情報が何もない段階では、まず「人口全体に占めるがん罹患者の割合」をそのまま確率として採用することになります。しかし、「その人物が喫煙者である」という新たな証拠が得られた場合はどうでしょうか。喫煙者はそうでない人に比べてがんに

辞書（ディクショナリ）は、オブジェクトの集合を格納するための汎用的なデータ構造として定義されます。辞書は「キー」の集合と関連付けられており、各キーには必ず1つの「値」が対応します。キーを指定すると、辞書はそのキーに関連付けられた値をそのまま返します。辞書の具体例例えば、クラスで実施したテストの結果は、学生の名前をキー、点数を値とする辞書で表現できます。results = {Anik : 75, Aftab :80, James : 85, Manisha: 77, Suhana :87, Margaret: 82}この例では、「Anik」というキーを渡せば「75」という点数が取得できる、という

ハフマン木とは？定義 ハフマン符号化（Huffman coding）は、各文字に出現頻度（重み）に応じた長さの符号を割り当てる圧縮手法です。ハフマン符号は可変長であり、かつ接頭辞条件（どの符号も他の符号の先頭部分にならない性質）を満たします。このような接頭辞条件を満たす2進符号は、符号化された文字を葉に配置した二分木として表現できます。 ハフマン木（ハフマン符号木）とは、木のすべての葉が与えられたアルファベットの各文字に対応する完全二分木として定義されます。 また、ハフマン木は「外部経路重みが最小」となる二分木として捉えられます。これは、与えられた葉の集合に対して、重み付き経路長の総和が最小

企業のデータ活用において、「データウェアハウス」と「オペレーショナルデータベース」は役割がまったく異なる二つの重要な基盤です。本記事では、それぞれの特徴と違いを、データ構造・パフォーマンス・主な用途などの観点から比較表付きでわかりやすく解説します。 データウェアハウスとは? データウェアハウスとは、特定の目的に向けてすでに加工・整理された、構造化されたフィルタリング済みデータを格納するリポジトリ(保管庫)のことです。複数のソースからデータを収集し、ETLプロセス(Extract:抽出、Transform:変換、Load:ロード)によって整形したうえでロードされ、ビジネス分析や意思決定のために活

問題概要 本記事では、次の2つの操作をサポートするデータ構造をC++で設計・実装する方法を解説します。 addWord(word):単語を辞書へ追加する search(word):単語を検索する search(word)は、通常の単語だけでなく、小文字アルファベット(a〜z)とドット(.)のみで構成されたパターン文字列も扱えます。ドットは任意の1文字に一致するワイルドカードとして機能します。 例えば、「bad」「dad」「mad」の3つの単語を登録した状態での検索結果は以下の通りです。 search(pad) → false search(bad) → true search(.ad)

ステガノグラフィ（隠蔽書法）とはステガノグラフィは「カバー・ライティング」とも呼ばれる技術で、秘密のメッセージを一見するとごく普通のメッセージに見える形へと変換する手法です。最大の特徴は、メッセージの内容を隠すだけでなく、「そもそも秘密の通信が存在していること」自体を目立たなくできる点にあります。ただし、その実装や理解には一定の専門知識が求められ、扱いは決して容易ではありません。また、ステガノグラフィではデータの構造は変更されず、元の状態が保たれます。テキスト、音声、動画、画像など、さまざまなメディアに応用できる点も大きな魅力です。暗号化（クリプトグラフィ）とは暗号化は「シークレット・ライティ

重み（コスト）が割り当てられた連結グラフ G(V,E) が与えられたとき、クラスカル法（Kruskals algorithm）は、グラフと各辺のコスト情報をもとに最小全域木（Minimum Spanning Tree：MST）を求めるアルゴリズムです。クラスカル法は「マージツリー（木の統合）」アプローチに分類されます。初期状態では各頂点がそれぞれ独立した木を構成しており、コストが最小となる辺から順に選びながらこれらの木を統合し、最終的に1本の木へとまとめ上げます。具体的な手順は以下の通りです。まずグラフのすべての辺を列挙し、コストの昇順にソートします。続いて、リストからコストの小さい辺を取り出

プリム法（最小全域木）とは 連結グラフ G(V,E) のすべての辺に重み（コスト）が与えられているとき、プリム法（Prims Algorithm）はそのグラフから最小全域木（Minimum Spanning Tree: MST）を見つけ出すアルゴリズムです。 プリム法は「木を成長させる（growing tree）」アプローチを採用しています。まず開始地点となる種（シード）の頂点を1つ決め、その頂点を起点として木全体を育てていきます。 この問題は2つの集合を使って解きます。一方の集合には「すでに選択されたノード」を保持し、もう一方には「まだ考慮していないノード」を保持します。種となる頂点から

非負の重みを持つグラフにおける単一始点最短経路問題を解くアルゴリズムは、「ダイクストラ法（Dijkstras algorithm）」として広く知られています。隣接行列で表現されたグラフ G(V,E) と始点（ソース頂点）が与えられたとき、ダイクストラ法を用いることで、始点からグラフ内の他のすべての頂点への最小コストの経路（最短経路）を求めることができます。 下図のように、開始ノードから他の各ノードまでの最小距離を求めるのが目的です。この問題では、グラフは隣接行列で表現します（この用途ではコスト行列と隣接行列は同じものとして扱えます）。 入力例：隣接行列 0 3 6 ∞ ∞ ∞ ∞ 3 0 2

単一始点最短経路問題とベルマン・フォード法 単一始点最短経路問題(single source shortest path problem)を解くための代表的なアルゴリズムがベルマン・フォード法(Bellman-Ford algorithm)です。このアルゴリズムは、重みが正でも負でも構わない任意のグラフにおいて、始点となる頂点(source vertex)から他のすべての頂点への最小距離を求めることができます。 同じく有名な最短経路アルゴリズムであるダイクストラ法との最大の違いは、負の重みを持つ辺の扱いです。ダイクストラ法では負の重みを含むグラフを正しく処理できませんが、ベルマン・フォード法

ワーシャル・フロイド法（全点対最短経路）とは全点対最短経路（All-Pair Shortest Path）問題を解くための代表的なアルゴリズムとして知られているのが「ワーシャル・フロイド（Floyd-Warshall）法」です。このアルゴリズムは、重み付きグラフが与えられた際に、すべての頂点ペア間の最短経路を一括して求めることができます。アルゴリズムを実行すると、最終的に1つの行列が出力されます。この行列には、グラフ内の任意のノードから他のすべてのノードへの最小距離が記録されます。処理の流れは次のとおりです。まず、出力用の行列をグラフのコスト行列（隣接行列）と同じ値で初期化します。その後、すべ

ハフマン符号化（Huffman Coding）は、圧縮後に元のデータを完全に復元できる可逆圧縮（ロスレス圧縮）アルゴリズムの一つです。この手法では、入力された各文字に対して可変長のコードを割り当てます。コードの長さは文字の出現頻度と密接に関係しており、出現頻度の高い文字ほど短いコードが与えられ、出現頻度の低い文字にはより長いコードが割り当てられます。 ハフマン符号化の処理は、大きく分けて次の2つの段階で構成されます。 ハフマン木（Huffman Tree）の構築 木を走査して各文字にコードを割り当てる 具体例として、文字列「YYYZXXYYX」を考えてみましょう。この文字列では、文字Yの

再帰とは何か再帰（recursion）とは、関数が自分自身を呼び出すプロセスのことです。大きな問題をより小さな部分問題に分割して解決するために用いられます。ただし、再帰的アプローチが有効なのは、各部分問題が同じパターンに従っている場合のみであるという点に注意が必要です。ベースケースと再帰ケース再帰関数には、大きく分けて2つの部分が存在します。1つは「ベースケース」、もう1つは「再帰ケース」です。ベースケースは、再帰の処理を終了させるための条件です。ベースケースが定義されていない場合、関数は理論上、無限に再帰を繰り返すことになります。再帰と内部スタックの仕組みコンピュータプログラムでは、ある関数

スタックは「後入れ先出し（LIFO：Last In First Out）」と呼ばれるデータ構造です。最後に格納した要素が最初に取り出されるというシンプルな特性を持ちながら、コンピュータサイエンスのさまざまな場面で重要な役割を果たしています。本記事では、スタックの代表的な応用例を詳しく解説します。スタックの主な応用例1. 式の処理（Expression Handling）中置記法から後置・前置記法への変換私たちが普段目にする数式は、演算子がオペランドの間に置かれる「中置記法（Infix）」で表現されています。スタックを利用すると、この中置記法の式を「後置記法（Postfix）」や「前置記法（Pr

正規化と非正規化とは？データベースの構造を設計・変更するプロセスは、大きく「正規化（Normalization）」と「非正規化（Denormalization）」という2つのアプローチに分けられます。正規化は、データベースから冗長なデータを取り除き、一貫性のある効率的なデータ構造を実現するための手法です。一方、非正規化は、複数のテーブルに分かれたデータをあえて統合し、クエリの実行速度を高めることを目的とした手法です。この記事では、両者の重要な違いを6つの観点からわかりやすく比較して解説します。正規化と非正規化の違い一覧項番比較項目正規化（Normalization）非正規化（Denormali