Lista de Exercícios 01

Prévia do material em texto

Lista de Exercícios 01 – Algoritmo
1. Dê um conceito de algoritmo, no contexto da computação.
Resposta: O Algoritmo é uma ferramenta para solucionar um problema computacional bem definido utilizando uma sequência de passos para transformar uma entrada em uma saída.
2. Descreva o que é uma instância de um algoritmo.
Resposta: é uma entrada, que satisfaz os critérios impostos pela especificação do algoritmo, necessária para a solução dele.
3. Descreva uma sequência de passos mentais que são usados para ordenar crescentemente um conjunto de números. Dê um exemplo com a sequência {5,3,7,2,9,1,8,5,3,5,6}
Resposta: 
1º Passo: definir qual o menor e o maior número e colocar o menor na primeira posição e o maior na última posição
 {1,5,3,7,2,8,5,3,5,6,9} (1 é o menor valor e o 9 é o maior)
2º Passo: comparar 2 elementos vizinhos iniciando da primeira posição até a última, levando o primeiro elemento da dupla a ser denominado “pivô”, caso o pivô seja maior que o elemento imediatamente sucessor a ele, faz-se necessário fazer uma troca de posição entre os mesmos e um laço de repetição até a condição ser finalmente atendida por todos os antecessores e sucessores. 
· Entrada: {1,5,3,7,2,8,5,3,5,6,9} O 5 é maior que o 1, então a posição dele continua a mesma, então comparando os 2 vizinhos posteriores ao primeiro elemento temos que: o 3 é menor que o 5, logo trocará de posição com ele. Saída provisória: {1,3,5,7,2,8,5,3,5,6,9}
· Entrada provisória: {1,3,5,7,2,8,5,3,5,6,9} O 7 é maior que o seu antecessor, então não muda sua posição, porém o número posterior ao 7 é menor que ele, pois é o 2, logo mudará de posição com o 7, porém o 2 também é menor que o 5, e mudará de posição com ele também, e consequentemente mudará de posição com o 3 e não mudará mais com o, pois é maior que ele. Saída provisória: {1,2,3,5,7,8,5,3,5,6,9}
· Entrada provisória: {1,2,3,5,7,8,5,3,5,6,9}. Seguindo adiante, o 8 é maior que o 5, então o 5 trocará de posição com o 8 antecedente a ele, com o 7 e ficará lado a lado com o outro 5. Saída provisória: {1,2,3,5,5,7,8,3,5,6,9}
· Entrada provisória: {1,2,3,5,5,7,8,3,5,6,9}. Seguindo a sequência já formada, onde finaliza no número 8, ao comparar com o 3 vemos que ele é maior, logo o 3 trocará de posição com o 8, 7e por fim os dois 5. Saída provisória: {1,2,3,3,5,5,7,8,5,6,9}
· Entrada provisória: {1,2,3,3,5,5,7,8,5,6,9} Agora é a vez do último 5 do conjunto, que trocará de posição com os anteriores até ficar emparelhado com seus iguais. Saída provisória: {1,2,3,3,5,5,5,7,8,6,9}
· Entrada provisória: {1,2,3,3,5,5,5,7,8,6,9} Por fim, só restou o elemento 6 que está depois do 8, então ele trocará de posição com o 8 e por fim com o 7, e o conjunto estará devidamente ordenado. Saída final {1,2,3,3,5,5,5,6,7,8,9}.
4. Conceitue Algoritmo Correto
Resposta: Um Algoritmo é considerado CORRETO se para toda e qualquer instância ele produzir uma saída correta
5. Apresente um exemplo de como um algoritmo incorreto pode ser útil
Resposta: o algoritmo incorreto pode ser útil para economizar tempo, por exemplo: suponhamos que eu queira gerar um número primo com 200 algarismos decimais, utilizando um algoritmo incorreto, consigo obter um resultado consideravelmente mais rápido que o algoritmo correto, com uma margem de erro considerável.
6. Pesquise e escreva o resultado de sua pesquisa sobre os algoritmos do Projeto Genoma Humano.
O Projeto Genoma Humano tem como objetivo o mapeamento e sequenciamento do genoma humano inteiro. Além do genoma humano, alguns organismos modelo foram selecionados para serem sequenciados e ajudarem a desenvolver novas tecnologias e a elucidar o genoma humano. Um dos grandes objetivos do Projeto Genoma Humano é sequenciar o genoma humano inteiro, obtendo as 3 bilhões de bases da cadeia que representam o DNA humano
Nesse projeto, um número considerável de amostras processadas foi obtido através do desenvolvimento de instrumentos de sequenciamento automatizados. Depois de quebrar uma sequência em vários fragmentos, cloná-los e sequenciá-los, há um conjunto de fragmentos que precisam ser montados para obtenção da sequência original. Este é um problema algorítmico conhecido como montagem de fragmentos ou sequence assembly.
O projeto utilizou um método tradicional de montagem de fragmentos, utilizando o algoritmo que seguia os seguintes passos: detecção de sobreposição, layout dos fragmentos e decisão da sequência consenso. E em cada passo desses, eram usados mais algoritmos ainda mais complexos
Os primeiros algoritmos para montagem de genomas eram baseavados no alinhamento dos reads e na concatenação de sequências obtidas dos reads com os maiores alinhamentos. O processo se dava de forma cíclica, concatenando as sequências com o maior alinhamento até que todos estes alinhamentos fossem utilizados. Esta montagem de genomas a partir de reads tem como base os seguintes passos: 
· cálculo de alinhamentos aos pares de todos os fragmentos;
· escolha de dois fragmentos com a maior sobreposição;
· fusão dos dois fragmentos;
· repetição dos passos anteriores até obtenção de uma única sequência.
Para as novas metodologias de sequenciamento, devido ao relativo pequeno tamanho dos fragmentos, algoritmos diferentes foram desenvolvidos. No projeto, foram utilizados diversos algoritmos, cada um com sua devida aplicação, para que obtivessem os melhores resultados.
Referências bibliográficas: 
· STAATS, Charley Christian; MORAIS, Guilherme Loss de; MARGIS, Rogerio. Projetos Genoma. Bioinformática: da biologia à flexibilidade molecular. Cap. 4, p. 63-79, 2014.
· LEMOS, Melissa; BASÍLIO, Antônio; CASANOVA, Marco Antônio. Um estudo dos algoritmos de montagen de fragmentos de DNA. PUC, 2003.
7. Escreva sobre o que é uma estrutura de dados.
Resposta: Uma Estrutura de Dados é uma forma de armazenar e organizar de tal maneira a facilitar seu acesso e modificação.
8. Comente sobre o problema da sintaxe e da semântica de uma língua.
Resposta: o problema de sintaxe, está relacionado com os erros de pontuação nos códigos, como por exemplo substituir “;” por “.”, já o erro de semântica está relacionado com o mal funcionamento da lógica correta, como por exemplo um algoritmo para pegar somente números menores que 10, e dentro da condição ter um (<=10), assim está semanticamente errado, pois dessa maneira vai pegar o número 10 também.
9. Pesquise sobre línguas naturais em computação para saber se elas são adequadas para descrever algoritmos.
Resposta: A Linguística Computacional ou Processamento de língua natural é uma vertente da inteligência artificial que ajuda computadores a entender, interpretar e manipular a linguagem humana, a informática, a estatística e a linguística. Com os frequentes avanços nas tecnologias, as inteligências artificiais estão cada vez mais inteligentes, pois elas aprendem até buscar a perfeição e nunca mais comentem o mesmo erro. Acredito que sejam adequadas para desenvolver algoritmos, pois tem uma capacidade de reunir milhares de dados a fim de criar um algoritmo correto que funcione muito bem.
10. Pesquise sobre a história da computação e disserte sobre o tema em, no mínimo, 20 linhas de texto contínuo. (fonte Arial 10, folha A4, margens 2cm).
A era da computação teve início com uma máquina de computar chamada “ábaco”, um instrumento chinês criado por volta de 2500 a.C., esse artefato foi considerado o primeiro “computador”, era uma calculadora que realizava operações algébricas. Durante o século XVII, o matemático John Napier foi um dos responsáveis pela invenção da “régua de cálculo”, que é um instrumento analógico que efetuava cálculos logaritmos.
Por voltar de 1640, o francês Pascal inventou a primeira máquina de calcular automática. Essa máquina foi sendo aprimorada, a calculadora trabalhava perfeitamente, ela transferia os números da coluna de unidades para a coluna de dezenas por um dispositivo semelhante a um velocímetro do automóvel. A máquina Pascal foi criada com objetivo de ajudar seu pai a computar os impostos. O projeto de Pascal foi bastante aprimorado pelomatemático alemão Gottfried, que também inventou o cálculo.
Data se de 1936 a invenção do primeiro computador eletromecânico, este foi chamado de Z-1 por seu inventor Konrad Zuse. Com a Segunda Guerra Mundial, se iniciaram várias pesquisas na área da informática, os pioneiros foram os Americanos com duas invenções que deixaram suas marcas na história, os famosos Mark I e ENIAC. Mark I foi construído em 1944 pela Marinha dos Estados Unidos em conjunto som a Universidade de Harvard e a IBM.
Por fim, vale mencionar a importância do matemático Alan Turing, que é conhecido por alguns como o pai da computação, Turing teve sucesso durante a Segunda Guerra Mundial, o matemático desenvolveu um sistema chamado “bombe”, para traduzir as mensagens secretas dos alemães, geradas por máquinas de criptografia chamadas de “Enigma”. Outro grande feito foi a invenção da Máquina de Turing. Uma criação automática capaz de manipular códigos e símbolos em uma fita de acordo com um conjunto de regras para guardar informação.