Algoritmos e Paradigmas de Programao

Definio: Um algoritmo um conjunto de instrues que realizam uma tarefa.

Pesquisa Binria
A entrada uma lista ordenada de elementos. Se o elemento que voc est buscando est na lista, a pesquisa binria retorna sua localizao, caso contrrio, 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 nmeros superiores. E assim por diante, conseguindo chegar ao resultado com um nmero bem menor de tentativas que um algoritmo de pesquisa simples. De maneira geral, para uma lista de n nmeros, a pesquisa binria precisa de log2n para retornar o valor correto, enquanto a pesquisa simples precisa de n etapas. A pesquisa binria s funciona quando a lista est ordenada.

Notao Big O
A notao Big O uma notao especial que diz o quo rpido um algoritmo. Ela permite que voc compare o nmero de operaes necessrias para achar determinado elemento em uma busca. Esta notao leva em conta a pior das hipteses na busca, apesar de tambm ser necessrio estudar o tempo de execuo para o caso mdio, na comparao dos algoritmos de busca.

Lista Encadeada
Este algoritmo funciona linkando o ltimo elemento com o prximo, assim, o elemento que est anterior sabe o endereo do prximo. Ele funciona como o array, porm, utilizado quando temos muitas inseres e no sabemos quantas posies vamos precisar ocupar de memria. Porm, quando necessrio 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 rpido para inseres, mas lento para buscas.

Listas Duplamente Encadeadas
Na lista encadeada, cada elemento tem a referncia para o elemento anterior e para o prximo elemento da lista, assim, o ltimo elemento da lista no aponta a referncia do prximo como null, como ocorre nas listas encadeadas.

Listas Circulares
quando o ltimo elemento da lista aponta para a referncia do primeiro elemento. Sendo que o ltimo elemento chamado de Cabea e o primeiro de Cauda. Temos tambm uma referncia de entrada para o primeiro n, onde entramos na lista pela Cauda. Os mtodos utilizados so: remove(), get(index), add(el) e isEmpty().
Array

Os elementos so inseridos de acordo com o ndice. O array tem tamanho fixo, se for necessrio adicionar novos elementos, mas no houver mais espaos, os elementos precisam ser realocados em um novo array, maior que o anterior. Por conta desta caracterstica, o array rpido para realizar buscas, mas lento para insero e deleo de elementos.

Ordenao por seleo
um algoritmo de ordenao 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 nmeros, ele vai pegar um dos nmeros e comparar com os demais, verificando se ele for maior ou menor que cada um dos elementos.

Quicksort
O quicksort um algoritmo de ordenao, sendo muito mais rpido que a ordenao por seleo. Para o funcionamento deste algoritmo, voc deve escolher um elemento do array, que ser chamado de piv. Assim, vamos encontrar os elementos que so menores do que o piv, e tambm os elementos que so maiores. Isso chamado de particionamento, e temos assim: um subarray contendo todos os nmeros do que o piv, o piv e um subarray contendo todos os nmeros maiores do que o piv (por exemplo, ao compararmos nmeros). s seguir a mesma lgica para ordenar todos os elementos de um array.
Tabelas Hash

Uma funo hash uma funo na qual voc insere uma string (sequncia de bytes) e a funo retorna um nmero, trabalhando em um sistema de chave-valor. Ela um algoritmo muito rpida tanto para buscas e inseres. Tambm pode ser utilizada para evitar inserir registros duplicados e como cache de dados (utilizado em sites e aplicativos para salvar dados de usurio ou que so acessados com frequncia)

Pesquisa em largura
um algoritmo que utiliza grafos (um modelo de grafos um conjunto de conexes, que formado por vrtices e arestas, sendo uma maneira de modelar como eventos diferentes esto 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 (no possvel pesquisar algum elemento no meio de uma pilha, por exemplo). Os mtodos possveis para manipulao de uma pilha so:

• Mtodo Top: utilizado para verificar qual o primeiro elemento da pilha (que est no topo). Por exemplo, pilha.top() recebe a referncia do topo da pilha;
• Mtodo Pop: tira, de fato, o primeiro elemento da pilha. Por exemplo, pilha.pop(), aps remover o elemento, a referncia de topo passa para o prximo elemento da pilha;
• Mtodo Push: adiciona um novo elemento na pilha;
• Mtodo isEmpty: verifica se a referncia para a entrada da pilha est nula (ou seja, se h ou no 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, no linear e constituda de ns que representam um modelo hierrquico (armazenam os dados com base em relaes de dependncias). Por exemplo, sistema de arquivos, banco de dados, pginas web, etc. As caractersticas de uma rvore hierrquica so: n, raiz, pai e filho, irmo, nvel de um n (posio hierrquica com relao a raiz), altura ou profundidade (grau mximo dos ns), folha ou n terminal, n interno, grau de um n, subrvore.

rvore de busca binria
A sua principal caracterstica a posio dos ns, pois sempre os maiores ns ficam direita e os menores ficam esquerda. As operaes bsicas so: insero, excluso e exibio.
Algoritmo de Dijkstra
O algoritmo de Dijkstra tambm utiliza grafos para a pesquisa e formado por 4 etapas:

1. Encontre o vrtice mais barato. Este o vrtice em que voc consegue chegar no menor tempo possvel;
2. Atualize o custo dos vizinhos desse vrtice. Explicarei o que quero dizer com isso em breve;
3. Repita at que voc tenha feito isso para cada vrtice do grafo;
4. Calcule o caminho final.

Neste algoritmo, cada aresta do grafo tem um nmero associado a ela, que so chamados de pesos. Um grafo com pesos chamado de grafo ponderado (ou grafo valorado) e um grafo sem pesos chamado de grafo no ponderado (ou grafo no valorado). Para calcular o caminho mnimo em um grafo no ponderado, utilize a pesquisa em largura, e para calcular o caminho mnimo e um grafo ponderado, utilize o algoritmo de Dijkstra. Porm, 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 soluo ideal. Quando necessrio muito tempo para calcular a soluo exata, um algoritmo de aproximao uma boa ideia e funciona. Eles so avaliados por sua rapidez e pela capacidade de chegar a soluo ideal.

Programao dinmica
Consiste em uma tcnica para resoluo de problemas complexos que se baseia na diviso de um problema em subproblemas, os quais so resolvidos separadamente. Ela muito til quando voc est tentando otimizar algo em relao a um limite. Todas as solues em programao dinmica envolvem uma tabela e os valores nas clulas so, geralmente, o que voc est tentando otimizar. Cada clula um subproblema, ento pense em como dividir este subproblema em outros subproblemas.

K-vizinhos mais prximo
O algoritmo dos K-vizinhos mais prximos utilizado na classificao e tambm na regresso, ele envolve observar os K-vizinhos mais prximos. Classificao = classificar em grupos e Regresso = adivinhar uma resposta (como um nmero). Escolher boas caractersticas uma parte importante para que este algoritmo opere corretamente. O algoritmo dos k-vizinhos mais prximos utilizado em sistemas de recomendao (filmes, produtos, etc.), aprendizado de mquina, filtro de spam de e-mails e, at, previso da bolsa de valores.

Paradigmas de Programao

Programao Funcional
Modela um problema computacional como uma coleo de funes matemticas, cada uma com um espao de entrada e resultado. Isso separa a programao funcional das funes que possuem o comando de atribuio. Por exemplo, CML, LISP, Scheme, Haskell;

Programao Imperativo
Os comandos so escritos na mesma ordem de execuo (ou seja, passo a passo). Por exemplo, Cobol, Fortran;

Programao Orientada a Objetos
Fornece um modelo na qual um programa uma coleo de objetos que interagem entre si, passando mensagens que transformam seu estado. Por exemplo, Java, C++;

Programao Declarativa
Permite um programa modelar um programa declarando qual resultado ele deve obter, ao invs de como ele deve ser obtido. Por exemplo, PROLOG.