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 : Un noyau, écrit en C, qui fournit à l'utilisateur: La gestion de la mémoire Un ensemble de fonctions de base, rapide, sur les entiers, les corps finis, les permutations, les mots, les listes et les collections. Un interprète pour le langage GAP, impératif et orientée objet. Des fonctions systèmes permettant de gérer les fichiers et d'exécuter des programmes externes. Un ensemble d'outils de programmation pour les tests, débogage, et synchronisation. Une interface "lecture-évaluation-vue" utilisateur. 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. 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). 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. * Dans la fenêtre ce cmd on fait : C:\GAP4R4\bin>gap 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 : ---------------- a + b ; # addition a - b ; # soustraction a * b ; # multiplication a / b ; # divison a mod b ; # modulo a^b ; # puissance ex: ((10^16)-1) mod 17 ;# ==> 0 #th Fermat * Test : -------- a = b ; a <> b; a < b; a > b; a <= b; a >= b; not , and , or 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) ; #pgcd 3 Lcm(20,30); #ppcm 60 Print(1234, "\n") ; '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) ;# p(5) 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; (3,2,1) = (1,3,2) Permutation inverse 2^(1,2,3); # p(2) 3 Image de 2 par la permutation (1,2,3) (1,2,3)^(2,4,3); #p^q = q^-1*p*q (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 : -------------- var := expr; a:= 3*2 ; local a ; # à l'intérieur d'une fonction 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 : ----------- nom_fonct := function( var ) statements ; return resultat ; end ; appel : nom_fonct (var) ; 1) sign := function(n) if n < 0 then return -1; elif n = 0 then return 0; else return 1; fi; end; sign(0); ==> 0 sign(-99); ==> -1 sign(11); ==> 1 2) f := function(x) return x^3 ; end; f(5); ==> 125 3) fib := function ( n ) local f1, f2, f3, i; f1 := 1; f2 := 1; for i in [3..n] do f3 := f1 + f2; f1 := f2; f2 := f3; od; return f2; end ; * 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 : ------------ list := ['a', 'b', 'c', 'd']; for var in list do statements ; od; for k in [1..15] do statements ; od; s:=0; for i in [1..100] do s := s + i; od; A := [ 1, 2, 3, 4, 5, 6 ];; for i in A do Print( i, " " ); if i mod 2 = 0 then Add( l, 3 * i / 2 ); fi; od; A:=[(1,2,3),(1,4,6),(2,3,4)]; p:=(); #()=id for x in A do p:=p*x; od; p; for k in [1..10] do statements ; od; * Boucle while : -------------- while condition do statements ; od; while s <= 200 do i := i + 1; s := s + i^2; od; Somme et produit : ------------------ Sum(E,f(x)) = sommer sur f(x) pour x€E f(x)=x² <=> f := x->x*x Product(E,f(x)) = produit sur f(x) pour x€E f(x)=x² <=> f := x->x*x Product ([1..7]) ; Sum([1..7]) ; f := x->x*x ;; 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)] ); Filtered([5,1,8,5], x->x<6); ForAll([4,5,6], x->x>2); * 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)) * if ... then : ----------------- if condition then statements ; else statements ; fi ; if i<0 then a:=-i; else a:=i; fi; if i < 0 then # if i is negative a := -i; # take its additive inverse else # otherwise a := i; # take itself fi; * Les fonctions : --------------- f := function ( var ) local s; statements ; s:= ... ; return s ; end ; f:= function ( ) Print( "hello, world.\n" ); return; end ; fib:= function(n) if n in [1, 2] then return 1; else return fib(n-2) + fib(n-21); fi; end; * 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; 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)); a8 := DerivedSubgroup( s8 ); // le sous-groupe dérivé = [G,G] aa8 := CommutatorSubgroup( s8, s8 ); a8 = aa8; Size( a8 ); IsAbelian(a8); IsPerfect(a8); false true IsNaturalAlternatingGroup (a8); a8 Alt( [ 1 .. 8 ] ) s3 := SylowSubgroup(a8,3); s5 := SylowSubgroup(a8,5); ComputedSylowSubgroups(a8); Normalizer(a8,s3); Centralizer(a8, Centre (s3) ); DerivedSeries( s3); IsElementaryAbelian (a8); SetName(a8, ""); a8; h := NaturalHomomorphismByNormalSubgroup(G,H) 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 ] ] ); [ 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 ] ); 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 ===============