Grátis: As recorrências são importantes no projeto de algoritmos por permitirem construir algoritmos recursivos que podem ter uma prova de corretude mais s... – Questões Respondidas

Lógica de Programação

Outros

As recorrências são importantes no projeto de algoritmos por permitirem construir algoritmos recursivos que podem ter uma prova de corretude mais sistemática.
Com relação a este contexto e levando em consideração o algoritmo de MergeSort, analise as asserções a seguir e a relação proposta entre elas:
I. A equação de recorrência do tempo de execução é T(n) quando n = 1 e T(n) = T(n/2) + n para caso recorrente, quando n > 1.
II. Quando n = 1, trata-se de um vetor de um elemento que pode ser considerado ordenado, portanto o tempo é constante. Quando n > 1, o vetor precisa ser dividido em 2 partes para a ordenação e isso justifica o termo T(n/2) na equação e, além disso, existe o processo de combinação das 2 partes pelo algoritmo Merge que processa n elementos, justificando o termo.
a. As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
b. As asserções I e II são falsas.
c. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
d. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.
e. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.

Aprendendo Através de Exercícios

há 4 dias

Aprendendo Através de Exercícios

há 4 dias

Aval-Sem02-COM540

Aval-Sem02-COM540

UNIVESP

Respostas

Ed

há 4 dias

Vamos analisar as asserções: I. A equação de recorrência do tempo de execução é T(n) quando n = 1 e T(n) = T(n/2) + n para caso recorrente, quando n > 1. Esta afirmação é verdadeira. A equação de recorrência para o MergeSort é corretamente expressa dessa forma. II. Quando n = 1, trata-se de um vetor de um elemento que pode ser considerado ordenado, portanto o tempo é constante. Quando n > 1, o vetor precisa ser dividido em 2 partes para a ordenação e isso justifica o termo T(n/2) na equação e, além disso, existe o processo de combinação das 2 partes pelo algoritmo Merge que processa n elementos, justificando o termo. Esta afirmação também é verdadeira. Ela explica corretamente a lógica por trás da equação de recorrência. Agora, vamos verificar a relação entre as asserções: - A asserção II realmente justifica a asserção I, pois explica o porquê da equação de recorrência apresentada. Portanto, ambas as asserções são verdadeiras e a II é uma justificativa da I. A alternativa correta é: a) As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.

Essa resposta te ajudou?

0

0

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

Aval-Sem02-COM540

Aval-Sem02-COM540

UNIVESP

Mais perguntas desse material

Leia trecho a seguir: Na análise de algoritmos, uma [preencher 1] é uma expressão que define uma função em termos dela mesma. Esse conceito é amplamente utilizado em algoritmos [preencher 2], como MergeSort. Esse tipo de expressão permite entender a complexidade de algoritmos que se dividem em subproblemas menores, resolvendo cada um deles de forma recursiva.
Os termos [preencher 1] e [preencher 2] são corretamente substituídos por:
a. 1 variável; 2 lineares
b. 1 equação; 2 recursivos
c. inequação; 2 não recursivos
d. 1 fórmula; 2 simples
e. 1 relação; 2 iterativos

No algoritmo MergeSort, vetor é repetidamente dividido em sub-vetores menores até que cada sub-vetor contenha apenas um elemento. Este processo de divisão é uma parte essencial do algoritmo, pois facilita a subsequente combinação ordenada dos elementos.
Considere vetor [38, 27, 43, 3, 9, 82, 10] e observe como ele é dividido na primeira fase do MergeSort. Nesse sentido, vetor após a primeira divisão completa no algoritmo MergeSort é:
a. [3, 9, 10, 27, 38, 43, 82]
b. [38, 27] e [43, 3] e [9, 82] e [10]
c. [27, 38, 3, 43, 9, 10]
d. [38, 27, 43, 3, 9, 82, 10]
e. [38, 27, 43, 3] e [9, 82, 10]

O segundo princípio da indução matemática é uma variação do primeiro princípio e é utilizado em situações onde a proposição depende não apenas do caso anterior, mas de múltiplos casos anteriores. Isso é especialmente útil em sequências ou séries onde cada termo é definido com base em vários termos anteriores. O processo envolve uma etapa inicial de verificação para um conjunto de casos base, seguida de uma etapa indutiva.
Neste contexto, assinale a alternativa que descreve corretamente o segundo princípio da indução matemática.
a. Prove que a proposição é verdadeira para todos os números impares. Depois, prove que é verdadeira para todos os números pares.
b. Prove que a proposição é verdadeira para todos os números pares. Depois, prove que é verdadeira para todos os números.
c. Suponha que a proposição é verdadeira para um número finito de casos consecutivos. Prove que é verdadeira para o próximo caso.
d. Suponha que a proposição é verdadeira para um caso arbitrário k. Prove que é verdadeira para 2k.
e. Provar que a proposição é verdadeira para caso base e para um caso arbitrário. Provar que é verdadeira para caso seguinte.

A indução matemática é uma técnica frequentemente utilizada. Esta técnica envolve demonstrar que uma propriedade é válida para um caso inicial e, em seguida, provar que, se for válida para um caso arbitrário n, então será válida para n+1. Sobre a aplicação da indução matemática, observe as seguintes afirmativas.
Está correto que se afirma em:
I. A indução matemática pode ser utilizada para provar propriedades de laços em algoritmos.
II. O primeiro passo na indução matemática é estabelecer a proposição base.
III. A indução matemática é uma técnica exploratória para descobrir novas propriedades.
a. II, apenas.
b. I e III, apenas.
c. III.
d. I e II, apenas.
e. I, II e III.

A ordenação é uma operação bastante comum no trato com dados. Por exemplo, ao recuperar os dados em um banco de dados é possível usar a cláusula 'ORDER BY' para recuperar dados ordenados e em planilhas eletrônicas é possível solicitar a ordenação de suas linhas.
Com base na execução do algoritmo, calcule quantas chamadas recursivas à função MergeSort ocorrem na subárvore de recursão proveniente da chamada MergeSort(Vetor, 10, 15), desconsiderando esta chamada com índices 10 e 15 na contagem.
a. 13 chamadas
b. 8 chamadas
c. 10 chamadas
d. 14 chamadas
e. 15 chamadas

O algoritmo de ordenação por inserção é frequentemente utilizado para ordenar pequenas quantidades de elementos, como ilustrado por uma analogia com o processo de ordenar cartas em um jogo de baralho.
Sobre os invariantes de laço no algoritmo de ordenação por inserção, assinale a alternativa que descreve corretamente como a correção do algoritmo é demonstrada por meio do invariante de laço:
a. O invariante de laço verifica se o número total de comparações é constante em cada iteração.
b. O invariante de laço prova que o arranjo é ordenado somente quando o número de comparações é menor que o tamanho do arranjo.
c. O invariante de laço garante que, ao final de cada iteração, o subarranjo de elementos até a posição atual está ordenado.
d. O invariante de laço indica que a complexidade do algoritmo é mantida constante a cada iteração.
e. O invariante de laço garante que, a cada iteração do laço, o arranjo inteiro já está ordenado.

A técnica de indução matemática é amplamente utilizada no desenvolvimento de algoritmos, especialmente em algoritmos recursivos. Ela ajuda a estabelecer a corretude e garantir que o algoritmo funcione para todos os casos possíveis.
Sobre a aplicação da indução matemática em algoritmos, avalie as afirmativas a seguir:
I. O caso-base da recursão corresponde ao caso-base da indução.
II. A hipótese de indução é utilizada para demonstrar a corretude do algoritmo para o passo k+1.
III. A indução matemática não pode ser aplicada para algoritmos recursivos.
a. I, II e III.
b. III, apenas.
c. I e II.
d. II, apenas.
e. II, apenas.

Os sistemas de informação precisam realizar as mais variadas operações sobre os dados, por exemplo, ao manter um catálogo de produtos em um site de comércio eletrônico pode inserir, alterar, excluir e listar os produtos do catálogo que serão ofertados aos clientes.
Considerando que um programador está testando a função Merge ou Combina e que ele está utilizando um vetor V com [7,8,4,7,9,5,6,1,10], assinale a alternativa que calcula o resultado da chamada à função da seguinte forma: Merge(v, 3, 5, 7).
a. [7,8,4,7,9,5,6,1,10]
b. [7,8,4,5,6,7,9,1,10]
c. [1,4,5,6,7,7,8,9,10]
d. [7,8,4,1,5,6,7,9,10]

Na computação, a ordenação de dados é um problema típico que contém diversos algoritmos clássicos, dentre eles o InsertionSort ou Ordenação por Inserção.
Considerando um vetor com os valores 10, 15, 8, 5, 3, 12, 1, avalie quantos deslocamentos de elementos à direita precisarão ser feitos para ordenar todo vetor e assinale a alternativa correta.
a. 19 deslocamentos
b. 13 deslocamentos
c. 10 deslocamentos
d. 15 deslocamentos
e. 16 deslocamentos

Leia trecho a seguir: A indução matemática é um mecanismo que pode contribuir para o projeto de algoritmos. A sua aplicação e processo de indução permite construir [Preencher 1] em que o caso base da indução equivale ao caso base da recursão e a aplicação da hipótese da indução equivale à [Preencher 2]. Um excelente benefício de aplicar a indução é que seu rigor matemático auxilia na [Preencher 3] do algoritmo.
Neste contexto, identifique os termos de [preencher 1], [preencher 2] e [preencher 3] que são substituídos por:
a. 1 algoritmos iterativos; 2 condição de parada; 3 prova de corretude.
b. 1 algoritmos recursivos; 2 recorrência; 3 prova de corretude.
c. 1 algoritmos iterativos; 2 condição de parada; 3 prova de complexidade.
d. 1 algoritmos recursivos; 2 recorrência; 3 prova de parada.
e. 1 algoritmos iterativos; 2 condição de parada; 3 prova de parada.

O projeto e análise de algoritmos pode aplicar diferentes conceitos e fundamentos matemáticos que orientam e auxiliam na construção de algoritmos e na avaliação de sua performance.
Nesse contexto, assinale a alternativa que reconhece o conceito de recorrência, na perspectiva de técnicas de projeto como a divisão e conquista:
a. Uma estrutura em árvore cuja raiz é uma chamada de função com diversos nós filhos.
b. Uma função que de forma iterativa e repetidamente realiza a ordenação de um vetor.
c. Um princípio baseado em afirmação base e na aplicação de hipótese: Se P(k) então P(k+1).
d. Uma função cuja definição é baseada na chamada ou aplicação da própria função.
e. Uma função cuja definição é baseada em comandos de controle de repetição.

A ordenação é uma das operações importantes no trato com dados, em diversas situações do cotidiano as informações ordenadas facilitam nossas tarefas.
Com base na aplicação deste algoritmo à sequência [3,2,8,7,1,5,6], analise o comportamento do vetor e assinale como ele estará ao final da iteração em que o índice 'i' assume valor 3.
a. [8,7,3,2,1,5,6]
b. [3,2,8,1,5,6,7]
c. [2,3,8,7,6,5,1]
d. [3,2,8,7,6,5,1]
e. [8,3,2,7,1,5,6]

O algoritmo InsertionSort é um método clássico de ordenação que constrói a lista ordenada um elemento por vez. Durante o processo, o algoritmo percorre a lista, movendo cada elemento para a sua posição correta.
Neste contexto, assinale a alternativa que representa a posição do número 4 após a primeira iteração do algoritmo InsertionSort.
a. Primeira posição.
b. Quarta posição.
c. Segunda posição.
d. Terceira posição.
e. Quinta posição.

Leia trecho a seguir: O algoritmo MergeSort utiliza a estratégia de intercalação para ordenar um vetor de entrada. A ideia básica é dividir o vetor original em duas partes até que cada parte tenha apenas um elemento, que está naturalmente ordenado.
Esse processo é realizado em duas etapas principais: [preencher 1] e [preencher 2].
a. Ordenação; 2 Fusão.
b. Organização; 2 Intercalação.
c. Divisão; 2 Combinação.
d. Separação; 2 Fusão.
e. Classificação; 2 Intercalação.

Durante processo, o algoritmo percorre a lista, movendo cada elemento para a sua posição correta. Considere um vetor AAA com elementos [5, 3,8,4,2]. Após a primeira iteração completa do algoritmo, o vetor já começa a mostrar sinais de ordenação.
Neste contexto, assinale a alternativa que representa a posição do número 4 após a primeira iteração do algoritmo InsertionSort.
a. Primeira posição.
b. Quarta posição.
C. Segunda posição.
d. Terceira posição.
e. Quinta posição.

Leia trecho a seguir: algoritmo MergeSort utiliza a estratégia de intercalação para ordenar um vetor de entrada. A ideia básica é dividir vetor original em duas partes até que cada parte tenha apenas um elemento, que está naturalmente ordenado. Em seguida, os vetores de um elemento são combinados em vetores de dois elementos ordenados, e assim sucessivamente, até que vetor original esteja completamente ordenado. Esse processo é realizado em duas etapas principais:
Os termos [preencher 1] e [preencher 2] são corretamente substituídos por:
a. Ordenação; 2 Fusão.
b. Organização; 2 Reunião.
d.1 Divisão; 2 Combinação.
e.1 Classificação; 2 Intercalação.

A indução matemática é uma técnica fundamental na matemática e na ciência da computação. Essa técnica assegura a validade de uma propriedade, possibilitando a demonstração de teoremas e a validação de algoritmos.
Neste contexto, identifique e associe corretamente os conceitos e as respectivas descrições de indução matemática. Considere que nem todos os itens das colunas podem possuir associação ou podem possuir mais de uma correlação.
I. Caso base
II. Hipótese de indução
III. Prova do passo k + 1
A. Suposição de que a propriedade é verdadeira para um número arbitrário k.
B. Demonstração de que a propriedade é verdadeira para k + 1, assumindo que é verdadeira para k.
C. Demonstração de que a propriedade é verdadeira para um valor específico.