Lista01

Algoritmos e Estruturas de Dados
Lista de Exercícios 01
Prof. Eduardo Henrique da Rocha Coppoli
Aluno: Daniel de Carvalho Ferrari
1- Dê o conceito de: a- Algoritmo:
R:
Um algoritmo pode ser uma sequência de ações executáveis para obtenção de uma solução para um determinado tipo de problema. O algoritmo de forma geral é uma sequência finita de instruções, bem definidas e não ambíguas, e nas quais podem ser executáveis durante um determinado período de tempo e com uma quantidade finita de esforço. b- Tipo de dados:
R:
São conjuntos 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. Os tipos básicos de dados são dos tipos; “integer – boolean – char – strings – real etc.” c- Tipo abstrato de dados:
R:
É um modelo matemático, acompanhado das operações definidas sobre o modelo. Além disso, é uma metodologia de programação que tem como proposta reduzir a informação necessária para a criação/programação de um algoritmo através da abstração das variáveis envolvidas em uma única entidade fechada, com operações próprias à sua natureza.
2- O que significa dizer que uma função g(u) é O(f(u))?
R:
Significa que a função f(u) domina assintoticamente a função g(u), ou seja, existe uma constante C e um número M, ambos maiores que zero, tal que C.f(u) > g(u) para u>M, em outras palavras, g(u) é no máximo a ordem de f(n). Veja gráfico abaixo:

3- O que significa dizer que um algoritmo executa em tempo proporcional a n?
R:
Significa que a razão de crescimento de uma função linear para tamanhos diferentes de n, cresce proporcionalmente no tempo de execução de um programa. Exemplo um algoritmo linear executa um milhão de operações em 1 segundo, logo 2 segundos o mesmo executa dois milhões de operações.
4- Qual a diferença entre O(1) e O(2)?
R:
Algoritmos O(1) e O(2)são de complexidade constante, o uso do algoritmo independe de n, ou seja, as instruções do algoritmo são executadas em número