サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
体力トレーニング
www.th.cs.meiji.ac.jp
AST ASTとは"Abstract Syntax Tree"の略で抽象構文木と呼ばれるものです。 計算機科学における木の一種でプログラミングの文法や計算式を木にしたものです。 これは式 "Z = X + Y;"をASTにしてみたものです。 まず初めに”Expression Statement”その子として"Assignment"がある。 Assignmentは子に"Z"と"+"を持ち、"+"はさらに子として"X"と"Y"を持つ。 これらの木から"Z=X+Y"を復元するには、頂点から頂点に戻るとき(returnするとき)に内容を取っていけば逆ポーランド記法として復元できる。 注意としてこの場合は左優先、深さ優先で潜ります。 この例題で探索してみると Expression StatementからAssignmentに移動する。 AssignmentからSimple Name(Z)に移動する。
ヒープソートとは? ヒープソートの考え方は、まず、データをヒープ構造にし、完成したらデータの先頭の値を取り出す。そしてまたヒープ構造を作り・・・という繰り返しである。 ここでヒープ構造とは、簡単に言うと、2分木の各節点にデータを保持し、親のデータが2つの子のデータよりも大きくなるように作られたデータ構造である。 つまり、これから分かることは全てのデータの中で2分木の「根」、すなわちデータの先頭に最大値を持つデータが必ず存在する。という事である。 考え方 配列N[]に次のようなデータが格納されているとする。 これを2分木で表現すると、 上図のようになる。 ヒープソートを行うには、まず、この配列(2分木)をヒープ構造にする必要がある。ヒープ構造の特徴は先にも述べた通り、次のようなものである。 二分木の根には必ず最大値がくる。 親子関係、すなわちN[a]・N[2a+1]・N[2a+2]の 値を
Ck:要素数kの頻出アイテム集合の候補の集合 Lk:要素数kの頻出アイテム集合の集合 minsupは最小サポートを満たすために必要なトランザクション数 - 最小サポートにトランザクションの総数|D|を乗じた値。 トランザクション、候補アイテム集合、頻出アイテム集合中のアイテムは、 すべてある決まった順序にソートされている。 C1からL1を生成 アイテム集合C1 D → スキャン アイテム集合L1カウント 候補 → 生成 {A}{A}2 {B}{B}3 {C}{C}3 {D}{E}3 {E} C2からL2を生成 アイテム集合C2 D → スキャン アイテム集合L2カウント 候補 → 生成 {A,B}{A,C}2 {A,C}{B,C}2 {A,E}{B,E}3 {B,C}{C,E}2 {B,E} {C,E} C3からL3を生成 アイテム集合C3 D → スキャン アイテム集合L3カウント
このページを最初にブックマークしてみませんか?
『Theory of Computing Lab. 計算理論研究室』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く