プログラミング

process Burst time A 4 B 1 C 8 D 1 タイムスライス=10単位 A B C D A C C C 0 2 3 5 6 8 10 12 14 したがって、Aは8サイクルを完了します。

リストを並べ替えるときに、バイナリ検索手法を使用してリスト上のアイテムを見つけることができます。この手順では、リスト全体が2つのサブリストに分割されます。アイテムが中央の位置にある場合は場所を返します。それ以外の場合は、左または右のサブリストにジャンプし、アイテムが見つかるか範囲を超えるまで同じプロセスを繰り返します。 二分探索手法の複雑さ 時間計算量 ： 最良の場合はO（1）。平均または最悪の場合はO（log2 n）。 スペースの複雑さ： O（1） 入力と出力 Input:  A sorted list of data: 12 25 48 52 67 79 88 93 The

指数検索は、ダブリング検索またはギャロッピング検索とも呼ばれます。このメカニズムは、検索キーが存在する可能性のある範囲を見つけるために使用されます。 LとUがリストの上限と下限である場合、LとUは両方とも2の累乗です。最後のセクションでは、Uはリストの最後の位置です。そのため、指数関数として知られています。 特定の範囲を見つけた後、二分探索手法を使用して検索キーの正確な位置を見つけます。 指数検索手法の複雑さ 時間計算量： 最良の場合はO（1）。平均または最悪の場合のO（log2 i）。ここで、iは検索キーが存在する場所です。 スペースの複雑さ： O（1） 入力と出力 Input:

二分探索手法では、リストは均等に分割されます。補間検索手法の場合、プロシージャは補間式を使用して正確な位置を見つけようとします。推定位置を見つけた後、その位置を使用してリストを分離できます。毎回正確な位置を見つけようとするため、検索時間が短縮されます。この手法では、アイテムが均一に分散されている場合、アイテムを簡単に見つけることができます。 補間検索手法の複雑さ 時間計算量： 平均的な場合はO（log2（log2 n））、最悪の場合（アイテムが指数関数的に分散されている場合）はO（n） スペースの複雑さ： O（1） 入力と出力 Input: A sorted list of data:

ジャンプ検索手法は順序付きリストでも機能します。ブロックを作成し、そのブロック内の要素を見つけようとします。アイテムがブロック内にない場合は、ブロック全体がシフトされます。ブロックサイズは、リストのサイズに基づいています。リストのサイズがnの場合、ブロックサイズは√nになります。正しいブロックを見つけた後、線形検索手法を使用してアイテムを見つけます。ジャンプ検索は、そのパフォーマンスに応じて、線形検索とバイナリ検索の間にあります。 ジャンプ検索手法の複雑さ 時間計算量：O（√n） スペースの複雑さ：O（1） 入力と出力 Input: A sorted list of data: 10 13

線形探索手法は最も単純な手法です。この手法では、アイテムを1つずつ検索します。この手順は、ソートされていないデータセットにも適用できます。線形検索は、順次検索とも呼ばれます。時間計算量がnO（n）のオーダーであるため、線形と呼ばれます。 線形探索手法の複雑さ 時間計算量： O（n） スペースの複雑さ： O（1） 入力と出力 Input: A list of data: 20 4 89 75 10 23 45 69 the search key 10 Output: Item found at location: 4 アルゴリズム linearSearch(array, size, ke

二分探索と同様に、リストもサブリストに分割されます。この手順では、2つの中間値を使用してリストを3つの部分に分割します。リストがより多くのサブディビジョンに分割されるため、キー値を検索する時間が短縮されます。 三元検索手法の複雑さ 時間計算量：O（log3 n） スペースの複雑さ：O（1） 入力と出力 Input: A sorted list of data: 12 25 48 52 67 79 88 93 The search key 52 Output: Item found at location: 3 アルゴリズム ternarySearch(array, start, end,

バブルソートは、比較ベースのソートアルゴリズムです。このアルゴリズムでは、隣接する要素が比較および交換されて、正しいシーケンスが作成されます。このアルゴリズムは他のアルゴリズムよりも単純ですが、いくつかの欠点もあります。このアルゴリズムは、多数のデータセットには適していません。並べ替えタスクの解決には時間がかかります。 バブルソート手法の複雑さ 時間計算量： 最良の場合はO（n）、平均および最悪の場合はO（n ^ 2） スペースの複雑さ： O（1） 入力と出力 Input: A list of unsorted data: 56 98 78 12 30 51 Output: Array

非永続的CSMAは、メディアアクセス制御（MAC）層で動作するCarrier Sense Multiple Access（CMSA）プロトコルの非アグレッシブバージョンです。 CMSAプロトコルを使用して、複数のユーザーまたはノードが、複数のノードを接続する単一のケーブルまたは光ファイバー、あるいはワイヤレススペクトルの一部である共有メディアを介してデータを送受信します。 非永続的CSMAでは、送信ステーションに送信するフレームがあり、ビジーチャネルを検出すると、その間にチャネルを検出せずにランダムな時間待機し、アルゴリズムを再度繰り返します。 アルゴリズム 非永続的CMSAのアルゴリズム

1-persistent CSMAは、メディアアクセス制御（MAC）層で動作するCarrier Sense Multiple Access（CMSA）プロトコルのアグレッシブバージョンです。 CMSAプロトコルを使用して、複数のユーザーまたはノードが、複数のノードを接続する単一のケーブルまたは光ファイバー、あるいはワイヤレススペクトルの一部である共有メディアを介してデータを送受信します。 1パーシステントCSMAでは、送信ステーションに送信するフレームがあり、ビジーチャネルを検知すると、送信の終了を待ってすぐに送信します。確率1で送信するため、名前1 –永続的なCSMAが与えられます。 イ

P-persistent CSMAは、1-persistentCMSAとnon-persistentCMSAの利点を組み合わせたCarrierSense Multiple Access（CMSA）プロトコルのアプローチです。 CMSAプロトコルを使用して、複数のユーザーまたはノードが、複数のノードを接続する単一のケーブルまたは光ファイバー、あるいはワイヤレススペクトルの一部である共有メディアを介してデータを送受信します。 p-persistent CSMAでは、送信ステーションに送信するフレームがあり、ビジーチャネルを検知すると、送信の終了を待ってから、確率pで送信します。確率pで送信するた

衝突検出を備えたCarrierSenseMultiple Access（CSMA / CD）は、メディアアクセス制御（MAC）層で動作するキャリア伝送用のネットワークプロトコルです。送信用の共有チャネルがビジーであるかどうかを検知またはリッスンし、チャネルが解放されるまで送信を延期します。衝突検出技術は、他のステーションからの送信を検知することで衝突を検出します。衝突を検出すると、ステーションは送信を停止し、ジャム信号を送信してから、ランダムな時間間隔で待機してから再送信します。 アルゴリズム CSMA/CDのアルゴリズムは次のとおりです。 フレームの準備ができると、送信ステーションは

衝突回避を伴うキャリアセンスマルチアクセス（CSMA / CA）は、メディアアクセス制御（MAC）層で動作するキャリア伝送用のネットワークプロトコルです。発生後の衝突を処理するCSMA/CD（Carrier Sense Multiple Access / Collision Detection）とは対照的に、CSMA/CAは発生前の衝突を防ぎます。 アルゴリズム CSMA/CAのアルゴリズムは次のとおりです。 フレームの準備ができると、送信ステーションはチャネルがアイドル状態かビジー状態かをチェックします。 チャネルがビジーの場合、ステーションはチャネルがアイドル状態になるまで待

データ型は基本的に、さまざまなコンピュータプログラムで使用できるデータの種類です。これは、整数、浮動小数点数などのタイプを意味します。整数などのスペースは4バイト、文字は1バイトのスペースなどを使用します。 抽象データ型は特殊な種類のデータ型であり、その動作は一連の値と一連の操作によって定義されます。これらのデータ型を使用できるため、キーワード「Abstract」が使用され、さまざまな操作を実行できます。しかし、これらの操作がどのように機能しているかは、ユーザーには完全に隠されています。 ADTはプリミティブデータ型で構成されていますが、操作ロジックは非表示になっています。 ADTの例とし

スタックは後入れ先出しのデータ構造です。スタックは、式、呼び出し、再帰戦略などを評価するためにさまざまな領域で使用されます。スタックには、いくつかの基本的な操作があります。ここでは、これらのスタックの操作と、スタックADTを使用した1つの例を示します。 ADT（抽象データ型）は特殊な種類のデータ型であり、その動作は一連の値と一連の操作によって定義されます。これらのデータ型を使用できるため、キーワード「Abstract」が使用され、さまざまな操作を実行できます。しかし、これらの操作がどのように機能しているかは、ユーザーには完全に隠されています。 ADTはプリミティブデータ型で構成されていますが

ここでは、末尾再帰とは何かを確認します。末尾再帰は基本的に、関数の最後のステートメントとして再帰関数を使用しています。したがって、再帰呼び出しから戻った後に何もすることが残っていない場合、それは末尾再帰と呼ばれます。末尾再帰の一例を見ていきます。 例 #include <iostream> using namespace std; void printN(int n){    if(n < 0){       return;    }    cout << n <<

キューは先入れ先出しデータ構造です。キューは、グラフ走査アルゴリズムの幅優先探索などのさまざまな領域で使用されます。キューには、いくつかの基本的な操作があります。ここでは、これらのキューの操作と、キューADTを使用した1つの例を示します。 ADT（抽象データ型）は特殊な種類のデータ型であり、その動作は一連の値と一連の操作によって定義されます。これらのデータ型を使用できるため、キーワード「Abstract」が使用され、さまざまな操作を実行できます。しかし、これらの操作がどのように機能しているかは、ユーザーには完全に隠されています。 ADTはプリミティブデータ型で構成されていますが、操作ロジック

ステップカウント法は、アルゴリズムを分析する方法の1つです。この方法では、1つの命令が実行されている回数をカウントします。そこから、アルゴリズムの複雑さを見つけようとします。 シーケンシャル検索を実行するアルゴリズムが1つあるとします。各命令がc1、c2、…を取ると仮定します。実行に時間がかかる場合は、このアルゴリズムの時間計算量を調べます アルゴリズム 回数 コスト seqSearch（arr、n、key） i：=0 i

このセクションでは、2つの行列を乗算する方法を説明します。行列の乗算は、この条件を満たす場合にのみ実行できます。 2つの行列がAとBであり、それらの次元がA（m x n）とB（p x q）であるとすると、結果の行列は、n=pの場合にのみ見つけることができます。その場合、結果の行列Cの次数は（m x q）になります。 アルゴリズム matrixMultiply(A, B): Assume dimension of A is (m x n), dimension of B is (p x q) Begin    if n is not same as p, then exit

償却分析 この分析は、時折の操作が非常に遅い場合に使用されますが、非常に頻繁に実行される操作のほとんどは高速です。データ構造では、ハッシュテーブル、互いに素なセットなどの償却分析が必要です。 ハッシュテーブルでは、ほとんどの場合、検索時間の複雑さはO（1）ですが、O（n）操作を実行することもあります。ほとんどの場合、ハッシュテーブルで要素を検索または挿入する場合、タスクは一定時間かかりますが、衝突が発生すると、衝突を解決するためにO（n）回の操作が必要になります。 集計方法 総コストを見つけるために集計方法が使用されます。大量のデータを追加する場合は、この式で償却原価を見つける必要があり