Existem diversos livros sobre algoritmos no mercado. Somente como exemplo mostro alguns abaixo:
O conhecimento de algoritmos é importante para podermos criar bons programas. Vamos mostrar no vídeo a seguir que utilizar uma aproximação errada por gerar um programa fácil de ler porém extremamente ineficiente. O melhor exemplo disto é a implementação do cálculo do número da série de Fibonacci.
Vamos ver neste post duas formas de pesquisa que apresentam vantagens diferentes dependendo do tipo de dados que estamos utilizando. Consideraremos como exemplo a avaliação de uma sequencia de bits. Esta sequencia será passada para o programa como um vetor de inteiros, desta forma queremos achar o primeiro a[i] cujo valor é igual a 1, isto é, que divide o array em duas partes, a inferior contendo "0"s e a superior contendo "1"s.
O primeiro tipo de pesquisa que iremos utilizar é denominado busca linear ou busca sequencial. Este tipo de pesquisa é aplicado em vetores ou listas de modo sequencial, i. e., elemento por elemento, do menor para o maior (ou vice-versa). Deste modo o tempo de execução é função do do número de elementos. Num vetor ordenado, essa não é a pesquisa mais eficiente. No nosso caso veremos que se esperamos que existam poucos bits "0", esta será a melhor opção.
Uma outra pesquisa é a busca binária, onde o tempo de pesquisa é logaritmo em relação ao número de elementos. Este tipo de pesquisa segue o paradigma de dividir e conquistar um vetor ordenado. Funciona mediante sucessivas divisões do espaço de busca, comparando o elemento buscado (ou chave - no nosso caso o primeiro elemento com bit 1) com o elemento no meio do subvetor pesquisado. Este procedimento é facilmente implementado recursivamente.
O segundo algoritmo que vou mostrar é o código de Hamming.
Este código é gerado por operações lineares sobre blocos de dados e foi desenvolvido por Richard Hamming. É muito utilizado no processamento de sinal e nas telecomunicações. Também devido à sua simplicidade é utilizado em memórias de computador tipo ECC.
Para um bloco de dados constituído por n bits (ou palavra), o código de Hamming é obtido inserindo pontos de controle, denominados bits de paridade, como mostrado na tabela abaixo. Para uma palavra de comprimento n bits, são inseridos um número fixo k bits de paridade, ficando a palavra de código com um comprimento N= n + k. A composição do código final é feita de acordo com a montagem das paridades abaixo:
Vamos ver um exemplo real para entender melhor. Veja no vídeo como é feito o algoritmo que implementa o código de Hamming (7,4), ou seja para palavras de 4 bits, gera um código final de 7 bits.
