Chip 2000 May

home *** CD-ROM | disk | FTP | other *** search

/ Chip 2000 May / Chip_2000-05_cd1.bin / zkuste / Perl / ActivePerl-5.6.0.613.msi / 䆊䌷䈹䈙䏵-䞅䞆䞀㡆䞃䄦䠥 / _ef5badafe9192e74daf62dd8bc3927e1 < prev next >

Wrap

Text File | 2000-03-23 | 9.3 KB | 239 lines

<HTML> <HEAD> <TITLE>Algorithm - the theory behind it</TITLE> <LINK REL="stylesheet" HREF="../../../Active.css" TYPE="text/css"> <LINK REV="made" HREF="mailto:"> </HEAD> <BODY> <TABLE BORDER=0 CELLPADDING=0 CELLSPACING=0 WIDTH=100%> <TR><TD CLASS=block VALIGN=MIDDLE WIDTH=100% BGCOLOR="#cccccc"> Algorithm - the theory behind it </TD></TR> </TABLE> <A NAME="__index__"></A>  <UL> <LI><A HREF="#name">NAME</A></LI><LI><A HREF="#supportedplatforms">SUPPORTED PLATFORMS</A></LI> <LI><A HREF="#description">DESCRIPTION</A></LI> <UL> <LI><A HREF="#semirings">Semi-Rings</A></LI> <LI><A HREF="#operator '*'">Operator '*'</A></LI> <LI><A HREF="#kleene's algorithm">Kleene's Algorithm</A></LI> <LI><A HREF="#kleene's algorithm and semirings">Kleene's Algorithm and Semi-Rings</A></LI> </UL> <LI><A HREF="#see also">SEE ALSO</A></LI> <LI><A HREF="#author">AUTHOR</A></LI> <LI><A HREF="#copyright">COPYRIGHT</A></LI> </UL>  <HR> <H1><A NAME="name">NAME</A></H1> Kleene's Algorithm - the theory behind it brief introduction <HR> <H1><A NAME="supportedplatforms">SUPPORTED PLATFORMS</A></H1> <UL> <LI>Linux</LI> <LI>Solaris</LI> <LI>Windows</LI> </UL> <HR> <H1><A NAME="description">DESCRIPTION</A></H1> <H2><A NAME="semirings">Semi-Rings</A></H2> A Semi-Ring (S, +, ., 0, 1) is characterized by the following properties: <OL> <LI><A NAME="item_%29">)</A> a) <CODE>(S, +, 0) is a Semi-Group with neutral element 0</CODE> b) <CODE>(S, ., 1) is a Semi-Group with neutral element 1</CODE> c) <CODE>0 . a = a . 0 = 0 for all a in S</CODE> <LI>) <CODE>"+"</CODE> is commutative and idempotent, i.e., <CODE>a + a = a</CODE> <LI>) Distributivity holds, i.e., a) <CODE>a . ( b + c ) = a . b + a . c for all a,b,c in S</CODE> b) <CODE>( a + b ) . c = a . c + b . c for all a,b,c in S</CODE> <LI>) <CODE>SUM_{i=0}^{+infinity} ( a[i] )</CODE> exists, is well-defined and unique <CODE>for all a[i] in S</CODE> and associativity, commutativity and idempotency hold <LI>) Distributivity for infinite series also holds, i.e., <PRE> ( SUM_{i=0}^{+infty} a[i] ) . ( SUM_{j=0}^{+infty} b[j] ) = SUM_{i=0}^{+infty} ( SUM_{j=0}^{+infty} ( a[i] . b[j] ) )</PRE> </OL> EXAMPLES: <UL> <LI> <CODE>S1 = ({0,1}, |, &, 0, 1)</CODE> Boolean Algebra See also <A HREF="../../../Math/MatrixBool(3).html">the Math::MatrixBool(3) manpage</A> <LI> <CODE>S2 = (pos. reals with 0 and +infty, min, +, +infty, 0)</CODE> Positive real numbers including zero and plus infinity See also <A HREF="../../../Math/MatrixReal(3).html">the Math::MatrixReal(3) manpage</A> <LI> <CODE>S3 = (Pot(Sigma*), union, concat, {}, {''})</CODE> Formal languages over Sigma (= alphabet) See also <A HREF="../../../DFA/Kleene(3).html">the DFA::Kleene(3) manpage</A> </UL> <H2><A NAME="operator '*'">Operator '*'</A></H2> (reflexive and transitive closure) Define an operator called ``*'' as follows: <PRE> a in S ==> a* := SUM_{i=0}^{+infty} a^i</PRE> where <PRE> a^0 = 1, a^(i+1) = a . a^i</PRE> Then, also <PRE> a* = 1 + a . a*, 0* = 1* = 1</PRE> hold. <H2><A NAME="kleene's algorithm">Kleene's Algorithm</A></H2> In its general form, Kleene's algorithm goes as follows: <PRE> for i := 1 to n do for j := 1 to n do begin C^0[i,j] := m(v[i],v[j]); if (i = j) then C^0[i,j] := C^0[i,j] + 1 end for k := 1 to n do for i := 1 to n do for j := 1 to n do C^k[i,j] := C^k-1[i,j] + C^k-1[i,k] . ( C^k-1[k,k] )* . C^k-1[k,j] for i := 1 to n do for j := 1 to n do c(v[i],v[j]) := C^n[i,j]</PRE> <H2><A NAME="kleene's algorithm and semirings">Kleene's Algorithm and Semi-Rings</A></H2> Kleene's algorithm can be applied to any Semi-Ring having the properties listed previously (above). (!) EXAMPLES: <UL> <LI> <CODE>S1 = ({0,1}, |, &, 0, 1)</CODE> <CODE>G(V,E)</CODE> be a graph with set of vortices V and set of edges E: <A HREF="../../../lib/Pod/perlfunc.html#item_m"><CODE>m(v[i],v[j]) := ( (v[i],v[j]) in E ) ? 1 : 0</CODE></A> Kleene's algorithm then calculates <CODE>c^{n}_{i,j} = ( path from v[i] to v[j] exists ) ? 1 : 0</CODE> using <CODE>C^k[i,j] = C^k-1[i,j] | C^k-1[i,k] & C^k-1[k,j]</CODE> (remember <CODE> 0* = 1* = 1 </CODE>) <LI> <CODE>S2 = (pos. reals with 0 and +infty, min, +, +infty, 0)</CODE> <CODE>G(V,E)</CODE> be a graph with set of vortices V and set of edges E, with costs <A HREF="../../../lib/Pod/perlfunc.html#item_m"><CODE>m(v[i],v[j])</CODE></A> associated with each edge <CODE>(v[i],v[j])</CODE> in E: <A HREF="../../../lib/Pod/perlfunc.html#item_m"><CODE>m(v[i],v[j]) := costs of (v[i],v[j])</CODE></A> <CODE>for all (v[i],v[j]) in E</CODE> Set <A HREF="../../../lib/Pod/perlfunc.html#item_m"><CODE>m(v[i],v[j]) := +infinity</CODE></A> if an edge (v[i],v[j]) is not in E. <CODE> ==> a* = 0 for all a in S2</CODE> <CODE> ==> C^k[i,j] = min( C^k-1[i,j] ,</CODE> <CODE> C^k-1[i,k] + C^k-1[k,j] )</CODE> Kleene's algorithm then calculates the costs of the ``shortest'' path from any <CODE>v[i]</CODE> to any other <CODE>v[j]</CODE>: <CODE>C^n[i,j] = costs of "shortest" path from v[i] to v[j]</CODE> <LI> <CODE>S3 = (Pot(Sigma*), union, concat, {}, {''})</CODE> <CODE>M in DFA(Sigma)</CODE> be a Deterministic Finite Automaton with a set of states <CODE>Q</CODE>, a subset <CODE>F</CODE> of <CODE>Q</CODE> of accepting states and a transition function <CODE>delta : Q x Sigma --> Q</CODE>. Define <A HREF="../../../lib/Pod/perlfunc.html#item_m"><CODE>m(v[i],v[j]) :=</CODE></A> <CODE> { a in Sigma | delta( q[i] , a ) = q[j] }</CODE> and <A HREF="../../../lib/Pod/perlfunc.html#item_m"><CODE>C^0[i,j] := m(v[i],v[j]);</CODE></A> <CODE>if (i = j) then C^0[i,j] := C^0[i,j] union {''}</CODE> (<CODE>{''}</CODE> is the set containing the empty string, whereas <CODE>{}</CODE> is the empty set!) Then Kleene's algorithm calculates the language accepted by Deterministic Finite Automaton M using <CODE>C^k[i,j] = C^k-1[i,j] union</CODE> <CODE> C^k-1[i,k] concat ( C^k-1[k,k] )* concat C^k-1[k,j]</CODE> and <CODE>L(M) = UNION_{ q[j] in F } C^n[1,j]</CODE> (state <CODE>q[1]</CODE> is assumed to be the ``start'' state) finally being the language recognized by Deterministic Finite Automaton M. </UL> Note that instead of using Kleene's algorithm, you can also use the ``*'' operator on the associated matrix: Define <A HREF="../../../lib/Pod/perlfunc.html#item_m"><CODE>A[i,j] := m(v[i],v[j])</CODE></A> <CODE> ==> A*[i,j] = c(v[i],v[j])</CODE> Proof: <CODE>A* = SUM_{i=0}^{+infty} A^i</CODE> where <CODE>A^0 = E_{n}</CODE> (matrix with one's in its main diagonal and zero's elsewhere) and <CODE>A^(i+1) = A . A^i</CODE> Induction over k yields: <CODE>A^k[i,j] = c_{k}(v[i],v[j])</CODE> <DL> <DT><A NAME="item_k_%3D_0%3A"><CODE>k = 0:</CODE></A> <DD> <CODE>c_{0}(v[i],v[j]) = d_{i,j}</CODE> with <CODE>d_{i,j} := (i = j) ? 1 : 0</CODE> and <CODE>A^0 = E_{n} = [d_{i,j}]</CODE> <DT><A NAME="item_k"><CODE>k-1 -> k:</CODE></A> <DD> <CODE>c_{k}(v[i],v[j])</CODE> <A HREF="../../../lib/Pod/perlfunc.html#item_m"><CODE>= SUM_{l=1}^{n} m(v[i],v[l]) . c_{k-1}(v[l],v[j])</CODE></A> <CODE>= SUM_{l=1}^{n} ( a[i,l] . a[l,j] )</CODE> <CODE>= [a^{k}_{i,j}] = A^1 . A^(k-1) = A^k</CODE> </DL> qed In other words, the complexity of calculating the closure and doing matrix multiplications is of the same order <CODE>O( n^3 )</CODE> in Semi-Rings! <HR> <H1><A NAME="see also">SEE ALSO</A></H1> Math::MatrixBool(3), Math::MatrixReal(3), DFA::Kleene(3). (All contained in the distribution of the ``Set::IntegerFast'' module) Dijkstra's algorithm for shortest paths. <HR> <H1><A NAME="author">AUTHOR</A></H1> This document is based on lecture notes and has been put into POD format by Steffen Beyer <<A HREF="mailto:sb@sdm.de">sb@sdm.de</A>>. <HR> <H1><A NAME="copyright">COPYRIGHT</A></H1> Copyright (c) 1997 by Steffen Beyer. All rights reserved. <TABLE BORDER=0 CELLPADDING=0 CELLSPACING=0 WIDTH=100%> <TR><TD CLASS=block VALIGN=MIDDLE WIDTH=100% BGCOLOR="#cccccc"> Algorithm - the theory behind it </TD></TR> </TABLE> </BODY> </HTML>