Exercícios Estrutura de Dados - Resolvidos

Lista de Exercícios

1. Dê o conceito de:
   1. Algoritmo
      R: É uma sequencia de ações executáveis para obtenção de uma solução para um determinado problema.
   2. Tipo de dados
      R: Conjunto de valores a que uma constante pertence, ou podem ser assumidos por uma variável ou expressão a que podem ser gerados por uma função.
   3. Tipo abstrato de dados
      R: Pode ser visto como um modelo matemático, acompanhado das operações definidas sobre um modelo.
      
      
2. Qual a descrição de algoritmos segundo Dijkstra?
   R: descreve como uma descrição de um padrão de comportamento, expresso em termos de um conjunto finito de ações.
   
   
3. Descreva o conceito de programar para estrutura de dados.
   R: consiste em estruturar dados e construir algoritmos, sendo formulações concretas de algoritmos abstratos, baseados em representações e estruturas específicas de dados, representando uma classe especial de algoritmos capazes de serem seguidos por computadores
   
   
4. Cite os tipos de operações que podem ser definidas sobre uma lista.
   R: Criar lista, Retirar, inserir, alterar.
   
   
5. Comente sobre os tipos de problemas distintos apresentado por Knuth.
   R: Análise de um algoritmo particular: custo ao usar um dado algoritmo para resolver um problema específico, investigar características importantes do algoritmo em questão devem ser investigadas.

Análise de uma classe de algoritmos: qual o algoritmo de menor custo possível para resolver um problema particular? Neste caso, deve ser investigado toda família de algoritmos para resolver um problema específico com a finalidade de identificar o melhor possível, colocando limites à complexidade computacional dos algoritmos pertencentes à classe

6. Comente sobre as formas de medir os custos de utilização de um algoritmo e levando em consideração que os resultados não devem ser generalizados.
   R: Obtendo as medidas desta forma são inadequadas e seus resultados não devem ser generalizados, devido as seguintes objeções: (i) Os resultados dependem do compilador que pode favorecer algumas construções em detrimento de outras; (ii) os resultados dependem do hardware; (iii) quando grandes memória são utilizados, as medidas de tempo dependem deste aspecto.
   
   
7. Cite e comente os três cenários distintos relacionados ao tempo de execução de um algoritmo.
   R: Melhor caso(Encontrar o registro rapidamente)
   médio caso(o mais difícil de se precisar) e pior caso(Percorrer todo o arquivo em busca de um registro.
   
   
8. Cite as principais classes de problemas e suas funções de complexidade.
   R: As principais classes de problemas possuem as funções de complexidade são descritas abaixo.

f(n) = O(1). Algoritmos de complexidade O(1) são ditos complexidade constante.

• f(n) = O(log n). Um algoritmo de complexidade O(log n) é dito ter complexidade logarítmica, onde a execução ocorre tipicamente em algoritmos que resolvem um problema transformando-o em problema menores.f(n) = O(n). Algoritmo de complexidade O(n) é dito ter complexidade linear, realizando um pequeno trabalho sobre cada elemento de entrada.
• f(n) = O(n log n). Este tempo de execução ocorre tipicamente em algoritmos que resolver um problema quebrando–o em problema menores, resolvendo cada um deles independentemente e depois ajuntando as soluções.

• f(n) = O(n²). Algoritmo de complexidade O(n²) é dito ter complexidade quadrática, são processados aos pares, sendo muitas vezes um anel dentro do outro.f(n) = O(n³). Algoritmo de complexidade O(n³) é dito ter complexidade cúbica e são úteis para resolver pequenos problemas.

f(n) = O(2ⁿ). Algoritmo de complexidade O(2ⁿ) é dito ter complexidade exponencial e geralmente não são úteis sob ponto de vista prático. São usados em algoritmos de força bruta.

9. O que caracteriza programas considerados resolvidos e os não resolvidos?
   R: são os que existe um função polinomial para solucioná-los, enquanto problemas que não existem uma função polinomial para resolvê-lo é considerado intratável.

10. Descreva sobre o problema do caixeiro viajante e apresente uma solução para o mesmo.
    R:Considere visitar as cidades de forma que sua viagem inicie e termine em uma mesma cidade e cada cidade seja vizitada uma única vez.
    
    
11. Descreva sobre as técnicas de análise de algoritmos.
    R: Utiliza matemática discreta, envolvendo contagens ou enumerações dos elementos, envolvendo manipulações de operações.
    
    
12. Cite os princípios a serem seguidos utilizando propriedade sobre notação O.
    R: O tempo de execução de um comando / O tempo de execução de uma seqüência de comandos / O tempo de execução de um comando de decisão/ O tempo para executar um anel /Quando o programa possui procedimentos não recursivos .

13. Suponha dois algoritmos A e B, com funções de complexidade de tempo a(n) = n2 – n + 549 e b(n) = 49n + 49 respectivamente. Determine quais valores de n pertencentes ao conjunto de números naturais para os quais A leva menos tempo para executar do que B.
    R: Não exixte valores de n que satisfaça a condição.