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

通信の方式

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

[memo title=”多重化方式”]

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

  • FDM(周波数)
  • TDM(時間)
  • CDM(コード)

[/memo]

[memo title=”同期方式”]

  • 調歩(低速):スタートビット0、ストップビット1を付けて送る
  • SYN(中速)
  • フレーム(高速):フレーム単位で送信する。フラグパターンを付けられる。

[/memo]

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

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

回線速度

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

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

[memo title=”回線使用率”]

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

[/memo]

[memo title=”データ伝送時間”]

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

[/memo]

データ構造,木構造

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

[box class=”box26″ title=”木構造”]

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

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

[/box]

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

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

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