Quellcodebibliothek Statistik Leitseite products/sources/formale Sprachen/GAP/pkg/alco/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 5.8.2025 mit Größe 11 kB image not shown  

Quelle  chap6_mj.html   Sprache: HTML

 
 products/sources/formale Sprachen/GAP/pkg/alco/doc/chap6_mj.html


<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
         "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<script type="text/javascript"
  src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (ALCO) - Chapter 6: Closure Tools</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap6"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chap4_mj.html">4</a>  <a href="chap5_mj.html">5</a>  <a href="chap6_mj.html">6</a>  <a href="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap5_mj.html">[Previous Chapter]</a>    <a href="chapBib_mj.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap6.html">[MathJax off]</a></p>
<p><a id="X86ED1AD579C62F21" name="X86ED1AD579C62F21"></a></p>
<div class="ChapSects"><a href="chap6_mj.html#X86ED1AD579C62F21">6 <span class="Heading">Closure Tools</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6_mj.html#X811639F384636DE8">6.1 <span class="Heading">Brute Force Method</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X87E8AA6582245C3E">6.1-1 Closure</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6_mj.html#X7F865ED67CC5740F">6.2 <span class="Heading">Random Choice Methods</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X78DC531B815591E8">6.2-1 RandomElementClosure</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6_mj.html#X7A4675E27B489038">6.2-2 RandomOrbitOnSets</a></span>
</div></div>
</div>

<h3>6 <span class="Heading">Closure Tools</span></h3>

<p>The <strong class="pkg">ALCO</strong> package provides some basic tools to compute the closure of a set with respect to a binary operation. Some of these tools compute the closure by brute force, while others use random selection of pairs to attempt to find new members not in the set.</p>

<p><a id="X811639F384636DE8" name="X811639F384636DE8"></a></p>

<h4>6.1 <span class="Heading">Brute Force Method</span></h4>

<p><a id="X87E8AA6582245C3E" name="X87E8AA6582245C3E"></a></p>

<h5>6.1-1 Closure</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Closure</code>( <var class="Arg">gens</var>, <var class="Arg">op</var>[, <var class="Arg">option</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>For <var class="Arg">gens</var> satisfying <code class="code">IsHomogeneousList</code>, this function computes the closure of <var class="Arg">gens</var> by addition of all elements of the form <code class="code"><var class="Arg">op</var>(x,y)</code>, starting with <code class="code">x</code> and <code class="code">y</code> any elements in <var class="Arg">gens</var>. The function will not terminate until no new members are produced when applying <var class="Arg">op</var> to all ordered pairs of generated elements. The argument <var class="Arg">option</var>, if supplied, ensures that the function treats <var class="Arg">op</var> as a commutative operation.</p>

<p>Caution must be exercised when using this function to prevent attempting to compute the closure of large or possibly infinite sets.</p>


<div class="example"><pre><span class="GAPprompt">gap></span> <span class="GAPinput">Closure([1,E(7)], \*);</span>
[ 1, E(7)^6, E(7)^5, E(7)^4, E(7)^3, E(7)^2, E(7) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">QuaternionD4Basis;</span>
Basis( <algebra-with-one of dimension 4 over Rationals>,
[ (-1/2)*e+(-1/2)*i+(-1/2)*j+(1/2)*k, (-1/2)*e+(-1/2)*i+(1/2)*j+(-1/2)*k,
  (-1/2)*e+(1/2)*i+(-1/2)*j+(-1/2)*k, e ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">Closure(QuaternionD4Basis,\*);</span>
[ (-1)*e, (-1/2)*e+(-1/2)*i+(-1/2)*j+(-1/2)*k,
  (-1/2)*e+(-1/2)*i+(-1/2)*j+(1/2)*k, (-1/2)*e+(-1/2)*i+(1/2)*j+(-1/2)*k,
  (-1/2)*e+(-1/2)*i+(1/2)*j+(1/2)*k, (-1/2)*e+(1/2)*i+(-1/2)*j+(-1/2)*k,
  (-1/2)*e+(1/2)*i+(-1/2)*j+(1/2)*k, (-1/2)*e+(1/2)*i+(1/2)*j+(-1/2)*k,
  (-1/2)*e+(1/2)*i+(1/2)*j+(1/2)*k, (-1)*i, (-1)*j, (-1)*k, k, j, i,
  (1/2)*e+(-1/2)*i+(-1/2)*j+(-1/2)*k, (1/2)*e+(-1/2)*i+(-1/2)*j+(1/2)*k,
  (1/2)*e+(-1/2)*i+(1/2)*j+(-1/2)*k, (1/2)*e+(-1/2)*i+(1/2)*j+(1/2)*k,
  (1/2)*e+(1/2)*i+(-1/2)*j+(-1/2)*k, (1/2)*e+(1/2)*i+(-1/2)*j+(1/2)*k,
  (1/2)*e+(1/2)*i+(1/2)*j+(-1/2)*k, (1/2)*e+(1/2)*i+(1/2)*j+(1/2)*k, e ]</pre></div>

<p><a id="X7F865ED67CC5740F" name="X7F865ED67CC5740F"></a></p>

<h4>6.2 <span class="Heading">Random Choice Methods</span></h4>

<p>In many cases the <code class="func">Closure</code> (<a href="chap6_mj.html#X87E8AA6582245C3E"><span class="RefLink">6.1-1</span></a>) function is impractical to use due to the long computation time of the brute force method. The following functions provide tools to generate more elements of a set under a binary operation without directly proving closure.</p>

<p><a id="X78DC531B815591E8" name="X78DC531B815591E8"></a></p>

<h5>6.2-1 RandomElementClosure</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RandomElementClosure</code>( <var class="Arg">gens</var>, <var class="Arg">op</var>[, <var class="Arg">N</var>[, <var class="Arg">print</var>]] )</td><td class="tdright">( function )</td></tr></table></div>
<p>For <var class="Arg">gens</var> satisfying <code class="code">IsHomogeneousList</code>, this function selects a random element <var class="Arg">r</var> in <var class="Arg">gens</var> and computes all elements of the form <code class="code"><var class="Arg"> op</var>(<var class="Arg">r</var>,<var class="Arg">x</var>)</code> for <var class="Arg">x</var> either in <var class="Arg">gens</var> or obtained in a previous closure step. Once this process yields a set of elements with equal cardinality <code class="code"><var class="Arg">N</var>+1</code> times, the function terminates and returns all elements obtained so far as a set. The default value of <var class="Arg">N</var> is <code class="code">1</code>. The optional <var class="Arg">print</var> argument, if supplied, prints the cardinality of the set of elements obtain so far at each iteration.</p>

<p>Caution must be exercised when using this function to prevent attempting to compute the random closure of an infinite set. Caution is also required in interpreting the output. Even for large values of <var class="Arg">N</var>, the result is not necessarily the full closure of set <var class="Arg">gens</var>. Furthermore, repeated calls to this function may result in different outputs due to the random selection of elements involved throughout. If the size of the expected closed set is known, use of a <code class="code">repeat</code>-<code class="code">until</code> loop can permit generating the full set of elements faster than <code class="func">Closure</code> (<a href="chap6_mj.html#X87E8AA6582245C3E"><span class="RefLink">6.1-1</span></a>) would.</p>


<div class="example"><pre><span class="GAPprompt">gap></span> <span class="GAPinput">start := Basis(QuaternionAlgebra(Rationals)){[2,3]};</span>
[ i, j ]
<span class="GAPprompt">gap></span> <span class="GAPinput">repeat</span>
<span class="GAPprompt">></span> <span class="GAPinput">start := RandomElementClosure(start, \*);</span>
<span class="GAPprompt">></span> <span class="GAPinput">until Length(start) = 8;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">start;</span>
[ (-1)*e, (-1)*i, (-1)*j, (-1)*k, k, j, i, e ]</pre></div>

<p><a id="X7A4675E27B489038" name="X7A4675E27B489038"></a></p>

<h5>6.2-2 RandomOrbitOnSets</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RandomOrbitOnSets</code>( <var class="Arg">gens</var>, <var class="Arg">start</var>, <var class="Arg">op</var>[, <var class="Arg">N</var>[, <var class="Arg">print</var>]] )</td><td class="tdright">( function )</td></tr></table></div>
<p>This function proceeds in a manner very similar to <code class="func">RandomElementClosure</code> (<a href="chap6_mj.html#X78DC531B815591E8"><span class="RefLink">6.2-1</span></a>) with the following differences. This function instead selects a random element <var class="Arg">r</var> in <var class="Arg">gens</var> and then for every <var class="Arg">x</var> in <var class="Arg">start</var>, or the set of previously generated elements, computes <code class="code"><var class="Arg">op</var>(<var class="Arg">r</var>,<var class="Arg">x</var>)</code>. At each step the cardinality of the union of <var class="Arg">start</var> and any previously generated elements is computed. Once the cardinality is fixed for <var class="Arg">N + 1</var> steps, the function returns the set of generated elements.</p>

<p>The same cautions as described in <code class="func">RandomElementClosure</code> (<a href="chap6_mj.html#X78DC531B815591E8"><span class="RefLink">6.2-1</span></a>) apply. Note that while <var class="Arg">start</var> is always a subset of the output, the elements of <var class="Arg">gens</var> are not necessarily included in the output.</p>


<div class="example"><pre><span class="GAPprompt">gap></span> <span class="GAPinput">start := Basis(QuaternionAlgebra(Rationals)){[1,2]};</span>
[ e, i ]
<span class="GAPprompt">gap></span> <span class="GAPinput">gens := Basis(QuaternionAlgebra(Rationals)){[3]};</span>
[ j ]
<span class="GAPprompt">gap></span> <span class="GAPinput">repeat </span>
<span class="GAPprompt">></span> <span class="GAPinput">start := RandomOrbitOnSets(gens, start, {x,y} -> x*y);</span>
<span class="GAPprompt">></span> <span class="GAPinput">until Length(start) = 8;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">start;</span>
[ (-1)*e, (-1)*i, (-1)*j, (-1)*k, k, j, i, e ]</pre></div>


<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap5_mj.html">[Previous Chapter]</a>    <a href="chapBib_mj.html">[Next Chapter]</a>   </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chap4_mj.html">4</a>  <a href="chap5_mj.html">5</a>  <a href="chap6_mj.html">6</a>  <a href="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.html">Ind</a>  </div>

<hr />
<p class="foot">generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>

100%


¤ Dauer der Verarbeitung: 0.14 Sekunden  (vorverarbeitet)  ¤

*© Formatika GbR, Deutschland




Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.