通信に関する理論/stackとqueue,木構造,2分探索木

通信の方式

  • 単向式:一方通行(ex. テレビ)
  • 半二重方式:両方向だが同時は不可(ex. トランシーバー)
  • 全二重方式:両方向で同時もOK
多重化方式

高速回線を同時に複数人で利用できるようにした技術。

  • FDM(周波数)
  • TDM(時間)
  • CDM(コード)
同期方式
  • 調歩(低速):スタートビット0、ストップビット1を付けて送る
  • SYN(中速)
  • フレーム(高速):フレーム単位で送信する。フラグパターンを付けられる。

パリティチェック:送信するビットデータの中に、パリティビットを付ける。途中で数がずれていたら、誤りがあると判断できる。

パリティチェックCRC誤り検出のみ、ハミング符号誤り検出と訂正もできる。

回線速度

回線速度(bps):1sあたりに伝送できるbitの数

↓ いずれの計算も、単位を合わせるのがポイント

回線使用率

=実際の伝送データ量(ビット/秒)÷伝送可能な最大データ量(ビット/秒)

データ伝送時間

=伝送データ量(ビット)÷{(データ伝送速度⋇回戦使用率)}

データ構造,木構造

  • stack:後からPUSHしたものを先にPOPする
  • queue:先にPUSHしたものを先にPOPする
木構造

データ最上位から根(ルート)、枝(ブランチ)、節(ノード)。それ以上枝分かれしないデータを葉(リーフ)。上下関係は親子関係になっている。そのデータより上は親、下は子になる。

枝がm本なら、ノードは(m-1)本。

2分木:ノードから出ている枝が2本以下

完全2分木:木の高さが同じ(もしくは1段違い)。

2分探索木:親の左の子は親より小さく、親の右の子は親より大きくなるように配置。