Buscar

RESUMÃO ED I

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Contagem de Algoritmo
Cada laço for equivale a N instruções executadas
Exemplo: 
Quantas instruções serão executadas? 
Se cada laço for equivale a N e temos 2 laços for, faremos: N*N.
Então, esse algoritmo executa O(n²) instruções. 
Está em tempo polinomial de grau 2.
AULA 2 COMPLEXIDADE DE ALGORITMOS
Sinopse: Nesta aula estudaremos as notações Big-O e como realizar a contagem de instruções (algoritmos).
Exercício X Problema
Exercício: é aquele que já temos conhecimento de como resolver.
	EX: Calcule 3*2.
	Aqui temos algo que sabemos imediatamente como resolver, mal precisamos pensar na resolução, GG Easy.
Resposta : 6
Problema: precisa de mais reflexão e esforço para criar uma solução.
EX: Em uma prova de física, Sheldon e Leonard tiraram 10 e Howard tirou 9. Quantos porcentos Sheldon e Leonard tiraram a mais que Howard?
	Percebe que aqui temos algo mais complexo, que exige uma reflexão mais profunda? Essa é a característica do problema, DIFICULDADE!
Resposta : 10%.
Pilares para um bom Desempenho de Solução
Dentro de um algoritmo devemos analisar:
Completeza: certeza de encontrar uma solução para o problema.
Otimização: se tem uma solução ótima (leva-se em consideração tempo e espaço).
Tempo/Velocidade: quantidade de tempo que o algoritmo leva para ser executado.
Espaço: quantidade de memória que o algoritmo ocupa.
Complexidade algorítmica: medida de eficiência e custo da implementação. Utilizamos a notação Big-O, para definir sua complexidade. 
Funções Polinomiais X Exponenciais
Polinomial: o problema é considerado TRATÁVEL. Seu expoente sempre é um número POSITIVO!
Exponencial: o problema é considerado INTRATÁVEL, pois nenhum computador o resolve num tempo satisfatório, a menos que “x" seja pequeno.
Insertion Sort
Para cada posição i de 1 até a última posição do vetor: Guardar o valor que está na posição i em uma variável temporária x. 
 Com um ciclo interno j começando em i, analisar, de direita para esquerda e, enquanto j > 0 e x for menor que o elemento na posição j-1: deslocar o valor em j-1 para direita, abrindo um espaço para inserção. 
 Colocar o valor x na posição de inserção j.
Toda vez que a variável que controla o laço é dividida por um número b, sua complexidade será de O(logb n).
Exemplo: 
Quantas instruções serão executadas? 
O contador (no caso i) está sendo dividido por 10.
Então, esse algoritmo executa O(log10 n) instruções. 
Está em tempo logarítmico de base 10.
AULA 3
VETORES: BUSCA E DESLOCAMENTO
Sinopse: Nesta aula estudaremos os dois tipos de busca dentro de um vetor (Sequencial e Binária) e como deslocá-lo.
Merge Sort
Merge (fundir, misturar, embaralhar) tem três etapas: 
1. Divisão: se o tamanho da entrada for menor que um certo limite, resolvemos diretamente e retornamos a solução obtida. Em qualquer outro caso, os dados de entrada são divididos, normalmente em uma ou duas partes. 
2. Recursão: Cada parte obtida no passo anterior será resolvida, utilizando o mesmo método, em forma recursiva. 
3- Conquista: as soluções dos subproblemas são unidas em uma única solução, até chegar no vetor final ordenado.
Tabela Eficiência Ordenação
O Quick Sort acaba sendo o método mais eficiente, confira o motivo:
Pilha Estática Sequencial
Quando dizemos que uma Pilha é Estática, significa que ela possui uma quantidade máxima de memória reservada.
Quando dizemos que a pilha é Sequencial, como o próprio nome sugere, significa que os elementos dela estão colocados um depois do outro, em uma ordem.
Assim, a quantidade de elementos não pode ultrapassar a quantidade de memória máxima e não podemos retirar elementos de uma pilha vazia.
Para suprir esses limites, precisamos de mais quatro métodos: 
construtor - inicializa a pilha no estado “vazia” e, opcionalmente, define a memória inicial; 
isEmpty - verifica se a pilha está vazia; 
 isFull - verifica se a pilha está “cheia”; 
 toString - para retornar os itens da pilha.
Pilha Dinâmica Encadeada
Faz uma requisição à memória heap toda vez que um novo elemento precisa ser inserido na Pilha. 
Ela libera a memória usada por um elemento que foi excluído dela, e acabamos usando somente a quantidade de memória exata que o programa necessita.
Para implementar, vamos pensar que cada elemento da Pilha será um nó ou nodo, sendo que teremos acesso somente ao topo da pilha (estrutura LIFO).
Usa organização encadeada, ou seja, os elementos não necessariamente estão dispostos na ordem física da memória, portanto, cada elemento deverá conter o endereço do próximo elemento da pilha.
EXERCÍCIOS DE FIXAÇÃO
RESPOSTAS
Para a esquerda quando queremos retirar um número;
Exemplo retirar o número 4.4.
No próximo slide veremos a implementação do código...
321
0.9
72
55
4.4
0
1
2
3
4
321
0.9
72
55
0
1
2
3
4
AULA 4
MÉTODOS DE ORDENAÇÃO PARTE I
Sinopse: Nesta aula estudaremos os métodos mais simples de ordenar um vetor: Bubble Sort, Insertion Sort e Selection Sort.
{5, 4, 3, 1, 2}: 5 > 4 = Sim, realizar troca. Reordenando o vetor:
{4, 5, 3, 1, 2}: 5 > 3 = Sim, realizar troca. Reordenando o vetor:
{4, 3, 5, 1, 2}:  5 > 1 = Sim, realiza troca. Reordenando o vetor:
{4, 3, 1, 5, 2}:  5 > 2 = Sim, realiza troca. Reordenando o vetor:
{4, 3, 1, 2,5}:  5 está na última posição, o vetor permanece como está.
Com isso é feito uma segunda iteração por completo. O processo vai se repetir.
{4, 3, 1, 2,5}:  4 > 3 = Sim, realiza troca. Reordenando o vetor:
{3, 4, 1, 2,5}:  4 > 1 = Sim, realiza troca. Reordenando o vetor:
{3, 1, 4, 2,5}:  4 >2 = Sim, realiza troca. Reordenando o vetor:
{3, 1, 2, 4,5}:  4 > 5 = Não, vetor permanece como está.
Terceira iteração realizada por completo. O processo se repete novamente:
{3, 1, 2, 4,5}:  3 > 1 = Sim, realiza troca. Reordenando o vetor:
{1, 3, 2, 4,5}:  3 > 2 = Sim, realiza troca. Reordenando o vetor:
{1, 2, 3, 4,5}:  3 > 4 = Não, vetor permanece como está.
{1, 2, 3, 4,5}:  4 > 5 = Não, vetor permanece como está.
Quarta iteração realizada por completo. O processo se repete novamente:
{1, 2, 3, 4,5}:  1 > 2 = Não, vetor permanece como está.
{1, 2, 3, 4,5}:  2 > 3 = Não, vetor permanece como está.
{1, 2, 3, 4,5}:  3 > 4 = Não, vetor permanece como está.
{1, 2, 3, 4,5}:  4 > 5 = Não, vetor permanece como está.
Vetor inicial: {5, 1, 7, 2}
[ 5, 1, 7, 2 ] : Como dito, iniciamos a trabalhar com o segundo valor do vetor, a posição v[1].
[ (5, 1), 7, 2 ] : Comparamos com o valor anterior.  1 < 5? Sim, realiza troca. 
[ 1, 5, 7, 2 ].
Na segunda iteração pegamos o próximo valor v[2].
[ 1, 5, 7, 2 ] 
[ 1, (5, 7), 2 ] :  Comparamos com o valor anterior. 7<5? Não, permanece como está.
Terceira iteração pegamos o próximo valor v[3].
[ 1, 5, 7, 2 ] : 
[ 1, 5, (7, 2) ] :   Comparamos com o valor anterior. 2<7? Sim, realiza troca. 
[ 1, (5, 2), 7 ] :   Comparamos com o valor anterior. 2<5? Sim, realiza troca.
[ (1, 2), 5, 7 ] :  Comparamos com o valor anterior. 2<1? Não, permanece como está.
Vetor Final: {1,2,5,7}
AULA 5
MÉTODOS DE ORDENAÇÃO PARTE II
Sinopse: Nesta aula estudaremos os métodos conhecidos como “Dividir para Conquistar”: Quick Sort e Merge Sort, além da definição de recursividade.
Recursividade
Quando o método chama a si próprio. É como se fosse um dentro de um sonho!
Divisão e Conquista
O Discurso do Método, de René Descartes, divide o raciocínio em 4 etapas:
Receber as informações, examinando sua racionalidade e aceitar somente o que não tenha dúvidas de ser verdade. 
Análise, divide o problema em problemas menores. 
Síntese, pega as partes que foram divididas e elabora suas conclusões. 
Juntar todas as conclusões para gerar uma solução do problema original de modo que seja coerente. 
Primeiro
selecionamos um pivô.
A partir dele, iremos dividir o vetor em duas partes.
Do lado esquerdo, os números menores que o pivô selecionado. (Lembre-se quanto mais pra esquerda, MENOR)
Do lado direito, os números maiores que o pivô selecionado. (Lembre-se quanto mais pra direita, MAIOR)
Vamos repetir o processo até o vetor estar ordenado.
Vetor Final: {-6, -3, 1, 2, 5, 6, 8, 9}
Outro exemplo de Quick Sort
Primeiro dividimos o vetor (embaralhamos).
Vamos dividir até não ser mais possível.
Quando isso ocorrer, iremos comparar, sempre em pares, qual o menor e maior valor, realizando as trocas necessárias.
Vamos repetir o processo até o vetor estar ordenado.
Outro exemplo de Merge Sort
AULA 7 
PILHAS ESTÁTICAS SEQUENCIAIS
Sinopse: Nesta aula estudaremos a definição de Pilhas Estáticas Sequenciais e como construí-las.
Tipos de Dados Primitivos
Tipos de Dados Estruturados
São organizações de dados obtidas a partir dos dados primitivos.
Vetores (unidimensional) e matrizes (bidimensional).
Tipos de Dados Abstratos
São as interfaces (classes abstratas), onde nos preocupamos apenas com o que ele faz e não em como faz. 
Por isso, além de termos nele alguns tipos de dados, vamos ter, métodos. Em outras palavras é apenas uma classe de definição de métodos. 
Suas vantagens são:
Integridade dos dados; 
Facilidade de manutenção; 
Reutilização.
Pilha em Geral
Last In, First Out (LIFO), o último que entrou será o primeiro a sair.
Temos acesso somente ao topo da pilha, ou seja, quando queremos inserir um elemento, colocamos no topo e se quisermos excluir um elemento, só podemos excluir o que está no topo.
Uma Pilha possui três operações básicas:
 top: retorna, sem eliminar, o elemento do topo;
push: insere um novo elemento no topo; 
pop: remove um elemento do topo.
No Tipo Abstrato da Pilha vamos:
Criar uma pilha vazia; 
Testar se a pilha está vazia; 
Testar se a pilha está cheia; 
Empilhar (push) um elemento no topo de uma pilha não cheia; 
Desempilhar (pop) o elemento do topo de uma pilha não vazia;
 Ler o elemento no topo de uma pilha não-vazia. 
Todas estas operações possuem tempo de execução constante em relação à entrada: O(1).
AULA 8 
PILHAS DINÂMICAS ENCADEADAS
Sinopse: Nesta aula estudaremos a definição de Pilhas Dinâmicas Encadeadas e como construí-las.
Como a alocação será dinâmica, não teremos a implementação de isFull, pois a Pilha não estará "cheia". Todos os métodos anteriores tem O(1), mas toString() é de O(n).
1) O algoritmo de ordenação que encontra o menor elemento e o troca com a primeira posição, depois o segundo menor com a segunda posição, e assim sucessivamente (n-1 vezes), usa o método de:
	a) Selection
	b) Insertion
	c) Bubble
	d) Merge
2) Para poder ser aplicado, o algoritmo de pesquisa binária exige que os elementos do array: 
	a) Sejam números
	b) Não sejam repetidos
	c) Estejam ordenados
	d) Ocupem somente as posições pares
3) O algoritmo QuickSort usa uma técnica conhecida por divisão e conquista, onde problemas complexos são reduzidos em problemas menores para se tentar chegar a uma solução. A complexidade deste algoritmo em sua implementação padrão e a de pior caso são, respectivamente:
	a) O(n log n) e O(n²)
	b) O(n) e O(n)
	c) O(n log n) e O(n log n)
	d) O(n) e O(n²)
4) A seleção de uma estrutura de dados adequada muitas vezes acelera a solução de um problema. A Pilha é uma das estruturas de dados mais importantes. Que propriedade caracteriza uma Pilha?
	a) Permite inserção em qualquer posição.
	b) O último elemento inserido será o primeiro a ser removido.
	c) O primeiro elemento inserido será o primeiro a ser removido.
	d) Seus nós têm no máximo dois filhos.
5) Um problema de algoritmo em uma estrutura recursiva demostra que: 
	a) Cada instância do problema contém uma instância menor do mesmo problema. 
	b) Toda instância do problema contém uma instância maior do mesmo problema. 	
	c) Cada instância do problema contém uma instância maior do mesmo problema. 	
	d) Cada instância do problema contém uma instância maior de outro problema. 
6) Considere os seguintes algoritmos e suas complexidades na notação Big O:
	Algoritmo A: O(log n)  || Algoritmo B: O(n2)  || Algoritmo C: O(n . log n) 
Considerando que são os piores casos de execução destes algoritmos, é correto afirmar que o algoritmo 
	a) A é o menos eficiente.
	b) C é o menos eficiente
	c) C é o mais eficiente
	d) B é o menos eficiente
7) Observe os quadros I e II, relacionados à estrutura de dados pilha. 
	
Após a execução de todas as operações indicadas no quadro II, o elemento de topo da pilha será igual a:
a) SANTA_CATARINA
b) SANTO_EXPEDITO
c) SANTA_GENOVEVA
d) SANTO_AGOSTINHO
8) O algoritmo Bubble Sort é popular, mesmo que ineficiente. Usando-se esse algoritmo para ordenar uma tabela, alocada sequencialmente, em ordem crescente contendo os números [5, 4, 1, 3, 2] serão feitas: 
	a) 10 comparações e 8 trocas
	b) 10 comparações e 9 trocas
	c) 10 comparações e 10 trocas
	d) 16 comparações e 9 trocas
9) Observe o algoritmo em JAVA. 
	
A complexidade de tempo desse algoritmo, no pior caso, em que n corresponde ao número de elementos do vetor v, é:
a) O(n log n)
b) O(n)
c) O(log2 n)
d) O(n²)
10) String paisesA [] = { "Suíça", "México", "Espanha", "Canadá", "Brasil}; 
String paisesB [] = {"Brasil", "Chile", "França", "Inglaterra", "Uruguai" }; 
String paisesC [] = { "Canadá", "Áustria", "Itália", "Portugal", "Grécia"};
I. Para buscar um país em paisesA[] o método mais adequado seria o da busca binária. 
II. Para buscar um país em paisesC[] o método mais adequado seria o da busca binária
III. Com o método de busca sequencial, no pior caso, encontrar um país tem complexidade O(n²).
IV. Seria possível buscar um país em paisesB[] com o método de busca sequencial.
V. Com o método de busca binária, no pior caso, encontrar um país tem complexidade O(log n).
	a) Apenas as afirmativas I, III, V são verdadeiras.
	b) Apenas as afirmativas I, IV e V são verdadeiras.
	c) Apenas as afirmativas I, II e IV são verdadeiras.
	d) Todas as afirmativas são verdadeiras.
1 - Correta a) Selection
2 - Correta c) Estejam ordenados
3 - Correta a) O(n log n) e O(n²)
4 - Correta b) O último elemento inserido será o primeiro a ser removido. 
5 - Correta a) Cada instância do problema contém uma instância menor do mesmo problema. 
6 - Correta d) B é o menos eficiente
7 - Correta a) SANTA_CATARINA
8 - Correta a) 10 comparações e 8 trocas
9 - Correta d) O(n²)
10 - Correta b) Apenas as afirmativas I, IV e V são verdadeiras.

Teste o Premium para desbloquear

Aproveite todos os benefícios por 3 dias sem pagar! 😉
Já tem cadastro?

Outros materiais