Flashcards
Manipulação de sequências
Cards in this deck (8)
- 1O que é o casamento de padrões?Descobrir se e a partir da onde o texto T é igual ao padrão P
- 2Como funciona o algoritmo de solução ingênua (força bruta) para casamento de padrões e qual seu custo?Criamos uma espécie de janela deslizante no texto. Em cada posição do texto, testamos o padrão, fazemos isso para todas as posições. Se m é o tamanho do padrão e n tamanho do texto, no pior caso, fazemos m comparações n vezes (o padrão não está no texto) e m = n. O(n²).
- 3Como funciona a abordagem de autômatos finitos para casamento de padrões e qual seu custo?Vai nos dizer o maior tamanho de prefixo que conseguimos aproveitar(cada estado vai representar +1 símbolo "casado"). Precisamos passar somente uma vez pelo texto, mas devemos criar o autômato para o padrão e todas as funções de transição. O(n) para o casamento, em que n é o tamanho do T que iremos consumir. Bom para utilizar quando o texto muda e o padrão permanece.
- 4O que é a função sufixo?Retorna o tamanho do prefixo de P que é sufixo de T.
Suponha P = ab
sufixo(lambda) = 0
sufixo(ccaca) = 1
sufixo (ccab) = 2 - 5Como funciona a criação da função de transição na abordagem de autômatos?"Se estou no estado e e leio um símbolo s, para qual estado devo ir?"
A ideia do algoritmo é sempre tentar avançar para o próximo estado, se não conseguirmos, vamos diminuindo até encontrarmos um prefixo que é sufixo.
O(m³ * tamanho do alfabeto) - 6O que é a função prefixo?Maior prefixo que é sufixo próprio. (qual é o maior prefixo do padrão que é sufixo dele mesmo (do padrão)? )
- 7Como computar a função prefixo?Utilizamos um vetor auxiliar e realizamos um pré-processamento do padrão. Ele procura pelo maior sufixo dos prefixos que também são prefixos. Tentamos sempre aumentar o valor retornado pela função prefixo e vamos tentando fazer isso analisando se os símbolos são iguais.
- 8Como funciona o casamento de padrões no algoritmo KMP?Depois de computar a função prefixo....
Information
- Description
- In-house Trainer Algoritmos II Flashcards on Manipulação de sequências, created by Gabriella De Lima on 30/10/2024.
- Created by
- Gabriella De Lima
- Views
- 0
- Rating