Estrutura de Dados_Algoritmos de Ordenação

ATIVIDADE

SÃO LUÍS – MA

1 – Dê o conceito de algoritmo, tipo de dados e tipo abstrato de dados.
2 – O que significa dizer que um algoritmo executa em um tempo proporcional a n?
3 – Qual algoritmo você prefere: um algoritmo que requer n5 passos ou um que requer 2n passos?
4 – Explique a diferença entre O(1) e O(2)?
5 – Implemente os três algoritmos apresentados nos programas para obter o máximo e o mínimo de um conjunto contendo n elementos. Execute os algoritmos para valores suficientemente grandes de n, gerando casos de teste para o melhor caso, pior caso e caso esperado. Comente os resultados obtidos.
6 – Faça uma pesquisa sobre outras notações diferentes da notação O. Apresente na forma de trabalho.
Resoluções
1 – Um algoritmo é uma seqüência de ações executáveis para a obtenção de uma solução para um determinado tipo de problema. Os tipos de dados são caracterizados por um o conjunto de valores a que uma constante pertence, ou que podem ser assumidos por uma variável ou expressão, ou que podem ser gerados por uma função, tipos simples de dados são grupos de valores indivisíveis (como os tipos básicos integer, boolean, char e real do Pascal).
Podemos considerar os tipos abstratos de dados como modelos matemáticos, acompanhado das operações definidas sobre o modelo.Exemplo: o conjunto dos inteiros acompanhado das operações de adição, subtração e multiplicação. Podemos, ainda, considerar TAD’s como generalizações de tipos primitivos e procedimentos(ou operações) como generalizações de operações primitivas.
2 – Significa dizer que o tempo de execução das operações principais do algoritmo são diretamente proporcionais a um problema de tamanho n. Se aumentarmos o tamanho do problema n também estaremos aumentando o tempo de execução do algoritmo ou a quantidade de memória utilizada por ele.
3 – Preferiria que requer 2n passos para n < 40 já que ele tem o domínio assintótico sobre o de n5 passos nesse