algoritmos estruturados 2

Prévia do material em texto

Exercício Algoritmo Estruturado II –valor (2 pontos) 
Aluno(a):___________________________________ Data: 24/08/2021 
Aluno(a):___________________________________ Data Entrega: 31/08/2021 
Professor: Ronilson R. Pinho 
1) Suponha que cada expressão abaixo represente o tempo T(n) consumido por 
um algoritmo para resolver um problema de tamanho n. Escreva os termo(s) 
dominante(s) para valores muito grandes de n e especifique o menor limite 
assintótico superior Ο(n) possível para cada algoritmo. 
 
2) Uma imagem discreta de largura W e altura h, pode ser representada em 
um computador através de uma matriz I[i,j], de ordem w ´h, que armazena 
em cada posição um número inteiro entre 0 e 255, o qual especifica uma 
certa cor em uma paleta de cores. Em pacotes de pintura interativos, é 
muito comum a operação que efetua o preenchimento de certa área de uma 
imagem com uma cor cant com uma nova cor c. Esta operação pode ser 
realizada de forma simples através de um método denominado Boundary-
fill. 
O procedimento em questão recebe como entrada um ponto no interior da 
região especificado por índices (x,y) e a cor de preenchimento c. O 
algoritmo inicialmente detecta a cor cantno ponto (x,y) e começa pintando tal 
ant. O processo é repetido recursivamente 
para os vizinhos acima I[x+1,y], abaixo I[x-1,y], à esquerda I[x,y-1] e à 
direita I[x,y+1] desde que estejam dentro da imagem e possuam cor igual a 
cant, isto é, igual a cor a ser substituída. 
Escreva procedimento que implemente tal algoritmo. 
 
 
3) Resolva as questões abaixo: 
 
a) Sejam f(n) e g(n) funções assintoticamente não negativas. Usando a 
definição básica da notação Θ, prove que max(f(n), g(n)) = Θ(f(n) + 
g(n)). 
 
b) Mostre que, para quaisquer constantes reais a e b, onde b > 0 
(n+a)
 b
 = Θ(nb) 
c) Prove que o tempo de execução de um algoritmo é Θ( g(n)) se e 
somente se seu tempo de execução do pior caso é O( g(n)) e seu 
tempo de execução do melhor caso é Ω( g(n)). 
d) Expresse a função n3/1000 − 100n2 − 100n + 3 em termos da notação 
Θ, O e Ω 
e) Considere a ordenação de n números armazenados no arranjo A, 
localizando primeiro o menor elemento de A e permutando esse 
elemento com o elemento contido em A[1]. Em seguida, determine o 
segundo menor elemento de A e permute-o com A[2]. Continue 
dessa maneira para os primeiros n − 1 elementos de A. 
Escreva o pseudocódigo para esse algoritmo, conhecido como 
ordenação por seleção. Qual invariante de laço esse algoritmo 
mantém? Por que ele só precisa ser executado para os primeiros n − 
1 elementos, e não para todos os n elementos? Forneça os tempos 
de execução do melhor caso e do pior caso da ordenação por 
seleção em notação Θ. 
 
4) Quantas unidades de tempo são necessárias para rodar os algoritmos 
abaixo? Qual a ordem de complexidade de tempo de cada? 
Questão a) 
 
Questão b)