●状態の入れ子とフローチャート
00788/00788 VFF15672 T's-Neko RE:内容の濃いＯＯＤの本 ？
( 7) 98/05/19 08:31 00786へのコメント
野田 真一 さん、こんばんは。T's-Neko です。(^o^)o
>>オブジェクト指向で書けば、こんな感じですけど、
>
>ちょっと、違う。結論を急ぎすぎるよ。
>
>再度、エピステーメさんのほうがいい。
すいません、結論を見せてから説明するのが早いと思って。
でも、ベクトルの要素を、配列にしたものと構造体にしたもの
といった違いだけなんですけど。
（επιστημηさん）
>"すべての状態遷移をベクトルで表示する"ってのは
>[状態-Sx]で[事象-E]が起こったら[活動-A]をやった後[状態-Sy]に遷移する
>を表現したベクトル(Sx,E,A,Sy)の集合、それと初期状態-Si,停止状態-St,
>それから事象の集合-E0..Enなどなどを状態遷移機械に食わせておいて、
>そいつに事象をがんがん投げ込めば動いてくれる、みたいなもんでしょうか。
># 「おーとまとん」だねこれは^^;
>＞そーゆーのは作ったことがありますです。
>＞結局(Sx,E,A,Sy)の集合から(Sx,E)をキーとして検索かけるだけなんですが。
>
>僕のは、これをかなり簡略してる。
これらから想像するに、グラフ理論におけるノードからノードへの
リンクをベクトルと呼んでるんですよね。（ベクトルの一例かも
しれませんが）。上の例の場合、
状態をノード、事象と活動をリンクとしているわけで。
リンクの表現は、配列であったり、ポインタであったり、
クラス（構造体）であったり、いろんなもので表現できます。
どれを使うかは設計者やケースによって様々ですが、
同じ人が設計したら、よく使うものの傾向が見られます。
僕の学んだオブジェクト指向では、クラス（概念）をノードとし、
それをインスタンスにしたオブジェクトと属性と操作を
関連（リンク）付けます。オブジェクトと属性は１対多の
関係があるので、１つのオブジェクトに複数のリンク（ベクトル）
があります。
というわけで、ベクトルの考えが無いわけではありません。
まぁ、ベクトルよりオブジェクトの方が主役ですけど。
ところで、ノードとリンクの関係は、ときに逆転することが
あります。たとえばブロック図はこんな感じです。
+--------+ param +---------+ picture +--------+ signal
| CPU |------->| Graphic |-------->| NTSC |-------->
+--------+ +---------+ +--------+
CPU から Graphic チップにパラメータを渡し、
Graphic チップから NTSC 出力へ画像を渡し、
NTSC 出力から信号が出ます。
一方、こういう図も書けると思います。
+--------+ Graphic +---------+ ntsc +--------+
| param |-------->| Picture |------>| signal |
+--------+ +---------+ +--------+
パラメータが、Graphic チップによって画像へ変換し、
画像を NTSC 出力チップによって信号へ変換していると。
これはノーテーションの違いなので、これらのうち
どちらが優れているがについて議論するのは無駄ですけど、
リンクで考えるものが、他の人はノードで考えている
可能性があるということです。
（UML のコラボレーション図は、このへんがあいまいだよな）
>ペンギンは、そんな事考えてなくても、とべる。余分な事考えるくらいなら、
>ぺンギンを観察している方が、いいように思える。
>その実践が、表面（ビュー）を観察し、分析するノーテーションに逃げては駄目だとい
>う事。
>
>コーヒー自動販売機の場合は、機械工学の実践とモデルに学ぶ、ないし機械職人に学ぶ
>という事でしょう。情報処理で考えるのは、時間の無駄。オートマトンは、機械工学だ
>。
ノーテーションは性質を理解するための土台であり、性質を見るための
視点を決定するものです。おなじコーヒー自動販売機でも、
機械工学の人と情報処理の人とコーヒーを飲むお客さんでは
ノーテーション（視点）が異なります。
機械工学のノーテーションは機械工学的な問題を解決するのに
最も適しているのはあたりまえです。自販機を作るのに機械職人を
開発メンバーからはずす人はいないでしょう。
だから時間の無駄ですけど、デジタル（電子）技術が発達して
性能がよくなっていますし、それを制御するには情報処理なわけで、
ノーテーションに逃げているとは思えないんですけど。
でも、目的がはっきりしないうちにモデリングすると、
見当違いの設計が出来ますね。UML にいろんなタイプの図が
あるように、目的に応じたノーテーションを選択して
分析しないと。
（そういう意味ではオブジェクト指向は何でもアリで
アイデンティティをつかみにくいですね）
--- Neko.
access to Sage Plaisir! → http://www.ceres.dti.ne.jp/~m-toda/
00866/00891 VFF15672 T's-Neko RE^13:内容の濃いＯＯＤの本 ？
( 7) 98/05/27 21:56 00861へのコメント コメント数：1
野田 真一 さん、こんばんは。T's-Neko です。(^o^)o
>の自動販売機 と同じモデルと思っています。自動販売機は、明らかな、
>有限状態の機械ですから。
そういえば、大学のころ、自販機に投入した金額に関する状態遷移図を
書け、って問題があったな。
初期状態が 0 円で、10円玉が入ったら 10円の状態へ。
更に 50円玉が入ったら 60円の状態へ。...
そうなことより、入れた金額を計算＆比較すれば、
状態は無くなるのに、面倒だな。と嫌々解いてました。
「入れた金額」が状態といえばそうだけど、
状態遷移図に書けるような状態じゃないよな。
こういった勘違いを利用して状態を減らすのに、
オブジェクト指向のカプセル化が役立った気がするけど
具体的には忘れた。（初心者のころだったし。）
--- Neko.
access to Sage Plaisir! → http://www.ceres.dti.ne.jp/~m-toda/
00939/00943 VFF15672 T's-Neko RE^17:内容の濃いＯＯＤの本 ？
( 7) 98/06/18 23:02 00937へのコメント コメント数：1
田中 祐 さん、こんばんは。T's-Neko です。(^o^)o
>T's-Neko さんの指摘では、肥大した状態遷移では、金額のようなものは投入
>された硬貨に応じて金額ごとに状態を設定するのではなく、変数として状態遷
>移から除外して遷移条件に表すようにすれば良い、というものでした。
>
>アバウトな図ですが、硬貨投入に応じた状態遷移はこんな感じでしょうか。
>
> ＋１０ ＋１０ ＋１０
>→１０円──→２０円───…──→１１０円──→１２０円≡ランプ点灯
> │ │ ↑ ↑
> └──────────…────┘ │
> ＋１００ └───…───────────┘
> ＋１００
>
>一方で変数として遷移条件に表しただけの図とは、
>
> 投入≧１２０円
>待ち受け──────────→ランプ点灯
>│ ↑
>└─┘投入＜１２０円
>
>という感じになります。
>
>
>私が前回の発言でカウンターなるものを持ち出したのは、上側の図の１０円か
>ら１２０円に至る状態が、１) 各状態からの遷移条件がみな同じものである、
>２) 状態が(おおざっぱな言い方をすると)一列に並ぶ、というような条件が満
>たされているので、下側の図のものに置き換えることができる、という理由か
>らでした。
遷移条件は同じだけど、アクションは異なるよね。
つまり、
１２０円より少ない状態 → １２０円以上の状態
と考えることができるわけです。
田中さんの言っている状態の入れ子ってこれだよね。
でも、この上位の状態は、人によって分類が異なることと同じ問題があります。
お酒の自販機は、350ml, 500ml, 1000ml とあって値段が異なりますね。
a)２２０円より少ない状態 → ２２０円以上の状態
b)２８０円より少ない状態 → ２８０円以上の状態
c)４２０円より少ない状態 → ４２０円以上の状態
のように「投入金額」という１つの状態に対して上位の状態が重なっている
わけです。まぁ、この例では、
a)２２０円〜２８０円、２８０円〜４２０円、４２０円〜
というように状態を設計すれば状態が重なってはいないけどね。
たぶん野田さんの「商単位半群」って、金額の単位「１円」のこと
じゃないかと思いますけど、何百という状態をえぴさんが紹介してくれた
方法でやるわけにもいかないわけですよね。
>あと、もうひとつ、金額でいえば、１２０円には違いないけど、実は１０円硬
>貨ばかりの１２０円とそうでない場合の１２０円とで処理がかわってくる場合
>などは、単なる「１２０円」の状態以外になにか別の判断要素があるわけです。
Level A : １０円玉の枚数、５０円玉の枚数、１００円玉の枚数
Level B : 投入金額
Level C : 350ml缶のランプの状態、500ml缶の〜、1000ml缶の〜
という入れ子構造ですね。
>状態遷移で状態数や遷移数が複雑な形に増大してしまった場合ですが、状態遷
>移のことをわかっている人が注意深く分解していけばかなりキレイなものが得
>られる一方で、行きあたりばったりにつくると簡単な状態遷移のようで実は動
>作の検証が困難なものになったりします。
状態遷移のキレイさも、オブジェクト抽出やメソッドの抽出のセンスと
近いものがあると思います。上の例の場合、投入金額は誰でも明示できる
けど、ランプの状態を明示できずに、プログラムのあらゆるところに、
その判断文が散らばったりすると、よくないですね。
--- Neko.
access to Sage Plaisir! → http://www.ceres.dti.ne.jp/~m-toda/
00946/00948 VFF15672 T's-Neko RE^19:内容の濃いＯＯＤの本 ？
( 7) 98/06/21 17:54 00942へのコメント
田中 祐 さん、こんばんは。T's-Neko です。(^o^)o
>》たぶん野田さんの「商単位半群」って、金額の単位「１円」のこと
>》じゃないかと思いますけど、何百という状態をえぴさんが紹介してくれた
>》方法でやるわけにもいかないわけですよね。
>違います、大間違いです。
>
>この場合、金額の単位「１円」とは遷移条件のことを指しているとしか考えら
>れませんが(状態としての「１円」なら何をもって半群としているのか意味が
>通らん)、だとすると、「１円」という条件は(これは投入金額だと解釈して)
>状態を変化しうるものなので、このモノイドにおける単位元にはなりえません。
>
>ふつうは状態遷移をモノイドで解釈したときの単位元は「なにも入力がない」
>ことを意味します。あるいは、この「商単位半群≡金額の単位の１円のこと」
>というのはなにか別の意味があるのでしょうか？
あれ？足し算に関する整数って半群じゃなかったっけ？
単位元は「０円」だけど。
「商単位半群」は、よう知らんけど、
「０円と１円を元にもつ集合」ですか？（違うだろうな）
>》Level A : １０円玉の枚数、５０円玉の枚数、１００円玉の枚数
>》Level B : 投入金額
>》Level C : 350ml缶のランプの状態、500ml缶の〜、1000ml缶の〜
>》
>》という入れ子構造ですね。
>これは各レベル間で依存関係がなければ、入れ子構造の分解に相当する部分の
>究極の形、直積分解、に相当します。
ほうほう。でもよくわかりません。(^^;
オブジェクト指向っぽく言えば、Level B, C は、派生属性です。
Level B := 10 * 10 円の枚数 + 50 * 50 円の枚数 + 100 * 100 円の枚数
Level C - 350ml := yen >= 220
Level C - 500ml := yen >= 280
Level C -1000ml := yen >= 420
つまり、各レベル間で依存関係があると思うのですが。
前の発言の Level A,B,C は、依存関係に注目し、
属性（状態、変数）が、変数属性か派生属性か分析した結果です。
状態の入れ子構造で見ると、トップのものが派生属性に、
ボトム（？）のものが、変数属性になることが多いです。
そして、最終的に残った変数属性が、独立になっている
可能性が高く、その数少ない状態のみ監視（オブジェクトの
正規状態を維持）すればいいことになります。
これは田中さんの言う直積分解ではないですね。
>状態を、例えば、a1、a2、a3、b1、b2、b3、という具合いにラベル付けできる
>ときに a、b、という状態遷移と 1、2、3、いう状態遷移の二つの独立した状
>態遷移に完全にわけられることが直積分解に相当します。
おお、なるほど。
直積分解は、どんどん進めた方がいいですね。
A={ a, b } と N={ 1, 2, 3 } が商単位半群ですか？
直積分解って、抽象クラスや部品クラスを見つけること、
属性を定義することと作業内容が似ていますね。
ただ、もし、a1、a2、a3、b1、b2、c1 という状態値なら、
a,b,c と 1,2,3 に分解するとややこしくなりますね。
（こういうケースのほうが圧倒的に多いよね）
こういう場合は、
X = { a1, a2, a3, b1, b2, c1 }
を変数属性に
A = { a, b, c }
N = { 1, 2, 3 }
を派生属性にした方がいいケースもあります。
>入れ子だ、分解だとごちゃごちゃしてきますが、状態遷移をなにか処理を行な
>うもの(つまり、オートマトンですが)をブラックボックスで考えてみると解り
>易いかもしれません。すると、一般に「入れ子」とよばれるものには、状態遷
>移の分解のしかたによって(私の考えでは)３種類にわけられると思います。直
>列、並列、自己埋め込み、の３つです。図にするとつぎのようになります。
>(固定長フォントでごらんください)
>
> ┌───┐
>ＩＮＰＵＴ→┤ ├→ＯＵＴＰＵＴ
> └───┘
うーん、入出力を考えると、どうも状態遷移に見えないのは僕だけか？
UML では、状態の記号（角が丸い枠）と、処理（アクション）の記号が、
同じ記号で表されていますが、これは、見方を変えれば、状態と処理が、
見方によってどちらにも解釈できるからだと思います。
どうしても、解釈できない場合は、#788 にも描いたように、
図（頭の中のイメージ）を変換するとうまくいくことも多いです。
つまり、状態遷移の裏は、フローチャートということです。
だから、状態において、並列処理も考えられるし、
そこで必要になる直積分解という概念も排他制御と
同じ考え方ができるわけです。
たとえば、直積分解できる状態/変数が２つあったなら
その２つを必ずロックしなくてもいいこと、
並列処理して動いているものは独立であること、
入れ子構造が取れること、
適切な条件文を入れるとキレイになることがあること
などです。
という理由から、僕は状態遷移図作るぐらいなら
フローチャートを作ります。（例外処理機構付きで）
--- Neko.
access to Sage Plaisir! → http://www.ceres.dti.ne.jp/~m-toda/
This text was copyed from Niftyserve Programer's Forum Pro.