Proposta Pôster Apresentação monografia em postscript

 
  MAC 499 - Trabalho de Formatura Supervisionado
IME-USP - BCC, 2001 - Prof. responsável: Carlos Eduardo Ferreira
 

Monografia
Aluno: Leo Kazuhiro Ueda
Supervisora: Nami Kobayashi
 

Projeto de Iniciação Científica
Autômatos Finitos: Algoritmos e Estruturas de Dados




Índice
Introdução

Este documento relata a experiência que obtive durante o projeto de iniciação científica realizado ao longo do ano de 2001.

  • Título do projeto: 
    		•  Autômatos Finitos: Algoritmos e Estruturas de Dados
  • Orientadora:
    		•  profa. Nami Kobayashi
  • Período:
    		•  março/2001 a dezembro/2001
  • Bolsas:
    		•  PIBIC/CNPq - março/2001 a julho/2001, agosto/2001 a fevereiro/2002

    Como começou o projeto

    No final do ano de 2000, eu procurava por um projeto de iniciação científica. Eu visitei páginas de projetos na Rede do IME, e cheguei até a falar com alguns professores. Porém, embora tenha encontrado muitas possibilidades interressantes, eu não conseguia me decidir. O problema era que eu tinha percebido que precisaria de conhecimentos mais específicos para participar desses projetos, ou ao menos para avaliar se eu realmente gostaria de participar deles. A verdade era que eu queria estudar qualquer um dos assuntos, mas não tinha parâmetros para escolher entre tantas opções interessantes.

    Naquele semestre, eu estava cursando a disciplina MAC 414 - Autômatos e Linguagens Formais com a profa. Nami. A professora, que já me conhecia, soube que eu estava procurando por uma iniciação científica e me ofereceu ajuda.

    A partir daí, eu comecei a olhar projetos que me interessavam e que poderiam se relacionar com Autômatos, que é a área da professora. Eu estudei alguns artigos, mas eu encontrei o mesmo problema de indecisão.

    Como eu estava indeciso e parecendo gostar de qualquer assunto, nós formulamos um projeto que me daria um conhecimento básico para eu poder talvez, no futuro, estudar algumas das aplicações mais complicadas que eu havia pesquisado no começo.

    E por isso, o objetivo foi simplesmente esse. Nós selecionamos alguns tópicos clássicos em Autômatos Finitos e preparamos o projeto.


    O Projeto

    A Teoria de Autômatos Finitos tem sido aplicada a áreas diversas, como, por exemplo, no desenvolvimento de analisadores léxicos e editores de texto, em Processamento de Imagens, Biologia Molecular Computacional e Lingüística Computacional.

    A quantidade e a diversidade dessas aplicações vêm crescendo significativamente, em grande parte devido ao aumento da demanda por sistemas de processamento de quantidades imensas de dados. Como estrutura de dados, um autômato pode armazenar informações de forma a economizar espaço em memória, enquanto isso, os algoritmos já conhecidos para autômatos podem oferecer um processamento eficiente.

    Para compreender e estudar essas aplicações, é importante conhecer os algoritmos e estruturas de dados fundamentais que utilizam autômatos finitos. O objetivo deste projeto foi iniciar um estudo de tais aspectos básicos da Teoria de Autômatos Finitos.

    Os tópicos estudados até o momento foram:

    Nós também implementamos esses três algoritmos.

    Além disso, planejamos estudar o Autômato dos Sufixos, mas o estudo está ainda em fase inicial.

    Metodologia

    As atividades foram voltadas basicamente para a compreensão e implementação de cada algoritmo, principalmente através da leitura de artigos e da realização de reuniões semanais. As reuniões envolveram discussões sobre o andamento do projeto, destacando:

    -
    resolução de dúvidas e análise dos detalhes dos artigos lidos, como por exemplo, provas de corretude e de complexidade de espaço e de tempo;
    -
    investigação de questões de implementação, que tem compromisso com as complexidades de espaço e tempo;
    -
    definição dos passos seguintes do projeto;
    -
    acompanhamento do desempenho acadêmico do aluno.

    Tópicos Estudados

    Eu havia preparado um texto adaptado do meu relatório parcial para o CNPq [13], especialmente para esta monografia. Infelizmente, não consegui fazer com que esse texto ficasse com um tamanho aceitável. Ele esta disponível aqui [14] como uma referência mais detalhada, mas oficialmente não faz parte da monografia.

    Assim, em vez de uma descrição um pouco mais formal, descreverei apenas a idéia dos algoritmos, numa visão bem simplificada. De uma certa maneira, isso deixa de explicitar as maiores dificuldades dos algoritmos, mas espero que seja possível ao menos ter uma noção dessa dificuldade.

    Notação e Definições Básicas

    Antes, precisamos definir uma convenção.

    Um autômato finito determinístico\ensuremath{\mathcal A} é uma quíntupla$(Q,\Sigma,\delta,q_0,F)$, onde:

    Uma palavra é uma seqüência finita de símbolos; a palavra vazia é denotada por $\lambda$. O conjunto de todas as palavras, incluindo $\lambda$, é $\Sigma^{*}$.

    A função $\delta$ será estendida para$\hat{\delta}: Q \times \Sigma^* \to Q$ da maneira usual:

    \begin{displaymath}\left\{ \begin{array}{ll}\hat{\delta}(q, \lambda) = q & \......ma^*,\ \forall \sigma \in \Sigma \quad\!.\end{array} \right.\end{displaymath}

    A partir de agora usaremos $\delta$ para denotar $\hat{\delta}$.

    Diremos também que $n$ é a cardinalidade de $Q$, ou seja, o número de estados de \ensuremath{\mathcal A}.

    A linguagem reconhecida por \ensuremath{\mathcal A}, denotada por $L(\ensuremath{\mathcal A})$, é o conjunto das palavras$x \in \Sigma^*$ tais que $\delta(q_0, x) \in F$.

    Seja $xuy$ uma palavras em $\Sigma^{*}$, então $x$ é um prefixo, $u$ é um fator e $y$ é um sufixo de $xuy$, para $x$, $u$ e $y$ em $\Sigma^{*}$.

    O grafo associado a \ensuremath{\mathcal A}, denotado por $G(\ensuremath{\mathcal A})$, é o grafo orientado $(V,A)$, onde:

    Minimização de Autômatos Finitos

    Estudamos dois algoritmos para minimização de autômatos finitos determinísticos, a versão de David Gries para o algoritmo de John Hopcroft, com complexidade de tempo $O(\vert\Sigma\vert n\log{n})$, e o algoritmo de Dominique Revuz para autômatos acíclicos, com complexidade $O(\vert\Sigma\vert n)$.

    O problema que queremos resolver é minimizar o número de estados de um autômato finito determinístico. Isto é, dado um autômato \ensuremath{\mathcal A}, queremos determinar um autômato \ensuremath{\mathcal B} com o menor número de estados e tal que $L(\ensuremath{\mathcal B})=L(\ensuremath{\mathcal A})$. Tal autômato \ensuremath{\mathcal B} é chamado de minimal.

    Os métodos utilizados pelos dois algoritmos que estudamos se baseiam na seguinte relação de equivalência sobre $Q$:

    Definição 1   Dois estados $p$ e $q$ são equivalentes se, e somente se, para todo $x \in \Sigma^*$, vale que $\delta(p,x) \in F \iff \delta(q,x) \in F$.
    De modo muito simplificado, os algoritmos procuram pelas classes de equivalência em $Q$.

    \includegraphics{export/mon-classes.eps}
    Figura 1: Minimização de \ensuremath{\mathcal A}

    As classes de equivalência em \ensuremath{\mathcal A} estão marcadas com a cor verde, repare que cada classe é um estado em \ensuremath{\mathcal B}. Portanto, se encontrarmos as classes de equivalência, teremos minimizado o autômato.

    O algoritmo de Hopcroft

    Em [8], Hopcroft apresenta um algoritmo para minimizar o número de estados de um autômato finito determinístico, e afirma que ele tem complexidade de tempo $O(\vert\Sigma\vert n\log{n})$.

    Até aquele momento, os algoritmos conhecidos levavam tempo $O(\vert\Sigma\vert n^2)$, ou mais, no pior caso. Porém, a descrição do novo algoritmo e as suas provas de corretude e complexidade de tempo foram consideradas complicadas demais.

    Por muitos anos, a despeito da importante melhora em relação aos algoritmos clássicos, o algoritmo de Hopcroft foi praticamente omitido de textos básicos sobre autômatos finitos. Alguns apenas descreviam o algoritmo, mas sem mostrar as provas de complexidade e corretude. Muitos dos textos básicos [9,11] continuaram a apresentar somente os algoritmos $O(\vert\Sigma\vert n^2)$.

    Com o objetivo de fornecer uma descrição mais clara, David Gries [7] redescreve o algoritmo de Hopcroft, mas com uma pequena modificação. Apesar de ter cumprido seu objetivo, a descrição de Gries não se tornou muito popular.

    Nosso estudo foi centrado no artigo de Gries.


    Descrição da idéia do algoritmo de Hopcroft

    Para encontrar as classes de equivalência, o algoritmo de Hopcroft começa com uma partição dos estados do autõmato \ensuremath{\mathcal A}. Essa partição é formada por dois blocos: um contendo os estados finais e outro contendo os não-finais.

    \includegraphics{export/mon-hop-ex1.eps}
    Figura 2: Ilustração da situação inicial

    Cada passo do algoritmo é um refinamento dos blocos da partição. Os blocos são divididos de forma que os estados equivalentes permanecem em blocos iguais. Podemos ver que na situação inicial isso é verdade, pois um estado final não pode ser equivalente a um estado não-final.

    A Figura 3 mostra a divisão do bloco $B_2$ em relação ao bloco $B_1$ e ao símbolo $a$ .

    \includegraphics{export/mon-hop-ex2.eps}
    Figura 3: Divisão de $B_2$ em relação a $(B_1, a)$

    No bloco $\overline{B_2}$ ficaram os estados que possuem uma transição com rótulo $a$ que vai para algum estado do bloco $B_1$. No bloco $\widetilde{B_2}$ ficaram os estados que não possuem tal transição. Dessa forma, os estados equivalentes de fato permanecem no mesmo bloco. No final, teremos que cada bloco da partição representa uma classe de equivalência, ou seja, em cada bloco, todos os estados são equivalentes entre si. Veja o resto das divisões relevantes.

    \includegraphics{export/mon-hop-ex3.eps}
    Figura 4: Divisões seguintes

    Temos então as classes de equivalência, e portanto o autômato minimal.

    \includegraphics{export/mon-hop-ex4.eps}
    Figura 5: Situação final

    A característica mais importante do algoritmo é a ordem em que são feitas essas divisões, mais precisamente, como ela é definida. Uma discussão sobre isso pode ser vista aqui [14].

    Em seu artigo, Gries propõe uma possível implementação das estruturas de dados. As estruturas dessa proposta são bem simples, são baseadas em vetores pré-alocados, por isso nós seguimos essa proposta em nossa implementação. O espaço em memória utilizado por elas é $O(\vert\Sigma\vert n)$.

    O algoritmo de Revuz para autômatos acíclicos

    Um autômato determinístico \ensuremath{\mathcal A} é acíclico se o grafo $G(\ensuremath{\mathcal A})$ é acíclico. Autômatos determinísticos acíclicos são bastante usados para representar dicionários [2] e manipular funções booleanas [3].

    O algoritmo de Revuz tem grande importância para essas aplicações, pois além de diminuir o espaço em memória utilizado e agilizar as buscas com autômatos, ele tem complexidade de tempo $O(\vert\Sigma\vert n)$.

    Descrição da idéia do algoritmo de Revuz

    O algoritmo começa calculando uma partição$\Pi = \Pi_0, \Pi_1, \cdots$ dos estados de \ensuremath{\mathcal A}. Os estados de um bloco $\Pi_i$ possuem altura$i$. A altura de um estado é o tamanho do caminho de maior comprimento que começa no estado e chega a um estado final. Note, portanto, que é possível calcular $\Pi$ fazendo uma busca em largura no grafo $G(\ensuremath{\mathcal A})$.

    \includegraphics{export/mon-rev-alturas.eps}
    Figura 6: A partição $\Pi$

    Repare que estados de alturas diferentes não podem ser equivalentes.

    A idéia do algoritmo é nomear cada estado com uma palavra que descreve as suas transições, de forma que dois estados possuem nomes iguais se e somente se eles são equivalentes. Tendo isso, o algoritmo percorre os blocos$\Pi_0, \Pi_1, \Pi_2, \cdots$ nessa ordem, aplicando uma ordenação lexicográfica nos nomes dos estados de cada bloco $\Pi_i$, e dessa forma encontrando os estados com nomes iguais. Os estados equivalentes são então unidos, formando um único estado.

    Veja o exemplo de execução.

    \includegraphics{export/mon-rev-ex1.eps}
    Figura 7: Passos do algoritmo

    Para termos complexidade de tempo linear, precisamos de um algoritmo também de tempo linear. Não apenas isso, os nomes dados aos estados também devem possuir tamanho linear, de uma certa forma. Detalhes disso podem ser vistos aqui [14].

    O algoritmo precisa de espaço em memória para armazenar o autômato e para realizar a ordenação linear. A soma de ambos é $O(\vert\Sigma\vert n)$.

    Um problema de busca de padrões

    Neste projeto estudamos também um problema particular de busca de padrões em textos. Trata-se do caso em que o padrão é um conjunto finito $K$ de palavras.

    O nosso  estudo foi  centrado no algoritmo  clássico de  Alfred Aho e Margaret Corasick. Em [1] eles apresentam o algoritmo, tendo como motivação a otimização de um sistema de consulta a um banco de dados de referências bibliográficas. Os resultados em relação aos algoritmos convencionais da época foram excelentes. Outras descrições do algoritmo podem ser encontradas em [4,5].

    Vamos então descrever o problema e o modelo de solução, que envolve a construção de um autômato finito determinístico que representa as palavras em $K$. Para essa construção foram aplicadas algumas idéias do algoritmo KMP, de Knuth, Morris e Pratt [10]. Esse algoritmo resolve o problema da busca de padrões para o caso em que o padrão é uma palavra.

    O problema e o modelo de solução de Aho e Corasick

    Seja $K = \{y_1, y_2, \cdots, y_k\}$ um conjunto finito de palavras em $\Sigma^{*}$, as quais chamaremos de palavras-chave, e $x$, também em $\Sigma^{*}$, uma palavra qualquer que chamaremos de texto. O problema que queremos resolver é localizar e identificar todos os fatores de $x$ que são também palavras-chave. Em outras palavras, queremos saber quais palavras do dicionário $K$ ocorrem no texto$x$.

    Para isso, utilizaremos um autômato que reconhece a linguagem $\Sigma^{*}K$. O autômato recebe como entrada o texto$x$ e gera uma saída contendo as posições em $x$ onde alguma palavra-chave aparece como fator. Essa fase é a busca propriamente dita, e sua complexidade de tempo é $O(\vert x\vert)$, mas pode depender de $\vert\Sigma\vert$, conforme a implementação da função de transição. Note que esse tempo não depende do número de palavras-chave.

    Há também a fase de construção do autômato. Ela é feita em duas etapas, em tempo $O(\vert\Sigma\vert m)$ no total, onde $m$ é a soma dos comprimentos das palavras em $K$. A primeira etapa consiste em construir, a partir do conjunto $K$, uma máquina de estados muito semelhante a um autômato finito determinístico. Essa construção utiliza as idéias do algoritmo KMP, e pode ser feita em tempo$O(m)$, dependendo da implementação. Em seguida, a partir da máquina de estados, pode-se obter em tempo $O(\vert\Sigma\vert m)$ o autômato finito determinístico, que reconhece a linguagem $\Sigma^{*}K$.

    Podemos ver que o tempo de construir e aplicar a máquina de estados é $O(\vert x\vert + m)$. Note que aplicando o algoritmo KMP $k$ vezes com entrada $x$, uma vez para cada palavra em $K$, a complexidade total de pior caso seria $O(k\vert x\vert + m)$.

    O algoritmo de Aho e Corasick

    Como já mencionamos, o algoritmo Aho-Corasick inicialmente constrói um autômato que reconhece a linguagem $\Sigma^{*}K$. Essa construção é feita em etapas, a primeira constrói um autômato que reconhece as palavras-chave. Vejamos um exemplo para $K = \{he, she, hers, his\}$.

    \includegraphics{export/tec-ac-arv.eps}
    Figura 8: Primeira etapa da construção

    A partir dessa estrutura, o algoritmo constrói uma máquina de estados semelhante a um autômato. A diferença dessa máquina é que ela possui uma segunda função de transição, chamada falha. Essa função utiliza as mesmas idéias do algoritmo KMP.

    \includegraphics{export/tec-ac-maq.eps}
    Figura 9: A máquina de estados com a função $falha$

    Numa busca do texto na máquina de estados, a transição de falha de um estado é usada quando a transição $\delta$ não está definida para esse estado. Ela indica o estado para o qual devemos voltar e repetir a busca. Por exemplo, numa busca no texto ``shine'', passaríamos pelos estados nesta ordem: $0,s,3,h,4,i,1,i,8,n,0,e,0$ (confira na Figura 9). Note que a máquina já é capaz de reconhecer $\Sigma^{*}K$, ou seja, pode resolver o problema.

    A última fase é a construção de um autômato finito determinístico a partir da máquina de estados.

    \includegraphics{export/tec-ac-aut.eps}
    Figura 10: O autômato que reconhece $\Sigma^{*}K$

    O tempo total consumido por essas três fases é $O(\vert\Sigma\vert m)$, dependendo da implementação.

    Vejamos novamente a busca das palavras do dicionário no texto ``shine'', mas desta vez no autômato da Figura 10: $0,s,3,h,4,i,8,n,0,e,0$. Não há ocorrência de nenhuma palavra-chave no texto ``shine''. Podemos notar também que o autômato utiliza um pouco menos transições em comparação com a máquina de estados. Porém, tanto o autômato quanto a máquina utilizam $O(\vert x\vert)$ transições numa busca em $x$ (ou seja, a complexidade não muda). Ademais, a quantidade de transições do autômato é bem maior ($O(\vert\Sigma\vert n)$ contra $O(n)$).

    O Autômato dos Sufixos

    O estudo do Autômato dos Sufixos ainda está em fase inicial. Até agora estudamos apenas tópicos relacionados:


    Implementações

    Nós implementamos os três algoritmos estudados na linguagem C, padrão ANSI. Embora essas implementações tivessem como objetivo auxiliar o entendimento das questões de complexidade de tempo e de espaço, elas geraram discussões interessantes sobre outras questões. Algumas delas foram:


    Desafios, Frustrações e Considerações Pessoais

    As dificuldades apareceram nas principais atividades deste projeto, que foram a leitura de artigos e a produção do relatório. Eu esperava por isso, já que, antes de começar o projeto, tinha tido muito pouca ou nenhuma experiência parecida no curso.

    Mas, com o passar do tempo e com a orientação da profa. Nami, eu pude perceber que, apesar disso, o curso havia sim me preparado para aqueles tipos de atividades. Em outras palavras, as atividades do curso foram diferentes das atividades da iniciação, entretanto, a experiência obtida no curso permitiu que eu realizasse as atividades da iniciação.

    Com isso, o desafio passou a ser a própria dificuldade de entender os artigos, e a base teórica obtida no curso foi fundamental para superá-lo. Ela também me ajudou a lidar com outros problemas, como deficiências e até erros nos artigos.

    Porém, o trabalho neste projeto foi praticamente individual, e essa foi uma grande frustração. Eu cheguei a receber conselhos importantes do aluno de mestrado da profa. Nami, Rodrigo de Souza, mas não chegamos a trabalhar juntos.

    O único trabalho em grupo eram as reuniões semanais, onde eu discutia com a profa. Nami o trabalho que tinha sido feito. Essa interação foi um dos aspectos mais valiosos do projeto. Nessas reuniões, por exemplo, discutíamos detalhes dos artigos lidos, e nessa interação eu não era simplesmente ensinado pela professora, mas também aprendia fatos novos junto com ela. Essa foi de fato uma experiência totalmente nova em relação às que eu conheci no BCC.

    Ademais, o apoio da profa. Nami foi de grande importância para mim. Não foi só um apoio como orientadora da iniciação científica, ela também me aconselhou em questões sobre o curso.

    Outra grande frustração foi que os resultados foram apenas para o meu benefício, o objetivo do projeto não incluía a produção de algo que pudesse ser útil para as outras pessoas. Há um ano eu estava desnorteado pela minha indecisão, não percebi que esse era um aspecto importante, e que eu sentiria falta disso. No entanto, o meu objetivo a longo prazo era justamente poder trabalhar num projeto com tais resultados, e por isso acredito que essa frustração não invalida este projeto.

    Disciplinas Relevantes

    Ao cursar uma disciplina, tento não ver o conhecimento que ela pode me fornecer como um fator principal. O que mais valorizo numa disciplina são as novas idéias e conceitos que eu posso adquirir, a absorção do conhecimento específico seria apenas uma conseqüência desejável. Nesse sentido, considero que quase todas as disciplinas foram relevantes para este projeto.

    Mas é claro que posso listar as disciplinas que tiveram alguma aplicação direta no meu trabalho.

    Uma disciplina que não teve aplicação direta, mas que teve uma importância destacável, foi MAC 315 - Programação Linear, com o prof. Leônidas. Pelo modo como ela foi dada, eu tive a chance de amadurecer a minha capacidade compreender e construir demonstrações matemáticas. E isso sim foi aplicado diretamente no projeto. É verdade que eu tive a mesma chance em muitas outras disciplinas, mas essa disciplina em especial foi marcante nesse aspecto.


    Conclusão

    O Trabalho de Formatura foi uma ótima oportunidade para que eu realizasse um projeto grande e tivesse, talvez, uma noção da qualidade da formação oferecida pelo BCC. Foi também, sem dúvida, a ocasião em eu mais apliquei e obtive conhecimentos.

    O projeto de iniciação científica ainda não está concluído, ainda prevê atividades até fevereiro de 2002. Depois disso pretendo continuar meus estudos, mas provavelmente não nessa área. Ainda não decidi a minha área de preferência, apenas sei que vou continuar estudando simplesmente porque gosto de aprender.


    Referências
    1
    A.V. Aho and M.J. Corasick.

    Efficient string matching: an aid to bibliographic search.
    Communications of the ACM, 18:333-340, 1975.
    2
    A.V. Aho, R. Sethi, and J.D. Ullman.

    Compilers, Priciples, Techniques and Tools.
    Addison Wesley: Reading, MA, 1986.
    3
    R.E. Bryant.

    Graph-based algorithms for boolean function manipulation.
    IEEE Transactions on Computers, C-35(5):677-691.
    4
    M. Crochemore and C. Hancart.

    Automata for matching patterns.
    In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 2, Linear Modeling: Background and Application, chapter 9, pages 399-462. Springer-Verlag, 1997.
    5
    M. Crochemore and C. Hancart.

    Pattern matching in strings.
    In M.J. Atallah, editor, Algorithms and Theory of Computation Handbook, chapter 11, pages 11.1-11.28. CRC Press, 1998.
    6
    M. Crochemore and W. Rytter.

    Text algorithms.
    Oxford University Press, 1994.
    7
    D. Gries.

    Describing an algorithm by Hopcroft.
    Acta Informatica, 2:97-109, 1973.
    8
    J. Hopcroft.

    An $n \log n$ algorithm for minimizing states in a finite automaton.
    In Theory of Machines and Computations, pages 189-196. Academic Press, 1971.
    9
    J.E. Hopcroft and J.D. Ullman.

    Introduction to Automata Theory, Languages and Computation.
    Addison-Wesley, 1979.
    10
    D. E. Knuth, J. H. Morris, and V. R. Pratt.

    Fast pattern matching in string.
    SIAM Journal of Computing, 6:323-350, 1977.
    11
    H.R. Lewis and C.H. Papadimitriou.

    Elements of the Theory of Computation.
    Prentice Hall, 1997.
    12
    E. McCreight.

    A space-economical suffix tree construction algorithm.
    Journal of the ACM, 23(2):262-272, 1976.
    13
    L.K. Ueda.

    Relatório de atividades para o CNPq, correspondente ao período de março/2001 a julho/2001 (com algumas correções). Está disponível em ps.gz e pdf.gz.
    14
    L.K. Ueda.

    Texto adaptado de [13], especialmente feito para esta monografia. Não faz parte da monografia porque ficou muito grande :-( . Está disponível em html e ps.gz.

    About this document ...
    MAC 449 - Trabalho de Formatura Supervisionado
    IME-USP - BCC, 2001 - Prof. responsável: Carlos Eduardo Ferreira

    This document was generated using the LaTeX2HTML translator Version 99.2beta8 (1.42)
    (Não completamente, tive que arrumar muitas coisas!)

    Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
    Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

    The command line arguments were:
    latex2html -split 0 -image_type gif -antialias -antialias_text mono

    The translation was initiated by Leo on 2001-12-10

    A tradução não ficou muito boa, há uma versão ps disponível...

    Página da disciplina
    Página da Rede Linux
    Página do IME

    Última atualização: seg dez 10 23:03:22 BRST 2001