GAP
(logiciel de calcul formel)

 

1) Introduction

GAP signifie Groupes, Algorithmes et Programmation. Le sujet s'est progressivement élargie aux semigroupes et aux algèbres.

Le développement de GAP c'est fait en 1986 à l'université d'Aix-la-Chapelle (Allemagne), puis en 1998 à l'université de St Andrews (Royaume-Uni), puis en 2005 en partenariat par quatre université : les deux précédentes et l'université du Colorado à Fort Collins (États-Unis) et l'université de Brunswick (Allemagne).

Le système de base se compose de quatre parties :

  1. Un noyau, écrit en C, qui fournit à l'utilisateur:
    1. La gestion de la mémoire
    2. Un ensemble de fonctions de base, rapide, sur les entiers, les corps finis, les permutations, les mots, les listes et les collections.
    3. Un interprète pour le langage GAP, impératif et orientée objet.
    4. Des fonctions systèmes permettant de gérer les fichiers et d'exécuter des programmes externes.
    5. Un ensemble d'outils de programmation pour les tests, débogage, et synchronisation.
    6. Une interface "lecture-évaluation-vue" utilisateur.
  2. Une bibliothèque de fonctions GAP écrites dans la langue GAP. L'utilisateur peut comme les programmeurs enquêter et varier les algorithmes de la bibliothèque et en ajouter de nouveaux, et les publier.
  3. Une bibliothèque de données sur la théorie des groupes (contenant entre autre tous les groupes d'ordre au plus 2000, sauf ceux de l'ordre 1024).
  4. La documentation est disponible en ligne, sous forme de fichiers PDF et HTML (en)

Site officiel : http://www.gap-system.org (en)
Information sur les paquets : http://www.gap-system.org/Packages/packages.html (en)
Centre for Interdisciplinary Research in Computational Algebra (CIRCA) : http://www-circa.mcs.st-and.ac.uk/CIRCA/circa.php (en)

Chaque instruction doit se terminer par un point-virgule ";".
Le double point-virgule ";;" empêche l'affichage du résultat de l'instruction.
Pour alléger l'écriture dans notre documentation, on ne notera pas le point-virgule en fin de ligne.

quit
Pour quitter GAP
Read("../../GAPProgs/Example.g")
Pour charger un fichier GAP
NamesGVars()
Affiche toutes les variables de GAP
NamesUserGVars()
Affiche les variables de l'utilisateur
last
Dernier résultat
last2; last3
Avant dernier et avant avant dernier résultat

Arithmétique :

7^7
823543
 
10 > 2*3
false
 
17 mod 3
2
 
5>2 and 3>1
true
 
5=2+3
true
 
 
Factorial(12)
479001600
 
Gcd(15,21)
3
 
Lcm(20,30)
60
 
Print(1234, "\n")
 
'a'
'a'
Un caractère

Permutation :

(3,1,2)
(1,2,3)
Les permutations sont notées par cycle
(1,2) = (2,1)
true
C'est la même permutation
5^(2,5,4,7)
4
L'image de 5 par la permutation (2,5,4,7)
(1,2,3)*(1,2)
(2,3)
Composition d'application (notation française)
(1,2,3)^-1
(1,3,2)
Permutation inverse
2^(1,2,3)
3
Image de 2 par la permutation (1,2,3)
(1,2,3)^(2,4,3)
(1,4,2)
Conjugaison de (1,2,3) par (2,4,3)
(2,4,3)^-1 * (1,2,3) * (2,4,3)
(1,4,2)
Conjugaison de (1,2,3) par (2,4,3)
(1^(2,4,3),2^(2,4,3),3^(2,4,3))
(1,4,2)
Conjugaison de (1,2,3) par (2,4,3)

Affectation :

a:= 3*2
6
Affectation
a:=a*(a+1)
42
Affectation
a:='a'
'a'
Affectation
a:=(1,2);; IsIdenticalObj(a,a)
true
 
b:=(1,2);; IsIdenticalObj(a,b)
false
Car pointe à deux endroits différents
b:=a;; IsIdenticalObj(a,b)
true
 

Fonction :

f := x->x^3 function( x ) ... end
f(5) 125

Liste :

[2..5] = [2,3,4,5] true
List([2..5],f) [8,27,64,125] Applique f à chaque élément de la liste
A:=[1,2,3] [1,2,3]
Append(A,[4,5]) Modification physisue de la liste A en y concaténant [4,5]
A [1,2,3,4,5]
Append(A,6) Modification physisue de la liste A en y ajoutant l'élément 6
A [1,2,3,4,5,6]
A[3] 3
A[9]:=9;; A [1,2,3,4,5,6,,,9]
Length(A) 9 Longueur de la liste A
B:=[true, "Hello", [1,2],,'a'] [true, "Hello", [1,2],,'a']
Position(B,[1,2]) 3 Position de l'élément [1,2] dans la liste B
Position(B, 2) fail 2 n'est pas dans la liste B
B[4]:=B [true, "Hello", [1,2], ~,'a']
s:=['H','e','l','l','o'] "Hello"
s{[1,5,1]} = "HoH"  
s{[2,1]} = [fail, 5];; s [5, fail, 'l', 'l', 'o']
[10,20,30,40]{[1..3]} [10,20,30]
A:=[1,2,3] [1,2,3]
B:=ShallowCopy(A) [1,2,3]    // Copie en recréant juste le premier niveau de liste
A=B true
IsIdenticalObj(A,B) false
B:=Immutable(A) [1,2,3]    // Copie non modifiable
A=[[1,2],[3,4]] [[1,2],[3,4]]
B:=ShallowCopy(A) [[1,2],[3,4]]    // Copie en recréant juste le premier

 

 

B[1][1]:=5;; A [[5,2],[3,4]]
B[1]:=6;; A [[5,2],[3,4]]
B [6,[3,4]]
isSSortedList ([1,5,8]) true    // Liste triée et sans doublon
A:=Set([8,1,5]) [1,5,8]
5 in A true    // Plus lent
5 in [8,1,5] true    // Plus lent
AddSet(A, 4); A [1,4,5,8]
AddSet(A, 5); A [1,4,5,8]
Intersection([1,3,5],[2,3,5,6]) [3,5]
Union(([1,3,5],[2,3,5,6])

[1,2,3,5,6];

[1..10] [1..10]
[1,2..10] [1..10]
IsRange([-2,0,2,4]) true
A:=[-2,0,2,4] [-2,0,2,4]
ConvertToRangeRep(A); A [-2,0..4]
A:=[1,2,3,4,5,6]  
Unbind(A[3]); A [1,2,,4,5,6]
B:=[1..7]  
Unbind(B[3]); B [1,2,,3,4,5,6,7]

 

A:=[(1,2,3),(1,4,6),,,(2,3,4)];;
p:=();;
for x in A do
   p:=p*x;
od;
p;

(1,3,2,4,6)

for var in list do statements od;
for var in range do statements od;
while condition do statements od;

Product ([1..7]); 5040
Sum([1..7]); 28
  Product([1..7],f) = Product(List([1..7],f))
  Sum([1..7],f) = Sum(List([1..7],f))
Product ( [(1,2,3),(1,4,6),(2,3,4)] ); (1,3,2,4,6)
Filtered([5,1,8,5], x->x<6); [5,1,5]
ForAll([4,5,6], x->x>2); true

Un vecteur ligne est une liste d'éléments dense à partir d'un champ commun. Une matrice est une liste dense de vecteurs lignes sur un champ commun et de longueur égale.

IsRowVector ([1,2,3]); true
[1,2,3]*[1,2,3]; 14
[1,2,3]*[1,2,3,4]; 14
Display( [[1,2],[3,4]] * One( GF(5) ) );  

Display( [[1,2],[3,4]] ^2 * Z(2) + m * Z(4) );

 

Les sous-matrices : mat{rows}{columns}

m:= [[1,-1, 1],[2, 0,-1],[1, 1, 1]];

[ [1, -1, 1], [2, 0, -1], [1, 1, 1] ]

m{[1,2]}{[2,3]};

[ [ -1, 1 ], [ 0, -1 ] ]
Order(m); infinity
Order(m * One(GF(5))); 8

f:= MinimalPolynomial( Rationals, m );; Factors( f );

[ x_1-2, x_1^2+3 ]

Les enregistrements

A:= rec(toto:=2);

rec(toto:=2)
A.titi = 3;; A; rec(toto:=2, titi:=3)
A.zo = rec(ga:= 0,bu:= 1) rec(toto:=2, titi:=3, zo:=rec(ga:= 0,bu:= 1))

Les fonctions

f:=function()
Print("Hello\n");
end;

function( n ) ... end

Print(f,"\n"); function ( )
    Print( "hello, world.\n" );
    return;
end
f(); Hello
fib:= function(n)
    if n in [1, 2] then
        return 1;
    else
        return fib(n-1) + fib(n-2);
    fi;
end;

function( n ) ... end

fib(15); 610

    function ( arguments ) statements end

    if condition then statements elif condition then statements else statements fi

Les variables locales

cd:= function(a, b)
    local c;
    while b <> 0 do 
        c:= b;
        b:= a mod b;
        a:= c;
    od;
    return c;
end;

function( n ) ... end

gcd(30, 63); 3

A:= function(n)
    local f;
    f:= function(n, m)
        local i, r;
        if n = 0 then return 1; fi;
        r:= 0;
        for i in [1..Minimum(n,m)] do
            r:= r + f(n-i, i);
        od;
        return r;
    end;
    return f(n,n);

end;

 

Les groupes et homomorphismes :

s8 := Group((1,2), (1,2,3,4,5,6,7,8));

Group([ (1,2), (1,2,3,4,5,6,7,8) ])

a8 :=DerivedSubgroup( s8 );

Group([ (1,2,3), (2,3,4), (2,4)(3,5), (2,6,4), (2,4)(5,7), (2,8,6,4)(3,5) ])    // le sous-groupe dérivé = [G,G]
aa8 := CommutatorSubgroup( s8, s8 ); Group([ (1,3,2), (2,3,4), (2,3,5), (2,3,5,4,6), (2,3)(4,6,5,7), (2,4)(5,7,6,8) ])
a8 = aa8; true

Size( a8 );
IsAbelian( a8 );
IsPerfect( a8 );

20160
false
true

IsNaturalAlternatingGroup (a8);

true
a8 Alt( [ 1 .. 8 ] )
s3 := SylowSubgroup( a8, 3 );
s5 := SylowSubgroup( a8, 5 );
ComputedSylowSubgroups(a8);

Group([ (1,2,3), (4,5,6) ])
Group([ (4,7,5,8,6) ])
[ 3, Group([ (3,6,8), (4,5,7) ]), 5, Group([ (4,7,5,8,6) ]) ]

Normalizer(a8,s3);
Centralizer(a8, Centre (s3) );
DerivedSeries( s3);
IsElementaryAbelian (a8);     false

SetName(a8, "<groupe symétrique à 8 éléments>");
a8;       <groupe symétrique à 8 éléments>
h := NaturalHomomorphismByNormalSubgroup(G,H)    <action epimorphism>
A := Image(h);
B := Kernel( hom );

IsSubgroup(a8,s3);   true
GroupHomomorphismByImages( G, H, gens, imgs )

Espace vectoriel et Algèbre

F:= Rationals;;
V:= VectorSpace( F, [ [ 1, 1, 1 ], [ 1, 0, 2 ] ] );
[ 2, 1, 3 ] in V;
Rationals
<vector space over Rationals, with 2 generators>
true
F:= GF( 7 );
V:= F^3;
[ 1, 2, 3 ] * One( F ) in V;
GF( 7 )
( GF(7)^3 )
true
m1:= [ [ 1, 2 ], [ 3, 4 ] ];; m2:= [ [ 0, 1 ], [ 1, 0 ] ];;
V:= VectorSpace( Rationals, [ m1, m2 ] );
m1+m2 in V;

<vector space over Rationals, with 2 generators>
true
W:= Rationals^[3,2];
[ [ 1, 1 ], [ 2, 2 ], [ 3, 3 ] ] in W;
( Rationals^[ 3, 2 ] )
true
IsVectorSpace( Rationals ); true

...

Domaines

AsList(a8);     // liste les élémnts du domaine a8
AsSortedList(a8);     // liste ordonnée les élémnts du domaine a8

g := Group( (1,2), (3,4) );;
h := Group( (3,4), (5,6) );;
Intersection( g, h );       Group([ (3,4) ])

k := ClosureGroup(g, (1,7));;

 


keys:=SortedList( GAPInfo.Keywords );


[ "Assert", "Info", "IsBound", "QUIT", "TryNextMethod", "Unbind", "and", "break", "continue", "do", "elif", "else",
"end", "false", "fi", "for", "function", "if", "in", "local", "mod", "not", "od", "or", "quit", "rec", "repeat",
"return", "then", "true", "until", "while" ]

IsBound(x)    // Retourne true si x a une valeur
Unbind(x)    // Supprime la valeur x

IsReadOnlyGlobal( name )
MakeReadOnlyGlobal( name )
MakeReadWriteGlobal( name )

a@toto      // Variable "a" de l'espace de nom "toto"

 

repeat statements until bool-expr;

 
CallFuncList(\+, [6, 7]);
\+(6, 7);

 

Display ( )     // Affiche de bel façon
ViewObj( )     // Bref et concis
PrintObj( )    // Complet et lisible par GAP

DisplayString ( )
ViewObjString( )     // Bref et concis
PrintObjString( )    // Complet et lisible par GAP
String( )

View( a1,a2,a3...)
Print(a1,a2,a3...) CH12
MemoryUsage(a)    // Quantité de mémoire utilisé par l'objet