Uma Introduç ˜ao ao GAP - Faculdade de Ciências
Contents
1. 18 5 4 7 2 12 O exemplo seguinte destina se a chamar a aten o para as fun es ShallowCopy faz uma c pia do primeiro n vel e StructuralCopy faz realmente uma c pia gap gt lista 1 2 1 2 gap gt k lista 1 2 J gap gt k 1 3 3 Sabe o que se passou com lista gap gt lista SS A i gap gt registo rec vertices 1 2 3 gt arestas 1 2 2 3 rec vertices ly 2 4 S y cartestas ta PT I 2 da 2 Bo gap gt cpl ShallowCopy registo rec vertices 1 2 3 Ty arestas x9 Eli Ze L2 3 1 gap gt cp StructuralCopy registo rec vertices 1 2 3 arestas L 1 2 2 3 1 gap gt cp2 vertices Le 3 gap gt cp2 vertices l 3 3 gap gt registo rect vertices 1 2 3 arestas 1 2 2 3 gap gt cpl arestas cpl vertices 1 5 gap gt cpl rec vertices 5 2 3 arestas gap gt registo rec vertices 5 2 3 arestas 1 2 2 31 8 1 Primeiros passos 1 3 Share packages As share packages GAP s o escritas num formato pr prio o qual an logo ao do pr prio GAP Cont m obrigatoriamente um direct rio doc com documenta o sendo o manual escrito em TEX Um direct rio gap contendo os algoritmos e um ficheiro README bem como outros contendo informa es sobre a vers o etc s o tamb m obrigat rios Como uma forma de encorajar os trabalhos GAP2. r ImplicitOperationOnnLetters 2 product 0 gt ImplicitOperationOnnLetters 2 0 1 gt ImplicitOperationOnnLetters 2 omegapower 5 2 xy w 5 gap gt ImplicitOperationOnnLetters 2 power 3 r xy w 5 3 Podem tamb m de modo an logo ao j feito com as express es racionais ser constru das opera es impl citas usando as fun es indicadas no exemplo a seguir 24 3 Semigrupos fi nitos gap gt OmegaPowelOp PowelOp Product 10p r r 7 3 xy w 5 xy w 5 7 w 3 Uma pseudoidentidade uma igualdade formal de opera es impl citas Uma pseudoidenti dade v lida num semigrupo finito se para qualquer substitui o das vari veis por elementos do semigrupo um por cada vari vel se obtiver uma igualdade Tal como as variedades no sentido de Birkhoff s o definidas por identidades as pseudovariedades de grande import ncia no estudo dos semigrupos finitos s o definidas por pseudoidentidades Nalguns casos ser capaz de testar pseudoidentidades basta para poder concluir da perten a ou n o de um semigrupo a uma pseudo variedade Podemos usar o GAP para testar pseudoidentidades gap gt wl ImplicitOperationOnnLetters 1 omegapower 1 1 x w 1 gap gt w2 ImplicitOperationOnnLetters 1 omegapower 0 1 X w gap gt CheckPseudoIdentity popi4 w1 w2 false gap gt CheckPseudoIdentity poi4 w1 w2 true Este exemplo n o testa mais que a aperiocidade ou n
3. 2 Z 0 8 Z 18 2 Aut omatos e linguagens racionais No meu trabalho tenho tido varias vezes necessidade de calcular a imagem comutativa da linguagem de um aut mato a qual um conjunto semilinear bem como o seu fecho profinito um conjunto Z semilinear gap gt aut Automaton det 5 2 1 2 4 2 1 1 1 1 5 1 3 2 3 4 5 do i384 5 a L 2 4 2 1 b p XS i d bd Initial state 3 Accepting states 2 3 4 5 gap AutomatonToRatExp aut 1UabUa 1Uaa gap LanguageCom aut imagem comutativa L do o E03 0p E70 po GL 2 Og Le S30 ey ON Jy N fecho da imagem comutativa qp ege 29 a gap LanguageAb aut 1 1 0 0 Capitulo 3 Semigrupos fi nitos Neste cap tulo falo de uma share package qual presentemente dou o nome de finsemi e que tal como a share package automata est em desenvolvimento Ela cont m desde j alguma documenta o que pode ser usada para completar alguns detalhes omitidos nete cap tulo e destina se a lidar com semigrupos finitos Espero n o perder nesta fase os leitores menos habituados linguagem dos semigrupos pois a maior parte das coisas que vou dizer s o perfeitamente gerais e o leitor pode facilmente imaginar exemplos na sua rea preferida Para motiva o e teoria sugiro a bibliografia Al D 98 D DF 3 1 Alguns mon ides J no primeiro cap tulo indiquei duas possibilidades para dar um mon ide Lembro que Bl ver
4. 9 2 1 16 7 8 9 10 1 2 3 4 5 6 7 8 9 10 a 7 5 7 5 4 9 10 9 10 9 b 8 6 8 9 9 1 3 1 9 9 Initial state 2 Accepting states 6 7 8 9 10 gap AutomatonToRatExp A b b aUb U aa bUb b aUb a aUb A forma relativamente simplificada desta express o deve se ao facto de a fun o AutomatonToRa tExp come ar por minimalizar o aut mato A 2 3 3 Conjuntos semilineares Os subconjuntos racionais do mon ide comutativo livre N s o os subconjuntos semilineares isto uni es finitas de subconjuntos da forma a b N 4 bpN com a b1 bp N aos quais se chama lineares O fecho profinito i e para a topologia profinita em Z de a b N bpN a b Z bpZ A uma uni o finita de subconjuntos desta forma ditos Z lineares chamo conjunto Z semilinear Note se que os subconjuntos Z semilineares s o uni es finitas de classes laterais de subconjuntos de Z O conjunto linear 0 1 1 2 N4 5 2 N pode ser dado do seguinte modo gap gt LN NLinear 2 0 1 1 2 Lu db o uwebduz N dw p5 SN Se quiser dar o conjunto Z linear 0 1 1 2 Z 5 2 Z obtenho um resultado diferente gap gt LZ ZLinear 2 0 1 Og Jo Ar lt 2 24 be PO Be Phe Observo que a matriz a forma normal hermitica da matriz logo o conjunto 1 1 2 0 8 5 2 1 2 0 8 gera precisamente o mesmo subgrupo de Z que 1 2 5 2 donde 0 1 1 2 Z 5 2 Z 0 1 1
5. GroupKernel pode por vezes ser til Conv m no entanto observar que isto n o desliga por exemplo o guardar autom tico do atributo Idempotents N o ter dificuldade em constat lo usando o comando KnownAttributesOfObject objecto Acima n o vimos qual a resposta dada por GroupKernel popi4 Garanto que nem para os semigrupistas interessante Bem mais interessante para estes poder ser saber da distribui o dos elementos do n cleo por D classes gap gt GroupKernelWithDClassInfo poi4 lista dos elementos do n cleo The D class of Transformation 1 5 has 1 element which is in K The D class of Transformation L2 35 555 has 16 elements 4 of which are in K The D class of Transformation ls Dc 5 has 36 elements 6 of which are in K The D class of Transformation Zy Dy Baz 5 5 has 16 elements 4 of which are in K The D class of Transformation Ox Oy Dg DB has 1 element which is in K O c lculo do n cleo Abeliano de um mon ide finito que tem servido de motiva o para muito do meu trabalho usando o algoritmo de que disponho bastante demorado Gosto por isso de ir sendo informado daquilo que o computador est a fazer Criei para o efeito as classes de informa o InfoKernel e InfoBasic que inclu com v rios n veis nos meus programas Num pro grama posso por exemplo escrever a seguinte linha Info InfoKernel 2 I am computing the right Cayley graph of lt M g
6. generators a b gt gap a GeneratorsOfMonoid f 1 tenho de dar nomes aos geradores a gap gt b GeneratorsOfMonoid f 2 gap r a 3 a 2 a 2 b a 2 gt b a 2 a 2 gt b 2 a 2 gt m a gt a b b a 3 a ae a 2 b a 2 b a 2 a 2 b 2 a 2 a bta a b a b b gap b21 f r fp semigroup on the generators identity gt a b gt gap gt GreensDClasses b21 lt identity gt a a 2 J gap gt Size b21 6 Se quisesse saber quanto tempo de processador tinha demorado esta ltima opera o o c lculo da ordem do mon ide gap gt time 3310 H outras maneiras de dar mon ides gap gt g0 Transformation 3 1 Transformation 3 1 3 3 gap gt gl Transformation 2 3 3 3 Transformation 2 3 1 gap gt poi2 Monoid g0 gl1 lt monoid with 2 generators gt gap gt g Transformation 2 1 3 Transformation 2 1 3 gap gt popi2 Monoid g 91 90 lt monoid with 3 generators gt gap DisplayEggBoxOfDClass GreensDClassOfElement popi2 90 0 1 1 0 1 2 Exemplos 7 gap gt Size popi2 7 gap gt time 110 Outro exemplo gap gt mat 18 5 4 7 2 12 18 53 de 7 2 12 gap gt HermiteNormalFormIntegerMat mat 2 0 0 1 0 0 Em particular 2 0 0 1 uma base para o subgrupo de Z gerado pelo conjunto de vectores
7. h presentemente a possibilidade de serem submetidos pacotes GAP os quais passam por um sistema de referee an logo ao de uma revista cient fica 1 4 Oficheiro gaprc Quando numa sess o GAP se pretendem usar share packages deve usar se a op o l para indicar onde que as share packages est o colocadas Tenho no meu ficheiro bashrc o seguinte alias alias gap4 home gap4r2 bin gap sh 1 home gap4r2 home mdelgado aut semi que me permite carregar em todas as sess es os pacotes automata e finsemi previamente colocados em aut semi pkg Ao iniciar uma sess o GAP o ficheiro gaprc dos primeiros a ser lido Indico a t tulo de exemplo o gaprc que eu tenho presentemente Change the variable EDITOR works in gap3 but not in gap4 EDITOR usr bin emacs nw packages RequirePackage automata RequirePackage finsemi read examples Read home mdelgado aut semi ex finsemi Read home mdelgado aut semi ex automata tabbreviations rcg RightCayleyGraph Capitulo 2 Aut matos e linguagens racionais Num sistema como o GAP h sempre algo que seria desej vel ter implementado mas ainda n o est Poder amos gostar de ter dispon veis implementa es de outros algoritmos para lidar com objectos j existentes por exemplo semigrupos ou mesmo ter dispon veis objectos novos Neste cap tulo vamos ver como criar um objecto que para j n o faz parte do GAP um aut mato Obviame
8. nl and IsPosInt n2 or n2 lt nl then Error lt nl gt e n2 devem ser inteiros positivos com nl lt n2 fis variavel 1 L for i in nl n2 do Info InfoTeste 1 vVou calcular o factorial de i n k fac i uso a funcao fac anteriormente escrita Info InfoTeste 2 Agora vou factoriza lo n Info InfoTudo 2 Ja calculei variavel factoriais n Info InfoTudo 1 O factorial de i n PrintFactorsInt k Print An UniteSet L FactorsInt k variavel variavel 1 od return L end Bibliografi a Al J Almeida Finite Semigroups and Universal Algebra World Scientific Singapore 1995 BL T Breuer e S Linton The GAP4 Type System Organizing Algebraic Algorithms in Proce edings of ISSAC 1998 ACM Press D 98 M Delgado Abelian pointlikes of a monoid Semigroup Forum 56 1998 339 361 D M Delgado Commutative images of rational languages and the Abelian kernel of a monoid in preparation 2001 DF M Delgado and V H Fernandes Abelian kernels of some monoids of injective partial transformations and an application Semigroup Forum 61 2000 435 452 GAP The GAP Group GAP Groups Algorithms and Programming Version 4 2 Aachen St Andrews 1999 http www gap dcs st and ac uk gap dG W de Graaf GAP4 nice and easy Universidade de St Andrews manuscrito H amp U J E Hopcroft e J D Ullman
9. o dos semigrupos em causa A fun o IsAperiodic faz precisamente isto Exercicios 1 Escreva um programa em GAP que lhe permita encontrar a lista das factoriza es em pri mos dos factoriais dos inteiros entre dois inteiros positivos n e n dados N o se esque a que o programa deve testar por exemplo se n e n2 s o inteiros positivos Crie algumas classes de informa o que lhe permitam se o desejar ir conhecendo resultados parciais bem como saber quais os c lculos que o computador est a realizar 2 Proponha e resolva um exerc cio an logo ao anterior substituindo o c lculo de factoriais bem como a factoriza o de inteiros por outras opera es 3 Quais s o os objectos com que mais trabalha Se eles j existem no GAP tamb m j existem no GAP implementa es dos algoritmos que mais usa Se alguma das respostas negativa seria capaz de mudar a situa o Na p gina seguinte proponho uma poss vel solu o para o primeiro exerc cio Os outros ficam ao cuidado do leitor o qual pode para o terceiro exerc cio e dentro das minhas limita es contar com a minha ajuda 25 26 Exerc 1 cios Uma poss vel solu o do primeiro exerc cio DeclareInfoClass InfoTeste DeclareInfoClass InfoTudo HERE RE REE EERE RE RERERERE EERE REREE EEE EEE EEE EEE EREREREE EGE AE ARE RE EE EEE F t F teste t t teste function nl n2 local i k L variavel if not IsPosInt
10. operativos UNIX MS DOS MacOS eu uso habitualmente o Linux e poder nalguns casos ser necess rio fazer adapta es s quais n o me refiro Al m dos manuais do GAP GAP foram de grande utilidade para a elabora o destas notas os trabalhos BL dG Hu 1 1 Como come ar A p gina web do GAP que aqui referirei v rias vezes tem o endere o http www gap dcs st and ac uk gap O GAP consiste de um n cleo uma livraria bases de dados share packages e documenta o O n cleo est escrito em C e cont m entre outras coisas um interpretador da linguagem GAP e por quest es de efici ncia as rotinas mais frequentemente utilizadas A livraria est escrita em GAP e cont m a quase totalidade dos algoritmos Entre as bases de dados existe por exemplo uma de grupos de pequena ordem Existem ou est o em prepara o share packages que cont m algoritmos envolvendo grupos polic clicos grupos autom ticos ou bases de Gr bner por exemplo 2 1 Primeiros passos A linguagem de programa o GAP tipo PASCAL de muito alto nivel est pr xima da linguagem que n s falamos O C embora do mesmo tipo de mais baixo n vel est mais pr ximo da linguagem m quina A instala o do GAP pode em princ pio ser feita em qualquer plataforma sendo tamb m independente do sistema operativo usado Num sistema Linux em parte porque um sistema Linux cont m sempre um compilador de C a instala o essencialment
11. os dois LogTo Outra maneira entrar num editor de texto dentro de uma sess o GAP basta usar a instru o Edit ficheiro com a qual entra por defeito no vi mas eu n o o costumo fazer O que eu costumo fazer escrever os meus programas fora da sess o GAP geralmente em paralelo usando um editor de texto qualquer de facto sempre o mesmo Se pretender escrever os seus programas usando o emacs o meu editor de texto favorito chamo a sua aten o para o facto de existir o gap mode que pode obter a partir da p gina web do GAP e que considero muito til A fun o fac poderia escrev la com o seguinte aspecto note a indenta o feita automaticamente no gap mode fac function n local r f xu for i in 1 n do f f i od return f end no ficheiro fac g Quando quisesse depois utilizar esta fun o e outras escritas no mesmo ficheiro bastaria escrever Read caminho fac g N o precisa de escrever o caminho se fac g estiver no direct rio corrente gap gt Read caminho fac g gap gt fac 13 6227020800 6 1 Primeiros passos O exemplo seguinte envolve o mon ide dado pela apresenta o B4 a b a b 0 aba a bab b E escusado dizer que costumo guardar os exemplos mais complexos que uso com frequ ncia num ficheiro o qual lido usando a fun o Read de que j falei atr s Ver tamb m o ficheiro gaprc na p gina 8 gap f FreeMonoid a b lt free monoid on the
12. p gina 6 dito o mon ide de Brandt com 6 elementos foi dado por meio de geradores e rela es sendo as rela es a b 0 aba a bab b para os geradores a e b O grafo de Cayley direito de um mon ide M com geradores a b um grafo cujos v rtices representam os elementos de M havendo uma aresta de um v rtice x para um v rtice y etiquetada por um gerador g se xg y N o surpreende assim o seguinte gap gt rcg RightCayleyGraph b21 1 2 3 4 5 6 a 2 4 6 4 2 4 b 3 5 4 4 4 3 Initial state Accepting states Os grafos de Cayley s o vistos como aut matos sem estados iniciais nem finais O grafo de Cayley pode ser transformado num aut mato por escolha de um estado final 19 20 gap gt AutCayley rcg 3 1 2 3 4 5 6 a 2 4 6 4 2 4 be oq Ss MA Ads Initial state 1 Accepting state 3 3 Semigrupos fi nitos Mais dois mon ides de transforma es parciais injectivas de um conjunto com 4 elementos o n mero 5 aparece por raz es t cnicas o GAP n o trabalha com transforma es parciais gap gt g0 Transformation 5 1 gap gt gl Transformation 1 2 gap gt g2 Transformation 1 3 gap gt g3 Transformation 2 5 gap gt g Transformation 2 3 4 gap gt poi4 Monoid g0 g1 9g2 93 gap gt popi4 Monoid g Ui 42 4318 gap gt Size poi4 Size popi4 10 141 3 2 N cleos eS Podemos usar o GAP para calcular o n cleo de um mon ide us
13. Introduction to Automata Theory Languages and Compu tation Addison Wesley 1979 Hu A Hulpke Using GAP tutorial dado no ISSAC 2000 27
14. Uma Introdu o ao GAP Notas de um mini curso Manuel Delgado Faculdade de Ci ncias da Universidade do Porto http www fc up pt cmup home mdelgado Vers o de 27 de Setembro de 2004 Contetido Introdu o 1 Primeiros passos 1 1 Como come ar uu sue ss EM ie A 1 2 Exemplos dus Ae pu raios es ed erui 1 3 Share packages 664 6 cs 1 4 HO ficheiro gapre 4 gon Sie Sow Soe oe 2 Aut matos e linguagens racionais 2 1 Um pouco sobre autOmatos 2 2 Como criar novos objectos um exemplo 2 3 Algumas fun es da share package automata 2 3 1 Aut matos osx Roe Rea 2 3 2 Conjuntosracionais 2 3 3 Conjuntos semilineares 3 Semigrupos finitos 3 1 Algunsmon ides 3 2 INNCICOS o Dado Med MEDA BOR edo O ott Mes 3 3 Operac es impl citas Exerc cios Bibliografia iii 10 14 14 16 17 19 19 20 23 25 27 il Introducao Estas notas foram escritas para servir de apoio a um mini curso intitulado Uma Introdu o ao GAP que apresentei em Fevereiro de 2001 no Centro de Matem tica da Universidade do Porto e no Centro de lgebra na Universidade de Lisboa A menos desta introdu o e de alguns pequenos detalhes trata se das notas distribu das no in cio do curso Pretendi neste curso relatar um pouco da minha experi ncia pessoal com o GAP Como acon tece com muitas coisas ligadas aos computadores n o h como mexer nelas para perceber
15. a express o racional bb a claro que express es racionais diferentes podem representar o mesmo conjunto O pacote automata tamb m serve para trabalhar com express es racionais de subconjuntos racionais do mon ide livre tamb m ditos linguagens racionais A express o racional a aUb mostrada com este aspecto em virtude de uma fun o PrintObj pode ser fornecida ao GAP do seguinte modo gap RatExpOnnLetters 2 star RatExpOnnLetters 2 product gt RatExpOnnLetters 2 1 RatExpOnnLetters 2 union gt RatExpOnnLetters 2 1 RatExpOnnLetters 2 2 1D D i a aUb Pode tamb m ser obtida do modo indicado a seguir e que torna f cil a constru o de express es racionais mais complexas gap gt rl RatExpOnnLetters 2 1 a gap gt r2 RatExpOnnLetters 2 2 b gap gt r3 UnionRatExp rl r2 aUb gap r4 ProductRatExp r1 r3 a aUb gap gt r5 StarRatExp r4 a aUb Posso determinar um aut mato que reconhega a linguagem dada por esta express o racional 2 3 Algumas fun oes da share package automata 17 gap RatExpToAutomaton r5 d 20 3 a 13 2 b X b 22 Initial state 2 Accepting state AUN e posso tamb m determinar uma express o racional para a linguagem reconhecida por um aut mato gap gt A Automaton det 10 2 7 5 7 5 r r 4 9 10 9 10 9 gt 8 6 8 9 9 1 3 1 9
16. ade o a oportunidade que me deram de levar a cabo a realiza o deste mini curso Ao V tor H Fernandes agrade o o ter me encorajado A ele e tamb m Helena Sezinando agrade o a organiza o no CAUL Agrade o ainda o financiamento parcial da FCT atrav s do Centro de Matem tica da Uni versidade do Porto e tamb m do Projecto SAPIENS 32817 99 iii iv Capitulo 1 Primeiros passos O GAP Groups Algorithms and Programing come ou por ser um sistema computacional para lidar com grupos mas tem sido estendido em v rias outras direc es Basta olhar para o ndice do manual e para o grande n mero de pacotes share packages que t m surgido para nos apercebermos disso O GAP tem sido utilizado na realiza o de muitos trabalhos de investiga o como o atesta a grande quantidade de cita es em artigos cient ficos ver http www gap system org Doc Bib bib html Tem tamb m sido usado no ensino especialmente para ensinar Teoria de Grupos Devo acrescentar que o GAP gratuito distribu do com as regras habituais para evitar o seu uso comercial Come ou a ser desenvolvido em 1984 em Aachen na Alemanha tendo o seu centro de desenvolvimento sido transferido para St Andrews na Esc cia em 1987 H pessoas a trabalhar no GAP um pouco por todo o mundo Estas notas escritas na primeira pessoa baseiam se na minha experi ncia pessoal com o GAP Devo advertir o leitor de que embora o GAP corra nos v rios sistemas
17. ando GroupKernel bem co nhecido dos semigrupistas pe o aos que o n o s o para imaginarem outro exemplo que h casos em que o n cleo de um mon ide pode ser calculado de forma muito eficiente quando os idempo tentes comutam por exemplo Assim para a opera o GroupKernel podemos ter um m todo para calcular o n cleo de um mon ide cujos idempotentes comutam facto que pode eventualmente ja ser conhecido do pr prio mon ide e outros m todos mais gerais O GAP escolhe depois o m todo mais adequado Posso escrever a opera o GroupKernel a qual pretendo que seja um atributo com o seguinte aspecto GroupKernel NewAttribute GroupKernel IsSemigroup tt InstallMethod GroupKernel for finite semigroups true function M local nwcl if not HasCommutingIdempotents M then TryNextMethod fais return Semigroup GeneratorsOfIdempotents M end IsSemigroup 1 3 2 Nucleos 21 InstallMethod GroupKernel for finite semigroups true IsSemigroup 0 function M end Agora um exemplo gap gt GroupKernel popi4 gap gt time 570 gap gt GroupKernel popi4 gap gt time 0 Pelo facto de ser um atributo o n cleo de um mon ide uma vez calculado colocado no saco e durante a sess o GAP a decorrer n o h necessidade de o calcular de novo claro que guardar todas estas informa es consome mem ria pelo que o comando DisableAttributeValueS toring
18. como funcionam Nesse sentido as notas come am com um cap tulo verdadeiramente introdut rio e que tem como objectivo fazer com que o leitor n o deixe de experimentar por ter dificuldades por exemplo na instala o do GAP no seu computador Embora a partir da os exemplos possam em geral parecer muito especializados nenhuma parte do texto foi escrita a pensar apenas em especialistas de alguma rea espec fica No segundo cap tulo falo de aut matos Porqu aut matos O leitor n o deve esquecer que tenho como objectivo relatar a minha experi ncia pessoal Pretendo na segunda sec o ilustrar a cria o de um objecto novo Fazendo altera es m nimas poderia dizer que estava a falar de qualquer outra coisa Deve sentir se encorajado a criar outros objectos do seu interesse e que ainda n o fa am parte do GAP Depois falo de fun es que fazem parte de uma share package em desenvolvimento e que se destina essencialmente a lidar com aut matos Pretendo ilustrar a utiliza o de objectos rec m criados No terceiro cap tulo falo de fun es que fazem parte de uma outra share package em desenvol vimento e que se destina a lidar com semigrupos finitos Os semigrupos s o objectos que j fazem parte do GAP Este cap tulo aproveitado para ilustrar alguns aspectos teis do GAP Por fim os inevit veis exerc cios Agradecimentos Aos Centro de Matem tica da Universidade do Porto CMUP e Centro de lgebra CAUL agr
19. da share package automata onde estes objectos s o criados Come o por escolher uma representa o neste caso um registo em que os campos s o type states etc DeclareRepresentation IsAutomatonRep IsComponentObjectRep type states alphabet transitions initial accepting Depois construo a fam lia de todos os aut matos e um tipo F NewFamily Automata IsAutomatonObj T NewType F IsAutomatonObj and IsAutomatonRep Posso agora usar a fun o Objectify o que vou fazer dentro da fun o global Automaton que indico a seguir omitindo o que nao me parece essencial nesta fase InstallGlobalFunction Automaton function Type Size SizeAlphabet 2 2 Como criar novos objectos um exemplo 11 5 TransitionTable ListInitial ListAccepting local A aut some tests if not IsPosInt Size and IsPosInt SizeAlphabet and IsMatrix TransitionTable and IsList ListInitial and IsList ListAccepting then Error you must give the specifications of an automaton fas aut rec type Type alphabet SizeAlphabet states Size initial ListInitial accepting ListAccepting transitions TransitionTable A Objectify T aut Return the automaton return aut end Posso agora construir um aut mato do modo seguinte gap aut Automaton det 4 2 3 3 4 3 4 0 41 1 4 O modo como este objecto impresso depende da f
20. e trivial Podem obter se a partir da p gina do GAP n cleos compilados i e j traduzidos para a linguagem m quina para outros sistemas operativos A instala o completa do GAP gap4r2 sem share packages ocupa presentemente cerca de 150 Mb de mem ria mas podem fazer se instala es que ocupam bastante menos espa o Para fazer a instala o deve come ar por obter o ficheiro gap4r2 zoo ou o basic4r2 zoo se quiser instalar apenas o essencial e ocupar assim menos espa o e caso n o o tenha feito ainda o ficheiro unzoo c Estes ficheiros podem ser obtidos sem dificuldade a partir da p gina do GAP O leitor n o deve ficar surpreendido se n o encontrar o ficheiro gap4r2 zoo mas o gap4r3 zoo ou outro posterior em seu lugar Vou supor que a instala o vai ser feita no direct rio caminho que cont m os ficheiros unzoo c e gap4r2 zoo e onde desde j nos encontramos i e caminho o direct rio corrente O unzoo c precisa de ser compilado o que pode ser feito executando caminho gt cc o unzoo DSYS IS UNIX O unzoo c Para descompactar o gap4r2 deve fazer caminho unzoo x gap4r2 zoo gap4r2 doc aboutgap tex extracted as text muitas linhas parecidas com esta caminho Depois deve fazer caminho cd gap4r2 caminho gap4r2 gt configure checking host system type i686 unknown linux2 0 27 muitas linhas mais Depois caminho gap4r2 make Fazendo agora caminho gap4r2 bin gap sh gap inicia
21. los de palavras reconhecidas pelo aut mato j que s o r tulos de caminhos que v o do estado inicial ao estado final O conjunto das palavras nestas condi es diz se a linguagem do aut mato O aut mato do exemplo anterior ou o grafo que lhe est subjacente est intimamente relacio nado com as transforma es que as letras a e b induzem no conjunto dos v rtices 123 a 3 2 b 2 2 1 Estas transforma es geram um submon ide dito mon ide de transi es do aut mato do mon ide das transforma es do conjunto dos estados do aut mato em si pr prio com a opera o de composi o Existe uma extensa bibliografia onde pode encontrar muito sobre aut matos Escolho H amp U para lhe sugerir 2 2 Como criar novos objectos um exemplo Nesta sec o digo como criar um objecto chamado Automaton O nome est para aut mato o qual pode ou n o ser determin stico Lembro que estes objectos correspondem ao estado actual de uma vers o preliminar daquilo que poder vir a ser uma share package sobre aut matos Em GAP um objecto come a por ser um saco capaz de conter informa o criado usando a fun o Objectify Atendendo a que para o uso comum do GAP n o h qualquer necessidade de saber como os objectos s o criados n o vou entrar em grandes detalhes limitando me a indicar uma maneira de criar um objecto que se espera possa comportar se como um aut mato As linhas que se seguem s o praticamente retiradas
22. nte o leitor n o est dispensado da consulta dos manuais se quiser criar os seus pr prios objectos Em particular o programmer s tutorial cont m exemplos de ndole um pouco diferente do aqui apresentado Pode tamb m ser muito til o trabalho dG de Willem de Graaf a cuja p gina pessoal pode aceder via a p gina do GAP a qual cont m tamb m apontadores para p ginas de diversos outros autores Este cap tulo baseia se numa vers o muito preliminar daquilo que poder vir a ser uma share package sobre aut matos e qual dou o nome automata Esse pacote j conta com alguma documenta o que poder ser utilizada para completar certos detalhes Procurarei manter informa o actualizada sobre esse trabalho no direct rio gap aut semi da minha p gina web 2 1 Um pouco sobre aut matos Um aut mato pode muitas vezes ser descrito por um diagrama como o que se segue a Este exemplo descreve um aut mato com 3 estados precisamente os elementos do conjunto 1 2 3 A seta a apontar para o estado 1 indica que 1 um estado inicial e a seta a sair do estado 9 10 2 Aut omatos e linguagens racionais 3 indica que 3 um estado final O conjunto a b o alfabeto do aut mato i e o conjunto das letras que podem ser etiqueta de alguma aresta Trata se de um aut mato determin stico j que n o existem duas arestas etiquetadas pela mesma letra a sair de um estado As palavras ba ba a aba e bb a com n N s o exemp
23. rmation 1 5 has 1 element which is in K The D class of Transformation T 2p Apos has 16 elements 4 of which are in K The D class of Transformation 135 293 5959 has 36 elements 36 of which are in K The D class of Transformation 25 5 B by 5 has 16 elements 16 of which are in K The D class of Transformation D D dia ge i has 1 element which is in K Posso agora querer saber mais alguma coisa acerca destes n cleos abelianos gap IsAperiodic AbelianKernel poi4 true gap IsAperiodic AbelianKernel popi4 false Pensava se que os n cleos abelianos dos mon ides de uma certa classe qual popi4 pertence fossem todos aperi dicos O ltimo exemplo mostra que n o Ver DF 3 3 Operacoes impli citas As nicas opera es impl citas aqui consideradas s o as palavras tamb m ditas opera es expl citas e as que envolvem pot ncias w k com k inteiro Devo observar que s o quase ex clusivamente estas as opera es impl citas que aparecem na literatura N o entro em detalhes observo apenas que se x um elemento de um semigrupo finito S ent o x o nico idempotente do subsemigrupo gerado por x O significado de x para k positivo bvio sendo n o t o bvio para k negativo digo apenas que se S for um grupo ent o x o inverso de x Pode encontrar toda a teoria em Al Uma opera o impl cita pode ser dada do modo seguinte gap
24. ssim mesmo sem entrar em detalhes sobre o resultado produzido pela fun o SylowSubgroup n o ficamos surpreendidos com o resultado seguinte gap gt Size SylowSubgroup s8 3 9 Os nomes das fun es que fazem parte do GAP come am sempre por mai sculas e s o em geral muito compridos A edi o tem muitas semelhan as com a edi o de comandos em UNIX ou em EMACS Considero particularmente til o facto de a t cnica de pressionar a tecla tab para completar os nomes dos comandos tamb m funcionar aqui gap gt Sylows Pressionando agora tab obt m se SylowSubgroup SylowSubgroupOp SylowSubgroupPermGroup SylowSystem gap gt Sylows O GAP tamb m uma linguagem de programa o Para evitar dar nomes que fazem parte do GAP as suas fun es basta come los por letras min sculas Pode escrever do modo seguinte um programa que lhe permite calcular o factorial de um n mero natural 1 2 Exemplos 5 gap fac function n local i f f 1 for i in 1 n do f f i od return f end function n end gap fac 10 3628800 gap fac 8 40320 MM MM MM OM Os programas assim escritos perdem se quando se termina a sess o Como evitar isso Uma maneira de guardar parte de numa sess o num ficheiro com endere o trabalho ficheiro fazer gap gt LogTo trabalho ficheiro tudo isto guardado gap gt LogTo ficando ent o guardado em ficheiro tudo o que se passar entre
25. t n 22 3 Semigrupos fi nitos Posso mudar o InfoKernel para o n vel 1 escrevendo SetlnfoLevel InfoKernel 1 Se escrever info n mudo as duas classes que referi para o nivel n por defeito tenho o n vel 1 passando ent o a ser dadas todas as informa es de n veis n o superiores a n gap gt AbelianKernel popi4 I I am testing whether the element Transformation 1 2 4 5 5 is in the abelian kernel mais linhas lt semigroup with 13 generators Mudando agora o n vel de informa o gap gt info 2 Info Level for InfoKernel and InfoBasic is set to 2 gap AbelianKernel poi4 I I am computing the right Cayley graph of M 1 M has 16 idempotents 1 The G kernel of lt M gt has 16 elements I I am testing whether the element Transformation 1 2 4 5 5 is in the abelian kernel I The minimal automaton associated to it has size 5 mais linhas 1 I am testing whether the element Transformation 1 3 5 5 5 is in the abelian kernel I The minimal automaton associated to it has size 12 1 Yes it is in the abelian kernel I Closing for weak conjugation I found 9 new elements of the 26 elements already found mais linhas lt semigroup with 13 generators 3 3 Operac oes impl 1 citas 23 A muito til distribui o por D classes gap gt AbelianKernelWithDClassInfo poi4 list of elements in the abelian kernel The D class of Transfo
26. t do if IsBound au j and IsBound au j i and 2 2 Como criar novos objectos um exemplo au j i lt gt then Add array i letters j au j il fi od od fi arr List array x gt List x String max Maximum List arr x gt Maximum List x Length Prantq 77s for 1 in 1 Length arr do if 1 gt 1 then Print fi Princ ys for k in 1 Length arr 1 do Print String arri 1 k max 1 if k Length arr 1 then Print 573 else Prrnt ws fi od if 1 Length arr then Print Xn 5 else Print An fi od Print Initial state aut initial Mn if Length aut accepting 1 then Print Accepting state aut accepting An else Print Accepting states aut accepting Mn fi end 14 2 Aut omatos e linguagens racionais Obt m se agora 0 seguinte gap gt aut 1 2 3 4 a 3 3 4 b 3 4 4 Initial state 1 Accepting state 4 Tamb m podemos criar um aut mato nao determin stico gap ndaut Automaton nondet 4 2 3 1 2 3 0 3 4 0 2 3 1 4 1 2 3 4 a b Initial state 1 Accepting state 4 A fun o PrintObj acima prev que possamos querer usar aut matos com muitos estados gap gt aut Automaton det 16 2 4 0 0 6 3 1 4 8 7 4 3 0 6 1 6 0 gt 3 4 0 0 6 1 0 6 1 6 1 6 6 4 8 7 4 5 1 4 1 a 4 1 b 3 2 b 4 23 ou
27. tivamente pressionado em simult neo as teclas ctrl d prompt gt gap gap gt quit prompt gt A utiliza o do manual on line pode ser feita do seguinte modo gap gt group muita informa o Se preferir visualizar a ajuda no Netscape que deve ter previamente aberto pode fazer gap gt SetHelpViewer Netscape The Help function will use netscape gap gt group a informa o mostrada no Netscape 4 1 Primeiros passos Os pedidos de ajuda subsequentes recorrem ao Netscape Se quiser mudar pode ent o escrever SetHelpViewer Screen Esta mudan a pode ser til quando se pretendem usar share packages em fase de desenvolvimento e que j tendo alguma documenta o n o a t m em HTML As instru es GAP terminam sempre com ponto e v rgula e o GAP d sempre uma resposta que por vezes significa muito pouco Quando n o queremos ver a resposta escrevemos em vez de Os exemplos seguintes quase n o precisam de coment rios gap gt s6 Group 1 2 1 2 3 4 5 6 j7 gap gt s8 Group 1 2 1 2 3 4 5 6 7 8 Group 1 2 1 2 3 4 5 6 7 8 gap gt Size s8 40320 gap gt Factorial 8 40320 gap gt IsAbelian s8 false gap gt FactorsInt 40320 25425 2 dp Dip Dip 2h Dye Br BET gap gt PrintFactorsInt 40320 Print Mn 2 3 2 5 Basta olhar para a factoriza o de 40320 para sabermos que os 3 subgrupos de Sylow do grupo sim trico Sg t m ordem 9 A
28. tras linhas 15 b 8 16 b 7 Initial state 1 Accepting state 4 2 3 Algumas fun es da share package automata Nas sec es anteriores j falei um pouco sobre aut matos e inclu alguns exemplos Os exem plos sobre aut matos continuam aqui na primeira subsec o estando as outras duas subsec es dedicadas a conjuntos racionais e semilineares 2 3 1 Aut matos Antes de continuar devo referir que o pacote automata conta desde j com a colabora o de outras pessoas s quais devo grande parte do trabalho de programa o das fun es apresentadas nesta subsec o 2 3 Algumas fun oes da share package automata 15 Cyril Nicaud Universidade de Paris 7 implementou em GAP 3 um algoritmo devido a Hopcroft para reduzir um aut mato determin stico e que facilmente leva produ o de um aut mato minimal Paulo Varandas num trabalho da disciplina de Teoria Alg brica dos Aut matos da licenci atura em Matem tica da Universidade do Porto implementou entre outros um algoritmo para determinizar um aut mato Al m dos exemplos aqui apresentados e que quase n o precisam de coment rios est o j programadas algumas outras fun es Remeto o leitor para o manual do pacote automata gap gt aut Automaton det 4 2 3 3 3 4 3 4 3 4 11 41 l 22 35 24 ai is 903 39 b 3 4 3 4 Initial state 1 Accepting state 4 gap MinimalizeDDAutomaton a
29. uma sess o GAP Antes de dar a instala o por completa deve proceder instala o de eventuais bugfixs se guindo as instru es 1 2 Exemplos 3 O manual Uma instala o completa do GAP inclui diversas vers es do manual TEX DVI PDF HTML e tamb m o manual on line Dizer dos manuais seria mais correcto existem de facto dois tutorials e dois manuais a pensar no utilizador e no programador A impress o do manual de todo desaconselhada o manual do utilizador do gap4r2 tem mais de 800 p ginas Considero a vers o HTML particularmente til Para a consultar basta escrever no seu browser file caminho gap4r2 doc htm index htm Se estiver a usar a vers o HTML do manual pode fazer copy paste para testar os exemplos l apresentados O manual on line particularmente til quando n o se est na presen a de um terminal gr fico 1 2 Exemplos Os exemplos desta sec o destinam se a familiarizar um pouco o leitor com a sintaxe do GAP N o pretendo com eles ilustrar o que se pode fazer com o GAP pois aquilo que eles cobrem absolutamente insignificante Depois de ter o GAP devidamente instalado no seu computador poder come ar uma sess o escrevendo no prompt do seu terminal a palavra gap seguida de um toque na tecla return Quando se entra num programa importante saber como sair dele por isso devo desde j dizer que para terminar a sess o GAP bastar escrever quit seguido de return ou alterna
30. un o HEHEHE HE REE EH HH EEE EH HH RE EE EE HH HE EEE EH RARE EE EEE REE EHH HE REE EH ERE EE EEE RE EEE HHH M PrintObj lt A gt print automata InstallMethod PrintObj special for a deterministic automaton true IsAutomatonObj and IsAutomatonRep 0 function A local au aut 11 12 arr array i j letters max R 1 k S t letters aut A au StructuralCopy aut transitions 12 2 Aut omatos e linguagens racionais for iin 1 Length aut transitions do for j in 1 Length aut transitions 1 do if not IsBound au i j or au i j 0 then au i j 5 fax od od if aut alphabet 5 then for small alphabets the letters a b c d are used letters a bp c d else for i in 1 aut alphabet do Add letters Concatenation a String i od fa 12 array S 14 arr List au x gt List x String max Maximum List arr x gt Maximum List x Length if aut states lt 16 then 11 Concatenation jJ 1 aut states for j in 1 max do S Concatenation s od for i in 1 aut states 2 do 12 i S od for i in 1 aut alphabet 2 do if i 1 then array i 11 elif i 2 then array i 12 else array 1 Concatenation letters i 2 au i 2 Ei od else for i in 1 aut states do for j in 1 aut alphabe
31. ut 1 a I Bx Initial state 1 Accepting states O algoritmo usado para produzir um aut mato determin stico reconhecendo a mesma lingua gem que o original n o determin stico o da constru o dos subconjuntos E claro que uma vez produzido um aut mato determin stico ele pode ser minimalizado gap aut Automaton nondet 3 2 1 2 3 1 I2 1 3 1 2 1 2 3 a 1 b M Initial state 1 Accepting state 2 gap SubSetAutomaton aut 1 2 3 4 5 6 7 8 a 12 4 4 2 T7 4 2 b 16 3 4 7 2 5 8 Initial state 2 Accepting states 3 4 6 7 16 2 Aut omatos e linguagens racionais gap aut Automaton det 4 2 3 1 3 4 3 4 2 4 1 4 gap Size TransitionSemigroup aut 24 2 3 2 Conjuntos racionais Os subconjuntos de um mon ide M que podem ser obtidos a partir dos subconjuntos singulares por meio de um n mero finito de uni es produtos e estrelas a estrela tem o significado de submon ide gerado por juntamente com o conjunto vazio s o os subconjuntos racionais de M Podemos ent o exprimir qualquer subconjunto racional n o vazio partindo de subconjuntos singulares e usando um n mero finito de vezes a uni o o produto e a opera o estrela Uma tal express o diz se uma express o racional desse subconjunto Por exemplo o conjunto ba a n N que est contido na linguagem do aut mato da p gina 9 pode ser representado pel
Download Pdf Manuals
Related Search