Algoritmos e complexidade Flashcards
O que são sub-rotinas?
São blocos (de funções) que realizam tarefas específicas
Para o que sub-rotinas são utilizadas?
Principalmente para a redução de complexidade de um algoritmo
Quais as partes obrigatórias de uma sub-rotina?
Nome, tipo de retorno e corpo da função
Qual a diferença entre função e procedimento?
Funções retornam valores, enquanto procedimentos não retornam nada
Cite algumas vantagens de sub-rotinas:
- Torna o algoritmo mais legível
- Podem ser testadas individualmente
- São independentes
- Podem ser reutilizadas
- Facilitam a manutenção do algoritmo
O que são vetores?
Uma lista de variáveis com mesmo tipo primitivo armazenada na memória de maneira sequencial
O que são registros?
Uma lista de variáveis que podem ter diferentes tipos primitivos, armazenada na memória de maneira sequencial
O que são ponteiros?
Variáveis que armazenam o endereço na memória de outras variáveis
Qual a principal justificativa para o uso de ponteiros?
Gerenciar o armazenamento de endereços na memória
Quais pontos a análise de algoritmos leva em consideração?
A exatidão do algoritmo, o tempo de execução e o espaço que ocupa em memória
O que é análise assintótica?
Uma análise que descreve a complexidade de um algoritmo quando a entrada de dados se torna muito grande.
O que é definição recursiva?
Quando um item é definido, e aparece como parte da própria definição.
Como também é chamada a definição recursiva?
Definição Indutiva
Quais as partes de uma definição recursiva?
1 - Uma base, que determina um caso simples de item definido
2 - Um passo recursivo, onde os outros casos do item vão ser definidos com base nos casos anteriores
Onde a definição recursiva pode ser utilizada?
1 - Sequência de objetos
2 - Funções
3 - Conjuntos
O que é uma sequência de objetos?
Uma lista de objetos enumerados.
O que ocorre com uma sequência de objetos quando é recursiva?
Explicita o primeiro valor e define os próximos valores com base no inicial
Qual a definição recursiva de uma função?
Um domínio de inteiros não negativos com dois passos.
O que é o problema de Fibonacci?
Uma sequência infinita de números naturais, aonde a partir do terceiro o valor é obtido pela soma dos dois números anteriores.
Qual a fórmula do algoritmo de Fibonacci?
F(n) = F(n-1) + F(n-2)
O que é um conjunto?
Um conjunto de valores finitos e desordenados.
Quais as 3 leis da recursividade?
1 - Deve ter um caso básico
2 - Deve mudar seu estado e se aproximar do caso básico
3 - Deve chamar a si mesmo
Quais os tipos de recursividade?
1 - Em cauda
2 - Indireta
3 - Aninhada
O que é a recursividade em cauda?
Quando a função chama ela mesmo no final da sua execução
