[Skip Navigation] [CSUSB] / [CNS] / [Comp Sci Dept] / [R J Botting] / [Samples] / design95
[Index] [Contents] [Source Text] [About] [Notation] [Copyright] [Comment/Contact] [Search ]
Tue Sep 18 15:25:36 PDT 2007

Contents


    A Theory of Design

      Warning

      This is a PBI: Partly Baked Idea, or work in progress. These version has been superceded by [ design99.html ] in which the ideas of process and architecture are integrated.

      Theory

    1. DESIGN::=
      Net{

      1. S::=Universe of systems::Sets,
      2. s0::=Current system::S,
      3. P::=Systems that do what the client wants::@S,
      4. Q::=`set of qualities, including cost, delivery time, reliability, etc,...`::Sets,
      5. R::=`Systems with objects modelling the relevant part of the real world`::@S,
      6. T::=`Techniques, tools, technology leading to changes in systems`::@(@S>->@S),

        Design presumes that PQRST are already known well enough to proceed. However, in the process of design any of PQRST may change. It is useful therefore to maintain a trace of the connection between conclusions and the PQRST that lead to them[Dasgupta 91, Gravell 90]. In USA DoD projects this traceability is a mandated requirement.

        Notice that (in theory) P can be expressed as

      7. (1): P=&Π where Π:@@S=Set of partial purposes. Typically the current system 's0' satisfies some of the purposes of the system, but not all of them:
      8. (2): For some π :@Π ( s0 in &π ~ P ). Indeed for any system s:S, we can define
      9. π(s)::={ p:Π || s in p }.

        Notice that since this is a model of systems rather than a model of designs, specifications, and implementations it is not natural to make a model of the relation (1st) implements (2nd). Instead the set of systems that are in P and/or R may be described by a separate universe of documentation and the (1st) implements (2nd) connects systems with their documentation. Thus a hierarchy of refinements may or may not exist between documentation, bot between systems. Loe Freijs has presented an interesting theory of this relation and the structure of designs[ Freijs 93].

        My focus here is on the essence of the engineering ethic: making something more effective.

        Properties of the T's

        1. (3): For t:T, t in @S->@S -- map sets of systems into new possibilities, with some unpredictability.

          Monotonicity.

        2. (4): For all t:T, A,B:@S, t(A) | t(B)==>t(A | B).
        3. (5): For all t:T, A,B:@S, if A==>B then t(A)==>t(B).

          By Knaster-Tarski Theorem Knaster 29

        4. |- (6): For all t:T, some F:@S, t(F)=F.

          The Do-Nothing Option

          One T is doing nothing(Id(@S)). The T's available to us are a subset of all possible changes that might be made, and if we can carry out two or more changes then any sequence of them is also a valid change. So we can assume that we have a monoid of T's
        5. (7): (monoid)(T, o, Id(@S))==>(@S, o, Id(@S)).
        6. (7)|- (8): Id(@S) in T.
        7. (7)|- (9): for t1, t2:T then t1; t2 in T.

          Dangerous Techniques

          Certain operations annihilate the system that they operate on, in the sense that there are maps in m:@S->@S such that for a given A:@S, m(A)={}. These are not useful techniques and so we suppose these are not part of those we might apply,
        8. (10): For all t:T, not {} in post(t).

          Abreviation

          Define an abbreviation for the special case of applying a change to a single system rather than a set of them:
        9. t::S>->@S=map[s:S](t({s})).

          Effect of T on P

          A technique can change the purposes that a system satisfies: Fot t:T, τ(t)::=rel[ π:@Π, π':@Π] (for all s:π (t(s) in π').

        . . . . . . . . . ( end of section Properties of the T's) <<Contents | End>>

        Theory of Values

          The values are additive and associated with the qualities[Von Neuman & Morgenstein].

        1. v::(S|T)>->(Q>->Real)=value/costs of various systems and changes.

          Assume that costs and qualities accumulate as successive changes are made.

        2. linear::@= v in (monoid)(T,o,Id(@S))->(Q>->Real,+,0).

        3. V::=set of satisfactory values::@(Q>->Real).
        4. f::=objective function::(Q>->Real)>->Real. [Operations Research]

          A triple in S><T><S can model a particular change to the system, and can have a value associated with it by:

        5. For s1:S, t:T, s2:t(s1), v(s1,t,s2)::Q>->Real=v(s2)+v(t) - v(s1).

        6. conflict_free::@,
          (11): conflict_free=( if f(x)>f(y) then for all q, x[q] >= y[q] ).


          ??{Arrow's theorem|-real projects will have conflicts}?

        7. ??{model of decision making see Cardenas-Garcia & Zelkowitz 91.}?

          We have an induced relation between systems:

        8. For R:@(Real,Real), R::@(S,S)=R mod (v;f).
        9. |- (12): For s1,s2:S, R:@(Real,Real), s1 R s2 = (s1.v;f) R (s2.v;f).

        10. G@S::=Global optima::={s:S || for all s1:S( s >= s1)}.

          The Travelling Salesperson Problem demonstrates that finding an optimal design is an NP-complete problem. The Busy Beaver problem for Turing Machines is an optimization problem as well (longest time), so it is clear that some Optimization problems are unsolvable.


        11. |- (13): G={s:S || for all s1:S(f(v(s))>=f(v(s1)))}

          If we can treat S as a topological space with

        12. near::S->@@S, near(x)::=The neighborhoods of x,

        13. L::=Local_optima::@S={s:S || for some N:near(s), for all n:N (s>=n)}.

          Simon's Satisficing heuristic - good enough now, is better than the best never[Simon 69, Dasgupta 91].

        14. F::=feasible systems::@S.


          (14): F==>&{R, P, &[ q:Q]{s1 || t:T(s1 in t(s0) & v(s0,t,s1)(q) in V(q))} }.

          Iterative Improvement or Evolution

        15. For s1:S,p:PerCent, safe_steps(s1,p)::={ t:T || for (p%) s2 in t(s)( s2 in P & R & s1./<) }

          Equilibrium Solutions

          A solution is stable with respect to a given quality if all changes can make it worse.

        16. stable_wrt(q)::= { s0:S || for some t:T, s1: t(s) ( v(s0,t,s1)(q) < 0 )
          }

        By analogy with Parieto's economic analysis there is probably a system from which all changes decrease some quality:

      10. equilibria::= &[q:Q] stable_wrt(q).

        However some equilibria are not optimal.

        Another attempt to optimize complex systems leads to the paradoxical trap of sub-optimization. In sub-optimization the problem is decomposed into parts and each part optimized separately. Although this is often successful there is no reason to expect the whole to be optimal as well. ...

      . . . . . . . . . ( end of section Theory of Values) <<Contents | End>>

      Structure

        The structure of design can be modeled as graph where each node is a component and the arcs connect parts to wholes. Each node has a type - indicating the form of decomposition. In software the following types of nodes give the simplest description of the product. Suppose N is decomposed into a list of n parts then one of the following can always be made to be true
      1. Sequence/Composition N=! n or N=; n.
      2. Union N= | n
      3. Intersection N = & n
      4. Type N = Net{ n } Given that N satisfies P then we can often deduce the PQRs of the components (n).

        A design is structurally stable with respect to a factor if small changes in that factor leave the structure unchanged. Values of factors where this is not so are said to be on a 'catastrophe'[Thom, ...].

      5. ...

        Close Structure

        Proof of 8

        Proof of 9

        See the definition of a monoid, [ math_33_Monoids.html ] }=::DESIGN

      . . . . . . . . . ( end of section A Theory of Design) <<Contents | End>>

    End