Aula 6 - Revisão AV1

Prévia do material em texto

CCT0608 ALGORITMOS AVANÇADOS
Aula 6: Revisão AV1
Prof. Dr. Roney L. de S. Santos
RONEY.LIRASALE@professores.estacio.br
DEFINIÇÕES IMPORTANTES
2
• Vetores
• Matrizes
• Ponteiros
• Registros (Struct)
• Funções
DEFINIÇÕES IMPORTANTES
3
• Vetores
– Arranjo cuja capacidade pode variar dinamicamente.
– Se o espaço reservado for totalmente ocupado e espaço adicional for
necessário, este será alocado automaticamente
• o programador não precisa se preocupar com a capacidade de armazenamento ou
com a ocupação até o momento
• Matrizes
• Ponteiros
• Registros (Struct)
• Funções
DEFINIÇÕES IMPORTANTES
4
• Vetores
• Matrizes
– Coleção de elementos de mesmo tipo acessíveis com um único nome e
armazenados contiguamente na memória.
– A individualização de cada elemento de um vetor é feita através do uso
de índices.
– Os vetores são matrizes de uma só dimensão.
• Ponteiros
• Registros (Struct)
• Funções
DEFINIÇÕES IMPORTANTES
5
• Vetores
• Matrizes
• Ponteiros
– O programador é responsável por operar explicitamente com os
endereços das variáveis
• Registros (Struct)
• Funções
DEFINIÇÕES IMPORTANTES
6
• Vetores
• Matrizes
• Ponteiros
• Registros (Struct)
– Permite agrupar dados de diferentes tipos numa mesma estrutura
• Ao contrário de matrizes que possuem elementos de um mesmo tipo
• Funções
DEFINIÇÕES IMPORTANTES
7
• Vetores
• Matrizes
• Ponteiros
• Registros (Struct)
• Funções
– Ideia básica : é encapsular um código que poderá ser
invocado/chamado por qualquer outro trecho do programa
– Implementada em alguma linguagem de programação
ALGORITMOS
8
ALGORITMOS
9
• Projetar algoritmos corretos
– Geram a solução esperada
• Eficientes
– Executam em tempo e espaço aceitáveis para problemas complexos
• Um algoritmo resolve um problema quando, para qualquer
entrada, produz uma resposta correta
– Se forem concedidos tempos e memória suficientes para sua execução
ALGORITMOS
10
• O fato de um algoritmo resolver (teoricamente) um problema
não significa que seja aceitável na prática
• Recursos de espaço e tempo requeridos têm grande importância
em casos práticos
• Às vezes, o algoritmo mais imediato está longe de ser razoável
em termos de eficiência
– Conseguem dar um exemplo?
ANÁLISE DE COMPLEXIDADE
11
• Principais medidas de complexidade:
– Tempo
– Espaço
– Relação a velocidade e a quantidade de memória
• Formas de medir a complexidade: empírica
– Podemos pensar em medir experimentalmente a quantidade de trabalho
(tempo ou memória) requerida por um algoritmo executado em um
computador específico.
ANÁLISE DE COMPLEXIDADE
12
Quantidade de trabalho para executar um algoritmo
=
DESEMPENHO DO ALGORITMO
• Complexidade pessimista fornece o pior caso
– Máximo esforço
• Tempo requerido por um algoritmo sobre uma entrada pode ser
medido pelo número de execuções de algumas operações
ANÁLISE DE COMPLEXIDADE
13
• Tempo de Execução depende:
– Da implementação computacional
• Programa, linguagem, compilador
– Do ambiente de execução
• Processador
• Sistema operacional
• Memória (real e cache)
• Barramento...
– Organização e conteúdo dos dados de entrada
ANÁLISE DE COMPLEXIDADE
14
• Deve-se identificar as operações primitivas e quantidade de
vezes que são executadas:
NOTAÇÃO ASSINTÓTICA
15
• Usada para problemas realmente grandes
– Com entradas grandes
• Preocupação com o quão rápido os limites serão atingidos
– Ordem de Crescimento de Funções
– Pior caso
ANÁLISE ASSINTÓTICA
16
• A notação O define uma cota assintótica superior a menos de
constantes
• A função quadrática g(n) = n2 cresce mais rapidamente do que
a linear f(n) 7n + 13. Dizemos que a f(n) é O(g(n))
• Dizer que um algoritmo é O(1) significa que o número de
operações primitivas executadas é limitado por uma constante
– Analogamente, uma função O(n) é limitada superiormente por uma
função linear cn
ANÁLISE ASSINTÓTICA
17
ANÁLISE ASSINTÓTICA
18
ANÁLISE ASSINTÓTICA
19
ANÁLISE ASSINTÓTICA
20
ANÁLISE ASSINTÓTICA
21
ANÁLISE ASSINTÓTICA
22
RECURSIVIDADE
23
• É uma técnica de programação na qual um método chama a si
mesmo.
• Uma função é dita recursiva quando dentro dela é feita uma ou
mais chamadas a ela mesma.
RECURSIVIDADE
24
• A ideia é dividir um problema original um subproblemas
menores de mesma natureza (divisão) e depois combinar as
soluções obtidas para gerar a solução do problema original de
tamanho maior (conquista).
• Os subproblemas são resolvidos recursivamente do mesmo modo
em função de instâncias menores, até se tornarem problemas
triviais que são resolvidos de forma direta, interrompendo a
recursão.
RECURSIVIDADE
25
• Uma definição recursiva é constituída de duas partes:
• Parte 1
– Há um ou mais casos base que dizem o que fazer em situações simples
• A resposta pode ser dada de imediato
– Garante que a recursão eventualmente possa parar.
• Parte 2
– Há um ou mais casos recursivos que são mais gerais e definem a função
em termos de uma chamada mais simples a si mesma.
RECURSIVIDADE
26
• Exemplo 1: Fatorial de um número
CASO BASE
CASO RECURSIVO
RECURSIVIDADE
27
• Exemplo 1: Fatorial de um número
RECURSIVIDADE
28
• Pilha de Execução: fat(5)
Fonte: Embarcados. Disponível em https://embarcados.com.br/recursividade/
https://embarcados.com.br/recursividade/
RECURSIVIDADE
29
• Exemplo 1: Fatorial de um número: Recursivo vs Iterativo
RECURSIVIDADE
30
• Código RECURSIVO vs Código ITERATIVO
• Tanto recursão quanto iteração usam repetição
– Iteração: comandos de repetição (for, while, do while, ...)
– Recursão: chamadas repetitivas a uma rotina
• Ambas precisam de um teste de terminação
– Iteração: quando uma expressão lógica de teste é falsa
– Recursão: quando se atinge o caso trivial
– Ambas podem entrar em loop...
• no caso da iteração se o teste nunca se tornar falso e no caso da recursão se o
problema não for reduzido de forma que convirja para o caso trivial
RECURSIVIDADE
31
• Código RECURSIVO vs Código ITERATIVO
• Gasto computacional (complexidade) da recursão é maior na
maioria das vezes!
– Vale a pena?
– É menos custoso implementar a mesma função de forma iterativa?
PRÁTICA
32
• Implemente soluções recursivas e iterativas para resolver os
problemas a seguir:
• Calcular xn, sendo n > 0
• Imprimir todos os elementos de um vetor
• Somar os elementos de uma lista de inteiros
• Transformar um número n >= 0 em binário
PRÁTICA
33
• Calcular xn, sendo n > 0
PRÁTICA
34
• Imprimir todos os elementos de um vetor
PRÁTICA
35
• Somar os elementos de uma lista de inteiros
PRÁTICA
36
• Somar os elementos de uma lista de inteiros
PRÁTICA
37
• Transformar um número n >= 0 em binário
CCT0608 ALGORITMOS AVANÇADOS
38
• Dúvidas?
• Fiquem à vontade para entrar em contato no 
RONEY.LIRASALE@professores.estacio.br
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39