Algoritmos e Paradigmas de Programação

Definição: Um algoritmo é um conjunto de instruções que realizam uma tarefa.

Pesquisa Binária
A entrada é uma lista ordenada de elementos. Se o elemento que você está buscando está na lista, a pesquisa binária retorna sua localização, caso contrário, retorna None. Este algoritmo elimina muitas possibilidades, pois busca o elemento pela metade da lista. Por exemplo, se temos 100 elementos em uma lista e estamos buscando o 63, primeiro o algoritmo vai buscar no elemento 50. Como 63 está acima de 50, ele vai eliminar todos abaixo dele e buscar pela metade novamente que é 75. Como 63 está abaixo de 75, ele vai eliminar todos os números superiores. E assim por diante, conseguindo chegar ao resultado com um número bem menor de tentativas que um algoritmo de pesquisa simples. De maneira geral, para uma lista de n números, a pesquisa binária precisa de log2n para retornar o valor correto, enquanto a pesquisa simples precisa de n etapas. A pesquisa binária só funciona quando a lista está ordenada.

Notação Big O
A notação Big O é uma notação especial que diz o quão rápido é um algoritmo. Ela permite que você compare o número de operações necessárias para achar determinado elemento em uma busca. Esta notação leva em conta a pior das hipóteses na busca, apesar de também ser necessário estudar o tempo de execução para o “caso médio”, na comparação dos algoritmos de busca.

Lista Encadeada
Este algoritmo funciona linkando o último elemento com o próximo, assim, o elemento que está anterior sabe o endereço do próximo. Ele funciona como o array, porém, é utilizado quando temos muitas inserções e não sabemos quantas posições vamos precisar ocupar de memória. Porém, quando é necessário buscar um elemento, é preciso buscar o primeiro elemento, que vai buscar o segundo, que vai buscar o terceiro, até encontrar o elemento desejado. Ou seja, ele é muito rápido para inserções, mas lento para buscas.

Listas Duplamente Encadeadas
Na lista encadeada, cada elemento tem a referência para o elemento anterior e para o próximo elemento da lista, assim, o último elemento da lista não aponta a referência do próximo como “null”, como ocorre nas listas encadeadas.

Listas Circulares
É quando o último elemento da lista aponta para a referência do primeiro elemento. Sendo que o último elemento é chamado de “Cabeça” e o primeiro de “Cauda”. Temos também uma referência de entrada para o primeiro nó, onde entramos na lista pela Cauda. Os métodos utilizados são: remove(), get(index), add(el) e isEmpty().
Array

Os elementos são inseridos de acordo com o índice. O array tem tamanho fixo, se for necessário adicionar novos elementos, mas não houver mais espaços, os elementos precisam ser realocados em um novo array, maior que o anterior. Por conta desta característica, o array é rápido para realizar buscas, mas lento para inserção e deleção de elementos.

Ordenação por seleção
É um algoritmo de ordenação que compara o elemento a ser ordenado com cada um dos elementos da lista, um a um. Por exemplo, se quiser ordenar uma lista de números, ele vai pegar um dos números e comparar com os demais, verificando se ele for maior ou menor que cada um dos elementos.

Quicksort
O quicksort é um algoritmo de ordenação, sendo muito mais rápido que a ordenação por seleção. Para o funcionamento deste algoritmo, você deve escolher um elemento do array, que será chamado de pivô. Assim, vamos encontrar os elementos que são menores do que o pivô, e também os elementos que são maiores. Isso é chamado de particionamento, e temos assim: um subarray contendo todos os números do que o pivô, o pivô e um subarray contendo todos os números maiores do que o pivô (por exemplo, ao compararmos números). É só seguir a mesma lógica para ordenar todos os elementos de um array.
Tabelas Hash

Uma função hash é uma função na qual você insere uma string (sequência de bytes) e a função retorna um número, trabalhando em um sistema de chave-valor. Ela é um algoritmo muito rápida tanto para buscas e inserções. Também pode ser utilizada para evitar inserir registros duplicados e como cache de dados (utilizado em sites e aplicativos para salvar dados de usuário ou que são acessados com frequência)

Pesquisa em largura
É um algoritmo que utiliza grafos (um modelo de grafos é um conjunto de conexões, que é formado por vértices e arestas, sendo uma maneira de modelar como eventos diferentes estão conectados entre si). A pesquisa em largura é utilizada percorrendo todos os elementos de um grafo, em profundidade, até encontrar o dado desejado.

Pilha (LIFO)
Baseado na lista encadeada, onde o primeiro elemento inserido é o primeiro que será retirado (não é possível pesquisar algum elemento no meio de uma pilha, por exemplo). Os métodos possíveis para manipulação de uma pilha são:

• Método Top: utilizado para verificar qual é o primeiro elemento da pilha (que está no topo). Por exemplo, pilha.top() recebe a referência do topo da pilha;
• Método Pop: tira, de fato, o primeiro elemento da pilha. Por exemplo, pilha.pop(), após remover o elemento, a referência de topo passa para o próximo elemento da pilha;
• Método Push: adiciona um novo elemento na pilha;
• Método isEmpty: verifica se a referência para a entrada da pilha está nula (ou seja, se há ou não uma pilha); Fila

Estrutura de dados onde o primeiro elemento inserido é o último que será lido (como uma fila qualquer).

Árvore
É uma estrutura de dados bidimensional, não linear e constituída de nós que representam um modelo hierárquico (armazenam os dados com base em relações de dependências). Por exemplo, sistema de arquivos, banco de dados, páginas web, etc. As características de uma árvore hierárquica são: nó, raiz, pai e filho, irmão, nível de um nó (posição hierárquica com relação a raiz), altura ou profundidade (grau máximo dos nós), folha ou nó terminal, nó interno, grau de um nó, subárvore.

Árvore de busca binária
A sua principal característica é a posição dos nós, pois sempre os maiores nós ficam à direita e os menores ficam à esquerda. As operações básicas são: inserção, exclusão e exibição.
Algoritmo de Dijkstra
O algoritmo de Dijkstra também utiliza grafos para a pesquisa e é formado por 4 etapas:

1. Encontre o vértice mais “barato”. Este é o vértice em que você consegue chegar no menor tempo possível;
2. Atualize o custo dos vizinhos desse vértice. Explicarei o que quero dizer com isso em breve;
3. Repita até que você tenha feito isso para cada vértice do grafo;
4. Calcule o caminho final.

Neste algoritmo, cada aresta do grafo tem um número associado a ela, que são chamados de pesos. Um grafo com pesos é chamado de grafo ponderado (ou grafo valorado) e um grafo sem pesos é chamado de grafo não ponderado (ou grafo não valorado). Para calcular o caminho mínimo em um grafo não ponderado, utilize a pesquisa em largura, e para calcular o caminho mínimo e um grafo ponderado, utilize o algoritmo de Dijkstra. Porém, este algoritmo só funciona em grafos sem ciclos ou em grafos com ciclo de peso positivo.

Algoritmos gulosos
Neste algoritmo, a cada etapa, escolhe-se a solução ideal. Quando é necessário muito tempo para calcular a solução exata, um algoritmo de aproximação é uma boa ideia e funciona. Eles são avaliados por sua rapidez e pela capacidade de chegar a solução ideal.

Programação dinâmica
Consiste em uma técnica para resolução de problemas complexos que se baseia na divisão de um problema em subproblemas, os quais são resolvidos separadamente. Ela é muito útil quando você está tentando otimizar algo em relação a um limite. Todas as soluções em programação dinâmica envolvem uma tabela e os valores nas células são, geralmente, o que você está tentando otimizar. Cada célula é um subproblema, então pense em como dividir este subproblema em outros subproblemas.

K-vizinhos mais próximo
O algoritmo dos K-vizinhos mais próximos é utilizado na classificação e também na regressão, ele envolve observar os K-vizinhos mais próximos. Classificação = classificar em grupos e Regressão = adivinhar uma resposta (como um número). Escolher boas características é uma parte importante para que este algoritmo opere corretamente. O algoritmo dos k-vizinhos mais próximos é utilizado em sistemas de recomendação (filmes, produtos, etc.), aprendizado de máquina, filtro de spam de e-mails e, até, previsão da bolsa de valores.

— — — — — — — — — — — — — — — — — — — — — — — — — —

Paradigmas de Programação

Programação Funcional
Modela um problema computacional como uma coleção de funções matemáticas, cada uma com um espaço de entrada e resultado. Isso separa a programação funcional das funções que possuem o comando de atribuição. Por exemplo, CML, LISP, Scheme, Haskell;

Programação Imperativo
Os comandos são escritos na mesma ordem de execução (ou seja, passo a passo). Por exemplo, Cobol, Fortran;

Programação Orientada a Objetos
Fornece um modelo na qual um programa é uma coleção de objetos que interagem entre si, passando mensagens que transformam seu estado. Por exemplo, Java, C++;

Programação Declarativa
Permite um programa modelar um programa declarando qual resultado ele deve obter, ao invés de como ele deve ser obtido. Por exemplo, PROLOG.