FCC - Resumo P1

Prévia do material em texto

FCC – Resumo P1 
Cite algumas características do Fortran. 
 O Fortran permite a criação de programas que se 
fundamentam na velocidade da execução. 
 Em principio dependia de comandos GO to. Posteriormente 
foram inseridos métodos como IF/else, while... 
 Erros de escrita de código são difíceis de serem identificados 
 
O que é MatLab? E qual sua vantagem? 
É um software interativo de grande eficiência especialmente 
voltado para a realização de operações de cálculo numérico. 
Sua grande vantagem é a sua capacidade de integração de 
diferentes áreas. Outra vantagem é o tempo gasto em relação a 
outras linguagens como o Fortran para a solução de problemas 
numericamente complexos. 
 
Cite algumas características do MatLab. 
 Elemento básico de informação é uma matriz 
 Variáveis são definidas com o operador de igualdade 
 Não há declaração de tipos. O espaço de armazenamento é 
alocado dinamicamente 
 
Defina simulação. 
Consiste em empregar formalizações em computadores, tais 
como expressões matemáticas ou especificações formalizadas, 
com o propósito de limitar um processo ou operações do 
mundo real. 
 
Quais as finalidades da simulação? O que é possível obter com 
a simulação? 
 Descrever o comportamento do sistema 
 Construir teorias e hipóteses a partir das observações 
 Usar o modelo para realizar previsões 
 
Defina otimização. 
É o estudo de problemas em que busca minimizar ou maximizar 
uma função através da escolha de variáveis dentro de um 
conjunto de valores possíveis. Através disso pode-se obter o 
melhor desempenho do sistema. 
 
O que é problema de otimização? 
Trata-se de um problema para encontrar a melhor solução de 
todas as soluções viáveis. 
 
O que é problema de otimização combinatória? 
É um problema de otimização com variáveis discretas. Neste 
tipo de problema, que é o mais complexo de ser resolvido, 
procura-se por uma solução, através da permutação de várias 
soluções. 
 
Qual a diferença de problema com variáveis discreto para um 
problema continuo? 
Nos problemas contínuos, o espectro de soluções é mais 
controlado dentro de um intervalo com infinitas soluções. Em 
geral, não modela problemas do mundo real. 
 
Defina um problema NP. 
É um problema de otimização combinatória com algumas 
condições especiais, tais como, o tamanho de toda solução 
viável ser delimitado em um tamanho de dada distancia x, 
poder ser descrito polinominalmente e m ser um tempo 
polinomial computacional. 
 
Defina algoritmo determinístico. Quais as vantagens e 
desvantagens? 
É um algoritmo que, dada certa entrada, produzirá sempre a 
mesma saída. São considerados práticos, pois executam em 
máquinas reais de forma razoavelmente eficiente, mas 
encontrar esse tipo de algoritmo para alguns problemas é difícil 
e nem sempre é do interesse que os resultados sejam 
previsíveis, além de serem computacionalmente complexos em 
alguns casos. 
 
Quais os fatores podem tornar um algoritmo não 
determinístico? 
 Se o algoritmo usa algum valor externo que não o de entrada, 
como um entrada de usuário, uma variável global, etc. 
 Se a operação é algo sensível ao tempo. 
 Potenciais erros de hardware causando mudanças 
inesperadas de estado 
 
Defina algoritmo não determinístico. 
É um algoritmo que pode apresentar comportamentos 
diferentes em diferentes execuções. 
 
Defina alinhamento de sequencias, alinhamento global e local. 
Alinhamento de sequencias – forma de organizar sequencias de 
DNA, RNA e proteínas para identificar regiões similares que 
podem ser consequências de relações funcionais, estruturais ou 
evolucionárias. 
Alinhamento Global – Estratégia para cobrir o comprimento de 
todas as sequencias. Mais genérico. 
Alinhamento Local – Identificam regiões de similaridade dentro 
de sequencias longas que, em gral, são divergentes no todo. 
 
Qual a diferença entre algoritmos baseados em programação 
dinâmica e heurística? 
Os baseados em programação dinâmica são bem mais lentos, 
no entanto precisos. Já os heurísticos são mais 
eficientes(rápidos), mas não produzem soluções exatas. 
 
Defina programação dinâmica. 
É um método aplicável a problemas onde a solução pode ser 
computada a partir de uma solução previamente calculada e 
memorizada de outros subproblemas que compõem o 
problema original. 
 
O que é preciso para que a programação dinâmica possa ser 
aplicada a um problema de otimização? 
Deve ter subestrutura ótima, ou seja, uma solução ótima para o 
problema contém em seu interior soluções ótimas para 
subproblemas, e superposição de problemas (um algoritmo 
recursivo reexamina o mesmo problema muitas vezes). 
 
Como funciona o nw? 
O algoritmo realiza o alinhamento par-a-par entre as 
sequencias, a partir da construção de uma matriz de valores e, 
posteriormente, faz uma escalada em caminho reverso para 
obter o melhor alinhamento. 
 
Qual a diferença entre os algoritmos needleman-wunsch(nw) 
e smith-waterman(sw)? 
O algoritmo nw busca o máximo de coincidências analisando as 
sequencias globalmente, enquanto o algortimo sw preocupa-se 
em encontrar pontos específicos de similaridade dentro das 
sequencias. 
 
De um exemplo de utilização do sw. 
Em um genoma de um vírus, se os pesquisadores tiverem 
conhecimento de uma região em particular que corresponda a 
sua capacidade de mutação, pode-se desenvolver um inibidor 
para ela. 
Algoritmo de needleman-wunsch(nw) 
Utilizando 2 sequencias cria-se uma matriz para alinhar as sequencias. 
Ex: 
Temos as sequencias: E: 
S1=GAATTCAGTTA Match=5 
S2=GGATCGA Mismatch=-3 
Gap=-4 
1. Montamos uma matriz: 
 - G A A T T C A G T T A 
- 
G 
G 
A 
T 
C 
G 
A 
2. Para preencher as células das linhas 0 e colunas 0: 
 
 
3. Para preencher os demais: 
 
 
 
 
 
 
 
4. Com a matriz preenchida: 
 
 - G A A T T C A G T T A 
- 0 -4 -8 -12 -16 -20 -24 -28 -32 -36 -40 -44 
G -4 5 1 -3 -7 -11 -15 -19 -23 -27 -31 -35 
G -8 1 2 -2 -6 -10 -14 -18 -14 -18 -22 -26 
A -12 -3 6 7 3 -1 -5 -9 -13 -17 -21 -16 
T -16 -7 2 3 12 8 4 0 -4 -8 -12 -16 
C -20 -11 -2 -1 8 9 13 9 5 1 -3 -7 
G -24 -15 -6 -5 4 5 9 10 14 10 6 2 
A -28 -19 -10 -1 0 1 5 14 10 11 7 11 
 
5. Para fazer o backtracking: 
 Começa-se no canto inferior direito verificando qual das formulas 
anteriores resultou nesse resultado para saber para qual direção 
seguir. 
 Caso se segue em direção a match/mismatch copiar as sequencias. 
Caso se segue pro lado o gap aparece na segunda sequencia. E 
caso se segue para cima, o gap aparece na primeira sequencia. 
 
 - G A A T T C A G T T A 
- 0 -4 -8 -12 -16 -20 -24 -28 -32 -36 -40 -44 
G -4 5 1 -3 -7 -11 -15 -19 -23 -27 -31 -35 
G -8 1 2 -2 -6 -10 -14 -18 -14 -18 -22 -26 
A -12 -3 6 7 3 -1 -5 -9 -13 -17 -21 -16 
T -16 -7 2 3 12 8 4 0 -4 -8 -12 -16 
C -20 -11 -2 -1 8 9 13 9 5 1 -3 -7 
G -24 -15 -6 -5 4 5 9 10 14 10 6 2 
A -28 -19 -10 -1 0 1 5 14 10 11 7 11 
 
Obtemos: 
 
G A A T T C A G T T A ALIN 1 
G G A _ T C _ G _ _ A 
G A A T T C A G T T A ALIN 2 
(USANDO 12) G G A T _ C _ G _ _ A 
 
Algoritmo de Smith-waterman(sw) 
1. De mesmo modo que em nw, temos 2 sequencias e construímos uma 
matriz a partir delas. 
2. Preenchemos as linhas 0 e colunas 0 com 0. 
3. Utilizamos para preencher as demais células: 
 
 
 
 
 
 
4. Para fazer o backtracking começamos a partir do maior valor encontrado 
na matriz e prosseguimos do mesmo modo que em nw.