FlaviusPress

O diário de um estagiário

Categoria: Específicas

Lógica de Programação – Questões (teóricas)

A estrutura de dados que consiste no armazenamento de cada elemento em um endereço calculado a partir da aplicação de uma função sobre a chave de busca denomina-se
a)lista.
b)tabela hashing.
c)deque.
d)fila.
e)árvore binária balanceada.
Gabarito:
B –

Lógica de programação – Questões (Estrutura de Dados – Árvore)

Em relação ao tema “estruturas de dados”, analise as afirmativas a seguir e marque a opção correta:
I – Nas árvores B todas as folhas sempre estarão no mesmo nível.
II – Nas listas duplamente encadeadas, todos os nós apontam para os nós sucessores e antecessores.
III – Nas árvores binárias cada nó pode ter no máximo duas subárvores.
a)somente as afirmativas I e II estão corretas;
b)somente as afirmativas I e III estão corretas;
c)somente as afirmativas II e III estão corretas;
d)somente a afirmativa I está correta;
e)somente a afirmativa II está correta.
Gabarito:
B

Lógica de Programação – Questões (Saída do algoritmo)

             

Assinale a opção que apresenta o resultado final após a execução do algoritmo precedente.

a)24
b)0
c)12
d)4
e)15

Assinale a opção que apresenta o resultado final após a execução do algoritmo precedente.
a)B

b)A
c)AC
d)C
e)BC

                

Assinale a opção que apresenta o resultado final após a execução do algoritmo precedente.

a)4
b)2345
c)1235
d)1234
e)5
Gabarito:
 A – B – E –

Lógica de Programação – Questões (Fluxograma)

Se, no fluxograma precedente, início indica o primeiro elemento do vetor e fim, o último elemento, então, para o vetor [11,6,2,7,8,3,5], o resultado final é
a)[2,7,3,5].
b)[11,7,3,5].

c)[11,6,2,7,8,3,5].
d)[2,3,5,6,7,8,11].
e)[6,2,8,3,5].
Gabarito:
D (bubble sort)

Lógica de Programação – Estrutura de Dados

https://www.ime.usp.br/~song/mac5710/slides/01complex.pdf

Lógica de Programação – Questões (Algoritmos e Estrutura de Dados Disciplina – Assunto Complexidade do algortimo)

O algoritmo QuickSort usa uma técnica conhecida por divisão e conquista, onde problemas complexos são reduzidos em problemas menores para se tentar chegar a uma solução. A complexidade média deste algoritmo em sua implementação padrão e a complexidade de pior caso são, respectivamente,
a)O(n-1) e Ο(n³).
b)Ο(n²) e Ο(n log n²).
c)O(n²) e O(n³).
d)Ο(n) e Ο(n²).
e)Ο(n log n) e Ο(n²).

Considere o algoritmo abaixo.
static int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n – 2) + fibonacci(n – 1);
}
A complexidade deste algoritmo, na notação Big O, é

a)O(2ⁿ).
b)O(n²).
c)O(n).
d)O(log(n)).
e)O(n⁴).
Gabarito:
E – B –

Lógica de programação: algoritmos, fluxogramas, depuração, estrutura de dados.

Algoritmo

Um algoritmo é uma sequência não ambígua de instruções que é executada até que determinada condição se verifique. Mais especificamente, em matemática, constitui o conjunto de processos (e símbolos que os representam) para efetuar um cálculo. Um algoritmo não representa, necessariamente, um programa de computador, e sim os passos necessários para realizar uma tarefa. Sua implementação pode ser feita por um computador, por outro tipo de autômato ou mesmo por um ser humano. Para qualquer processo computacional teórico, o algoritmo precisa estar rigorosamente definido, especificando a maneira que ele se comportará em todas as circunstâncias. A corretude do algoritmo pode ser provada matematicamente, bem como a quantidade assintótica de tempo e espaço (complexidade) necessários para a sua execução. Estes aspectos dos algoritmos são alvo da análise de algoritmos. As implementações, porém, podem se limitar a casos específicos.

Término do algoritmo

Alguns autores restringem a definição de algoritmo para procedimentos que eventualmente terminam. Minksy constatou que se o tamanho de um procedimento não é conhecido de antemão, tentar descobri-lo é problema indecidível já que o procedimento pode ser executado infinitamente, de forma que nunca se terá a resposta. Alan Turing provou em 1936 que não existe máquina de Turing para realizar tal análise para todos os casos, logo não há algoritmo para realizar tal tarefa para todos os casos. Tal condição é conhecida atualmente como problema da parada. Basicamente, isto quer dizer que não existe um programa de computador que possa antever, de forma geral, se um outro programa de computador vai parar algum dia. Para algoritmos intermináveis o sucesso não pode ser determinado pela interpretação da resposta e sim por condições impostas pelo próprio desenvolvedor do algoritmo durante sua execução. Por exemplo, podemos querer um algoritmo interminável para controlar um sinal de trânsito.

Análise de algoritmos

A análise de algoritmos é um ramo da ciência da computação que estuda as técnicas de projeto de algoritmos e os algoritmos de forma abstrata. Ela preocupa-se com os recursos necessários para a execução do algoritmo tais como o tempo de execução e o espaço de armazenamento de dados. Os algoritmos podem ser classificados de 4 formas:

Classificação por implementação:

  • Recursivo ou iterativo – um algoritmo recursivo possui a característica de invocar a si mesmo repetidamente até que certa condição seja satisfeita e ele é terminado, que é um método comum em programação funcional. Algoritmos iterativos usam estruturas de repetição tais como laços, ou ainda estruturas de dados adicionais tais como pilhas, para resolver problemas. Cada algoritmo recursivo possui um algoritmo iterativo equivalente e vice versa, mas que pode ter mais ou menos complexidade em sua construção. É possível construir algoritmos que sejam ao mesmo tempo iterativo e recursivo, provavelmente para aproveitar alguma otimização de tempo ou espaço que isso permita.
  • Lógico – um algoritmo pode ser visto como uma dedução lógica controlada. O componente lógico expressa os axiomas usados na computação e o componente de controle determina a maneira como a dedução é aplicada aos axiomas. Tal conceito é base para a programação lógica.
  • Serial ou paralelo – algoritmos são geralmente assumidos por serem executados instrução à instrução individualmente, como uma lista de execução, o que constitui um algoritmo serial. Tal conceito é base para a programação imperativa. Por outro lado existem algoritmos executados paralelamente, que levam em conta arquiteturas de computadores com mais de um processador para executar mais de uma instrução ao mesmo tempo. Tais algoritmos dividem os problemas em sub-problemas e o delegam a quantos processadores estiverem disponíveis, agrupando no final o resultado dos sub-problemas em um resultado final ao algoritmo. Tal conceito é base para a programação paralela. De forma geral, algoritmos iterativos são paralelizáveis; por outro lado existem algoritmos que não são paralelizáveis, chamados então problemas inerentemente seriais.
  • Determinístico ou não-determinístico – algoritmos determinísticos resolvem o problema com uma decisão exata a cada passo enquanto algoritmos não-determinísticos resolvem o problema ao deduzir os melhores passos através de estimativas sob forma de heurística.
  • Exato ou aproximado – enquanto alguns algoritmos encontram uma resposta exata, algoritmos de aproximação procuram uma resposta próxima a verdadeira solução, seja através de estratégia determinística ou aleatória. Possuem aplicações práticas sobretudo para problemas muito complexos, do qual uma resposta correta é inviável devido à sua complexidade computacional.

Classificação por paradigma:

  • Divisão e conquista – algoritmos de divisão e conquista reduzem repetidamente o problema em sub-problemas, geralmente de forma recursiva, até que o sub-problema é pequeno o suficiente para ser resolvido. Um exemplo prático é o algoritmo de ordenação merge sort. Uma variante dessa metodologia é o decremento e conquista, que resolve um sub-problema e utilização a solução para resolver um problema maior. Um exemplo prático é o algoritmo para pesquisa binária.
  • Programação dinâmica – pode-se utilizar a programação dinâmica para evitar o re-cálculo de solução já resolvida anteriormente.
  • Algoritmo ganancioso – um algoritmo ganancioso é similar à programação dinâmica, mas difere na medida que as soluções dos sub-problemas não precisam ser conhecidas a cada passo, uma escolha gananciosa pode ser feita a cada momento com o que até então parece ser mais adequado.
  • Redução – a redução resolve o problema ao transformá-lo em outro problema. É chamado também transformação e conquista.
  • Busca e enumeração – vários problemas podem ser modelados através de grafos. Um algoritmo de exploração de grafo pode ser usado para caminhar pela estrutura e retornar informações úteis para a resolução do problema. Esta categoria inclui algoritmos de busca e backtracking.
  • Paradigma heurístico e probabilístico – algoritmos probabilísticos realizam escolhas aleatoriamente. Algoritmos genéticos tentam encontrar a solução através de ciclos de mutações evolucionárias entre gerações de passos, tendendo para a solução exata do problema. Algoritmos heurísticos encontram uma solução aproximada para o problema.

Classificação por campo de estudo: Cada campo da ciência possui seus próprios problemas e respectivos algoritmos, adequados para resolvê-los. Exemplos clássicos são algoritmos de busca, de ordenação, de análise numérica, de teoria de grafos, de manipulação de cadeias de texto, de geometria computacional, de análise combinatória, de aprendizagem de máquina, de criptografia, de compressão de dados e de interpretação de texto.

Classificação por complexidade: Alguns algoritmos são executados em tempo linear, de acordo com a entrada, enquanto outros são executados em tempo exponencial ou até mesmo nunca terminam de ser executados. Alguns problemas possuem múltiplos algoritmos enquanto outros não possuem algoritmos para resolução.

As linguagens de programação podem ser separadas em dois tipos:

  • Linguagens de Baixo Nível: são linguagens de programação que tratam a informação na linguagem de máquina.
  • Linguagens de Alto Nível: são linguagens de programação modeladas quase como a linguagem comum humana, que quando compiladas são convertidas para linguagem de máquina. Cada linguagem deste tipo possui uma sintaxe própria, que deve ser respeitada e aprendida para que possa ser corretamente processada por seu compilador. Compilador é um programa que permite que determinada programação em uma linguagem específica seja adaptada para linguagem de máquina.

Fontes:
https://pt.wikibooks.org/wiki/Introdu%C3%A7%C3%A3o_%C3%A0_programa%C3%A7%C3%A3o/Defini%C3%A7%C3%B5es_sobre_L%C3%B3gica_de_Programa%C3%A7%C3%A3o
https://pt.wikibooks.org/wiki/Introdu%C3%A7%C3%A3o_%C3%A0_programa%C3%A7%C3%A3o/Algoritmos

Fluxograma:
http://academicotech.blogspot.com.br/2014/02/v-behaviorurldefaultvmlo.html

https://www.devmedia.com.br/fluxogramas-diagrama-de-blocos-e-de-chapin-no-desenvolvimento-de-algoritmos/28550 

Depuração:
https://panda.ime.usp.br/pensepy/static/pensepy/Appendices/app_a.html

 

Desenvolvido em WordPress & Tema por Anders Norén