Aval-Sem02-COM540

Prévia do material em texto

PERGUNTA 1 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 fórmula; 2 simples b.1 equação; 2 recursivos inequação; 2 não recursivos d.1 variável; 2 lineares e.1 relação; 2 iterativos PERGUNTA 2 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] PERGUNTA 3 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 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 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. PERGUNTA As recorrências são relevantes na construção de algoritmos ao se pensar algoritmos recursivos analisar seus tempos de Diversos algoritmos clássicos são estudados em sua forma recursiva com análise feita por recorrências, por exemplo, caso do Mergesort, operações em Binárias Outros algoritmos são mais conhecidos em sua versão iterativa mas podem ser pensados analisadas com viés recursivo, por exemplo, InsertionSort e pesquisa linear. Busca Linear MergeSort foram explorados no curso os conhecimentos podem ser aplicados por exemplo no algoritmo de pesquisa binária seguir Linha Código int PesquisaBinaria(int v[], int ch, int 4 { 6 return -1; int meio 8 if( ch v[meio] 9 return ch, 10 elseif( ch 11 return PesquisaBinaria(v, ch, 12 else 13 return meio; 14 Neste contexto, analise relacione para cada um dos algoritmos clássicos sua respectiva equação de recorrência do tempo de execução. Algoritmo Equação de recorrência Pesquisa linear A. T(n) n=1 T(n/2) caso contrário II. Pesquisa binária B. T(n) n=1 T(n-1) caso contrário C. T(n) III. InsertionSort T(n-1) caso contrário T(n) n=1 IV. MergeSort T(n/2) caso contrário Assinale alternativa que representa a associação correta: I-D; IV-A II-A; II-C: III-B; IV-D III-D; e. II-D;PERGUNTA 6 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. I. A indução matemática pode ser utilizada para provar propriedades de laços em algoritmos. II. 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. Está correto que se afirma em: a. II, apenas. b. e III, apenas. III. d.ll, apenas. e. apenas. PERGUNTA 7 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. Dentre diversos algoritmos, existe MergeSort que recursivamente envolve a divisão do vetor em duas partes, a ordenação de cada uma delas depois a combinação dos resultados. A sua simulação pode gerar uma árvore de recursão típica e os parâmetros de sua função tem como parâmetros vetor e os limites envolvidos na ordenação. 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 PERGUNTA 8 algoritmo de ordenação por inserção é frequentemente utilizado para ordenar pequenas quantidades de elementos, como ilustrado por uma analogia com processo de ordenar cartas em um jogo de baralho. Ao trabalhar com esse algoritmo, é necessário garantir sua correção por meio de uma técnica chamada "invariantes de laço", que permite analisar o comportamento do algoritmo em cada iteração. 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: invariante de laço verifica se número total de comparações é constante em cada iteração. b.O invariante de laço prova que arranjo é ordenado somente quando número de comparações é menor que o tamanho do arranjo. C. invariante de laço garante que, ao final de cada iteraçã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, arranjo inteiro já está ordenado. PERGUNTA 1 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 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. 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 passo k+1. III. A indução matemática não pode ser aplicada para algoritmos recursivos. Está correto que se afirma em: apenas. b. III, apenas. C. III. d.ll, apenas. e. II, apenas. PERGUNTA 2 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. Uma das operações sobre os dados pode ser a de ordenar os dados e existem alguns métodos para realizar isso, por exemplo, InsertionSort ou MergeSort. No caso do MergeSort, internamente ele utiliza uma função Merge ou Combina em seu processamento. 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 resultado da chamada à função da seguinte forma: Merge(v, 3, 5, 7). Considere que índice da primeira casa do vetor 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]PERGUNTA 3 Na computação, a ordenação de dados é um problema típico que contem diversas algoritmos clássicos, dentre eles o InsertionSort ou Ordenação por Inserção. Neste algoritmo, para realizar a inserção de um elemento na sua devida posição, elementos precisam ser deslocados, por exemplo, à direita, e daí elemento pode ser inserido. Na Figura 1.a 3 elementos foram deslocados, 4, 5 e 6 para que elemento 3 pudesse ser inserido em sua posição. Este movimento é parecido com feito em uma mão de baralho, vide imagem meramente ilustrativa (Figura 1.b), sem correlação com os dados exemplificados no vetor. 2 3 4 5 6 1 2 4 5 6 3 Figura 1.a e 1.b Simulação de deslocamentos para inserção do elemento 3 e figura ilustrativa de mão de baralho para analogia com método de inserção. Fonte: (CORMEM, LEISERSON e RIVEST, 2024, p.13). Descrição: A figura está dividida em duas, uma à esquerda com um vetor e outra à direita com a ilustração de uma mão de baralho. Na figura da esquerda está um vetor com os números nesta ordem, 1, 2, 4, 5, 6 e 3. Os números 1, 2, 4, 5 e 6, estão ocupando posições ou casas com um cinza claro para diferenciar do elemento 3 que está em uma posição ou casa em cinza mais escuro. Nos elementos 4, 5 e 6 existem uma seta sinalizando um deslocamento de cada um destes elementos para a direita. No elemento 3 já uma seta sinalizando a inserção dele na posição logo depois do 2. CORMEN, Thomas H.; LEISERSON, Charles E.; Ronald L. Rivest; et al. Algoritmos. 4. ed. Rio de Janeiro: GEN LTC, 2024. E-book. p.13. ISBN 9788595159914. Disponível em: https://integrada.minhabibli oteca.com.br/reader/books/9788595159914/.Acesso em: 18 abr. 2025. Considerando um vetor com os valores 10, 15,8,5,3,12,1, avalie quantos deslocamentos de elementos a direita precisarão ser feitos para ordenar todo vetor e assinale a alternativa correta. a. 19 deslocamentos b. 13 deslocamentos 10 deslocamentos d. 15 deslocamentos e. 16 deslocamentos PERGUNTA 4 Leia trecho a seguir: A indução matemática é um mecanismo que pode contribuir para projeto de algoritmos. A sua aplicação e processo de indução permite construir [Preencher 1] em que caso base da indução equivale ao caso base da recursão e 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. 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. PERGUNTA 5 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 inequação; 2 não recursivos d.1 fórmula; 2 simples e.1 relação; 2 iterativos PERGUNTA 6 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, por exemplo, conceitos como indução matemática, comportamento assintótico de funções, provas de teoremas, entre outros, são conhecimentos matemáticos que sustentam universo de construção de algoritmos. Nesse contexto, assinale a alternativa que reconhece conceito de recorrência, na perpectivas 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.PERGUNTA 8 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, por exemplo, ao visualizar nossos emails eles em geral estão ordenados em ordem decrescente de chegado, extratos bancários mostram transações em ordem e a classificação em um concurso também obedece certa ordenação. InsertionSort é um exemplo de algoritmo que realiza esta ordenação, e ele foi implementado com a seguinte adaptação na lógica. Linha Código 1 ORDENA-POR-INSERÇÃO(A, n) 2 for to n 3 chave A[i] 4 j=i-1 5 while 0 e A[j] chave 6 A[j A[j] 7 8 A[j 1] chave Com base na aplicação deste algoritmo à sequência [3,2,8,7,1,5,6], analise comportamento do vetor e assinale como ele estará ao final da iteração em que í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] PERGUNTA 1 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. o tempo de execução de uma recorrência possui uma forma típica que envolve a equação do esforço computacional do caso básico e a equação do caso recorrente. Com relação a este contexto e levando em consideraçã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) + para caso recorrente, quando n > 1. PORQUE II. Quando n = 1, trata-se de um vetor de um elemento que pode ser considerado ordenado portanto tempo é Quando n >1, vetor precisa ser dividido em 2 partes para a ordenação e isso justifica termo T(n/2) na equação e além disso existe processo de combinação das 2 partes pelo algoritmo Merge que processa n elementos justificando termo A respeito dessas asserções, assinale a alternativa correta: a. As asserções e são proposições verdadeiras, e a é uma justificativa da b. As asserções e são falsas. C. A asserção é uma proposição falsa, e a é uma proposição verdadeira. As asserções e são proposições verdadeiras, mas a não é uma justificativa da I. e. A asserção é uma proposição verdadeira, e a II é uma proposição falsa. PERGUNTA 5 algoritmo InsertionSort é um método clássico de ordenação que constrói a lista ordenada um elemento por vez. 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. PERGUNTA 6 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: [preencher 1] e [preencher 2]. Os termos [preencher 1] e [preencher 2] são corretamente substituídos por: a. Ordenação; 2 Fusão. Organização; 2 Reunião. d.1 Divisão; 2 Combinação. e.1 Classificação; 2 Intercalação.PERGUNTA 8 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. Conceitos Descrições I. Caso base A. Suposição de que a propriedade é verdadeira para um número arbitrário k. II. Hipótese de indução B. Demonstração de que a propriedade é verdadeira para k + 1, assumindo que é verdadeira para k. III. Prova do passo k + 1 C. Demonstração de que a propriedade é verdadeira para um valor específico. a. A; C; III C; A; III C; B; III A B; A; III A; B; III