Lista de exercícios sobre AEDS

Mini Teste 1 - AEDS - Tutoria

1Instituto de Ciencias Exatas e Aplicadas Universidade Federal de Ouro Preto (UFOP)Departamento de Engenharia de Computacao e Sistemas de Informacao

Joao Monlevade, MG Brasil

1. Escreva o que voce entende sobre:(a) Algoritmo

Uma sequencia de passos bem definidas para resolver um problema.(b) Tipo de dados

Metodos para interpretar o conteudo da memoria do computador.(c) Tipo abstrato de dados Conjunto de valores com operacoes bem definidas

sobre ele.

2. O que significa dizer que g(n) = O(f(n))?Significa que f(n) domina assintoticamente g(n).

3. Seja o problema de multiplicar um numero k por ele mesmo, n vezes. Apresenteuma funcao recursiva em C que resolva este problema e de sua complexidade.

int multiplica(int k, int n){if( n == 0 )

return 1;

return k * multiplica(k, n-1);

}

A relacao de recorrencia que descreve esse algoritmo e dada por:

T (n) = 1 p/n = 0

T (n) = T (n 1) + 1 p/n 0A resolucao desta relacao de recorrencia se assemelha com a do fatorial. Se ex-pandirmos T (n) ate T (n 2) teremos:

T (n) = T (n 3) + 3

logo

T (n) = T (n k) + k

chegaremos no caso base quando n k = 0 k = n, portanto:

T (n) = T (n n) + n

T (n) = T (0) + n

T (n) = 1 + n

E logo este algoritmo e O(n).

4. Qual o conceito de inducao matematica?A inducao matematica busca provar algum problema K atraves de provar K + 1.Se pudermos provar K + 1 utilizando K, entao K tambem sera provado.

5. Crie um struct para abstrair um livro. Crie as caractersticas que achar necessarias.

struct livro{int paginas;int codigo;char autor[50];char tipo[30];

};