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)

Les commentaires sur une ligne commencent par un dièze #.
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("C:/gap/ProgDom/essai.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]]
IsSortedList ([1,5,8]) true    // Liste triée avec éventuellement des doublons
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]
[0,2..10] [0,2..10]
[1,3,5,7,9]=[1,3..9] true
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]

Boucle for :

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

A:=[(1,2,3),(1,4,6),(2,3,4)]; [(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)
p:=(); for x in A do p:=p*x; od; p; (1,3,2,4,6)

Somme et produit :

Product ([1..7]) 5040
Sum([1..7]) 28
F:=x->x*x ;;  
Product([1..7],f) = Product(List([1..7],f)) true
Sum([1..7],f) = Sum(List([1..7],f)) true
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

Vecteur et matrice :

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

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

function ( arguments ) statements end

if condition then statements elif condition then statements else statements fi

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

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;; Rationals
V:= VectorSpace( F, [ [ 1, 1, 1 ], [ 1, 0, 2 ] ] ); <vector space over Rationals, with 2 generators>
[ 2, 1, 3 ] in V; true
F:= GF( 7 ); GF( 7 )
V:= F^3; ( GF(7)^3 )
[ 1, 2, 3 ] * One( F ) in V; true
m1:= [ [ 1, 2 ], [ 3, 4 ] ];; m2:= [ [ 0, 1 ], [ 1, 0 ] ];;  
V:= VectorSpace( Rationals, [ m1, m2 ] ); <vector space over Rationals, with 2 generators>
m1+m2 in V; true
W:= Rationals^[3,2]; ( Rationals^[ 3, 2 ] )
[ [ 1, 1 ], [ 2, 2 ], [ 3, 3 ] ] in W; 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...)
MemoryUsage(a)    // Quantité de mémoire utilisé par l'objet