計算機科学

基礎

計算機科学の導入

計算機科学の歴史と概要

計算機科学（Computer Science; CS）は、情報と計算の理論、ならびにその応用を研究する学問分野です。この分野の歴史は、19世紀のチャールズ・バベッジによる解析機関の設計に遡ります。彼の機械は、現代のコンピュータの祖先と見なされています。その後、20世紀前半にアラン・チューリングがチューリング機械の概念を提案し、計算可能性の理論的基盤を確立しました。

1940年代、エニグマ暗号を解読するために開発された電子計算機「コロッサス」や、1946年に稼働を開始した世界初の汎用電子計算機「ENIAC」などの重要なマイルストーンがありました。1950年代には、プログラム内蔵方式を採用した「EDSAC」や「UNIVAC」が登場し、コンピュータの商業利用が始まりました。

計算機科学はその後急速に発展し、アルゴリズムとデータ構造、プログラミング言語、オペレーティングシステム、ネットワーク、データベース、人工知能など、多岐にわたる分野を包含するようになりました。

計算機科学の主要な分野

計算機科学は非常に広範な学問分野であり、以下のような主要な分野が含まれます。

アルゴリズムとデータ構造

問題解決のための効率的な手法とデータの整理方法を研究します。効率的なアルゴリズムは計算時間を短縮し、効率的なデータ構造はメモリ使用量を最適化します。

プログラミング言語

コンピュータに指示を与えるための言語とその構造を研究します。高級言語（Ruby、Javaなど）から低級言語（アセンブリ言語など）まで、多様なプログラミング言語があります。

ソフトウェア工学

大規模なソフトウェアシステムの設計、開発、保守の方法を研究します。ソフトウェアのライフサイクル全体を対象とし、品質保証やプロジェクト管理も含まれます。

コンピュータアーキテクチャ

コンピュータシステムの内部構造とその動作原理を研究します。CPU、メモリ、I/Oデバイスなどのハードウェアコンポーネントの設計と機能を学びます。

ネットワーク

コンピュータ同士の通信方法とその基盤技術を研究します。インターネットのプロトコル（TCP/IPなど）やネットワークセキュリティも含まれます。

データベース

大量のデータを効率的に格納、検索、管理する方法を研究します。リレーショナルデータベースやSQL、NoSQLデータベースが主要なテーマです。

人工知能（AI）と機械学習（ML）

コンピュータが知能的な行動を取るための方法を研究します。機械学習アルゴリズム、自然言語処理、コンピュータビジョンなどが含まれます。

計算機科学の応用

計算機科学は、多岐にわたる応用分野を持ち、現代社会の多くの領域でその技術が活用されています。以下に主要な応用例を挙げます。

インターネットとウェブ技術

ウェブブラウザ、ウェブアプリケーション、クラウドコンピューティングなど、日常的に利用される技術の基盤となっています。これにより、情報の共有やリソースの分散処理が可能になっています。

データ分析とビッグデータ

大量のデータを収集、分析し、ビジネスや科学研究に役立てます。機械学習や人工知能の手法を用いることで、予測分析やパターン認識が可能になります。

セキュリティ

コンピュータシステムやネットワークの安全性を確保し、不正アクセスやデータ漏洩を防ぐ技術が求められます。暗号化技術や認証プロトコルが重要な役割を果たします。

ゲーム開発

コンピュータグラフィックス、シミュレーション、人工知能などの技術が駆使され、エンターテインメント産業の重要な部分を担っています。リアルタイムレンダリングや物理シミュレーションが主要な技術です。

ロボティクス

自律的に動作するロボットの設計・開発に計算機科学の知識が活用されています。ロボット工学は、センサー技術、制御理論、機械学習など多くの分野と連携しています。

計算機科学は、現代の社会において欠かせない基盤技術を提供する重要な学問分野です。その応用範囲はますます広がり続け、新たな発見とイノベーションを生み出し続けています。

アルゴリズムとデータ構造の基礎

アルゴリズムとは

アルゴリズムは、特定の問題を解決するための一連の手順や計算手法を指します。アルゴリズムは、入力から出力への変換を効率的かつ確実に行うための明確な手順を提供します。例えば、ソートアルゴリズムは無秩序なデータを順序付けられたデータに変換します。

アルゴリズムの設計には以下の要素が重要です。

正確性

アルゴリズムが常に正しい結果を返すこと。

効率性

時間と空間のリソースを最小限に抑えること。

明確性

手順が明確であり、理解しやすいこと。

再利用性

他の問題にも適用可能な汎用的な手順であること。

データ構造の基本

データ構造は、データを効率的に格納、管理、操作するための方式や構造を指します。適切なデータ構造を選択することで、アルゴリズムの性能を大幅に向上させることができます。以下にいくつかの基本的なデータ構造を紹介します。

配列 (Array)

固定サイズの連続したメモリ領域にデータを格納します。各要素はインデックスによってアクセスされます。

リスト (List)

動的にサイズを変更できるデータ構造で、要素の追加や削除が容易です。シングルリンクリスト、ダブルリンクリストなどがあります。

スタック (Stack)

後入れ先出し (LIFO) のデータ構造です。要素の追加と削除は常にスタックのトップで行われます。

キュー (Queue)

先入れ先出し (FIFO) のデータ構造です。要素はキューの末尾に追加され、先頭から削除されます。

ツリー (Tree)

階層的なデータ構造で、各ノードが0個以上の子ノードを持ちます。バイナリツリー、AVLツリー、Bツリーなどが代表的です。

グラフ (Graph)

ノード（頂点）とエッジ（辺）からなるデータ構造です。ネットワークや経路探索などに使用されます。

時間計算量と空間計算量

アルゴリズムの性能を評価するために、時間計算量と空間計算量が用いられます。

時間計算量

アルゴリズムが実行されるのに要する時間の尺度です。入力サイズに対する計算ステップの数で表されます。

空間計算量

アルゴリズムが実行されるのに要するメモリの量の尺度です。入力サイズに対する使用メモリの量で表されます。

これらの計算量は、アルゴリズムの効率性を測るために重要です。効率的なアルゴリズムは、少ない時間と空間で問題を解決します。

ビッグO記法

ビッグO記法は、アルゴリズムの時間計算量と空間計算量を表現するための標準的な方法です。入力サイズが大きくなるときの最悪ケースの計算量を表現します。ビッグO記法の一般的な形式はO(f(n))であり、f(n)は入力サイズnに対する計算ステップの関数です。

以下に、一般的なビッグO記法の例を示します。

O(1)

定数時間。入力サイズに関わらず一定の時間で実行される。

O(n)

線形時間。入力サイズに比例して実行時間が増加する。

O(log n)

対数時間。入力サイズの対数に比例して実行時間が増加する。

O(n^2)

二乗時間。入力サイズの二乗に比例して実行時間が増加する。

O(2^n)

指数時間。入力サイズが増加するごとに実行時間が指数関数的に増加する。

ビッグO記法を理解することで、異なるアルゴリズムの効率性を比較し、適切なアルゴリズムを選択するための基準を得ることができます。

プログラミング基礎

プログラミング言語の概要

プログラミング言語は、コンピュータに対して指示を与えるための形式言語です。これらの言語は、特定の構文とセマンティクスに基づいてプログラムを記述する手段を提供します。プログラミング言語は、一般的に以下のように分類されます。

低水準言語

機械語

コンピュータが直接実行できる命令セット。非常に低レベルで人間には理解しにくい。

アセンブリ言語

機械語に対応するニーモニック（記号）を使用し、低レベルのハードウェア操作を容易にする。

高水準言語

手続き型言語

プログラムを手順や手続きの集合として記述する。例: C、Pascal。

オブジェクト指向言語

データと操作をオブジェクトとしてカプセル化し、再利用性と拡張性を高める。例: Java、Python、C++。

関数型言語

プログラムを数学的関数の集合として記述する。状態や副作用を最小限に抑える。例: Haskell、Lisp。

スクリプト言語

簡易なタスクの自動化や迅速な開発に適している。例: Python、JavaScript、Ruby。

プログラミング言語を選択する際には、プロジェクトの要件、開発チームのスキル、および言語の特性を考慮する必要があります。

基本的なプログラミング構造（変数、データ型、制御構造）

変数

プログラム内でデータを格納するための名前付きの記憶場所です。変数には値を代入したり、変更したり、値を参照することができます。

x = 10
name = "Alice"

データ型

データの種類を示すもので、プログラム内で使用される値の範囲と操作を定義します。一般的なデータ型には以下のものがあります。

整数型 (int)

整数値を表す。

浮動小数点型 (float)

小数点を含む実数値を表す。

文字列型 (string)

文字の列を表す。

ブール型 (bool)

真（True）または偽（False）を表す。

age = 25
price = 19.99
message = "Hello, World!"
is_valid = True

制御構造

プログラムの流れを制御するための構造です。代表的な制御構造には以下のものがあります。

条件分岐 (if, elif, else)

条件に基づいて異なるコードを実行します。

if age >= 18
  puts "あなたは大人です。" 
else
  puts "あなたは未成年者です。" 
end

繰り返し (for, while)

指定された条件が満たされるまでコードを繰り返し実行します。

for i in 1..5 do
  puts i 
end

age = 20
while age < 30
  age += 1
  puts age
end

関数とモジュール

関数

特定のタスクを実行するために再利用可能なコードのブロックです。関数は、入力として引数を受け取り、出力として値を返すことができます。

def greet(name)
  "Hello, #{name}!"
end

message = greet("Alice")
puts message  # Output: Hello, Alice!

関数を使うことで、コードの再利用性が高まり、プログラムの構造が整理されます。

デバッグとテスト

デバッグ

プログラムに含まれるエラー（バグ）を見つけて修正するプロセスです。デバッグには以下のような方法があります。

プリントステートメント

変数の値や実行の流れを出力して確認します。

puts "Debugging message: #{variable}"

デバッガ

ステップ実行やブレークポイントを利用してプログラムの動作を詳細に調査します。

テスト

プログラムが期待通りに動作することを確認するためのプロセスです。テストには以下の種類があります。

ユニットテスト

個々の関数やクラスなど、小さな単位のテストを行います。

統合テスト

複数のモジュールが連携して動作することを確認します。

システムテスト

システム全体が設計通りに動作することを確認します。

テストを行うことで、プログラムの信頼性が向上し、バグの発見と修正が容易になります。テスト駆動開発（TDD）などの手法を取り入れることで、品質の高いソフトウェアを効率的に開発することができます。

データ構造とアルゴリズム

アルゴリズムとは、特定の問題を解決するための手順や計算方法を指します。計算機科学において、アルゴリズムは効率的で正確な計算を行うための基盤となります。本章では、いくつかの主要なアルゴリズム設計技法と解析手法を紹介します。これらの技法は、問題を解決するための基本的なツールとして広く利用されています。

基本データ構造

配列とリスト

配列 (Array)

配列は、同じデータ型の要素を連続したメモリ領域に格納するデータ構造です。各要素はインデックス（整数値）でアクセスされます。配列のサイズは固定であり、宣言時に決定されます。配列の利点は、インデックスを使って素早く任意の要素にアクセスできる点です。

# Rubyの配列
array = [1, 2, 3, 4, 5]
puts array[2]  # Output: 3

リスト (List)

リストは、配列と似ていますが、動的にサイズを変更できるデータ構造です。Rubyの配列は内部的に動的配列として実装されています。リストは異なるデータ型の要素を含むことができます。

# Rubyのリスト
list = [1, "hello", 3.14]
list << 42  # リストの末尾に要素を追加
puts list.inspect  # Output: [1, "hello", 3.14, 42]

スタックとキュー

スタック (Stack)

スタックは、後入れ先出し (LIFO) のデータ構造です。要素の追加（プッシュ）と削除（ポップ）は常にスタックのトップで行われます。スタックは、関数呼び出しの管理や逆ポーランド記法の計算などに使用されます。

stack = []
stack.push(1)  # プッシュ操作
stack.push(2)
puts stack.pop  # ポップ操作、Output: 2

キュー (Queue)

キューは、先入れ先出し (FIFO) のデータ構造です。要素の追加（エンキュー）はキューの末尾で行われ、削除（デキュー）はキューの先頭で行われます。キューは、タスクのスケジューリングや幅優先探索などに使用されます。

queue = []
queue.push(1)  # エンキュー操作
queue.push(2)
puts queue.shift  # デキュー操作、Output: 1

リンクリスト

リンクリスト (Linked List)

リンクリストは、各要素（ノード）が次の要素への参照（ポインタ）を持つデータ構造です。リンクリストは、サイズが動的に変化する場合や頻繁な挿入・削除が必要な場合に有効です。

リンクリストにはいくつかの種類があります： - **シングルリンクリスト (Singly Linked List)**: 各ノードが次のノードへのポインタを持つ。 - **ダブルリンクリスト (Doubly Linked List)**: 各ノードが前後のノードへのポインタを持つ。 - **循環リンクリスト (Circular Linked List)**: 最後のノードが最初のノードへのポインタを持ち、リストが循環する。

class Node
  attr_accessor :data, :next

  def initialize(data)
    @data = data
    @next = nil
  end
end

class SinglyLinkedList
  def initialize
    @head = nil
  end

  def append(data)
    new_node = Node.new(data)
    if @head.nil?
      @head = new_node
      return
    end
    current = @head
    current = current.next while current.next
    current.next = new_node
  end

  def print_list
    current = @head
    while current
      puts current.data
      current = current.next
    end
  end
end

# リストの作成と操作
sll = SinglyLinkedList.new
sll.append(1)
sll.append(2)
sll.append(3)
sll.print_list  # Output: 1 2 3

高度なデータ構造

ツリー（バイナリツリー、AVLツリー、Bツリー）

バイナリツリー (Binary Tree)

バイナリツリーは、各ノードが最大2つの子ノード（左子ノードと右子ノード）を持つツリーです。

class Node
  attr_accessor :value, :left, :right

  def initialize(value)
    @value = value
    @left = nil
    @right = nil
  end
end

class BinaryTree
  def initialize(value)
    @root = Node.new(value)
  end

  def add_node(value, current = @root)
    if value < current.value
      current.left.nil? ? current.left = Node.new(value) : add_node(value, current.left)
    else
      current.right.nil? ? current.right = Node.new(value) : add_node(value, current.right)
    end
  end

  def in_order_traversal(node = @root, &block)
    return if node.nil?
    in_order_traversal(node.left, &block)
    yield node
    in_order_traversal(node.right, &block)
  end
end

# バイナリツリーの使用例
bt = BinaryTree.new(10)
bt.add_node(5)
bt.add_node(15)
bt.add_node(3)
bt.in_order_traversal { |node| puts node.value }  # Output: 3 5 10 15

グラフ（無向グラフ、有向グラフ）

無向グラフ (Undirected Graph)

無向グラフでは、エッジは両方向に通行可能です。

class Graph
  def initialize
    @adj_list = {}
  end

  def add_edge(v1, v2)
    @adj_list[v1] ||= []
    @adj_list[v1] << v2
    @adj_list[v2] ||= []
    @adj_list[v2] << v1
  end

  def display
    @adj_list.each do |vertex, edges|
      puts "#{vertex}: #{edges.join(', ')}"
    end
  end
end

# 無向グラフの使用例
graph = Graph.new
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'C')
graph.display
# Output:
# A: B, C
# B: A, C
# C: A, B

有向グラフ (Directed Graph)

有向グラフでは、エッジは一方向にのみ通行可能です。

class DirectedGraph
  def initialize
    @adj_list = {}
  end

  def add_edge(v1, v2)
    @adj_list[v1] ||= []
    @adj_list[v1] << v2
  end

  def display
    @adj_list.each do |vertex, edges|
      puts "#{vertex} -> #{edges.join(', ')}"
    end
  end
end

# 有向グラフの使用例
dgraph = DirectedGraph.new
dgraph.add_edge('A', 'B')
dgraph.add_edge('A', 'C')
dgraph.add_edge('B', 'C')
dgraph.display
# Output:
# A -> B, C
# B -> C
# C ->

ハッシュテーブル

ハッシュテーブル (Hash Table)

ハッシュテーブルは、キーと値のペアを効率的に格納するデータ構造です。ハッシュ関数を使用してキーをハッシュ値に変換し、そのハッシュ値を使用して値を格納する場所を決定します。ハッシュテーブルは平均して O(1) の時間で挿入、削除、および検索操作を行うことができます。

class HashTable
  def initialize(size)
    @size = size
    @buckets = Array.new(size)
  end

  def hash(key)
    key.sum % @size
  end

  def set(key, value)
    index = hash(key)
    @buckets[index] ||= []
    @buckets[index] << [key, value]
  end

  def get(key)
    index = hash(key)
    bucket = @buckets[index]
    return nil unless bucket

    bucket.each do |k, v|
      return v if k == key
    end
    nil
  end

  def display
    @buckets.each_with_index do |bucket, index|
      next unless bucket
      bucket.each do |key, value|
        puts "Bucket #{index}: #{key} => #{value}"
      end
    end
  end
end

# ハッシュテーブルの使用例
hash_table = HashTable.new(10)
hash_table.set("name", "Alice")
hash_table.set("age", 30)
puts hash_table.get("name")  # Output: Alice
puts hash_table.get

("age")   # Output: 30
hash_table.display
# Output:
# Bucket 0: name => Alice
# Bucket 4: age => 30

---

この章では、基本的なデータ構造と高度なデータ構造について学びました。次の章では、これらのデータ構造を利用したアルゴリズムの設計と解析について詳しく見ていきます。

高度なデータ構造

ツリー（バイナリツリー、AVLツリー、Bツリー）

ツリー (Tree)

ツリーは階層的なデータ構造であり、根 (root) から始まり、子ノード (child node) が分岐していく構造です。各ノードは0個以上の子ノードを持ちます。

バイナリツリー (Binary Tree)

バイナリツリーは、各ノードが最大2つの子ノード（左子ノードと右子ノード）を持つツリーです。

class Node
  attr_accessor :value, :left, :right

  def initialize(value)
    @value = value
    @left = nil
    @right = nil
  end
end

class BinaryTree
  attr_accessor :root

  def initialize(value)
    @root = Node.new(value)
  end

  def add_node(value, current = @root)
    if value < current.value
      current.left.nil? ? current.left = Node.new(value) : add_node(value, current.left)
    else
      current.right.nil? ? current.right = Node.new(value) : add_node(value, current.right)
    end
  end

  def in_order_traversal(node = @root, &block)
    return if node.nil?
    in_order_traversal(node.left, &block)
    yield node
    in_order_traversal(node.right, &block)
  end
end

# バイナリツリーの使用例
bt = BinaryTree.new(10)
bt.add_node(5)
bt.add_node(15)
bt.add_node(3)
bt.in_order_traversal { |node| puts node.value }  # Output: 3 5 10 15

AVLツリー (AVL Tree)

AVLツリーは、自己平衡二分探索木です。挿入や削除の際に自動的にバランスを保ちます。各ノードの左部分木と右部分木の高さの差（バランス因子）が-1, 0, 1の範囲内に収まるようにします。

Bツリー (B-Tree)

Bツリーは、自己平衡の多分木であり、データベースやファイルシステムで使用されます。各ノードは複数の子ノードを持ち、データの挿入、削除、検索の効率性を向上させます。Bツリーの実装は複雑であり、ここでは概念のみを紹介します。

グラフ（無向グラフ、有向グラフ）

グラフ (Graph)

グラフは、ノード（頂点）とそれらを結ぶエッジ（辺）から構成されるデータ構造です。グラフには無向グラフと有向グラフがあります。

無向グラフ (Undirected Graph)

無向グラフでは、エッジは両方向に通行可能です。

class Graph
  def initialize
    @adj_list = {}
  end

  def add_edge(v1, v2)
    @adj_list[v1] ||= []
    @adj_list[v1] << v2
    @adj_list[v2] ||= []
    @adj_list[v2] << v1
  end

  def display
    @adj_list.each do |vertex, edges|
      puts "#{vertex}: #{edges.join(', ')}"
    end
  end
end

# 無向グラフの使用例
graph = Graph.new
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'C')
graph.display
# Output:
# A: B, C
# B: A, C
# C: A, B

有向グラフ (Directed Graph)

有向グラフでは、エッジは一方向にのみ通行可能です。

class DirectedGraph
  def initialize
    @adj_list = {}
  end

  def add_edge(v1, v2)
    @adj_list[v1] ||= []
    @adj_list[v1] << v2
  end

  def display
    @adj_list.each do |vertex, edges|
      puts "#{vertex} -> #{edges.join(', ')}"
    end
  end
end

# 有向グラフの使用例
dgraph = DirectedGraph.new
dgraph.add_edge('A', 'B')
dgraph.add_edge('A', 'C')
dgraph.add_edge('B', 'C')
dgraph.display
# Output:
# A -> B, C
# B -> C
# C ->

ハッシュテーブル

ハッシュテーブル (Hash Table)

ハッシュテーブルは、キーと値のペアを効率的に格納するデータ構造です。ハッシュ関数を使用してキーをハッシュ値に変換し、そのハッシュ値を使用して値を格納する場所を決定します。ハッシュテーブルは平均して O(1) の時間で挿入、削除、および検索操作を行うことができます。

class HashTable
  def initialize(size)
    @size = size
    @buckets = Array.new(size)
  end

  def hash(key)
    key.sum % @size
  end

  def set(key, value)
    index = hash(key)
    @buckets[index] ||= []
    @buckets[index] << [key, value]
  end

  def get(key)
    index = hash(key)
    bucket = @buckets[index]
    return nil unless bucket

    bucket.each do |k, v|
      return v if k == key
    end
    nil
  end

  def display
    @buckets.each_with_index do |bucket, index|
      next unless bucket
      bucket.each do |key, value|
        puts "Bucket #{index}: #{key} => #{value}"
      end
    end
  end
end

# ハッシュテーブルの使用例
hash_table = HashTable.new(10)
hash_table.set("name", "Alice")
hash_table.set("age", 30)
puts hash_table.get("name")  # Output: Alice
puts hash_table.get("age")   # Output: 30
hash_table.display
# Output:
# Bucket 7: name => Alice
# Bucket 3: age => 30

アルゴリズム設計と解析

ソートアルゴリズム（クイックソート、マージソート、ヒープソート）

クイックソート (Quicksort)

クイックソートは、分割統治法に基づく効率的なソートアルゴリズムです。リストを基準点（ピボット）で分割し、左右の部分リストを再帰的にソートします。

def quicksort(arr)
  return arr if arr.length <= 1

  pivot = arr[arr.length / 2]
  left = arr.select { |x| x < pivot }
  middle = arr.select { |x| x == pivot }
  right = arr.select { |x| x > pivot }

  quicksort(left) + middle + quicksort(right)
end

arr = [3, 6, 8, 10, 1, 2, 1]
puts quicksort(arr).inspect  # Output: [1, 1, 2, 3, 6, 8, 10]

マージソート (Merge Sort)

マージソートも分割統治法に基づくソートアルゴリズムで、リストを半分に分割し、それぞれを再帰的にソートした後、マージします。

def mergesort(arr)
  return arr if arr.length <= 1

  mid = arr.length / 2
  left = mergesort(arr.slice(0, mid))
  right = mergesort(arr.slice(mid, arr.length - mid))

  merge(left, right)
end

def merge(left, right)
  result = []
  until left.empty? || right.empty?
    result << (left.first <= right.first ? left.shift : right.shift)
  end
  result + left + right
end

arr = [3, 6, 8, 10, 1, 2, 1]
puts mergesort(arr).inspect  # Output: [1, 1, 2, 3, 6, 8, 10]

ヒープソート (Heap Sort)

ヒープソートは、ヒープデータ構造を利用してリストをソートするアルゴリズムです。

def heapsort(arr)
  n = arr.length

  (n / 2 - 1).downto(0) { |i| heapify(arr, n, i) }

  (n - 1).downto(1) do |i|
    arr[0], arr[i] = arr[i], arr[0]
    heapify(arr, i, 0)
  end

  arr
end

def heapify(arr, n, i)
  largest = i
  left = 2 * i + 1
  right = 2 * i + 2

  largest = left if left < n && arr[left] > arr[largest]
  largest = right if right < n && arr[right] > arr[largest]

  if largest != i
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, n, largest)
  end
end

arr = [3, 6, 8, 10, 1, 2, 1]
puts heapsort(arr).inspect  # Output: [1, 1, 2, 3, 6, 8, 10]

検索アルゴリズム（二分探索、深さ優先探索、幅優先探索）

二分探索 (Binary Search)

二分探索は、ソートされたリスト内で指定された値を探す効率的なアルゴリズムです。

def binary_search(arr, target)
  left, right = 0, arr.length - 1

  while left <= right
    mid = (left + right) / 2
    if arr[mid] == target
      return mid
    elsif arr[mid] < target
      left = mid + 1
    else
      right = mid - 1
    end
  end

  -1
end

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
puts binary_search(arr, 6)  # Output: 5

深さ優先探索 (Depth-First Search)

深さ優先探索は、グラフやツリーの探索アルゴリズムで、まず可能な限り深く探索します。

class Graph
  def initialize
    @adj_list = {}
  end

  def add_edge(v1, v2)
    @adj_list[v1] ||= []
    @adj_list[v1] << v2
  end

  def dfs(start, visited = {})
    return if visited[start]
    puts start
    visited[start] = true
    @adj_list[start]&.each { |neighbor| dfs(neighbor, visited) }
  end
end

# グラフの使用例
graph = Graph.new
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'D')
graph.add_edge('C', 'E')
graph.dfs('A')
# Output:
# A
# B
# D
# C
# E

幅優先探索 (Breadth-First Search)

幅優先探索は、グラフやツリーの探索アルゴリズムで、まず隣接ノードをすべて探索します。

class Graph
  def initialize
    @adj_list = {}
  end

  def add_edge(v1, v2)
    @adj_list[v1] ||= []
    @adj_list[v1] << v2
  end

  def bfs(start)
    queue = [start]
    visited = { start => true }

    until queue.empty?
      vertex = queue.shift
      puts vertex
      @adj_list[vertex]&.each do |neighbor|
        unless visited[neighbor]
          queue << neighbor
          visited[neighbor] = true
        end
      end
    end
  end
end

# グラフの使用例
graph = Graph.new
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'D')
graph.add_edge('C', 'E')
graph.bfs('A')
# Output:
# A
# B
# C
# D
# E

動的計画法 (Dynamic Programming)

動的計画法は、部分問題の結果を再利用して効率的に問題を解決する手法です。典型的な例として、フィボナッチ数列があります。

def fib(n, memo = {})
  return n if n <= 1
  memo[n] ||= fib(n - 1, memo) + fib(n - 2, memo)
end

puts fib(10)  # Output: 55

貪欲法 (Greedy Algorithm)

貪欲法は、局所的に最適な選択を繰り返し行うことで全体の最適解を目指す手法です。例として、コイン問題があります。

def coin_change(coins, amount)
  coins.sort.reverse.each_with_object([]) do |coin, result|
    while amount >= coin
      amount -= coin
      result << coin
    end
    return result if amount == 0
  end
end

coins = [1, 5, 10, 25]
amount = 63
puts coin_change(coins, amount).inspect  # Output: [25, 25, 10, 1, 1, 1]

附録

• 数学の基礎（離散数学、線形代数、確率と統計）
• 追加のリソースと参考文献
• 練習問題と解答