DAA-はじめに

アルゴリズムは、計算、データ処理、および自動推論タスクを実行する問題を解決する一連の操作ステップです。アルゴリズムは、有限の時間と空間内で表現できる効率的な方法です。

アルゴリズムは、特定の問題の解決策を非常にシンプルかつ効率的な方法で表すための最良の方法です。特定の問題に対するアルゴリズムがある場合、任意のプログラミング言語でアルゴリズムを実装できます。つまり、*アルゴリズムはどのプログラミング言語*からも独立しています。

アルゴリズム設計

アルゴリズム設計の重要な側面には、最小の時間とスペースを使用して効率的な方法で問題を解決するための効率的なアルゴリズムの作成が含まれます。

問題を解決するには、さまざまなアプローチに従うことができます。そのうちのいくつかは、時間の消費に関して効率的である場合がありますが、他のアプローチはメモリ効率が良い場合があります。ただし、時間消費とメモリ使用量の両方を同時に最適化することはできないことに注意してください。アルゴリズムをより短い時間で実行する必要がある場合、より多くのメモリに投資する必要があり、アルゴリズムをより少ないメモリで実行する必要がある場合、より多くの時間を必要とします。

問題開発手順

計算上の問題を解決するには、次の手順が必要です。

問題の定義
モデルの開発
アルゴリズムの仕様
アルゴリズムの設計
アルゴリズムの正当性を確認する
アルゴリズムの分析
アルゴリズムの実装
プログラムのテスト
ドキュメンテーション

アルゴリズムの特徴

アルゴリズムの主な特徴は次のとおりです-

アルゴリズムには一意の名前が必要です
アルゴリズムには、入力と出力のセットが明示的に定義されている必要があります
アルゴリズムは明確な操作で整然としています
アルゴリズムは有限時間で停止します。アルゴリズムは無限に実行しないでください。つまり、ある時点でアルゴリズムを終了する必要があります。

疑似コード

擬似コードは、プレーンテキストに関連するあいまいさを伴わずに、特定のプログラミング言語の構文を知る必要なしに、アルゴリズムの高レベルの説明を提供します。

実行時間は、Pseudocodeを使用してアルゴリズムを基本的な操作のセットとして表現することにより、より一般的な方法で推定できます。

アルゴリズムと擬似コードの違い

アルゴリズムは、特定のタスクを実行するためにチューリング完全なコンピューターマシンによって実行されるプロセスを記述する特定の特性を備えた正式な定義です。一般的に、「アルゴリズム」という言葉は、コンピューターサイエンスの高度なタスクを表すために使用できます。

一方、擬似コードは、多くの詳細な情報を残した、アルゴリズムの非公式で（多くの場合、初歩的な）人間が読める記述です。擬似コードの記述にはスタイルの制限はなく、その唯一の目的は、アルゴリズムの高レベルのステップを自然言語で非常に現実的な方法で記述することです。

たとえば、挿入ソートのアルゴリズムは次のとおりです。

Algorithm: Insertion-Sort
Input: A list L of integers of length n
Output: A sorted list L1 containing those integers present in L
Step 1: Keep a sorted list L1 which starts off empty
Step 2: Perform Step 3 for each element in the original list L
Step 3: Insert it into the correct position in the sorted list L1.
Step 4: Return the sorted list
Step 5: Stop

アルゴリズムInsertion-Sortで前述した高レベルの抽象プロセスをより現実的な方法で記述する方法を説明する擬似コードを次に示します。

for i <- 1 to length(A)
   x <- A[i]
   j <- i
   while j > 0 and A[j-1] > x
      A[j] <- A[j-1]
      j <- j - 1
   A[j] <- x

このチュートリアルでは、アルゴリズムはC、C ++、Java、Python、およびその他のプログラミング言語に多くの点で似ている擬似コードの形式で提示されます。

Design-and-analysis-of-algorithms-introduction

目次