Apostila Programação Avançada EM Engenharia DE Computação PDF

Preview

Summary

Série de exercicios valendo nota docx...

Description

Engenharia Elétrica e Computação- FATECS

APOSTILA PARA O CURSO DE APERFEIÇOAMENTO RM PROGRAMAÇÃO AVANÇADA EM ENGENHARIA DE COMPUTAÇÃO E SUAS ESTRUTURAS

Professor: William Roberto Malvezzi

Brasília 2020

Engenharia Elétrica e Computação- FATECS

PROGRAMAÇÃO AVANÇADA EM ENGENHARIA DE COMPUTAÇÃO E SUAS ESTRUTURAS

Pilha Uma pilha é uma estrutura de dados que admite remoção de elementos e inserção de novos objetos. Mais especificamente, uma pilha (= stack) é uma estrutura sujeita à seguinte regra de operação: sempre que houver uma remoção, o elemento removido é o que está na estrutura há menos tempo. Em outras palavras, o primeiro objeto a ser inserido na pilha é o último a ser removido. Essa política é conhecida pela sigla LIFO (= Last-In-First-Out). Pilha Alocada Dinamicamente #include #include // Estrutura struct NoPilha { int dado; struct NoPilha *prox; // ponteiro do tipo noPilha }; typedef struct NoPilha NoPilha; // sinônimo para struct noPilha typedef NoPilha *NoPilhaPtr; // sinônimo para NoPilha* // protótipos void push(NoPilhaPtr *topo, int info); int pop(NoPilhaPtr *topo); int estaCheia(NoPilhaPtr topo); void imprimePilha(NoPilhaPtr ponteiroAuxiliar); void menu(void); int main(void) { NoPilhaPtr ponteiroPilha = NULL; int valor; menu(); // mostra o menu printf("%s", "? "); unsigned int opcao; scanf("%u", &opcao); while (opcao != 3) { switch (opcao) { // push valor onto stack case 1: printf("%s", "Entre um valor inteiro: "); scanf("%d", &valor); push(&ponteiroPilha, valor); imprimePilha(ponteiroPilha); break; // pop valor off stack case 2:

Engenharia Elétrica e Computação- FATECS

// if stack is not empty if (!estaCheia(ponteiroPilha)) { printf("O valor desempilhado %d.\n", pop(&ponteiroPilha)); } imprimePilha(ponteiroPilha); break; default: puts("Opcao Invalida.\n"); menu(); break; } // end switch printf("%s", "? "); scanf("%u", &opcao); } puts("End of run."); } // display program menu to user void menu(void) { puts("Enter opcao:\n" "1 PUSH: empilhar um valor na Pilha\n" "2 POP: Retirar um valor para fora da Pilha\n" "3 Para fechar o programa"); } void push(NoPilhaPtr *topo, int info) { NoPilhaPtr ponteiroNovo = (NoPilha*)malloc(sizeof(NoPilha)); // insere o Nó no Topo da Pilha if (ponteiroNovo != NULL) { ponteiroNovo->dado = info; ponteiroNovo->prox = *topo; *topo = ponteiroNovo; } else { // não há recurso de memória printf("%d Nao Inserido. Sem memoria disponivel.\n", info); } } // remove um nó do topo da Pilha int pop(NoPilhaPtr *topo) { NoPilhaPtr tempPtr = *topo; int popValor = (*topo)->dado; *topo = (*topo)->prox; free(tempPtr); return popValor; } // Imprime a Pilha void imprimePilha(NoPilhaPtr ponteiroAuxiliar) { // Se a Pilha está vazia if (ponteiroAuxiliar == NULL) { puts("A Pilha está vazia.\n");

Engenharia Elétrica e Computação- FATECS

} else { puts("A Pilha eh:"); // enquanto não chegar ao fim da Pilha while (ponteiroAuxiliar != NULL) { printf("%d --> ", ponteiroAuxiliar->dado); ponteiroAuxiliar = ponteiroAuxiliar->prox; } puts("NULL\n"); } } // retorna 1 se a Pilha estiver vazia, 0 caso contrário int estaCheia(NoPilhaPtr topo) { return topo == NULL; }

Lista de Exercícios

1. As técnicas de projeto de algoritmos são essenciais para que os desenvolvedores possam implementar software de qualidade. Essas técnicas descrevem os princípios que devem ser adotados para se projetar soluções algorítmicas para um dado problema. Entre as principais técnicas, destacam-se os projetos de algoritmos por tentativa e erro, divisão e conquista, programação dinâmica e algoritmos gulosos. Nesse contexto, faça o que se pede nos itens a seguir. A. Descreva o que caracteriza o projeto de algoritmos por divisão e conquista. Resp.: Essa técnica consiste em dividir um problema maior em problemas menores até que o mesmo possa ser resolvido diretamente. São 3 fases: divisão, conquista e combinação._____________________________________________________ ________________________________________________________________ ________________________________________________________________ ________________________________________________________________ ________________________________________________________________ ________________________________________________________________ ________________________________________________________________ B. Apresente uma situação de uso da técnica de projeto de algoritmos por divisão e conquista:

Engenharia Elétrica e Computação- FATECS

Resp.: Uma situação de uso dessa técnica é o somatório de N números, ele pode ser dividido em dois problemas menores: 1. Somar o primeiro até N/2; 2. Somar N/2 até N; 3. Somar os dois resultados. ___________________________________ ________________________________________________________________ ________________________________________________________________ ________________________________________________________________ ________________________________________________________________ ________________________________________________________________ ________________________________________________________________ ________________________________________________________________ ________________________________________________________________ ________________________________________________________________

2. Qual o valor de retorno da função a seguir, caso n=27? int recursao (int n){ if (n 1 Abaixo, apresenta-se uma implementação em linguagem funcional para essa relação de recorrência: fib fib fib fib

:: Integer -> Integer 0 = 0 1 = 1 n = fib (n - 1) + fib (n - 2)

Considerando que o programa acima não reutilize resultados previamente computados, quantas chamadas são feitas à função fib para computar fib 5? (A) 11 (B) 12 (C) 15 (D) 24 (E) 25

4. As aplicações financeiras que os bancos oferecem atualmente conferem rendimentos cumulativos sobre um capital inicialmente investido. O regime de juros compostos pode ser expresso por meio da taxa de juros continuamente composta. A fórmula da taxa de juros continuamente composta pode ser escrita da seguinte maneira: r .n VF=C . e Em que: VF é o valor futuro; C é o capital inicial aplicado; r é a taxa de juros continuamente composta; n é o número de períodos; e é o número de Euler, aproximadamente igual 2,718281828459045235360287... Essa fórmula leva ao cálculo de uma expressão do tipo exponencial e x , que pode ser calculada pela série abaixo. e x =1+

x x2 x 3 + + +… ,−∞topo = -1; return pilha; } void push (pilha *p, int element) { if (p ->topo >= 99) return; p->elementos[++p->topo] = element; } int pop(pilha *p) { int a = p->elementos[p->topo]; p->topo--; return a; } O programa a seguir utiliza uma pilha int main(){ pilha * p = cria_pilha( ); push(p, 2); push(p, 3); push(p, 4); pop(p); push(p, 2); int a = pop(p) + pop(p); push(p, a); a += pop(p); printf(“ %d”, a); return 0; } A esse respeito, avalie as afirmações a seguir. I. A complexidade computacional de ambas as funções push e pop e O (1). II. O valor exibido pelo programa seria o mesmo caso a instrução a += pop(p); fosse trocada por a += a; III. Em relação ao vazamento de memória (memory leak), é opcional chamar a função free(p), pois o vetor usado pela pilha é alocado estaticamente.

Engenharia Elétrica e Computação- FATECS

É correto o que se afirma em: A. I, apenas B. III, apenas C. I e II, apenas D. II e III, apenas E. I, II e III 6. Um programador propôs um algoritmo não-recursivo para o percurso em preordem de uma árvore binária com as seguintes características. 

 

Cada nó da árvore binária é representado por um registro com três campos: chave, que armazena seu identificador; esq e dir, ponteiros para os filhos esquerdo e direito, respectivamente. O algoritmo deve ser invocado inicialmente tomando o ponteiro para o nó raiz da árvore binária como argumento. O algoritmo utiliza push() e pop() como funções auxiliares de empilhamento e desempilhamento de ponteiros para nós de árvore binária, respectivamente.

A seguir, está apresentado o algoritmo proposto, em que λ representa o ponteiro nulo. Procedimento preordem (ptraiz : PtrNoArvBin) var ptr : PtrNoArvBin; ptr := ptraiz; enquanto (ptr ≠ λ) Faça escreva (ptr↑.chave); Se (ptr↑.dir ≠ λ) Então push(ptr↑.dir); Se (ptr↑.esq ≠ λ) Então push(ptr↑.esq); ptr := pop(); fim_Enquanto fim_Procedimento Com base nessas informações e supondo que a raiz de uma árvore binária com n nós seja passada ao procedimento preordem(), julgue os itens seguintes. I. II. III.

O algoritmo visita cada nó da árvore binária exatamente uma vez ao longo do percurso. O algoritmo só funcionará corretamente se o procedimento pop() for projetado de forma a retornar λ caso a pilha esteja vazia. Empilhar e desempilhar ponteiros para nós da árvore são operações que podem ser implementadas com custo constante.

Engenharia Elétrica e Computação- FATECS

IV.

A complexidade do pior caso para o procedimento preordem() é O(n). Assinale a opção correta. (A) Apenas um item está certo. (B) Apenas os itens I e IV estão certos. (C) Apenas os itens I, II e III estão certos. (D) Apenas os itens II, III e IV estão certos. (E) Todos os itens estão certos.

7. Tabelas de dispersão (tabelas hash) armazenam elementos com base no valor absoluto de suas chaves e em técnicas de tratamento de colisões. As funções de dispersão transformam chaves em endereços-base da tabela, ao passo que o tratamento de colisões resolve conflitos em casos em que mais de uma chave é mapeada para um mesmo endereço-base da tabela. Suponha que uma aplicação utilize uma tabela de dispersão com 23 endereçosbase (índices de 0 a 22) e empregue h(x) = x mod 23 como função de dispersão, em que x representa a chave do elemento cujo endereço-base desejasse computar. Inicialmente, essa tabela de dispersão encontra-se vazia. Em seguida, a aplicação solicita uma sequência de inserções de elementos cujas chaves aparecem na seguinte ordem: 44, 46, 49, 70, 27, 71, 90, 97, 95. Com relação à aplicação descrita, faça o que se pede a seguir. A Escreva, no espaço reservado, o conjunto das chaves envolvidas em colisões. Resp.: As colisões deverão ocorrer entre elementos cujas chaves forem mapeadas pela função h(x) = x mod 23 no mesmo endereço base. Assim, o conjunto de envolvidas

em

colisões

será

S

=

{44,

49,

95,

90}._____________________________________________________________ ________________________________________________________________ ________________________________________________________________ ________________________________________________________________ ________________________________________________________________ ________________________________________________________________ ________________________________________________________________ ________________________________________________________________ ________________________________________________________________

Engenharia Elétrica e Computação- FATECS

________________________________________________________________ ________________________________________________________________ ________________________________________________________________

B Assuma que a tabela de dispersão trate colisões por meio de encadeamento exterior. Esboce a tabela de dispersão para mostrar seu conteúdo após a sequência de inserções referida. Resp.: ________0___46__________________________________________________ ________1___70__________________________________________________ ________2___71__________________________________________________ ________3___49____95____________________________________________ ________4___27__________________________________________________ ________5___97__________________________________________________ ________.___.____________________________________________________ ________.___.____________________________________________________ ________.___.____________________________________________________ ________21__44____90____________________________________________ ________22______________________________________________________ ________________________________________________________________ As entradas de 6 a 20 possuem ponteiros nulos(semelhantes à entrada 22) e, portanto, foram omitidas.____________________________________________ ________________________________________________________________ ________________________________________________________________ 8. A figura a seguir apresenta uma árvore binária de pesquisa, que mantém a seguinte propriedade fundamental: o valor associado à raiz é sempre menor do que o valor de todos os nós da subárvore à direita e sempre maior do que o valor de todos os nós da subárvore à esquerda.

Engenharia Elétrica e Computação- FATECS

Em relação à árvore apresentada na figura, avalie as afirmações a seguir. I. A árvore possui a vantagem de realizar a busca de elementos de forma eficiente, como a busca binária em um vetor. II. A árvore está desbalanceada, pois a subárvore da esquerda possui um número de nós maior do que a subárvore da direita. III. Quando a árvore é percorrida utilizando o método de caminhamento pósordem, os valores são encontrados em ordem decrescente. IV. O número de comparações realizadas em função do número n de elementos na árvore em uma busca binária realizada com sucesso é O(log n). É correto apenas o que se afirma em: A. I e III B. I e IV C. II e III D. I, II e IV E. II, III e IV

9. Os autômatos celulares são sistemas dinâmicos discretos no espaço e no tempo que operam em uma rede celular finita ou infinita e são caracterizados por interações locais. Cada elemento, denominado célula, está associado a um dado estado a um conjunto discreto e é utilizado com base nos estados anteriores de suas células vizinhas imediatas, de acordo com um conjunto de regras locais. Os autômatos celulares geram um grande interesse na área de engenharia de computação desde o início dos anos 1960, quando foi criado o Jogo da Vida, e agora são amplamente estudados para modelagem e simulação de processos espaço-temporais reais em uma ampla variedade de domínios de aplicação. (SMILI, R. et al. A celular automata model for Chagas disease. Amsterdã, 2009) As regras do Jogo da Vida são:    

qualquer célula viva com menos de dois vizinhos morre de solidão; qualquer célula viva com mais de três vizinhos morre de superpopulação; qualquer célula viva com dois ou três vizinhos vivos continua no mesmo estado para a próxima geração; qualquer célula viva com três vizinhos vivos torna-se uma célula viva.

Nesse contexto, escreva uma rotina em C (ANSI) em que se utilizem as regras acima descritas para definir o estado atual de uma célula com base em seu estado anterior e no de suas vizinhas. Ao elaborar sua resposta, considere que:

Engenharia Elétrica e Computação- FATECS

     



as células são entradas de uma matriz; os casos não cobertos pela regra significam permanência no mesmo estado; a rotina deve ter como parâmetros a matriz M, definida como “unsign ed char **M, e os índices i e j da posição da célula, definidos como inteiros; a rede é quadriculada, o valor 1 (um) da matriz significa célula viva, e o valor 0 (zero) significa célula morta; os vizinhos correspondem aos quatro lados e às diagonais das células de interesse; não há necessidade de se preocupar com os limites da matriz.

Resp.: void jogoDaVida (char** M, int i, int j){ char vizinhosVivos = 0; int p, q; for (p = -1; p...