インターネットスクール 『まなぶ』のe-ラーニングへ  yahoo  MSN  エキサイト  Google
辞書先頭ページへ戻る

ツから始まる情報処理用語

00000104    通信情報網
00000714    通信モデル
00000437    ツリー
104:通信情報網       ＬＡＮ・WANに関してのグループ先頭へ    このページ先頭へ移動    辞典の先頭へ


または、通信回線網、単に回線（circuit）と読んだりする。

通信方式は、
専用線サービス
電話交換サービス
回線交換サービス
パケット交換サービス
ISDN
に分類される。

回線交換方式は、あるノード間の接続中は、この中継回線が独占されるため、この中継している回線を別のノード間通信に使えない。
しかし、独占しているので高いトラフィック（密度の多い）通信が行える。対してパケット交換の場合は、情報をパケット単位に分割し、回線を独占することはない。
714:通信モデル       情報理論のグループ先頭へ    このページ先頭へ移動    辞典の先頭へ
シャノン通信モデル

図1


シャノンは、この通信モデルによって、情報の伝達量に対して、初めて定量的な尺度を導入しました。
437:ツリー       データ構造のグループ先頭へ    このページ先頭へ移動    辞典の先頭へ
tree 木構造
木(tree)：節点（node)と辺（枝，edge)の集合を言う。
図1


○を節点（node）や、頂点(vertex)と呼び、名前を付けたり，色々な情報や意味を持たせられる。
そして、最上位置の節点を根（root）と呼ぶ。

そして、接点との節点を結ぶもの（関係）を辺や枝（edge）と呼ぶ。
なお、異なる隣り合う節点の並びを辺で結んだものを経路（道，path）と呼ぶ。

木の名前として、順序木、2分木、2分探索木、平衡木、完全２分木、B‐木、1-2-3木、解析木、多分木などが挙げられる。

順序木 　　　　　節が複数の子を持っていて、子の間に順序がある木
多分木 　　　　　順序木において，どの非終端点も一定個数の子をもつ木
２分木 　 　　　　節の子の数が２つ以下の順序木
完全にバランスした木　　どの節点においても、その左部分木と右部分木のレベルの差は１以下（多分木でも使う表現）
AVL木 　　　　各節点に着目して、『その左右の子の部分木の深さの差が１以内』と言う条件を全ての節点で満足している二分木（高さがバランスした二分木、平衡木とも言う。完全にバランスした木はAVL木であるが、逆は成立しない）
完全二分木 　全ての葉の深さが同じ深さ
B木　 　　　　　葉までの深さがすべて等しい多分木



その他に次の用語が使われる

親（parent） 　　　　　　　根以外の節点は，上に丁度1つだけの節点があるが，相対的に上の節点をこう呼ぶ。
子(child) 　　　　　　　節点に対して，直接下の節点
祖先 　　　　　　　自分および上にある節点
子孫 　　　　　　　自分および下にある節点
兄弟 　　　　　　　同じ親をもつ自分以外の節点
葉(leaf) 　　　　　　　子の無い節点（別名：終端点、外部節点（external node)）
非終端点 　　　　　　　少なくとも1つ子のある節点
内部節点（internal node)　非終端点
部分木（subtree)　　　　　　木の節点とその子孫からなる木
森（forest) 　　　　　　木の集合、木を分解すると森が出来る
節点のレベル(level) 　根からその節点に至る辺の数
木の高さ(height) 　木の節点のレベルの中で根から最も遠い節点までの辺の数
木の道長（path length) 　木の節点のレベルの総和


全ての節点を系統的に訪れる方法は、節点を訪れる順序に従って以下のように分類できる。

先行順(preorder)　　　　　　　　　　　　　　　根に訪れ，次に左の部分木に訪れ，そして右の部分木に訪れる。
中央順(inorder) 　　　　　　　　　　　　　　　左部分木に訪れ，次に根に訪れ，そして右部分木に訪れる。別名：対称順(symmetric-order)
後行順(postorder)　　　　　　　　　　　　　　左部分木に訪れ，次に右部分木に訪れ，そして根に訪れる。
レベル順走査(level-order,breadth-first)　同一レベル内の操作。


グラフ理論で説明すると、根（root)とそれ以外の節点の間に、1つだけ道のあるもが木と言える。